���TSP����Ŀ�����Ⱥ�㷨
���義1,2, ������1,2, ����ƽ1,2, �� ��3, ��ϰ��1
1.���ִ�ѧ �������ѧ�뼼��ѧԺ,���� 130012
2.���ִ�ѧ ���ż�����֪ʶ���̽������ص�ʵ����,���� 130012
3.����ʯ�ͼ����������ι�˾ 䬺�ũ��,���� ��ԭ 138000
ժҪ
�����Ⱥ�㷨�������������ʱ���������ٶ�������������ֲ����ŵ�����,�����һ�ָĽ�����Ⱥ�㷨���Ľ��㷨������Ϣ�ػӷ���������Ӧ��������,�����㷨�����ٶ�,��֤�㷨��ȫ������������ͬʱ���ݹ���·��������Ⱥ�㷨����ʱ��,�յ���ȺѰ�Ҹ��Ž⡣ʵ��������,�Ľ��㷨�ڵ���������Խ��ٵ��������õ�ƽ��������֪���Ž�ƫ��Ϊ0.46%,���Ž�����֪���Ž�ƫ��Ϊ0.23%,�������ٶȼ���⾫���Ͼ�ȡ���˽Ϻõ�Ч����
�ؼ���: �˹�����; ��Ⱥ�㷨; ����·��; ����Ӧ; ����������
Fast ant colony algorithm for solving traveling salesman problem
SHEN Xuan-jing1,2, LIU Yang-yang1,2, HUANG Yong-ping1,2, XU Tie3, He Xi-wen1
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
3.Taohe Farm, Jilin Oil Refco Group Ltd, Songyuan 138000,China
Abstract
Using ant colony algorithm to solve Traveling Salesman Problem (TSP) has certain disadvantages, such plunging into local minimum, slower convergence speed and so on. In order to find the optimal path accurately and rapidly, an improved ant colony algorithm is proposed. The improved algorithm uses adaptive adjusting mechanism of pheromone decay parameter to adjust the convergence speed and ensure the global search ability. With the help of common path, the computation time is reduced and the better solution can be obtained. Experiments show that, in a relatively few iterations, the percentage deviation of the average solution to the best known solution is 0.46%, and the percentage deviation of the best solution to the best known solution is 0.23%. The improved algorithm has high accuracy and convergence speed.
Keyword: artificial intelligence; ant colony algorithm; common path; adaptive; traveling salesman problem

TSP��������NP������,�ڵ�·�岼�֡�VLSIоƬ��ơ��������ȵ�����Ż����������Ź㷺��Ӧ�á���Ⱥ�㷨���������ѧ��Dorigo��[1]���������һ�ֻ�����Ⱥģ�������������ʽ�㷨,���Ѿ��ɹ�Ӧ����TSP�ȶ��NP�ѵ�����Ż��������,��������Ⱥ�㷨Ҳ�������׳������졢ͣ�͵�ȱ�ݡ������Ⱥ�㷨����Щȱ��,�������������Ľ����㷨,����Q-Learning�����Ant-Q�㷨[2]��MMAS�㷨[3],���ڸ���������Ⱥ�㷨[4]�ȡ�������ʶ����Ⱥ����֯���зֹ�������,�����������̬��Ⱥ�㷨,��һ���̶��ϸ�������Ⱥ�㷨������,Ҳ�����TSP���Ч�ʵ�һ����չ���򡣵����з����������ٶȺ���⾫����δ�ﵽһ���ܺõ�ƽ�⡣

�����㷨ͨ��������Ϣ�ػӷ���������Ӧ��������,��֤�㷨��ȫ����������,��Ч�ر����㷨����ֲ����Ž⡣����,ͨ����ǿ����·����ѡ�������㷨Ѱ�Ҹ���·��,ʹ�����㷨ͣ��ǰ���ڷ��ָ��õ�·��,����������·���⡣���㷨������Ч��ֹ����ֲ����Ž�,ͬʱ����������ٶȡ�

1 �㷨����
1.1 ����Ⱥ���ƶ�����

���㷨��,��kֻ�����ɳ���iѡ����һ������j�Ĺ�����:.

��q��q0ʱ,

��q>q0ʱ,���ϸ���ת�Ƹ��ʹ�ʽ(2)ѡ����һ����:

