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

发布时间：2018-01-21 07:56

本文关键词： 布谷鸟搜索莱维飞行旅行商问题群智能算法　出处：《计算机工程与应用》2017年24期 　论文类型：期刊论文

【摘要】：布谷鸟搜索(Cuckoo Search,CS)算法在求解连续优化问题时表现出了较好的性能,但现有的CS算法在求解旅行商问题(Traveling Salesman Problem,TSP)时收敛较慢且未能体现Levy飞行的特点,针对这些不足提出了一种新的基因-表现型的布谷鸟算法(Genotype-Phenotype Cuckoo Search,GPCS),GPCS算法首先赋予每个城市一个整数部分为城市编号的随机小数编码即基因,而此基因所表现的内容由小数和整数共同决定,小数决定城市的访问次序,整数部分代表某个城市,两个部分组合起来构成Levy飞行的邻域空间,最后根据不同的飞行结果选择重定位或替换操作。实验结果表明,GPCS算法优于同类的CS算法,也优于一些其他的群智能算法,特别在求解大规模TSP时其优势更加明显。
[Abstract]:Cuckoo search Cuckoo SearchCass (Cuckoo) algorithm shows good performance in solving continuous optimization problems. However, the current CS algorithm is slow to converge and does not reflect the characteristics of Levy flight when it is used to solve traveling salesman problem (TSP). A new gene-phenotype Cuckoo algorithm, Genotype-Phenotype Cuckoo search Cuckoo, is proposed. The GPCS algorithm first gives each city a random decimal code with an integer part of the city number, that is, gene. The content of the gene is determined by the decimal and integer, and the decimal determines the access order of the city. The integer part represents a city, and the two parts combine to form the neighborhood space of Levy flight. Finally, according to different flight results, the relocation or replacement operation is selected. The experimental results show that. The GPCS algorithm is superior to the similar CS algorithm and some other swarm intelligence algorithms, especially for solving large scale TSP.
【作者单位】：福建农林大学计算机与信息学院;
【基金】：福建省自然科学基金(No.2015J01233) 福建省教育厅项目(No.JAT160143)
【分类号】：TP18
【正文快照】： 1引言旅行商问题(Traveling Salesman Problem,TSP)是组合优化领域的一个典型问题,在运筹学和理论计算机科学中非常重要,其求解方案可广泛应用于集成电路布线、车间调度、物流配送等,由于其所代表的意义以及易描述性,常常作为基准函数用来测试算法的性能。TSP属于NP-困难问题,

【相似文献】