電子發燒友App
蟻群算法計算過程如下：
（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類：
1： import java.util.Random;
2： import java.util.Vector;
3：
4： /**
5： *
6： * @author BIAO YU
7： *
8： */
9： public class Ant implements Cloneable {
10：
11： private Vector《Integer》 tabu; //禁忌表
12： private Vector《Integer》 allowedCities; //允許搜索的城市
13： private float［］［］ delta; //信息數變化矩陣
14： private int［］［］ distance; //距離矩陣
15：
16： private float alpha;
17： private float beta;
18：
19： private int tourLength; //路徑長度
20： private int cityNum; //城市數量
21：
22： private int firstCity; //起始城市
23： private int currentCity; //當前城市
24：
25： public Ant（）{
26： cityNum = 30;
27： tourLength = 0;
28：
29： }
30：
31： /**
32： * Constructor of Ant
33： * @param num 螞蟻數量
34： */
35： public Ant（int num）{
36： cityNum = num;
37： tourLength = 0;
38：
39： }
40：
41： /**
42： * 初始化螞蟻，隨機選擇起始位置
43： * @param distance 距離矩陣
44： * @param a alpha
45： * @param b beta
46： */
47： public void init（int［］［］ distance， float a， float b）{
48： alpha = a;
49： beta = b;
50： allowedCities = new Vector《Integer》（）;
51： tabu = new Vector《Integer》（）;
52： this.distance = distance;
53： delta = new float［cityNum］［cityNum］;
54： for （int i = 0; i 《 cityNum; i++） {
55： Integer integer = new Integer（i）;
56： allowedCities.add（integer）;
57： for （int j = 0; j 《 cityNum; j++） {
58： delta［i］［j］ = 0.f;
59： }
60： }
61：
62： Random random = new Random（System.currentTimeMillis（））;
63： firstCity = random.nextInt（cityNum）;
64： for （Integer i: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： * @param pheromone 信息素矩陣
78： */
79： public void selectNextCity（float［］［］ pheromone）{
80： float［］ p = new float［cityNum］;
81： float sum = 0.0f;
82： //計算分母部分
83： for （Integer i:allowedCities） {
84： sum += Math.pow（pheromone［currentCity］［i.intValue（）］， alpha）*Math.pow（1.0/distance［currentCity］［i.intValue（）］， beta）;
85： }
86： //計算概率矩陣
87： for （int i = 0; i 《 cityNum; i++） {
88： boolean flag = false;
89： for （Integer j: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： Random random = new Random（System.currentTimeMillis（））;
105： float sleectP = random.nextFloat（）;
106： int selectCity = 0;
107： float sum1 = 0.f;
108： for （int i = 0; i 《 cityNum; i++） {
109： sum1 += p［i］;
110： if （sum1 》= sleectP） {
111： selectCity = i;
112： break;
113： }
114： }
115：
116： //從允許選擇的城市中去除select city
117： for （Integer i:allowedCities） {
118： if （i.intValue（） == selectCity） {
119： allowedCities.remove（i）;
120： break;
121： }
122： }
123： //在禁忌表中添加select city
124： tabu.add（Integer.valueOf（selectCity））;
125： //將當前城市改為選擇的城市
126： currentCity = selectCity;
127：
128： }
129：
130： /**
131： * 計算路徑長度
132： * @return 路徑長度
133： */
134： private int calculateTourLength（）{
135： int len = 0;
136： for （int i = 0; i 《 cityNum; i++） {
137： len += distance［this.tabu.get（i）.intValue（）］［this.tabu.get（i+1）.intValue（）］;
138： }
139： return len;
140： }
141：
142：
143：
144： public Vector《Integer》 getAllowedCities（） {
145： return allowedCities;
146： }
147：
148： public void setAllowedCities（Vector《Integer》 allowedCities） {
149： this.allowedCities = allowedCities;
150： }
151：
152： public int getTourLength（） {
153： tourLength = calculateTourLength（）;
154： return tourLength;
155： }
156： public void setTourLength（int tourLength） {
157： this.tourLength = tourLength;
158： }
159： public int getCityNum（） {
160： return cityNum;
161： }
162： public void setCityNum（int cityNum） {
163： this.cityNum = cityNum;
164： }
165：
166： public Vector《Integer》 getTabu（） {
167： return tabu;
168： }
169：
170： public void setTabu（Vector《Integer》 tabu） {
171： this.tabu = tabu;
172： }
173：
174： public float［］［］ getDelta（） {
175： return delta;
176： }
177：
178： public void setDelta（float［］［］ delta） {
179： this.delta = delta;
180： }
181：
182： public int getFirstCity（） {
183： return firstCity;
184： }
185：
186： public void setFirstCity（int firstCity） {
187： this.firstCity = firstCity;
188： }
189：
190： }
?
?
ACO類：
1： import java.io.BufferedReader;
2： import java.io.FileInputStream;
3： import java.io.IOException;
4： import java.io.InputStreamReader;
5：
6： /**
7： *
8： * @author BIAO YU
9： *
10： *
11： */
12： public class ACO {
13：
14： private Ant［］ ants; //螞蟻
15： private int antNum; //螞蟻數量
16： private int cityNum; //城市數量
17： private int MAX_GEN; //運行代數
18： private float［］［］ pheromone; //信息素矩陣
19： private int［］［］ distance; //距離矩陣
20： private int bestLength; //最佳長度
21： private int［］ bestTour; //最佳路徑
22：
23： //三個參數
24： private float alpha;
25： private float beta;
26： private float rho;
27：
28：
29： public ACO（）{
30：
31： }
32： /** constructor of ACO
33： * @param n 城市數量
34： * @param m 螞蟻數量
35： * @param g 運行代數
36： * @param a alpha
37： * @param b beta
38： * @param r rho
39： *
40： **/
41： public ACO（int n， int m， int g， float a， float b， float r） {
42： cityNum = n;
43： antNum = m;
44： ants = new Ant［antNum］;
45： MAX_GEN = g;
46： alpha = a;
47： beta = b;
48： rho = r;
49：
50： }
51：
52： @SuppressWarnings（“resource”）
53： /**
54： * 初始化ACO算法類
55： * @param filename 數據文件名，該文件存儲所有城市節點坐標數據
56： * @throws IOException
57： */
58： private void init（String filename） throws IOException{
59： //讀取數據
60： int［］ x;
61： int［］ y;
62： String strbuff;
63： BufferedReader data = new BufferedReader（new InputStreamReader（new FileInputStream（filename）））;
64：
65： distance = new int［cityNum］［cityNum］;
66： x = new int［cityNum］;
67： y = new int［cityNum］;
68： for （int i = 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］）;
73： }
74： //計算距離矩陣 ，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優值為10628
75： for （int i = 0; i 《 cityNum - 1; i++） {
76： distance［i］［i］ = 0; //對角線為0
77： for （int j = i + 1; j 《 cityNum; j++） {
78： double rij = Math.sqrt（（（x［i］ - x［j］） * （x［i］ - x［j］）+ （y［i］ - y［j］） * （y［i］ - y［j］））/10.0）;
79： int tij = （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;
90：
91： //初始化信息素矩陣
92： pheromone=new float［cityNum］［cityNum］;
93： for（int i=0;i《cityNum;i++）
94： {
95： for（int j=0;j《cityNum;j++）{
96： pheromone［i］［j］=0.1f; //初始化為0.1
97： }
98： }
99： bestLength=Integer.MAX_VALUE;
100： bestTour=new int［cityNum+1］;
101： //隨機放置螞蟻
102： for（int i=0;i《antNum;i++）{
103： ants［i］=new Ant（cityNum）;
104： ants［i］.init（distance， alpha， beta）;
105： }
106： }
107：
108： public void solve（）{
109：
110： for （int g = 0; g 《 MAX_GEN; g++） {
111： for （int i = 0; i 《 antNum; i++） {
112： for （int j = 1; j 《 cityNum; j++） {
113： ants［i］.selectNextCity（pheromone）;
114： }
115： ants［i］.getTabu（）.add（ants［i］.getFirstCity（））;
116： if （ants［i］.getTourLength（） 《 bestLength） {
117： bestLength = ants［i］.getTourLength（）;
118： for （int k = 0; k 《 cityNum + 1; k++） {
119： bestTour［k］ = ants［i］.getTabu（）.get（k）.intValue（）;
120： }
121： }
122： for （int j = 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： }
127：
128： //更新信息素
129： updatePheromone（）;
130：
131： //重新初始化螞蟻
132： for（int i=0;i《antNum;i++）{
133：
134： ants［i］.init（distance， alpha， beta）;
135： }
136： }
137：
138： //打印最佳結果
139： printOptimal（）;
140： }
141：
142： //更新信息素
143： private void updatePheromone（）{
144： //信息素揮發
145： for（int i=0;i《cityNum;i++）
146： for（int j=0;j《cityNum;j++）
147： pheromone［i］［j］=pheromone［i］［j］*（1-rho）;
148： //信息素更新
149： for（int i=0;i《cityNum;i++）{
150： for（int j=0;j《cityNum;j++）{
151： for （int k = 0; k 《 antNum; k++） {
152： pheromone［i］［j］ += ants［k］.getDelta（）［i］［j］;
153： }
154： }
155： }
156： }
157：
158： private void printOptimal（）{
159： System.out.println（“The optimal length is： ” + bestLength）;
160： System.out.println（“The optimal tour is： ”）;
161： for （int i = 0; i 《 cityNum + 1; i++） {
162： System.out.println（bestTour［i］）;
163： }
164： }
165：
166： public Ant［］ getAnts（） {
167： return ants;
168： }
169：
170： public void setAnts（Ant［］ ants） {
171： this.ants = ants;
172： }
173：
174： public int getAntNum（） {
175： return antNum;
176： }
177：
178： public void setAntNum（int m） {
179： this.antNum = m;
180： }
181：
182： public int getCityNum（） {
183： return cityNum;
184： }
185：
186： public void setCityNum（int cityNum） {
187： this.cityNum = cityNum;
188： }
189：
190： public int getMAX_GEN（） {
191： return MAX_GEN;
192： }
193：
194： public void setMAX_GEN（int mAX_GEN） {
195： MAX_GEN = mAX_GEN;
196： }
197：
198： public float［］［］ getPheromone（） {
199： return pheromone;
200： }
201：
202： public void setPheromone（float［］［］ pheromone） {
203： this.pheromone = pheromone;
204： }
205：
206： public int［］［］ getDistance（） {
207： return distance;
208： }
209：
210： public void setDistance（int［］［］ distance） {
211： this.distance = distance;
212： }
213：
214： public int getBestLength（） {
215： return bestLength;
216： }
217：
218： public void setBestLength（int bestLength） {
219： this.bestLength = bestLength;
220： }
221：
222： public int［］ getBestTour（） {
223： return bestTour;
224： }
225：
226： public void setBestTour（int［］ bestTour） {
227： this.bestTour = bestTour;
228： }
229：
230： public float getAlpha（） {
231： return alpha;
232： }
233：
234： public void setAlpha（float alpha） {
235： this.alpha = alpha;
236： }
237：
238： public float getBeta（） {
239： return beta;
240： }
241：
242： public void setBeta（float beta） {
243： this.beta = beta;
244： }
245：
246： public float getRho（） {
247： return rho;
248： }
249：
250： public void setRho（float rho） {
251： this.rho = rho;
252： }
253：
254：
255： /**
256： * @param args
257： * @throws IOException
258： */
259： public static void main（String［］ args） throws IOException {
260： ACO aco = new ACO（48， 100， 1000， 1.f， 5.f， 0.5f）;
261： aco.init（“c://data.txt”）;
262： aco.solve（）;
263： }
264：
265： }
266：
ACO應用進展及發展趨勢
應用的進展
自從ACO在一些經典的組合規劃問題如TSP和QAP等NP難的組合優化問題上取得成功以來，目前已陸續滲透到許多新的實際的工程領域中。
（1）在各種工程和工業生產中的應用。例如采用ACO的思想來求解大規模集成電路綜合布線問題。在布線過程中，各個引腳對螞蟻的引力可根據引力函數來計算。各個線網agent根據啟發策略，像蟻群一樣在開關盒網格上爬行，所經之處便布上1條金屬線，歷經1個線網的所有引腳之后，線網便布通了。
（2） ACO在各種實際規劃問題中的應用。例如在機器人路徑規劃中的應用［6］。機器人作為一種智能體，在復雜工作環境下的路徑規劃問題、多機器人之間的協作策略問題，在很大程度上類似于螞蟻覓食優選路徑以及螞蟻群體中個體之間通過信息素形成協作。路徑規劃算法是實現機器人控制和導航的基礎之一，試驗證明ACO解決該問題有很大的優越性。
另外，ACO在動態優化組合問題中也有應用，具體是在有向連接的網絡路由和無連接網絡系統路由中的應用。其他應用還包括螞蟻人工神經網絡、車輛路線問題（Vehicle Routine Prob-lem，VRP）、在圖像處理和模式識別領域的應用等等。
存在的問題
蟻群算法的研究成果令人矚目，但作為一種較新的理論，它依然存在一些問題。
（1）對于大規模組合優化問題，算法的計算時間而且復雜。由于蟻群算法的時間復雜度是，因此在處理較大規模的組合優化問題時，運算量較大，時間較長。
（2）算法容易在某個或某些局部最優解的鄰域附近發生停滯現象，造成早熟收斂，即搜索進行到一定程度后，所有螞蟻發現的解完全一致，不能繼續對解空間進一步搜索，不利于發現全局最優解。
（3）不能較好的解決連續域問題。
（4）由于蟻群算法中螞蟻個體的運動過程的隨機性，當群體規模設置較大時，很難在較短時間內從雜亂無章的路徑中找出一條較好的路徑。
（5）信息素更新策略，路徑搜索策略和最優解保留策略都帶有經驗性，沒有經過嚴格的理論論證。因此基本蟻群算法的求解效率不高、收斂性較差、求解結果具有較大的分散性。
發展趨勢
隨著蟻群算法在工程實踐中應用的深入和系統復雜性的增加，需要處理的數據量也越來越大，這些問題的影響日益突出，使得單純一到兩種智能方法往往不能很好的解決問題。由于蟻群算法易與其他進化算法或者局部搜索算法結合。所以如何根據實際情況融合多種智能方法必將成為今后蟻群算法新的研究熱點。目前，蟻群算法的研究大多集中在算法、模型的更新，以及軟件的開發上，所處理的數據也都是靜態的。硬件的運行速度要高于軟件，如何利用硬件的優勢，利用DSP，FPGA和PLC等硬件實現蟻群算法，并使它能夠應用于實時系統將是以后研究的一個方向。
工商網監
評論