The Electromagnetic Like Algorithm is a population based meta-heuristics proposed by Birbil and Fang1 to tackle with combinatorial optimisation problems. Algorithm is based on the natural law of attraction and repulsion between charges (Coulomb’s law)2. EM simulates electromagnetic interaction3. The algorithm evaluates fitness of solutions considering charge of particles. Each particle represents a solution. Two points into the space had different charges in relation to what electromagnetic field acts on them4. An electrostatic force, in repulsion or attraction, manifests between two points charges. The electrostatic force is directly proportional to the magnitudes of each charge and inversely proportional to the square of the distance between the charges. The fixed charge at time iteration (t) of particle i is shown as follows:
|
Where t represents the iteration step, qi(t) is the charge of particle i at iteration t, f(xi,,t), f(xbest,t), and f(xk,t) denote the objective value of particle i, the best solution, and particle k from m particles at time t; finally, n is the dimension of search space.The charge of each point i, qi(t), determines point’s power of attraction or repulsion. Points (xi) could be evaluated as a task into the graph representation Figure 1.2.
The particles move along with total force and so diversified solutions are generated. The following formulation is the resultant force of particle i:
|
The following notes described an adapted version of EM for JSSP. According to this application, the initial population is obtained by choosing randomly from the list or pending tasks, as for the feasibility of solution, particles’ path. The generic pseudo-code for the EM is reported in Figure 5.6 Each particle is initially located into a source node (see disjunctive graph of Figure 1.2). Particle is uniquely defined by a charge and a location into the node’s space. Particle’s position in each node is defined in a multigrid discrete set. While moving, particle jumps in a node based on its attraction force, defined in module and direction and way. If the force from starting line to arrival is in relation of positive inequality, the particles will be located in a plane position in linear dependence with force intensity. A selection mechanism could be set in order to decide where particle is directed, based on node force intensity. Force is therefore the resultant of particles acting in node. A solution for the JS is obtained only after a complete path from the source to the sink and the resulting force is updated according to the normalized makespan of different solutions.
- 1431 reads
