TSP��������NP������,�ڵ�·�岼�֡�VLSIоƬ��ơ��������ȵ�����Ż����������Ź㷺��Ӧ�á���Ⱥ�㷨���������ѧ��Dorigo��[1]���������һ�ֻ�����Ⱥģ�������������ʽ�㷨,���Ѿ��ɹ�Ӧ����TSP�ȶ��NP�ѵ�����Ż��������,��������Ⱥ�㷨Ҳ�������׳������졢ͣ�͵�ȱ�ݡ������Ⱥ�㷨����Щȱ��,�������������Ľ����㷨,����Q-Learning�����Ant-Q�㷨[2]��MMAS�㷨[3],���ڸ���������Ⱥ�㷨[4]�ȡ�������ʶ����Ⱥ����֯���зֹ�������,�����������̬��Ⱥ�㷨,��һ���̶��ϸ�������Ⱥ�㷨������,Ҳ�����TSP���Ч�ʵ�һ����չ�������з����������ٶȺ���⾫����δ�ﵽһ���ܺõ�ƽ�⡣
�����㷨ͨ��������Ϣ�ػӷ���������Ӧ��������,��֤�㷨��ȫ����������,��Ч�ر����㷨����ֲ����Ž⡣����,ͨ����ǿ����·����ѡ�������㷨Ѱ�Ҹ���·��,ʹ�����㷨ͣ��ǰ���ڷ��ָ��õ�·��,����������·���⡣���㷨������Ч��ֹ����ֲ����Ž�,ͬʱ����������ٶȡ�
���㷨��,��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)��ɵ�ת�ƹ����Ϊα�������,�˹���������ѡ�������Ϣ��Ũ�ȴ�ı���Ϊ�ƶ�����
ÿ������������,��ÿֻ���ϵ���Ϣ�ذ�ʽ(4)(5)(6)���и���:
ʽ��:mΪ�����ܸ���;��Ϊ��Ϣ�ӷ���;��ijΪ�����ڱ���ѭ��������·��(i,j)�ϵ���Ϣ��;����ijΪ����ѭ�������о�����·��(i,j)���������ڸ�·���ϵ���Ϣ��������;QΪһ������(��ʾ����ѭ��һ�����ͷŵ�����Ϣ��);LkΪ��kֻ�����ڱ���ѭ��������·���ij��ȡ�������Ϣ���¹�������������ǿ,�ܹ����ϵͳ�����ٶȡ�
�ѷ�Ӧ������Ⱥϵͳ�Ľ���״̬,���Ĵ�Сֱ�ӹ�ϵ����Ⱥ�㷨��ȫ�����������������ٶȡ����ѹ���ʱ,Ҳ��Ӱ�쵽�㷨��������ܺ�ȫ����������;��֮,ͨ����С��Ϣ�ػӷ��Ȧ���Ȼ���Ը��Ƹ�����,���ֻ�ʹ�㷨�������ٶȽ��͡�
Ϊ��ʹ��Ⱥʼ���ܹ��ڡ�̽�����͡����á�֮�䱣��ƽ��,ʹ�㷨�ھ��н�ǿ��ȫ������������ͬʱ�������ͣ��״̬,����[5-[6]]�������˲�ͬ������Ӧ����������̬������ֵ,������㷨ȫ����������,���������ڽ��Ž⡣���ĵĸĽ��㷨��ѡ�ü���Ч������Ӧ������������,�������ʽΪ
ʽ��:����(0,1)Ϊ�ӷ����ӵ���ϵ��;��minΪ�ѵ���Сֵ���㷨���ڸ���ѽϴ��ֵ,��Ϣ������������ռ������λ,��ǰ��������·����ѡ��Ŀ����Խϴ�,�����ٶȱȽϿ�,��Ҳ����������ֲ����Ž⡣�������ͦѵ�ֵ,��Ϣ�����������û���������,��Щ��δ����������·����Ϣ������,����������Ծ���ǿ,�����ȫ����������,���ֻ�Ӱ����Ⱥ�㷨�����ٶȡ�����,Ϊ������һ����Сֵ,��ֹ�˦ѹ�С�������㷨�������ٶȡ�ͨ���Իӷ�ϵ����������Ӧ�ظı�,�ȿ�����߽��ȫ����,�ֿ��Ա�֤�������ٶȡ�
��������Ӧ������Ч���������Ⱥ�㷨��ȫ����������,ʹ���㷨�ܹ��Ͽ��������һЩ���Ž�,���ӽ��Ž��ѽ�Ľ�������ʱ��ϳ�,�������û��ڹ���·��Ѱ�ŵķ����ӿ�Ѱ���ٶȡ��÷�����������[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 |
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��ȡ�
Ϊ�˸��õ�˵�����㷨����Ч��,ѡ�ù�����ͨ�õ�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 |
�����㷨������Ϣ�ػӷ���������Ӧ�������Ƶ����㷨�����ٶ�,������ȼ�����ijЩ���ŵ�·���ϡ���ͨ����ǿ�㷨�Թ���·��������ʹ�㷨��������Ѱ�������е��ظ�����,������Ⱥ�㷨������ʱ��,���������������ֲ�����,��ǿ���㷨��ȫ��Ѱ��������ʵ��������,�Ľ��㷨�ڵ���������Խ��ٵ������,��õĽ����ڻ�ӽ����г��������㷨,ƽ��������֪���Ž�ƫ��Ϊ0.46%,���Ž�����֪���Ž�ƫ��Ϊ0.23%,�Ϻõ����������TSP���⡣
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|