基于蚂蚁算法的混合方法求解旅行商问题

基于蚂蚁算法的混合方法求解旅行商问题

黄岚　王康平　周春光　原媛　庞巍

吉林大学计算机科学与技术学院,长春,130012

收稿日期:2002-04-19 修回日期:1900-01-01 出版日期:2002-10-26
通讯作者: 周春光

Hybrid Approach Based on Ant Algorithm for Solving Traveling Salesman Problem

HUANG Lan , WANG Kang-ping , ZHOU Chun-guang , YUAN Yuan , PANG Wei

College of Computer Science and Technology , Jilin University , Changchun 130012 , China

Received:2002-04-19 Revised:1900-01-01 Online:2002-10-26
Contact: ZHOU Chun-guang

摘要/Abstract

摘要： 通过介绍蚂蚁觅食过程中最短路径的搜索策略,给出蚂蚁算法在旅行商问题中的应用,并加入3-opt方法和去交叉策略对问题求解进行局部优化.实验结果证明了其有效性.

关键词: 蚂蚁算法, 旅行商问题, 组合优化

Abstract: In the present paper the authors introduce an ant algorithm , a distributed algorithm for the solution of combinatorial optimization problems which has been inspired by the observation of real colonies of ants. Then the authors apply a hybrid approach of ant algorithm with 3-opt and cross-removing to the traveling salesman problem (TSP). The results show that it is able to find good solutions quickly.

Key words: ant algorithm, traveling salesman problem, combinatorial optimization

中图分类号:

TP31

黄岚　王康平　周春光　原媛　庞巍. 基于蚂蚁算法的混合方法求解旅行商问题[J]. J4, 2002, 40(04): 369-373.

HUANG Lan , WANG Kang-ping , ZHOU Chun-guang , YUAN Yuan , PANG Wei. Hybrid Approach Based on Ant Algorithm for Solving Traveling Salesman Problem[J]. J4, 2002, 40(04): 369-373.

[1]	任维武, 张波辰, 底晓强, 卢奕南. 基于人工蜂群优化的密度聚类异常入侵检测算法[J]. 吉林大学学报(理学版), 2018, 56(1): 95-100.
[2]	于连江, 吴春国, 郭立强, 梁艳春, 杨锌朔. 易物模型及其求解算法[J]. J4, 2010, 07(4): 653-657.
[3]	袁华, 李文辉, 常欣. 用IAA求解约束模型多解问题[J]. J4, 2010, 07(4): 636-640.
[4]	关凇元, 刘大有, 金弟, 王新华, 苏奎. 基于局部搜索的遗传算法求解自动组卷问题[J]. J4, 2009, 47(05): 961-968.
[5]	胡平, 常晓宇, 王康平, 郭东伟, 周春光. 用基于蚂蚁算法的混合方法求解不确定TSP问题[J]. J4, 2007, 45(02): 221-224.
[6]	黄岚，王康平，周春光，庞巍，董龙江, 彭利. 粒子群优化算法求解旅行商问题[J]. J4, 2003, 41(04): 477-480.