Novel electromagnetism-like mechanism method for multiobjective optimization problems

Lixia Han,Shujuan Jiang,and Shaojiang Lan

School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China

Novel electromagnetism-like mechanism method for multiobjective optimization problems

Lixia Han*,Shujuan Jiang,and Shaojiang Lan

School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China

As a new-style stochastic algorithm,the electromagnetism-like mechanism(EM)method gains more and more attention from many researchers in recent years.A novel model based on EM(NMEM)for multiobjective optimization problems is proposed,which regards the charge of all particles as the constraints in the current population and the measure of the uniformity of non-dominated solutions as the objective function.The charge of the particle is evaluated based on the dominated concept,and its magnitude determines the direction of a force between two particles.Numerical studies are carried out on six complex test functions and the experimental results demonstrate that the proposed NMEM algorithm is a very robust method for solving the multiobjective optimization problems.

electromagnetism-like mechanism (EM)method, multi-objective optimization problem,particle,Pareto optimal solutions.

1.Introduction

Many real life problems in areas such as computer science,engineering design,business and chemistry involve the optimization of multiple,usually conficting objectives at the same time.These problems are known as multiobjective optimization problems(MOPs)[1–8]in numerical optimization,which are very diffcult to be solved by the traditional exact methods,such as the gradient search, and linear programming.To overcome the diffculties described above,a lot of population-based stochastic algorithms,such as evolutionary algorithm(EA),genetic algorithm(GA)and particle swarm optimization(PSO),have been established at hand for the MOPs since 1980s.These population-based stochastic algorithms provide a new tool for complex single-objective and multi-objective optimization problems and are testifed to be able to approximate the Pareto-optimal front of the MOPs tightly in a single run.

In general,the approaches for solving the MOPs are mainly classifed three categories:criterion selection,aggregation method,and Pareto-based technique.Methods based on criterion selection switch between the objectives during the selection phase.An individual is chosen for reproduction,and another objective function determines which chromosome of the population will be chosen into the next generation.Similar to the traditional singleobjective optimization approaches,the algorithms based on the aggregation method usually convert the multiple objectives into a single objective problem by linear combination.Pareto-based techniques seem to be the most popular method for solving the MOP by using the dominance relation.

Schaffer[2]presented the vector evaluated genetic algorithm(VEGA)which treated multiple objectives separately in the evolution to generate a set of nondominated solutions in a single run.This method is the frst pioneering studies on evolutionary multiobjective optimization and of great importance for the MOP.The VEGA belongs to the class of the criterion selection approaches,and this algorithm has been a strong point of reference up to now.Among the class of the aggregation methods,the Hajela and Lin’s weighted-sum based genetic algorithm(HLGA)[3]is motivated from the combination with ftness sharing,where an individual is assessed by summing up the weighted objective values.Thus,the multiobjective problem is converted into a single-objective optimization problem.Unfortunately,this type of approach requires a strong prior preference and needs multiple runs to generate the desired Pareto set of solutions with adequate weights.Pareto-based techniques are widely used for solving the MOP in recent years.This kind of algorithms adopts an external population to store the evolved Pareto front and an internal po-pulation to generate new candidate solutions,such as the fonseca and feming genetic algorithm(FFGA)[4],nondominated sorting genetic algorithm(NSGA)[5],and the niched pareto genetic algorithm(NPGA)[6].

Although many successful evolutionary algorithms have been proposed over the years,the exploration of highperformance optimization method continues for the multiobjective problem.In this paper,the study is concentrated on a novel population-based optimization algorithm,known as the electromagnetism-like mechanism (EM)method for solving the MOPs.The EM was frst proposed by Birbil and Fang[9]in 2002 for single-objective global optimization problems.It is a global search method which utilizes an attraction-repulsion mechanism to move a population of particles(solutions)toward the global optimality.The simulation results on nonlinear unconstrained optimization functions show the potentiality of the EM algorithm,and its theoretical study for convergence to the optimal solution was proved by Birbil et al.[10]in 2003.Interestingly,the EM has been extended successfully to solve engineering optimization[11–13],project scheduling[14],traveling salesman problem,fuzzy relation equation[15],fow shop scheduling[16,17]and so on[18–21].Thus,the ease implementation and fexibility of the EM gains signifcant attention from numerous researchers and scholars and becomes a hot spot in intelligent optimization at present.

