Multi-objective Sparrow Search Algorithm Based on New Crowding Distance

doi:10.3778/j.issn.1002-8331.2011-0468

Abstract

Abstract:

More and more complex multi-objective optimization problems have emerged in the real world, and the solution of such complex problems requires efficient optimization algorithms. Based on sparrow search algorithm, this paper proposes Multi-objective Sparrow Search Algorithm（MSSA）. Firstly, the sparrow population scale factor is dynamically adjusted according to the external archive convergence to achieve the optimal balance between global exploration and local development. Secondly, the population of sparrow is sorted by non-dominance. Then, polynomial mutation is introduced to the discoverer of sparrow population to enhance the ability of the algorithm to jump out of local optimum. Last, a new crowding distance calculation strategy is proposed, which uses the crowding degree of the solution to eliminate similar individuals, the population is pruned so that the individual does not exceed the upper limit of the archive while maintaining the diversity of the population. The performance of the proposed algorithm is tested through multi-objective functions and the design of a disc brake. MSSA is compared with MOPSO, MOGWO, NSGA-II and SPEA2 on multi-objective test problems, and the experimental results show that MSSA has significant performance advantages in terms of convergence and homogeneity. The disc brake design results show that MSSA can quickly find the non-dominant solution of the problem, which proves the effectiveness of MSSA.

Key words: Sparrow Search Algorithm（SSA）, scale factor, external archive, polynomial mutation, crowding distance

摘要：

现实中的多目标问题日益复杂，解决这类问题需要高效的优化算法。基于麻雀搜索算法，提出多目标麻雀搜索算法（Multi-objective Sparrow Search Algorithm，MSSA），对多目标优化问题进行求解。依据外部存档收敛性动态调整麻雀种群比例因子，以达到全局探索能力和局部开发能力的最佳平衡，确保收敛性；对麻雀种群进行非支配排序；对麻雀种群的发现者引入多项式变异因子，增强算法跳出局部最优的能力；设计一种新型拥挤度距离计算策略，利用外部存档解的拥挤度大小剔除相似个体的方法对种群进行裁剪，使个体不超过存档上限的同时维持种群的多样性。分别使用多目标函数和盘式制动器设计测试算法性能。MSSA与MOPSO、MOGWO、NSGA-II和SPEA2在多目标测试函数上进行对比实验，结果表明MSSA算法在收敛性和均匀性两项指标上有显著的优势。盘式制动器仿真结果表明，MSSA可以快速地找到问题的非支配解，证明了该方法的有效性。

关键词: 麻雀搜索算法（SSA）, 比例因子, 外部存档, 多项式变异, 拥挤度距离

WEN Zeyu, XIE Jun, XIE Gang, XU Xinying. Multi-objective Sparrow Search Algorithm Based on New Crowding Distance[J]. Computer Engineering and Applications, 2021, 57(22): 102-109.

温泽宇，谢珺，谢刚，续欣莹. 基于新型拥挤度距离的多目标麻雀搜索算法[J]. 计算机工程与应用, 2021, 57(22): 102-109.

References

