狭义TSP小窗口蚁群算法研究

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (12): 45-46.

狭义TSP小窗口蚁群算法研究

秦姝,王锦彪

中国民航大学计算机科学与技术学院，天津 300300

收稿日期:2007-08-07 修回日期:2007-11-19 出版日期:2008-04-21 发布日期:2008-04-21
通讯作者: 秦姝

Study of window ant colony algorithm of narrow TSP

QIN Shu,WANG Jin-biao

Computer Science and Technology College，Civil Aviation University of China，Tianjin 300300，China

Received:2007-08-07 Revised:2007-11-19 Online:2008-04-21 Published:2008-04-21
Contact: QIN Shu

摘要/Abstract

摘要： 蚁窗^[1]算法是蚁群算法研究的重要进展之一。定义了大窗口和小窗口，指出经典蚁群算法实质上是大窗口蚁窗算法。研究表明，小窗口蚁窗直径的下限统计平均值约为5，使狭义TSP问题的计算复杂性由1/2（n-1）!降为5^n-1。

关键词: 蚁窗, 蚁窗直径, 大窗口, 小窗口, 狭义TSP

Abstract: The algorithm of Ant-Window^[1] is one of the important improvement of the study about ant colony algorithm.This paper defines big window and small window and points that the classical ant colony algorithm is the ant colony algorithm of big window essentially.The study demonstrates that the statistic average of Ant-Window’s diameter is 5 and that makes calculation complexity of narrow TSP problem down form 1/2（n-1）! to 5^n-1.

Key words: Ant-Window, diameter of Ant-Window, big window, small window, narrow TSP

秦姝,王锦彪. 狭义TSP小窗口蚁群算法研究[J]. 计算机工程与应用, 2008, 44(12): 45-46.

QIN Shu,WANG Jin-biao. Study of window ant colony algorithm of narrow TSP[J]. Computer Engineering and Applications, 2008, 44(12): 45-46.