The remainder of the paper is organized as follows.Section 2 introduces the multi-objective optimization problems.The general scheme and the sub procedures of the improved EM are presented in Section 3.Section 4 reports the simulation results and the performance analysis in our experimental studies.Further research and conclusions are given in Section 5.

2.Multi-objective optimization problem

Without loss of generality,the multi-objective optimization problems can be formulated as the following minimization.

where f1(x),f2(x),...,fm(x)denote the m objective functions,Ω=[a,b]represents the feasible solution space, and x=(x1,x2,...,xn)is an n-dimensional decision vector.

The aim of the MOP is to fnd the ideal global optimal solution x?∈Ω,then each objective function fi(x?)(i= 1,2,...,m)is minimized simultaneously.Unfortunately, there exists no such an ideal optimal solution x?∈Ω for almost all multi-objective problems because of the incompatible objective functions.Therefore,many trade-off solutions,called non-dominated solutions,are preferred for the MOP.In order to facilitate the description,we introduce the related defnitions for the MOP.

Defnition 1For any two feasible solutions x1and x2to(1),x1is said to dominate x2(denoted by x1＜x2),if and only if the following conditions hold:

Thus,if x1＜x2,then G(x1)＜G(x2)in the objective space to(1).

Defnition 2A solution x∈Ω is said to be nondominated regarding a set Ω′/?Ω if and only if there is no solution in Ω′which dominates x.

Defnition 3A solution x?∈Ω is said to be Paretooptimal if there exists no solution x∈Ω that x＜x?.The set of all the Pareto optimal solutions is called the Pareto set(PS),and the image of PS in the objective space constitutes the Pareto frontier(PF).

Based on the above defnitions,we know that Paretooptimal solutions cannot be made better in any objective function without causing degradation in at least one other objective.In our terminology,the Pareto-optimal solutions represent the globally optimal solution to(1).Generally,two vital issues are taken into consideration to establish an effective algorithm for solving the MOP:(i)to track and obtain a group of the Pareto solutions which approach the Pareto-optimal solutions tightly;(ii)to fnd a set of widespread and uniformly distributed Pareto solutions.Thus,the decision maker can make the most appropriate choice according to the specifc condition.Fig.1 gives two sets of the Pareto solutions in the objective space for a bi-objective optimization problem.

Fig.1 Pareto solutions in the objective space for a bi-objective problem

It follows from Fig.1 that the solutions in the frst set are distributed more uniformly than those in the second set over the given portion frontier.Based on the characteristic of the MOP,the frst set of solutions in Fig.1 is desirable by the decision maker.Actually,the measure of the uniformity of a group of solutions to(1)makes numerous scholars crazy for its diffculty and tremendous amount ofcomputation.Take a bi-objective optimization problem as an example.Fig.2 gives the distribution of seven nondominated solutions in the objective space.

Fig.2 Nondominated front in the objective space of a bi-objective optimization

where didenotes the distance of two adjacent points.Letthus,we can defne the density variance of the solutions in the bi-objective space as

Undoubtedly,the density variance is the most reasonable mean to measure the distribution of a set of solutions for the bi-objective optimization problems.Inspired by the above defnitions,we further defne the index of uniform distribution to(1).

Suppose that the population P(t)consists of individuals x1,x2,...,xNat generation t,and U1,U2,...,UNare the points corresponding to the individuals x1,x2,...,xNin the objective space,respectively.Randomly select two objective fiandfj(1≤i＜j≤m),then the density variance of the solutions in the bi-objective space is obtained according to scheme(2)which is denoted by Uij.Therefore,the index of uniform distribution of solutions to(1)is computed as follows:

In fact,the value of U is the maximum of the density variance of the population in the bi-objective space.The smaller the value of U,the better the uniformity of the population.When U=0,the distribution of the solutions in the objective space are completely uniform.Thus,the novel measure of the population can be used to exam the distribution of solutions on the entire Pareto front.In addition,all the objective functions have been normalized because different objectives take different orders of magnitude.

3.Improved EM for the multi-objective optimization problem

