基于高效非支配排序的多目标人工蜂群算法
|
摘要
多目标优化问题广泛存在于科学与工程领域,为了提高求解效率,改进算法中的关键环节——非支配排序,提出了一种基于高效非支配排序的多目标人工蜂群算法。本文算法根据精英指导离散解生成策略进行局部搜索,运用高效非支配排序计算解的前沿面,最后根据前沿面排名和拥挤距离来挑选表现较好的解进行下一轮迭代。在基准函数上的实验验证了本文算法在保证求解性能的前提下,可以降低1/2的比较次数,运行效率提升近65%。
Multi-objective optimization problems exist widely in the fields of science and engineering. In order to improve the efficiency,the key non-dominated sorting step was improved and a novel multi-objective artificial bee colony algorithm was proposed based on efficient non-dominated sorting( EMOABC-ENS). In this algorithm,the elite-guided solution generation strategy was used to exploit the neighborhood of the exist solutions based on the guidance of the elite. The efficient non-dominated sorting method was applied to calculate the front of solutions.Furthermore,the better solutions were selected for the next iteration based on the front value and the crowding distance. The proposed algorithm is validated on the standard test problems,and the experimental results show that the proposed approach can reduce the number of comparisons by half and improve the efficiency by nearly 65%.
Multi-objective optimization problems exist widely in the fields of science and engineering. In order to improve the efficiency,the key non-dominated sorting step was improved and a novel multi-objective artificial bee colony algorithm was proposed based on efficient non-dominated sorting( EMOABC-ENS). In this algorithm,the elite-guided solution generation strategy was used to exploit the neighborhood of the exist solutions based on the guidance of the elite. The efficient non-dominated sorting method was applied to calculate the front of solutions.Furthermore,the better solutions were selected for the next iteration based on the front value and the crowding distance. The proposed algorithm is validated on the standard test problems,and the experimental results show that the proposed approach can reduce the number of comparisons by half and improve the efficiency by nearly 65%.
引文
1 Wang Z,Wang Q,Zukerman M,et al. A seismic resistant design algorithm for laying and shielding of optical fiber cables[J]. Journal of Lightwave Technology,2017,35(14):3060-3074
2 Huo Y,Qiu P,Zhai J,et al. Multi-objective service composition model based on cost-effective optimization[J]. Applied Intelligence,2018,48(3):651-669
3 Antonio L M,Coello C A C. Coevolutionary multi-objective evolutionary algorithms:A survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation,2018,22(6):851-865
4 李娅,秦忆.一种基于分解的、改进的多目标蚁群算法及其应用[J].科学技术与工程,2016,16(12):89-96Li Ya,Qin Yi. A novel multi-objective ant colony optimization algorithm based on decomposition and its application[J]. Science Technology and Engineering,2016,16(12):89-96
5 Lin Q,Liu S,Zhu Q,et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation,2018,22(1):32-46
6 刘建昌,李飞,王洪海,等.进化高维多目标优化算法研究综述[J].控制与决策,2018,33(5):879-887Liu Jianchang,Li Fei,Wang Honghai,et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and Decision,2018,33(5):879-887
7 Deb K,Pratap A,Agarwal S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197
8 Zitzler E,Laumanns M,Thiele L. SPEA2:Improving the strength pareto evolutionary algorithm[C]//The proceedings of the Evolutionary Methods for Design,Optimization and Control with Applications to Industrial Problems. Greece:International Center for Numerical Methods in Engineering,2001:95-100
9 Zitzler E,Künzli S. Indicator-based selection in multiobjective search[C]//International Conference on Parallel Problem Solving from Nature,Lecture Notes in Computer Science. Heidelberg:Springer,2004:832-842
10 Bader J,Zitzler E. Hype:An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation,2011,19(1):45-76
11 Zhang Q,Li H. Moea/d:A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731
12 Trivedi A,Srinivasan D,Sanyal K,et al. A survey of multiobjective evolutionary algorithms based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2017,21(3):440-462
13 Karaboga D. An idea based on honey bee swarm for numerical optimization:Technical Report-TR06[R]. Kayseri:Erciyes University,Engineering Faculty,Computer Engineering Department,2005
14 Huo Y,Zhuang Y,Gu J,et al. Discrete gbest-guided artificial bee colony algorithm for cloud service composition[J]. Applied Intelligence,2015,42(4):661-678
15 Huo Y, Zhuang Y, Gu J, et al. Elite-guided multi-objective articial bee colony algorithm[J]. Applied Soft Computing,2015,32(1):199-210
16 霍瑛.云计算环境下服务组合技术研究[D].南京:南京航空航天大学,2016Huo Ying. Research on service composition in cloud computing environment[D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2016
17 Zhang X,Tian Y,Cheng R,et al. An efficient approach to nondominated sorting for evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(2):201-213
18 Coello C A C,Pulido G T,Lechuga M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(3):256-279
19 Zitzler E,Deb K,Thiele L. Comparison of multiobjective evolutionary algorithms:Empirical results[J]. Evolutionary Computation,2000,8(2):173-195
20 Deb K,Thiele L,Laumanns M,et al. Scalable multi-objective optimization test problems[C]//The Proceedings of the Evolutionary Computation(CEC). Honolulu:IEEE,2002:825-830
21 Van Veldhuizen D A,Lamont G B. Multiobjective evolutionary algorithm research:A history and analysis:Technical Report TR-98-03[R]. Dayton,OH:Air Force Institute Technology,1998
22 Van Veldhuizen D A. Multiobjective evolutionary algorithms:Classifications,analyses,and new innovations[D]. Wright-Patterson AFB,OH:Air Force Institute of Technology,1999
2 Huo Y,Qiu P,Zhai J,et al. Multi-objective service composition model based on cost-effective optimization[J]. Applied Intelligence,2018,48(3):651-669
3 Antonio L M,Coello C A C. Coevolutionary multi-objective evolutionary algorithms:A survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation,2018,22(6):851-865
4 李娅,秦忆.一种基于分解的、改进的多目标蚁群算法及其应用[J].科学技术与工程,2016,16(12):89-96Li Ya,Qin Yi. A novel multi-objective ant colony optimization algorithm based on decomposition and its application[J]. Science Technology and Engineering,2016,16(12):89-96
5 Lin Q,Liu S,Zhu Q,et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation,2018,22(1):32-46
6 刘建昌,李飞,王洪海,等.进化高维多目标优化算法研究综述[J].控制与决策,2018,33(5):879-887Liu Jianchang,Li Fei,Wang Honghai,et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and Decision,2018,33(5):879-887
7 Deb K,Pratap A,Agarwal S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197
8 Zitzler E,Laumanns M,Thiele L. SPEA2:Improving the strength pareto evolutionary algorithm[C]//The proceedings of the Evolutionary Methods for Design,Optimization and Control with Applications to Industrial Problems. Greece:International Center for Numerical Methods in Engineering,2001:95-100
9 Zitzler E,Künzli S. Indicator-based selection in multiobjective search[C]//International Conference on Parallel Problem Solving from Nature,Lecture Notes in Computer Science. Heidelberg:Springer,2004:832-842
10 Bader J,Zitzler E. Hype:An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation,2011,19(1):45-76
11 Zhang Q,Li H. Moea/d:A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731
12 Trivedi A,Srinivasan D,Sanyal K,et al. A survey of multiobjective evolutionary algorithms based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2017,21(3):440-462
13 Karaboga D. An idea based on honey bee swarm for numerical optimization:Technical Report-TR06[R]. Kayseri:Erciyes University,Engineering Faculty,Computer Engineering Department,2005
14 Huo Y,Zhuang Y,Gu J,et al. Discrete gbest-guided artificial bee colony algorithm for cloud service composition[J]. Applied Intelligence,2015,42(4):661-678
15 Huo Y, Zhuang Y, Gu J, et al. Elite-guided multi-objective articial bee colony algorithm[J]. Applied Soft Computing,2015,32(1):199-210
16 霍瑛.云计算环境下服务组合技术研究[D].南京:南京航空航天大学,2016Huo Ying. Research on service composition in cloud computing environment[D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2016
17 Zhang X,Tian Y,Cheng R,et al. An efficient approach to nondominated sorting for evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2015,19(2):201-213
18 Coello C A C,Pulido G T,Lechuga M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(3):256-279
19 Zitzler E,Deb K,Thiele L. Comparison of multiobjective evolutionary algorithms:Empirical results[J]. Evolutionary Computation,2000,8(2):173-195
20 Deb K,Thiele L,Laumanns M,et al. Scalable multi-objective optimization test problems[C]//The Proceedings of the Evolutionary Computation(CEC). Honolulu:IEEE,2002:825-830
21 Van Veldhuizen D A,Lamont G B. Multiobjective evolutionary algorithm research:A history and analysis:Technical Report TR-98-03[R]. Dayton,OH:Air Force Institute Technology,1998
22 Van Veldhuizen D A. Multiobjective evolutionary algorithms:Classifications,analyses,and new innovations[D]. Wright-Patterson AFB,OH:Air Force Institute of Technology,1999