基因-表现型的布谷鸟算法求解旅行商问题  

Genotype-phenotype cuckoo search algorithm for traveling salesman problem

作　　者：林敏[1] 钟一文[1] 刘必雄[1] 林晓宇[1] LIN Min;ZHONG Yiwen;LIU Bixiong;LIN Xiaoyu(College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002, China)

机构地区：[1]福建农林大学计算机与信息学院,福州350002

出　　处：《计算机工程与应用》2017年第24期172-181,共10页Computer Engineering and Applications

基　　金：福建省自然科学基金(No.2015J01233);福建省教育厅项目(No.JAT160143)

摘　　要：布谷鸟搜索(Cuckoo Search,CS)算法在求解连续优化问题时表现出了较好的性能,但现有的CS算法在求解旅行商问题(Traveling Salesman Problem,TSP)时收敛较慢且未能体现Levy飞行的特点,针对这些不足提出了一种新的基因-表现型的布谷鸟算法(Genotype-Phenotype Cuckoo Search,GPCS),GPCS算法首先赋予每个城市一个整数部分为城市编号的随机小数编码即基因,而此基因所表现的内容由小数和整数共同决定,小数决定城市的访问次序,整数部分代表某个城市,两个部分组合起来构成Levy飞行的邻域空间,最后根据不同的飞行结果选择重定位或替换操作。实验结果表明,GPCS算法优于同类的CS算法,也优于一些其他的群智能算法,特别在求解大规模TSP时其优势更加明显。Cuckoo Search(CS)algorithm shows better performance in solving continuous problems,but the existing CS algorithm converges slowly and fails to reflect the characteristics of Levy flight.To solve the drawback,a new Genotype-Phenotype Cuckoo Search(GPCS)algorithm is proposed in this paper.In the GPCS algorithm,each city is encoded with random decimal called gene which the integer part is the city number,and the meanings contained in the genes are together decided by the decimal and the integer parts.The decimal part determines the access order of the city,the integer part represents the city number,and the two parts together constitute the neighborhood space of Levy flight,then selects the relocate or displace operation according to the flight results.The experimental results show that GPCS algorithm is not only better than other cuckoo search based algorithms,but is better than some state-of-the-art swarm intelligence algorithms too.

关 键 词：布谷鸟搜索 莱维飞行 旅行商问题 群智能算法 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]