The EM is a population-based stochastic algorithm for solving the single-objective optimization problem with bound constraints[9,11].It simulates the attractionrepulsion mechanism of the electromagnetism theory to manipulate the individuals in the population based on Coulomb’slaw.Each solution in the population is regarded as a charged particle that is released to an electromagnetic space.For its advantages of simple concept,intelligence, and economic computation,EM has been widely used in the areas of function optimization[7–9],fuzzy neural network training[10],project scheduling[11],and other combinatorial optimization felds.The standard EM algorithm includes four basic steps as follows.

Step 1Initialize the population set while not satisfy the stop criterion;

Step 2Local search;

Step 3Calculate the total force;

Step 4Move particles to a new position.

Generally,the procedure initialization is used to generate N points(particles)randomly from the feasible solution space.

3.1Charge of the particle

In the standard EM,the quality or charge of each particle determines the magnitude of an attraction and repulsion effect in the population.In the case of the MOP,suppose that the population P(t)is made of particles x1,x2,...,xNat generation t,ri(t)is the number of particle xi(i= 1,2,...,N)dominated by the other particles in the current population,then the charge of particle xiis designed as(4)based on the nondominated concept.

Based on the defnition of the charge,the magnitude of particle charge is closely related to the quality of the particle,and 0＜q(xi)≤1.The better the quality of the particles,the larger value of the charge.Moreover,the charge of each particle is not constant and it will change from iteration to iteration,except for the global Pareto optimal particles.For any Pareto optimal particle,its charge always equals to 1.

3.2Constrained optimization model for the MOP

From the analysis mentioned above,we can regard the chargeof all particles as the constraints and the measure of the uniformity of solutions as the objective function.Then the MOP(1)can be transformed into the following constrained optimization model.

The constraint condition can ensure that the particle is Pareto optimal in the current population.In other words, the population consists of non-dominated particles.The optimizing U(t)can improve the uniform distribution of the population.

3.3Selection strategy

The selection strategy plays an important role in the evolution of EM for MOP.In this subsection,an innovative selection operator is presented to produce the next generation population to(5)regarding to the magnitude of the particle charge.

(i)If two particles have different magnitudes of charge, we prefer to select the one with the higher charge.

(ii)If two particles have the same magnitude of charge, we prefer to choose the one with the smaller objective function value to(5)(e.g.particle xiand xjhave the same magnitude of charge,then we calculate the objective of xiand xjin the set S based on(3),where S denotes the set which consists of all non-dominated particles in the current population).

It follows that the preference of particles with a larger magnitude of charge can guide the search towards the Pareto-optimal set quickly in case(i)while the preference selection in case(ii)facilitates to prevent premature convergence and achieve a well distributed trade-off front for the MOP.Therefore,the novel selection scheme can guide the search toward the Pareto-optimal set and achieve a well distributed trade-off front.

3.4Calculation of total force vector

The diffculty of EM for MOP is to determine the direction of a force between two particles as a traditional mean in the single-objective optimization.Particularly,the direction of a force between two particles is decided by comparing with their charges in the proposed EM to(5).In accordance with the Coulomb’s law,the magnitude of the force between two particles relates to their charges and distance.Hence, the total force Fiexerted on particle xiby other particles in the population is calculated as

(i)If the particle xidominates the particle xj,xiattracts xj;otherwise it repels xj.Therefore,the Pareto-optimal solution will always attract the other particles dominated by it in the population.

(ii)If the particle xiand the particle xjhave the same charge,the direction of the force between them is determined by the random number r∈(0,1).

In this way,the force computed by(6)is proportional to the charges of two particles and inversely proportional to the Euclidean distance between them.In fact,the new calculation of force encourages the particles to approach to their local non-dominated solution and maintain the diversity of the population.For the global Pareto optimal particles,they act as an absolute point of attraction,i.e.,they attract all other ordinary particles in the current population.

3.5Movement according to the total force

After the calculation of the total force Fi,the particle xiis moved to a new position along the direction of the force by a random step length.In addition,the force exerted on each particle is normalized to maintain the feasibility as

where the parameter λ is assumed to be uniformly distributed between 0 and 1,and VFis a parameter whose components denote the allowed feasible movement toward the upper bound,or the lower bound.

3.6Novel model based on EM for MOP

Step 1Determine the relevant parameters,such as the population size N and the maximal generation number T.

Step 2Randomly generate N particles as the initial population P(0)from the feasible search space Ω.Let the generation number t=0.

