|
|
|
| A Fast Bi-Objective Non-Dominated Sorting Algorithm |
| LIU Min1,2,3, ZENG Wen-Hua4, ZHAO Jian-Feng1,2 |
1.Cognitive Science Department,Xiamen University,Xiamen 361005
2.Fujian Key Laboratory of the Brain-like Intelligent Systems,Xiamen University,Xiamen 361005
3.Department of Computer Science and Engineering,Zhangzhou Normal University,Zhangzhou 363000
4.Software School,Xiamen University,Xiamen 361005 |
|
|
|
|
Abstract A fast bi-objective non-dominated sorting algorithm (BNSA) is proposed. An operator of forward comparison is designed to identify non-dominated individuals quickly. A sorting strategy according to need is proposed to avoid generating unnecessary non-dominated fronts. Then, the correctness of BNSA is proved and its time complexity is analyzed to be O(NlogN). Next, some comparable experiments are carried out on nine benchmark test problems for bi-objective optimization. Results of the experiments indicate that the proposed BNSA, for the most test problems, is faster than the other three non-dominated sorting algorithms. Furthermore, the BNSA, on all the test problems, has the best of accelerative effect, particularly when the number of evolutionary generations exceeds 400. In addition, the BNSA is concise and easy to be implemented. It can be incorporated into any multi-objective evolutionary algorithms based on non-dominated sorting to improve the running speed of bi-objective optimization.
|
|
Received: 30 November 2010
|
|
|
|
|
|
[1] Coello C A,Lamont G B,Van Veldhuizen D A.Evolutionary Algorithms for Solving Multi-Objective Problems.2nd Edition.New York,USA: Springer-Verlag,2007
[2] Gong Maoguo,Jiao Licheng,Yang Dongdong,et al.Research on Evolutionary Multi-Objective Optimization Algorithms.Journal of Software,2009,20(2): 271-289 (in Chinese)
(公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报,2009,20(2): 271-289)
[3] Deb K,Pratap A,Agarwal S,et al.A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.IEEE Trans on Evolutionary Computation,2002,6(2): 182-197
[4] Jensen M T.Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms.IEEE Trans on Evolutionary Computation,2003,7(5): 503-515
[5] Zheng Jinhua,Jiang Hao,Kuang Da,et al.An Approach of Constructing Multi-Objective Pareto Optimal Solutions Using Arenas Principle.Journal of Software,2007,18(6): 1287-1297 (in Chinese)
(郑金华,蒋浩,邝达,等.用擂台赛法则构造多目标Pareto最优解集的方法.软件学报,2007,18(6): 1287-1297)
[6] Berrichi A,Amodeo L,Yalaoui F,et al.Bi-Objective Optimization Algorithms for Joint Production and Maintenance Scheduling: Application to the Parallel Machine Problem.Journal of Intelligent Manufacturing,2009,20(4): 389-400
[7] Jozefowiez N,Semet F,Talbi E G.An Evolutionary Algorithm for the Vehicle Routing Problem with Route Balancing.European Journal of Operational Research,2009,195(3): 761-769
[8] Abido M A.Multiobjective Evolutionary Algorithms for Electric Power Dispatch Problem.IEEE Trans on Evolutionary Computation,2006,10(3): 315-329
[9] Deb K,Datta R.A Hybrid Bi-Objective Evolutionary-Penalty Approach for Computationally Fast and Accurate Constrained Optimization.Technical Report,2010004.Kanpur Genetic Algorithms Laboratory,Indian Institute of Technology.Kanpur,India,2010
[10] Deb K,Saha A.Multimodal Optimization Using a Bi-Objective Evolutionary Algorithm.Technical Report,2009006.Kanpur Genetic Algorithms Laboratory,Indian Institute of Technology.Kanpur,India,2009
[11] Deb K,Goel T.Controlled Elitist Non-Dominated Sorting Genetic Algorithms for Better Convergence // Zitzler E,Deb K,Thiele L,et al,eds.Proc of the 1st International Conference on Evolutionary Multi-Criterion Optimization.Zurich,Switzerland,2001: 67-81 |
|
|
|
2011, Vol. 24 
