蝉鸣优化算法在组合优化问题中的应用

沈秋玲 胡甜 马婷 李社蕾

【摘 要】文献（1）提出了蝉鸣优化（CSO）算法，利用CSO、PSO和DE对9个高维Benchmark函数的仿真，得到了非常好的优化结果，该算法尚未在组合优化问题中应用，本文利用CSO算法对旅行商问题（TSP），这一典型的组合优化问题，进行优化，建立了CSO算法解决TSP问题的模型，并利用MATLAB进行仿真。实验结果表明，CSO也是一种非常适于求解组合最优化问题的进化算法。

【关键词】蝉鸣优化算法;组合优化;旅行商问题;水平集

中图分类号：TP391.4文献标识码： A文章编号： 2095-2457（2019）04-0099-002

DOI：10.19694/j.cnki.issn2095-2457.2019.04.038

Application of cicada song optimization algorithm in combinatorial optimization problems

SHEN Qiu-ling HU Tian MA Ting LI She-lei

（College of Information & Inteligence Engineering  Sanya University，Sanya Hainan 572022，China）

【Abstract】The literature（1）proposed a CSO algorithm and uses CSO， PSO， and DE to simulate 9 high-dimensional Benchmark functions. The result of the optimization is very good. The algorithm has not yet been applied to combinatorial optimization problems. The CSO algorithm optimizes the traveling salesman problem（TSP）， a typical combinatorial optimization problem， established a CSO algorithm to solve the TSP problem model， and used MATLAB to simulate. The experimental results shown that CSO is a kind of evolutionary algorithm very suitable to solve combination optimization problems.

【Key words】Cicada optimization algorithm; Combination optimization; Traveling salesman problem; Level set

0 引言

TSP（traveling salesman problem）的歷史很久，是一个经典的组合优化问题[2-5]，问题表述为[6-9]：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。很多高效的算法被用于尝试求解TSP。遗传算法、蚁群算法、模拟退火算法、粒子群算法和神经网络等仿自然算法在求解TSP问题上都获得不错的结果。随着旅游业和物流业快速发展，高效、低成本、低能耗成了各个物流企业追求的目标，更加合理的配送路线能明显地为物流公司增大利润;如何有效地节省出行费用和时间一直都是游客、旅行社、物流企业探索和研究的内容。出行路线的选择其实是旅行最优商问题（TSP），是一个组合优化问题。因此，旅行商问题（TSP）有着广泛的应用领域和巨大的发展空间。

2014年，贺毅朝[2]等人提出了借鉴秋蝉鸣叫中表现出的某种同步化以及蝉的生活习性提出了一种新的仿生优化算法： 蝉鸣优化（CSO），从秋蝉的求偶歌，使用5种信号构成一种音乐节律的现象得到启发， 提出了一种基于5种不同进化方式的进化算子： 五音进化算子（Five Timbre Evolution Operator ，FTEO），对9个高维Benchmark函数进行仿真计算，在求解数值优化问题性较好，在求解组合优化问题方面尚未进行研究，虽然近年来不断涌现了许多基于仿生学的优化算法，常见的有粒子群算法、遗传算法、蚁群算法人工鱼等算法。在解决组合问题过程中都得到了很好的优化结果，但是对于某一特定的优化问题，不同的优化算法的优化效果存在一定的差异，因此对于不同的优化问题，设计更适于求解的优化算法是有一定的研究价值的，本文尝试将CSO算法应用在组合优化问题的求解中，选取旅行商问题（TSP），这一典型的组合优化问题，进行优化，建立了CSO算法解决TSP问题的模型。

1 基于CSO算法的TSP问题数学模型

假设有一个G=（V，E），其中V是顶点集，E是边集，设D=（dij），是由顶点i和顶点j之间的距离所组成的距离矩阵，TSP问题就是求解一条经过所有顶点且每个顶点只通过一次的具有最短距离的回路。

对于TSP问题，L为问题的最优解，用CSO算法求解该问题，其控制参数如下：种群大小POPSIZE，最大迭代次数NC，城市数目NumCity，距离矩阵D，城市列表W，best_route为最优路径，inindividual_cso为种群矩阵，大小为POPSIZE*NumCity，rand（5）为{1，2，3，4，5}中的一个随机数，则FTEO定义如下：

其中，1≤i≤POPSIZE，p1≠p2≠p3≠i，A为（0，1）的随机数。FTEO算子可能会使群体中产生一些不满足问题的约束条件或者无意义的巡回路线，为克服这一缺点，采用Grefenstettet 编码法，任意种群中的个体都对应这一条有实际意义的巡回路线，是的概算子有意义，然后对其解码得到实际巡回路径。

设阈值threshold的个体的生命周期，种群inindividual_cso的第i个体的生存因子为sp（i），初始sp（i）=0; 1≤i≤POPSIZE，每当产生新一代种群后，如果当前的最短路径L_generation>L，则sp（i）= sp（i）+1，否则sp（i）不变。对于种群inindividual_cso中的个体inindividual_cso（i），如果其生存因子sp（i）>threshod，则用一个随机产生的新个体替换inindividual_cso（i）。

2 仿真结果分析

为了验证CSO的可行性与有效性，使用硬件环境为Intel（R）Core（TM）i3-2100 CPU@3.10GHz 3.09GHz，3.01GB内存硬件，操作系统为windows XP操作系统， 利用Matlab2012a软件，进行仿真并与蚁群算法和遗传算法进行对比，实验结果表明，CSO算法的优化结果由于遗传算法，和蚁群算法的优化结果相近，但种群的收敛性不如遗传算法。

3 结论

本文利用CSO算法对旅行商问题（TSP），这一典型的组合优化问题，进行优化，建立了CSO算法解决TSP问题的模型，利用该算法模拟仿真求解——30个城市的TSP问题，并用MATLAB实现了该算法，仿真实验结果验证了CSO结果组合优化问题的可行性和有效性，为解决组合优化问题提供一种方案。优化结果有待进一步改进，下一步考虑将CSO优化算法应用到其他组合优化问题上，研究CSO求解其他组合优化问题的方法，并逐步改进其性能。

【参考文献】

[1]贺毅朝，李宁，李文斌.蝉鸣优化：一种新的仿生进化算法[J].计算机科学，2014，41（06）：235-238+249.

[2]郑明，卓慕瑰.四点三线遗传算法求解旅行商问题[J].计算机工程与应用，2017，53（14）：148-154.

[3]梁旗军，舒坚，樊鑫，刘琳岚.一种基于遗传算法的TSP建模方法[J].计算机工程，2011，37（05）：68-70.

[4]代桂平，王勇，侯亚荣.基于遗传算法的TSP问题求解算法及其系统[J].微计算机信息，2010，26（04）：15-16+19.

[5]Bergeron J，Nightingai A.Verification methodology manualfor System Verilog [M].New York：Springer-Ver1ag，2006.

[6]葉欢，经亚枝.Grefenstette编码法的MATLAB实现[J].中国测试技术，2004（02）：58-60.

[7]温清芳.遗传算法求解TSP问题的MATLAB实现[J].韶关学院学报，2007（06）：18-22.

[8]袁汪凰，游晓明，刘升，朱艳.求解TSP问题的自适应模拟退火蚁群算法[J].计算机应用与软件，2018，35（02）：261-266.

[9]陈海英，李淑玉.TSP问题的蚁群算法模型及仿真研究[J].科技通报，2012，28（12）：72-75.