Step 3Evaluate the current particles.If the termination condition holds,stop;otherwise,go to Step 4.

Step 4Perform a random line local search to explore the neighborhood of each particle x=(xi1,xi2,...,xin)in the current population.The procedure of the local search is described as follows.

End If

If G(y)＜G(xi)

End If

End For

All these offspring constitute a set denoted by O1.

Step 5Compute the charges of all particles by using (4)and evaluate the total forces exerted on each particle in the current population.

Step 6Move each particle to a new position along the direction of the total force according to(7).All these new offspring constitute a set denoted by O2.

Step 7Select the next generation population P(t+1) among P(t)∪O1∪O2by using the selection strategy in Section 3.3.Let t=t+1,go to Step 3.

4.Simulation results and analysis

4.1Test functions

In order to evaluate the effciency of the proposed algorithm,we performed it on all benchmark functions used on Zitzler and Thiele[1]denoted by F1,F2,F3,F4,F5 and F6,respectively.These six test functions are diffcult MOPs which are often used to testify the effectiveness of the various algorithms.Here,the test function F1 has a convex Pareto-optimal front while F2 has a non-convex counterpart to F1.As for the test function F3,its Paretooptimal front consists of several noncontiguous convex parts because of the existence of the sine function in h. The test function F4 has the characteristic of multimodality.Its global Pareto-optimal points are surrounded by 219local Pareto-optimal ones.Therefore,it is a giant challenge for any algorithm to track the true Pareto-front of the test function.As for the test function F5,the global Paretooptimal front as well as the local ones are convex.Due to the non-uniformity of the search space,the Pareto-optimal solutions of the test functions F6 are non-uniformly distributed along the global Pareto front and the density of the solutions is the lowest near the Pareto-optimal front and highest away from the front which augments the diffculty to solve the multi-objective problem.

4.2Experimental results of the proposed algorithm

All experiments were performed in Matlab 7.4.0.For each of the test problems,the presented algorithm is run 20 times independently with randomly generated initial populations.Figs.3–5 show the non-dominated front obtained by the proposed novel mode based on EM(NMEM)for solving the six test problems.

In Figs.3–5,the non-dominated fronts achieved by NMEM are visualized.The results indicate that:

(i)The proposed algorithm can approximate the true Pareto-optimal frontier well for all test functions.

(ii)The distribution of the non-dominated solutions is relatively uniform in the objective space.

(iii)The extent of the non-dominated frontier obtained by NMEM spreads broadly.

Fig.3 Non-dominated fronts achieved by NMEM for F1 and F2

Fig.4 Non-dominated fronts achieved by NMEM for F3 and F4

Fig.5 Non-dominated fronts achieved by NMEM for F5 and F6

4.3Comparison with other algorithms and discussion

Verifying the effectiveness of the proposed algorithm always involves the comparison of the performance of different optimization techniques experimentally.In the case of the multi-objective optimization,six algorithms are compared on all test functions.They are NSGA[5],VEGA [2],HLGA[3],NPGA[6],FFGA[4]and RAND[1].

To be consistent with[1],the initial population size is set to 100 and the maximum generation number is equal to 50.The simulation results of the above algorithmscan be found from the website:http://www.tik.ee.ethz. ch/～zitzler/test data.html.

Figs.6–11 present the comparison results of seven algorithms(NMEM,NSGA,VEGA,HLGA,NPGA,FFGA, RANG)on all test functions.The symbols(?,?,◇,?,+, ?,?)denote the dominated solutions of NMEM,NSGA, VEGA,HLGA,NPGA,FFGA,and RANG,respectively.

In Figs.6–11,the non-dominated fronts achieved by the seven algorithms are visualized.It can be seen clearly from Fig.6 that all algorithms can track reasonably distributed fronts for test function F1.Thus,the convexity seems to cause the least amount of diffculty for the seven algorithms.As for non-convex test function F2,HLGA and VEGA are incapable of fnding intermediate solutions due to linear combinations of the objectives in the evolution.To the contrary,NMEM and NSGA seek out more non-dominated solutions with uniform distribution than other methods in Fig.7.In the case of convex test function F3,its Pareto-optimal front consists of several noncontiguous parts.The front achieved by the proposed algorithm covers the maximum portion of the reference set among all the algorithms discussed,while that of the HLGA covers the minimal section.F4,F5 and F6 are the most diffcult problems to be solved.The NMEM is the only method which approximates a widely distributed front,and NSGA follows.