ʽ��:q0��һ��������λ��(0,1)֮��ij���;q��һ����(0,1)֮����ȷֲ��������;��iu(t)��ʾ����i�ͳ���u֮��·���ϵ���Ϣ��Ũ��;dijΪ��������֮��ľ���;��Ϣ����ʽ���Ӧ���ӳ�������˶������������۵���Ϣ��(��������Ϣ����iu(t))��ָ����Ⱥ�����е������Ҫ�̶�;����ֵ����ʽ���Ӧ·�ӳ�������˶�������������Ϣ(������ֵ��ij)��ָ����Ⱥ�����е������Ҫ�̶�;allowedk��ʾ��kֻ���ϵ�ǰ�Ŀ��е㼯����ʽ(1)��ʽ(2)��ɵ�ת�ƹ����Ϊα�������,�˹���������ѡ�������Ϣ��Ũ�ȴ�ı���Ϊ�ƶ�����

1.2 ��Ϣ������Ӧ���²���

ÿ������������,��ÿֻ���ϵ���Ϣ�ذ�ʽ(4)(5)(6)���и���:

ʽ��:mΪ�����ܸ���;��Ϊ��Ϣ�ӷ���;��ijΪ�����ڱ���ѭ��������·��(i,j)�ϵ���Ϣ��;����ijΪ����ѭ�������о�����·��(i,j)���������ڸ�·���ϵ���Ϣ��������;QΪһ������(��ʾ����ѭ��һ�����ͷŵ�����Ϣ��);LkΪ��kֻ�����ڱ���ѭ��������·���ij��ȡ�������Ϣ���¹�������������ǿ,�ܹ����ϵͳ�����ٶȡ�

�ѷ�Ӧ������Ⱥϵͳ�Ľ���״̬,���Ĵ�Сֱ�ӹ�ϵ����Ⱥ�㷨��ȫ�����������������ٶȡ����ѹ���ʱ,Ҳ��Ӱ�쵽�㷨��������ܺ�ȫ����������;��֮,ͨ����С��Ϣ�ػӷ��Ȧ���Ȼ���Ը��Ƹ�����,���ֻ�ʹ�㷨�������ٶȽ��͡�

Ϊ��ʹ��Ⱥʼ���ܹ��ڡ�̽�����͡����á�֮�䱣��ƽ��,ʹ�㷨�ھ��н�ǿ��ȫ������������ͬʱ�������ͣ��״̬,����[5-[6]]�������˲�ͬ������Ӧ����������̬������ֵ,������㷨ȫ����������,���������ڽ��Ž⡣���ĵĸĽ��㷨��ѡ�ü򵥶���Ч������Ӧ������������,�������ʽΪ

ʽ��:����(0,1)Ϊ�ӷ����ӵ���ϵ��;��minΪ�ѵ���Сֵ���㷨���ڸ���ѽϴ��ֵ,��Ϣ������������ռ������λ,��ǰ��������·����ѡ��Ŀ����Խϴ�,�����ٶȱȽϿ�,��Ҳ����������ֲ����Ž⡣�����𽥽��ͦѵ�ֵ,��Ϣ�����������û��𽥼�������,��Щ��δ����������·����Ϣ������,����������Ծ���ǿ,�����ȫ����������,���ֻ�Ӱ����Ⱥ�㷨�����ٶȡ�����,Ϊ������һ����Сֵ,��ֹ�˦ѹ�С�������㷨�������ٶȡ�ͨ���Իӷ�ϵ����������Ӧ�ظı�,�ȿ�����߽��ȫ����,�ֿ��Ա�֤�������ٶȡ�

1.3 ����·����������

��������Ӧ������Ч���������Ⱥ�㷨��ȫ����������,ʹ���㷨�ܹ��Ͽ��������һЩ���Ž�,���ӽ��Ž⵽��ѽ�Ľ�������ʱ��ϳ�,�������û��ڹ���·��Ѱ�ŵķ����ӿ�Ѱ���ٶȡ��÷�����������[7]����������ĸĽ����ԡ�����[7]�����ٴε����󷴸��߹���·����Ϊ�ؾ�����,�Խ����㷨������ʱ��,������Ⱥ�㷨��������ֲ�����,��������õĿ���Ϊ�ֲ����Ž�,�������㷨��׼ȷ�ԡ�

���ݸ�˼�뱾�����һ���µĸĽ�����,����Ⱥ��Ϊ����ֱ��Բ�ͬ�ķ���Ѱ������һ�鰴������Ⱥ�㷨����ȫ������·��,�ڶ������ù���·��Ѱ�š�����Ѱ��ʱ������Ϣ�ص�����,һ������һЩ�϶̲��ظ�������·����,������ͼ1��ʾ�����,��ֻ����a1��a2���߹���ͬ��·���Ρ�����,�ڸĽ��㷨��������ֹ���·������������,����ȡ��ǰ��������Ž�Ĺ���·��,
��Щ����·���м���Ŀ����Ǹ��Ž�·����ȫ�����Ž����ɲ���,Ϊ�ڶ��������ṩ�����õ�Ѱ����������,����ǰ����·�������ڽṹ����,�ڶ����������ù���·��ȥѰ��ʱ,�ɼ����㷨���Ĺ�����,������һ���ռ临�Ӷȵķ�ʽ����ȡ���ٵ�ʱ�临�Ӷȡ�����������Ѱ��������,ͳһ�޸���Ϣ�ص�ֵ,����Ⱥ��һ��Ѱ��ʹ��,���µ�ǰ��������Ž⡣����·��Ϊ�㷨��Ѱ���������ṩ�����õĵ���,ʹ�����㷨ͣ��ǰ���ڷ��ָ��õ�·��,������������·����,�����Լ��ٴ������ظ�����,����㷨�����ٶȡ��㷨����������ͼ2��ʾ��


ͼ3Ϊ�Ľ��㷨���Eil51ʵ���õ���·��ͼ��ͼ3(a)��(b)�ֱ�Ϊ��i�ε����õ������������·��,�ҵ�����·��(��ͼ3(c)),��Ϊ��һ�ε����еڶ�����Ⱥ�ؾ����ıߡ�����ȡ�˹���·����,�㷨�ĺ�������ʵ�����ǴӴ��ڷǹ���·���ij����й���һ�����·�������Ǻ͹���·���������һ����·,�����ͱ�����Ѱ�������е������ظ�����,���㷨����һ��������,���Ž�����Ž�Ĺ���·�����п�����ʵ�����Ž����ɲ���,�����ָ����㷨һ�����õķ�����ʹ�����㷨ͣ��ǰ���ڷ��ָ��õ�·������ͼ3(c)��(d)���Կ���,�Ľ��㷨�����ҵ��˷dz��ӽ�ʵ������·���Ľ�,���������������˴󲿷ֵĹ���·����

ͼ1 һ��������������ֵ��ظ�·��Fig.1 Repeated paths at a particular iteration
ͼ2 һ�ε����е���ȺѰ������ͼFig.2 Flowchart of looking for paths in an iteration
ͼ3 �Ľ��㷨��õ�·��Fig.3 Routes found by proposed algorithm
1.4 �㷨����

Step1 ��ʼ��:Nmax_A����Ⱥ�㷨��������������;m�����ϸ���;NA��1,��Ⱥ�㷨����������;��Ⱥ��Ϣ�ئ�ij��C;����ij��0��

Step2 ����Ⱥ�ֳ�����,��һ�鰴��ʽ(1)��(2)����״̬ת��,������Ⱥ·���⡣

Step3 �������źʹ��Ž�,���ҵ����Ž�ʹ��Ž�Ĺ���·����

Step4 �ڶ������õõ��Ĺ���·��Ѱ��,������·����Ϊ�ؾ����ı�,�ǹ���·���ϵij��а�ʽ(1)(2)����״̬ת���빫��·������һ����·,������Ⱥ·���⡣

Step5 ������Ⱥ�������Ž����С�ڵ�ǰ���Ž�,�������źʹ��Ž�,תStep7;������ڵ�ǰ���Ž�,תStep6��

Step6 ���С�ڵ�ǰ���Ž�,���´��Ž⡣

Step7 ��ʽ(4)(5)��(6)������Ϣ�ء�

Step8 NA��NA+1,���NA>Nmax_AתStep9,����תStep2��

Step9 �������·��������·���ij��ȡ�

2 ʵ���������

Ϊ�˸��õ�˵�����㷨����Ч��,ѡ�ù�����ͨ�õ�TSPLIB���Կ��е�Eil51ʵ�����в��ԡ�ʵ����滷��:1.60 GHz��Ƶ��Intel������,1 G�ڴ�,��������Microsoft Visual C++6.0��ʵ������������m=51/1.5=34,������=1.0����=3.0��q0=0.5,.

��Ϣ�ػӷ����ӳ�ʼֵ��0��Ϊ0.9,�ӷ����ӵ���ϵ������Ϊ0.98,��min��Ϊ0.5��ͼ4�DZ��ĸĽ��㷨��������4�ε���������ͼ,�㷨��600��֮���������,���������430,���������428��ͼ5���㷨��������15�εĽ��ͼ,�����·��ֵΪ433,���·��ֵΪ427,·����ֵΪ428��

������Eil51Ϊ���Ƚ��˼����㷨������,�������1��ʾ������,ACS�㷨ÿ�ε���3000��;ShyiMing Chen��ChihYao Chien����ķ����ڲ��Ŵ��㷨����100��,�����Ⱥ�㷨����30��,ÿ��120ֻ����;�Ľ��Ļ�������㷨ÿһ������510ֻ,������50�Ρ�

��1�и����˲�ͬ�㷨��ƽ���������Ž����TSPLB������֪Eil51���Ž�(426)��ƫ��ٷֱ�PDav��PDbest,ͼ6��ͼ7�����㷨���Eil51ʵ����õ�ƽ��ֵ����֪���Ž�ƫ�������ʱ������һ��ֱ�۵ıȽϡ�
PDav��PDbest������������:

����1��ͼ6��ͼ7��֪,���㷨�ڵ����������ٵ������,�㷨���������ڻ�ӽ����г��ĶԱ��㷨,�Ӷ���һ����֤���㷨����Ч�ԡ�

ͼ4 �Ľ��㷨����������ͼFig.4 Convergence process map of proposed algorithm
ͼ5 �Ľ��㷨����15�ν��ͼFig.5 Results of proposed algorithm after
running 15 times
��1 �����㷨�������㷨�ıȽ�Table 1 Comparison between proposed algorithm
and other algorithms
ͼ6 ��ͬ�㷨��ƽ��������֪���Ž��ƫ��Fig.6 Percentage deviations of average solution to
best known solution for different methods
ͼ7 ��ͬ�㷨��ƽ������ʱ��Fig.7 Average running time of different methods
3 ������

�����㷨������Ϣ�ػӷ���������Ӧ�������Ƶ����㷨�����ٶ�,������ȼ�����ijЩ���ŵ�·���ϡ���ͨ����ǿ�㷨�Թ���·��������ʹ�㷨��������Ѱ�������е��ظ�����,������Ⱥ�㷨������ʱ��,���������������ֲ�����,��ǿ���㷨��ȫ��Ѱ��������ʵ��������,�Ľ��㷨�ڵ���������Խ��ٵ������,��õĽ����ڻ�ӽ����г��������㷨,ƽ��������֪���Ž�ƫ��Ϊ0.46%,���Ž�����֪���Ž�ƫ��Ϊ0.23%,�Ϻõ����������TSP���⡣

�����
[1] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26��1��: 29-41. [��������:1]
[2] Dorigo M, Gambardella L M, Middendorf M, et al. Guest editorial: special section special section on ant colony optimization[J]. IEEE Transaction on, Evolutionary Computation, 2002, 6��4��: 317-319. [��������:1]
[3] Stutzle T, Hoos H H. Max-min ant system[J]. Future Generation Computer Systems, 2000��16��: 889-914. [��������:1]
[4] Malisia A R, Tizhoosh H R. Applying opposition- based ideas to the ant colony system[C]��2007 IEEE Congress on Swarm Intelligence Symposium, Hono-lulu, HI, 2007: 182-189. [��������:1]
[5] Duan H B, Zhang X Y, Wu J, et al. Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments[J]. Journal of Bionic Engineering, 2009, 6��2��: 161-173. [��������:0] [JCR: 1.023] [CJCR: 0.38]
[6] Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem[J]. Euro- pean Journal of Operational Research, 2009, 196��1��: 171-176. [��������:0] [JCR: 1.815]
[7] Tseng S P, Tsai C W, Chiang M C, et al. A fast ant colony optimization for traveling salesman problem[C]��2010 IEEE Congress on Evolutionary Computation, Barcelona, 2010: 1-6. [��������:0]
[8] ��ѩ��, ����, ��ϼ. �Ľ���������㷨�������������[J]. ͨ��ѧ��, 2009, 30��7��: 130-134.
Luo Xue-hui, Yang Ye, Li Xia. Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J]. Journal on Communications, 2009, 30��7��: 130-134.
[��������:0] [CJCR: 1.119]
[9] Masutti T A S, Castro L N D. A self-organizing neural network using ideas from the immune system to solve the travelling salesman problems[J]. Information Sciences, 2009, 179��10��: 1454-1468. [��������:0]
[10] Chen S M, Chien C Y. Solving the traveling sales-man problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J]. Expert Systems with Applications, 2011��38��: 14439-14450. [��������:0] [JCR: 2.203]