[1] SRINIVAS N，DEB K.Multi-objective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation，1994，2（3）：221-248.
[2] DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.
[3] ZITZLER E，THIELE L.Multi-objective evolutionary algorithms：a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.
[4] ADHAM A M，MOHDGHAZALI N，AHMAD R.Performance optimization of a microchannel heat sink using the improved strength pareto evolution algorithm（SPEA2）[J].Journal of Engineering Thermophysics，2015，24（1）：86-100.
[5] COELLO C A C，LECHUGA M S.MOPSO：a proposal for multiple objective particle swarm optimization[C]//2002 Congress on Evolutionary Computation，Honolulu，2002：1051-1056.
[6] MIRJALILI S，SAREMI S，MIRJALILI S M，et al.Multi-objective grey wolf optimizer：a novel algorithm for multi-criterion optimization[J].Expert Systems with Applications，2016，47（1）：106-119.
[7] 谢承旺，肖驰，丁立新，等.HMOFA：一种混合型多目标萤火虫算法[J].软件学报，2018，29（4）：251-270.
XIE C W，XIAO C，DING L X，et al.HMOFA：a hybrid multi-objective firefly algorithm[J].Journal of Software，2018，29（4）：251-270.
[8] 谢承旺，邹秀芬，夏学文，等.一种多策略融合的多目标粒子群优化算法[J].电子学报，2015，43（8）：1538-1544.
XIE C W，ZOU X F，XIA X W，et al.A multi-objective partical swarm optimization algorithm integrating multiply strategies[J].Acta Electronica Sinica，2015，43（8）：1538-1544.
[9] 耿焕同，陈哲，陈正鹏，等.一种基于群体分布特征的自适应多目标粒子群优化算法[J].控制与决策，2017，32（8）：1386-1394.
GENG H T，CHEN Z，CHEN Z P.A self-adaptive multi-objective particle swarm optimization algorithm based on swarm distribution characteristic[J].Control and Decision，2017，32（8）：1386-1394.
[10] XUE J，SHEN B.A novel swarm intelligence optimization approach：sparrow search algorithm[J].Systems Science & Control Engineering，2020，8（1）：22-34.
[11] 李雅丽，王淑琴，陈倩茹，等.若干新型群智能优化算法的对比研究[J].计算机工程与应用，2020，56（22）：1-12.
LI Y L，WANG S Q，CHEN Q R，et al.Comparative study of several new swarm intelligence optimization algorithms[J].Computer Engineering and Applications，2020，56（22）：1-12.
[12] 汤安迪，韩统，徐登武，等.基于混沌麻雀搜索算法的无人机航迹规划方法[J].计算机应用，2021，41（7）：2128-2136.
TANG A D，HAN T，XU D W，et al.Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm[J].Journal of Computer Applications，2021，41（7）：2128-2136.
[13] 吕鑫，慕晓冬，张钧.基于改进麻雀搜索算法的多阈值图像分割[J].系统工程与电子技术，2021，43（2）：318-327.
LV X，MU X D，ZHANG J.Multi-threshold image segmentation based on improved sparrow search algorithm[J].Systems Engineering and Electronics，2021，43（2）：318-327.
[14] 韩敏，何泳.基于高斯混沌变异和精英学习的自适应多目标粒子群算法[J].控制与决策，2016，31（8）：1372-1378.
HAN M，HE Y.Adaptive multi-objective particle swarm optimization with Gaussian chaotic mutation and elite learning[J].Control and Decision，2016，31（8）：1372-1378.
[15] DEB K，GOYAL M.A combined genetic adaptive search（GeneAS） for engineering design[J].Computer Science and Information，1996，26（4）：30-45.
[16] 李珺，党建武，王垚，等.多目标细菌觅食优化算法[J].计算机应用研究，2018，35（7）：1996-2000.
LI J，DANG J W，WANG Y，et al.Multi-objective bacteria foraging optimization algorithm[J].Application Research of Computers，2018，35（7）：1996-2000.
[17] JIANG S，YANG S.An improved multi-objective optimization evolutionary algorithm based on decomposition for complex Pareto fronts[J].IEEE Transactions on Cybernetics，2017，46（2）：421-437.
[18] LI M，YANG S，LIU X.Pareto or Non-Pareto：bi-criterion evolution in multi-objective optimization[J].IEEE Transactions on Evolutionary Computation，2016，20（5）：645-665.
[19] ZITZLER E，DEB K，THIELE L.Comparison of multi-objective 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]//2002 Congress on Evolutionary Computation，Honolulu，2002：825-830.
[21] GONG W Y，CAI Z H，ZHU L.An effective multi-objective differential evolution algorithm for engineering design[J].Structural & Multidisciplinary Optimization，2012，38（2）：137-157.