Fig.6 Comparison results of seven algorithms on F1

Fig.7 Comparison results of seven algorithms on F2

Fig.8 Comparison results of seven algorithms on F3

Fig.9 Comparison results of seven algorithms on F4

Fig.10 Comparison results of seven algorithms on F5

Fig.11 Comparison results of seven algorithms on F6

Generally,it can be seen clearly from Figs.6–11 that the Pareto front obtained by NMEM is always in the below of the other Pareto fronts achieved by other algorithms for all test functions.This indicates that the NMEM is capable of approaching the true Pareto-optimal frontier.Furthermore,it can be observed that NMEM outperforms other algorithms regarding both distributions and the extent of the non-dominated solutions in the objective space.

In addition to the graphical presentation,the different algorithms are assessed by using the U-measure[22].The U-measure is a famous quality measure to measure the uniformity of a given set of non-dominated solutions over the Pareto frontier,from which a smaller U-measure value indicates a better uniformity.Fig.12 shows the U-measure values for seven algorithms on six test functions,where the number 1,2,3,4,5,6,7 denote the U-measure value for NSGA,VEGA,HLGA,NPGA,FFGA and RAND,respectively.

Fig.12 Comparison results of U-measure for seven algorithms

As Fig.12 indicates,NMEM performs better than the other six algorithms regarding the uniformity of the nondominated solutions for all test functions.In general,the simulation results for all test problems show that the novel algorithm can fnd a group of uniformly distributed Pareto optimal solutions widely spread and is competitive for MOP.

Considering the popular fashion of the methods based on EA,two famous MOEAs(SOEA and SPEA[1])are employed to solve all the test functions.The simulation results are compared with that of the proposed algorithm.The symbols(?,?,?)are used to represent the dominated solutions of NMEM,SOEA and SPEA.Figs. 13–15 give the comparison results of the proposed algorithm,SOEA and SPEA on all test functions.

Fig.13 Comparison results of three algorithms on F1 and F2

Fig.14 Comparison results of three algorithms on F3 and F4

Fig.15 Comparison results of three algorithms on F5 and F6

In the same parameters condition,the non-dominated front achieved by NMEM well approaches the true Pareto front for all test functions,and SPEA follows as seen from Figs.13–15.The simulation results proved that the proposed algorithm is a competitive method for MOP with the bound constraints.

5.Conclusions

For MOPs,it is desirable to provide a variety of choices so that the decision makers can select the most suitable solution based on their own preference.In this paper,the NMEM is presented for solving MOPs which adopts new charge and force vector calculations rely on the defnition of Pareto optimality.The experimental results on benchmark problems demonstrate that the proposed algorithm can much more quickly track the Pareto optimal solutions in comparison with other existing algorithms.Further developments will focus on more complex MOPs with equality and inequality constraints.

[1]E.Zitzler,K.Deb,L.Thiele.Comparison of multiobjective evolutionary algorithms:empirical results.Evolutionary Computation,2000,8(2):1–24.

[2]J.D Schaffer.Multiple objective optimization with vector evaluated genetic algorithms.Proc.of the International Conference on Genetic Algorithms and Their Applicatiions,1985: 93–100.

[3]P.Hajela,C.Y.Lin.Genetci search strategies in multicriterion optimal design.Structural Optimization,1992,4:99–107.

[4]C.M.Fonseca,P.J.Fleming.Genetic algorithms for multiobjective optimization:formulaion,discussion and generalization.Proc.of the Fifth International Conference on Genetic Algorithms,1993:416–423.

[5]N.Srinivas,K.Deb.Multiobjective optimization using nondominated sorting in genetic algorithms.Evolutionary Computation,1994,2(3):221–248.

[6]J.Horn,N.Nafpliotis.Multiobjective optimization using the niched pareto genetic algorithm.Urbana,Illinois:University of Illinois,1993.

[7]A.H.Aguirre,S.B.Rionda,C.A.C.Coello,et al.Handling constraints using multiobjective optimization concepts.International Journal for Numerical Methods in Engineering,2004, 59(15):1989–2017.

