计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (24): 172-181.DOI: 10.3778/j.issn.1002-8331.1708-0001

• 模式识别与人工智能 • 上一篇    下一篇

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

林  敏,钟一文,刘必雄,林晓宇   

  1. 福建农林大学 计算机与信息学院,福州 350002
  • 出版日期:2017-12-15 发布日期:2018-01-09

Genotype-phenotype cuckoo search algorithm for traveling salesman problem

LIN Min, ZHONG Yiwen, LIU Bixiong, LIN Xiaoyu   

  1. College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002, China
  • Online:2017-12-15 Published:2018-01-09

摘要: 布谷鸟搜索(Cuckoo Search,CS)算法在求解连续优化问题时表现出了较好的性能,但现有的CS算法在求解旅行商问题(Traveling Salesman Problem,TSP)时收敛较慢且未能体现Levy飞行的特点,针对这些不足提出了一种新的基因-表现型的布谷鸟算法(Genotype-Phenotype Cuckoo Search,GPCS),GPCS算法首先赋予每个城市一个整数部分为城市编号的随机小数编码即基因,而此基因所表现的内容由小数和整数共同决定,小数决定城市的访问次序,整数部分代表某个城市,两个部分组合起来构成Levy飞行的邻域空间,最后根据不同的飞行结果选择重定位或替换操作。实验结果表明,GPCS算法优于同类的CS算法,也优于一些其他的群智能算法,特别在求解大规模TSP时其优势更加明显。

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

Abstract: 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.

Key words: cuckoo search, Levy flight, traveling salesman problem, swarm intelligence algorithm