开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2022.01.23
蚁群算法计算过程如下：
（1）初始化
设t=0，初始化bestLength为一个非常大的数（正无穷），bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，Allowed表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在Tabu中加入起始节点，Allowed中去掉该起始节点。
（2）为每只蚂蚁选择下一个节点。
为每只蚂蚁选择下一个节点，该节点只能从Allowed中以某种概率（公式1）搜索到，每搜到一个，就将该节点加入到Tabu中，并且从Allowed中删除该节点。该过程重复n-1次，直到所有的城市都遍历过一次。遍历完所有节点后，将起始节点加入到Tabu中。此时Tabu表元素数量为n+1（n为城市数量），Allowed元素数量为0。接下来按照（公式2）计算每个蚂蚁的Delta矩阵值。最后计算最佳路径，比较每个蚂蚁的路径成本，然后和bestLength比较，若它的路径成本比bestLength小，则将该值赋予bestLength，并且将其Tabu赋予BestTour。
（3）更新信息素矩阵
（4）检查终止条件
（5）输出最优值
Java实现
在该java实现中我们选择使用tsplib上的数据att48，这是一个对称tsp问题，城市规模为48，其最优值为10628.其距离计算方法如图（2）所示：
att48距离计算方法
实现中，使用了两个java类，一个Ant类，一个ACO类。
具体实现代码如下（此代码借鉴了蚁群优化算法的JAVA实现）：
Ant类：
3：
4：/**
5：*
6：*@authorBIAOYU
7：*
8：*/
9：publicclassAntimplementsCloneable{
10：
11：privateVector《Integer》tabu;//禁忌表
13：privatefloat［］［］delta;//信息数变化矩阵
14：privateint［］［］distance;//距离矩阵
15：
16：privatefloatalpha;
17：privatefloatbeta;
18：
19：privateinttourLength;//路径长度
20：privateintcityNum;//城市数量
21：
22：privateintfirstCity;//起始城市
23：privateintcurrentCity;//当前城市
24：
25：publicAnt（）{
26：cityNum=30;
27：tourLength=0;
28：
29：}
30：
31：/**
32：*ConstructorofAnt
33：*@paramnum蚂蚁数量
34：*/
35：publicAnt（intnum）{
36：cityNum=num;
37：tourLength=0;
38：
39：}
40：
41：/**
42：*初始化蚂蚁，随机选择起始位置
43：*@paramdistance距离矩阵
44：*@paramaalpha
45：*@parambbeta
46：*/
47：publicvoidinit（int［］［］distance，floata，floatb）{
48：alpha=a;
49：beta=b;
51：tabu=newVector《Integer》（）;
52：this.distance=distance;
53：delta=newfloat［cityNum］［cityNum］;
54：for（inti=0;i《cityNum;i++）{
55：Integerinteger=newInteger（i）;
56：allowedCities.add（integer）;
57：for（intj=0;j《cityNum;j++）{
58：delta［i］［j］=0.f;
59：}
60：}
61：
62：Randomrandom=newRandom（System.currentTimeMillis（））;
63：firstCity=random.nextInt（cityNum）;
64：for（Integeri:allowedCities）{
65：if（i.intValue（）==firstCity）{
66：allowedCities.remove（i）;
67：break;
68：}
69：}
70：
71：tabu.add（Integer.valueOf（firstCity））;
72：currentCity=firstCity;
73：}
74：
75：/**
76：*选择下一个城市
77：*@parampheromone信息素矩阵
78：*/
79：publicvoidselectNextCity（float［］［］pheromone）{
80：float［］p=newfloat［cityNum］;
81：floatsum=0.0f;
82：//计算分母部分
83：for（Integeri:allowedCities）{
84：sum+=Math.pow（pheromone［currentCity］［i.intValue（）］，alpha）*Math.pow（1.0/distance［currentCity］［i.intValue（）］，beta）;
85：}
86：//计算概率矩阵
87：for（inti=0;i《cityNum;i++）{
88：booleanflag=false;
89：for（Integerj:allowedCities）{
90：
91：if（i==j.intValue（））{
92：p［i］=（float）（Math.pow（pheromone［currentCity］［i］，alpha）*Math.pow（1.0/distance［currentCity］［i］，beta））/sum;
93：flag=true;
94：break;
95：}
96：}
97：
98：if（flag==false）{
99：p［i］=0.f;
100：}
101：}
102：
103：//轮盘赌选择下一个城市
104：Randomrandom=newRandom（System.currentTimeMillis（））;
105：floatsleectP=random.nextFloat（）;
106：intselectCity=0;
107：floatsum1=0.f;
108：for（inti=0;i《cityNum;i++）{
109：sum1+=p［i］;
110：if（sum1》=sleectP）{
111：selectCity=i;
112：break;
113：}
114：}
115：
116：//从允许选择的城市中去除selectcity
117：for（Integeri:allowedCities）{
118：if（i.intValue（）==selectCity）{
119：allowedCities.remove（i）;
120：break;
121：}
122：}
123：//在禁忌表中添加selectcity
124：tabu.add（Integer.valueOf（selectCity））;
125：//将当前城市改为选择的城市
126：currentCity=selectCity;
127：
128：}
129：
130：/**
131：*计算路径长度
132：*@return路径长度
133：*/
134：privateintcalculateTourLength（）{
135：intlen=0;
136：for（inti=0;i《cityNum;i++）{
137：len+=distance［this.tabu.get（i）.intValue（）］［this.tabu.get（i+1）.intValue（）］;
138：}
139：returnlen;
140：}
141：
142：
143：
144：publicVector《Integer》getAllowedCities（）{
145：returnallowedCities;
146：}
147：
148：publicvoidsetAllowedCities（Vector《Integer》allowedCities）{
149：this.allowedCities=allowedCities;
150：}
151：
152：publicintgetTourLength（）{
153：tourLength=calculateTourLength（）;
154：returntourLength;
155：}
156：publicvoidsetTourLength（inttourLength）{
157：this.tourLength=tourLength;
158：}
159：publicintgetCityNum（）{
160：returncityNum;
161：}
162：publicvoidsetCityNum（intcityNum）{
163：this.cityNum=cityNum;
164：}
165：
166：publicVector《Integer》getTabu（）{
167：returntabu;
168：}
169：
170：publicvoidsetTabu（Vector《Integer》tabu）{
171：this.tabu=tabu;
172：}
173：
174：publicfloat［］［］getDelta（）{
175：returndelta;
176：}
177：
178：publicvoidsetDelta（float［］［］delta）{
179：this.delta=delta;
180：}
181：
182：publicintgetFirstCity（）{
183：returnfirstCity;
184：}
185：
186：publicvoidsetFirstCity（intfirstCity）{
187：this.firstCity=firstCity;
188：}
189：
190：}
ACO类：
1：importjava.io.BufferedReader;
2：importjava.io.FileInputStream;
3：importjava.io.IOException;
4：importjava.io.InputStreamReader;
5：
6：/**
8：*@authorBIAOYU
9：*
10：*
11：*/
12：publicclassACO{
13：
14：privateAnt［］ants;//蚂蚁
15：privateintantNum;//蚂蚁数量
16：privateintcityNum;//城市数量
17：privateintMAX_GEN;//运行代数
18：privatefloat［］［］pheromone;//信息素矩阵
19：privateint［］［］distance;//距离矩阵
20：privateintbestLength;//最佳长度
21：privateint［］bestTour;//最佳路径
22：
23：//三个参数
24：privatefloatalpha;
25：privatefloatbeta;
26：privatefloatrho;
27：
29：publicACO（）{
31：}
32：/**constructorofACO
33：*@paramn城市数量
34：*@paramm蚂蚁数量
35：*@paramg运行代数
36：*@paramaalpha
37：*@parambbeta
38：*@paramrrho
39：*
40：**/
41：publicACO（intn，intm，intg，floata，floatb，floatr）{
42：cityNum=n;
43：antNum=m;
44：ants=newAnt［antNum］;
45：MAX_GEN=g;
46：alpha=a;
47：beta=b;
48：rho=r;
49：
50：}
51：
52：@SuppressWarnings（“resource”）
53：/**
54：*初始化ACO算法类
55：*@paramfilename数据文件名，该文件存储所有城市节点坐标数据
56：*@throwsIOException
57：*/
58：privatevoidinit（Stringfilename）throwsIOException{
59：//读取数据
60：int［］x;
61：int［］y;
62：Stringstrbuff;
63：BufferedReaderdata=newBufferedReader（newInputStreamReader（newFileInputStream（filename）））;
64：
65：distance=newint［cityNum］［cityNum］;
66：x=newint［cityNum］;
67：y=newint［cityNum］;
68：for（inti=0;i《cityNum;i++）{
69：strbuff=data.readLine（）;
70：String［］strcol=strbuff.split（“”）;
71：x［i］=Integer.valueOf（strcol［1］）;
72：y［i］=Integer.valueOf（strcol［2］）;
74：//计算距离矩阵，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
75：for（inti=0;i《cityNum-1;i++）{
76：distance［i］［i］=0;//对角线为0
77：for（intj=i+1;j《cityNum;j++）{
78：doublerij=Math.sqrt（（（x［i］-x［j］）*（x［i］-x［j］）+（y［i］-y［j］）*（y［i］-y［j］））/10.0）;
79：inttij=（int）Math.round（rij）;
80：if（tij《rij）{
81：distance［i］［j］=tij+1;
82：distance［j］［i］=distance［i］［j］;
83：}else{
84：distance［i］［j］=tij;
85：distance［j］［i］=distance［i］［j］;
86：}
87：}
88：}
89：distance［cityNum-1］［cityNum-1］=0;
91：//初始化信息素矩阵
92：pheromone=newfloat［cityNum］［cityNum］;
93：for（inti=0;i《cityNum;i++）
94：{
95：for（intj=0;j《cityNum;j++）{
96：pheromone［i］［j］=0.1f;//初始化为0.1
97：}
98：}
99：bestLength=Integer.MAX_VALUE;
100：bestTour=newint［cityNum+1］;
101：//随机放置蚂蚁
102：for（inti=0;i《antNum;i++）{
103：ants［i］=newAnt（cityNum）;
104：ants［i］.init（distance，alpha，beta）;
105：}
106：}
107：
108：publicvoidsolve（）{
109：
110：for（intg=0;g《MAX_GEN;g++）{
111：for（inti=0;i《antNum;i++）{
112：for（intj=1;j《cityNum;j++）{
113：ants［i］.selectNextCity（pheromone）;
115：ants［i］.getTabu（）.add（ants［i］.getFirstCity（））;
116：if（ants［i］.getTourLength（）《bestLength）{
117：bestLength=ants［i］.getTourLength（）;
118：for（intk=0;k《cityNum+1;k++）{
119：bestTour［k］=ants［i］.getTabu（）.get（k）.intValue（）;
120：}
122：for（intj=0;j《cityNum;j++）{
123：ants［i］.getDelta（）［ants［i］.getTabu（）.get（j）.intValue（）］［ants［i］.getTabu（）.get（j+1）.intValue（）］=（float）（1./ants［i］.getTourLength（））;
124：ants［i］.getDelta（）［ants［i］.getTabu（）.get（j+1）.intValue（）］［ants［i］.getTabu（）.get（j）.intValue（）］=（float）（1./ants［i］.getTourLength（））;
125：}
126：}
128：//更新信息素
129：updatePheromone（）;
130：
131：//重新初始化蚂蚁
132：for（inti=0;i《antNum;i++）{
133：
134：ants［i］.init（distance，alpha，beta）;
135：}
136：}
137：
138：//打印最佳结果
139：printOptimal（）;
142：//更新信息素
143：privatevoidupdatePheromone（）{
144：//信息素挥发
145：for（inti=0;i《cityNum;i++）
146：for（intj=0;j《cityNum;j++）
147：pheromone［i］［j］=pheromone［i］［j］*（1-rho）;
148：//信息素更新
149：for（inti=0;i《cityNum;i++）{
150：for（intj=0;j《cityNum;j++）{
151：for（intk=0;k《antNum;k++）{
152：pheromone［i］［j］+=ants［k］.getDelta（）［i］［j］;
153：}
154：}
156：}
157：
158：privatevoidprintOptimal（）{
159：System.out.println（“Theoptimallengthis：”+bestLength）;
160：System.out.println（“Theoptimaltouris：”）;
161：for（inti=0;i《cityNum+1;i++）{
162：System.out.println（bestTour［i］）;
163：}
166：publicAnt［］getAnts（）{
167：returnants;
170：publicvoidsetAnts（Ant［］ants）{
171：this.ants=ants;
174：publicintgetAntNum（）{
175：returnantNum;
178：publicvoidsetAntNum（intm）{
179：this.antNum=m;
182：publicintgetCityNum（）{
183：returncityNum;
186：publicvoidsetCityNum（intcityNum）{
187：this.cityNum=cityNum;
190：publicintgetMAX_GEN（）{
191：returnMAX_GEN;
192：}
193：
194：publicvoidsetMAX_GEN（intmAX_GEN）{
195：MAX_GEN=mAX_GEN;
196：}
197：
198：publicfloat［］［］getPheromone（）{
199：returnpheromone;
200：}
201：
202：publicvoidsetPheromone（float［］［］pheromone）{
203：this.pheromone=pheromone;
204：}
205：
206：publicint［］［］getDistance（）{
207：returndistance;
208：}
209：
210：publicvoidsetDistance（int［］［］distance）{
211：this.distance=distance;
212：}
213：
214：publicintgetBestLength（）{
215：returnbestLength;
216：}
217：
218：publicvoidsetBestLength（intbestLength）{
219：this.bestLength=bestLength;
220：}
221：
222：publicint［］getBestTour（）{
223：returnbestTour;
224：}
225：
226：publicvoidsetBestTour（int［］bestTour）{
227：this.bestTour=bestTour;
228：}
229：
230：publicfloatgetAlpha（）{
231：returnalpha;
232：}
233：
234：publicvoidsetAlpha（floatalpha）{
235：this.alpha=alpha;
236：}
237：
238：publicfloatgetBeta（）{
239：returnbeta;
240：}
241：
242：publicvoidsetBeta（floatbeta）{
243：this.beta=beta;
244：}
245：
246：publicfloatgetRho（）{
247：returnrho;
248：}
249：
250：publicvoidsetRho（floatrho）{
251：this.rho=rho;
252：}
253：
254：
255：/**
256：*@paramargs
257：*@throwsIOException
258：*/
259：publicstaticvoidmain（String［］args）throwsIOException{
260：ACOaco=newACO（48，100，1000，1.f，5.f，0.5f）;
261：aco.init（“c://data.txt”）;
262：aco.solve（）;
263：}
264：
265：}
266：
应用的进展
自从ACO在一些经典的组合规划问题如TSP和QAP等NP难的组合优化问题上取得成功以来，目前已陆续渗透到许多新的实际的工程领域中。
（1）在各种工程和工业生产中的应用。例如采用ACO的思想来求解大规模集成电路综合布线问题。在布线过程中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网agent根据启发策略，像蚁群一样在开关盒网格上爬行，所经之处便布上1条金属线，历经1个线网的所有引脚之后，线网便布通了。
（2）ACO在各种实际规划问题中的应用。例如在机器人路径规划中的应用［6］。机器人作为一种智能体，在复杂工作环境下的路径规划问题、多机器人之间的协作策略问题，在很大程度上类似于蚂蚁觅食优选路径以及蚂蚁群体中个体之间通过信息素形成协作。路径规划算法是实现机器人控制和导航的基础之一，试验证明ACO解决该问题有很大的优越性。
另外，ACO在动态优化组合问题中也有应用，具体是在有向连接的网络路由和无连接网络系统路由中的应用。其他应用还包括蚂蚁人工神经网络、车辆路线问题（VehicleRoutineProb-lem，VRP）、在图像处理和模式识别领域的应用等等。
存在的问题
蚁群算法的研究成果令人瞩目，但作为一种较新的理论，它依然存在一些问题。
（2）算法容易在某个或某些局部最优解的邻域附近发生停滞现象，造成早熟收敛，即搜索进行到一定程度后，所有蚂蚁发现的解完全一致，不能继续对解空间进一步搜索，不利于发现全局最优解。
（3）不能较好的解决连续域问题。
（5）信息素更新策略，路径搜索策略和最优解保留策略都带有经验性，没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。
发展趋势
随着蚁群算法在工程实践中应用的深入和系统复杂性的增加，需要处理的数据量也越来越大，这些问题的影响日益突出，使得单纯一到两种智能方法往往不能很好的解决问题。由于蚁群算法易与其他进化算法或者局部搜索算法结合。所以如何根据实际情况融合多种智能方法必将成为今后蚁群算法新的研究热点。目前，蚁群算法的研究大多集中在算法、模型的更新，以及软件的开发上，所处理的数据也都是静态的。硬件的运行速度要高于软件，如何利用硬件的优势，利用DSP，FPGA和PLC等硬件实现蚁群算法，并使它能够应用于实时系统将是以后研究的一个方向。