[8]C.A.C.Coello.Constraint handling using an evolutionary multiobjective optimization technique.Civil Engineering System,2000,17:319–346.

[9]S.I.Birbil,S.C.Fang.An electromagnetism-like mechanism for global optimization.Journal of Global Optimization,2003, 25:263–282.

[10]S.I.Birbil,S.C.Fang,R.L.Sheu.On the convergence of a population-based global optimization algorithm.Journal of Global Optimization,2004,30:301–318.

[11]P.K.M.M.Ali.Differential evolution algorithms using hybrid mutation.Computation.Optimization.Application,2007,37: 231–246.

[12]C.S.Tsou,C.H.Kao.An electromagnetism-like metaheuristic for multi-objective optimization.Proc.of the IEEE Congress on Evolutionary Computation,2006:1171–1178.

[13]Q.H.Wang,J.C.Zeng,W.P.Song.A new electromagnetismlike algorithm with chaos optimization.Proc.of the International Conference on Computational Aspects of Social Networks,2010:535–538.

[14]Y.Xu,M.L.Jin.Electromagnetism-like algorithm without local search on PAPR reduction for OPDM.Proc.of the 3rd International conference on Awareness Science and Technology, 2011:51–56.

[15]C.H.Lee,F.Y.Chang.Prediction-based neural fuzzy controller design using modifed electromagnetism-like algorithm.Proc.of the SICE Annual Conference,2010:2088–2093.

[16]H.C.Liu,L.Gao.A discrete electromagnetism-like mechanism algorithm for solving distributed permutation fowshop scheduling problem.Proc.of the International Conference on Manufacturing Automation,2010:156–163.

[17]A.Zarei,T.M.Akbarzadeh,M.Gharehjanloo.An improved electromagnetism-like mechanism for capacitated vehicle routing problem.Proc.of the 2nd International Conference on Computer and Knowledge Engineering,2012:139–143.

[18]Y.H.Chou,C.C.Chang,C.H.Chiu.Classical and quantuminspired electromagnetism-like mechanism for solving 0/1 knapsack problems.Proc.of the IEEE Internation Conference on Systems Man and Cybernetics,2010:3211–3218.

[19]O. Aghalatif, M. R. Bonyadi. DEM: a discrete electromagnetism-like mechanism for solving discrete problems.Proc.of the IEEE International Symposium on Computational Intelligence in Robotics and Automation,2009: 120–125.

[20]Q.Wu,X.Y.Li,L.Gao,et al.A simplifed electromagnetismlike mechanism algorithm for tool pathplanning in 5-axis fank milling.Proc.of the IEEE 17th International Conference on Computer Supported Cooperative Work in Design,2013:422–426.

[21]Y.H.Chou,C.Y.Chen,C.H.Chiu,et al.Classical and quantum-inspired electromagnetism-like mechanism and its applications.Control Theory and Application,2012,6(10): 1424–1433.

[22]Y.W.Leung,Y.P.Wang.U-measure:a quality measure for multiobjective programming.IEEE Trans.on System,Man and Cybernetics–Part A:Systems and Humans,2003,33(3):337–343.

Biographies

Lixia Han was born in 1980.She received her M.S.degree in 2005 and Ph.D.degree in 2009 from Xidian University.She is now a lecturer in China University of Mining and Technology.Her main research interests include evolutionary computation and combinatorial optimization.

E-mail:lxhan@cumt.edu.cn

Shujuan Jiang was born in 1966.She received her M.S.degree from China University of Mining and Technology in 2000.In 2006,she received her Ph.D.degree from Southeast University.She is currently a professor and a doctoral supervisor in China University of Mining and Technology.Her main research interests include software engineering,and software analysis and testing.

E-mail:shjjiang@cumt.edu.cn

Shaojiang Lan was born in 1977.He received his B.S.degree from Ludong University in 2002.He received his M.S.degree from Xidian University in 2009.He is currently a research assistant in China University of Mining and Technology.His research interests include genetic algorithm and combinatorial optimization.

E-mail:sjlan2006@cumt.edu.cn

10.1109/JSEE.2015.00023

Manuscript received October 17,2013.

*Corresponding author.

This work was supported by the National Natural Science Foundation of China(60873099)and the Fundamental Research Funds for the Central Universities(2011QNA29).