蟻群算法概況
蟻群算法又稱螞蟻算法,是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出,其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法,初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題,將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較,數(shù)值仿真結(jié)果表明,蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。
各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物以后,它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失,信息素濃度的大小表征路徑的遠(yuǎn)近)來實(shí)現(xiàn)的,吸引其他的螞蟻過來,這樣越來越多的螞蟻會(huì)找到食物。有些螞蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路,他們會(huì)另辟蹊徑,如果另開辟的道路比原來的其他道路更短,那么,漸漸地,更多的螞蟻被吸引到這條較短的路上來。最后,經(jīng)過一段時(shí)間運(yùn)行,可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。
蟻群算法是一種仿生學(xué)算法,是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中,螞蟻覓食過程中,蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。圖(1)顯示了這樣一個(gè)覓食的過程。
在圖1(a)中,有一群螞蟻,假如A是蟻巢,E是食物源(反之亦然)。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現(xiàn)了一個(gè)障礙物(圖1(b)),那么,在B點(diǎn)(或D點(diǎn))的螞蟻將要做出決策,到底是向左行駛還是向右行駛?由于一開始路上沒有前面螞蟻留下的信息素(pheromone),螞蟻朝著兩個(gè)方向行進(jìn)的概率是相等的。但是當(dāng)有螞蟻?zhàn)哌^時(shí),它將會(huì)在它行進(jìn)的路上釋放出信息素,并且這種信息素會(huì)議一定的速率散發(fā)掉。信息素是螞蟻之間交流的工具之一。它后面的螞蟻通過路上信息素的濃度,做出決策,往左還是往右。很明顯,沿著短邊的的路徑上信息素將會(huì)越來越濃(圖1(c)),從而吸引了越來越多的螞蟻沿著這條路徑行駛。
?
蟻群算法原理
假如蟻群中所有螞蟻的數(shù)量為m,所有城市之間的信息素用矩陣pheromone表示,最短路徑為bestLength,最佳路徑為bestTour。每只螞蟻都有自己的內(nèi)存,內(nèi)存中用一個(gè)禁忌表(Tabu)來存儲(chǔ)該螞蟻已經(jīng)訪問過的城市,表示其在以后的搜索中將不能訪問這些城市;還有用另外一個(gè)允許訪問的城市表(Allowed)來存儲(chǔ)它還可以訪問的城市;另外還用一個(gè)矩陣(Delta)來存儲(chǔ)它在一個(gè)循環(huán)(或者迭代)中給所經(jīng)過的路徑釋放的信息素;還有另外一些數(shù)據(jù),例如一些控制參數(shù)(α,β,ρ,Q)(α,β,ρ,Q),該螞蟻行走玩全程的總成本或距離(tourLength),等等。假定算法總共運(yùn)行MAX_GEN次,運(yùn)行時(shí)間為t。
?
蟻群算法計(jì)算過程如下:
(1)初始化
設(shè)t=0,初始化bestLength為一個(gè)非常大的數(shù)(正無窮),bestTour為空。初始化所有的螞蟻的Delt矩陣所有元素初始化為0,Tabu表清空,Allowed表中加入所有的城市節(jié)點(diǎn)。隨機(jī)選擇它們的起始位置(也可以人工指定)。在Tabu中加入起始節(jié)點(diǎn),Allowed中去掉該起始節(jié)點(diǎn)。
(2)為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)。
為每只螞蟻選擇下一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)只能從Allowed中以某種概率(公式1)搜索到,每搜到一個(gè),就將該節(jié)點(diǎn)加入到Tabu中,并且從Allowed中刪除該節(jié)點(diǎn)。該過程重復(fù)n-1次,直到所有的城市都遍歷過一次。遍歷完所有節(jié)點(diǎn)后,將起始節(jié)點(diǎn)加入到Tabu中。此時(shí)Tabu表元素?cái)?shù)量為n+1(n為城市數(shù)量),Allowed元素?cái)?shù)量為0。接下來按照(公式2)計(jì)算每個(gè)螞蟻的Delta矩陣值。最后計(jì)算最佳路徑,比較每個(gè)螞蟻的路徑成本,然后和bestLength比較,若它的路徑成本比bestLength小,則將該值賦予bestLength,并且將其Tabu賦予BestTour。
?
(3)更新信息素矩陣
(4)檢查終止條件
(5)輸出最優(yōu)值
Java實(shí)現(xiàn)
在該java實(shí)現(xiàn)中我們選擇使用tsplib上的數(shù)據(jù)att48,這是一個(gè)對(duì)稱tsp問題,城市規(guī)模為48,其最優(yōu)值為10628.其距離計(jì)算方法如圖(2)所示:
?
att48距離計(jì)算方法
實(shí)現(xiàn)中,使用了兩個(gè)java類,一個(gè)Ant類,一個(gè)ACO類。
具體實(shí)現(xiàn)代碼如下(此代碼借鑒了蟻群優(yōu)化算法的JAVA實(shí)現(xiàn)):
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; //信息數(shù)變化矩陣
14: private int[][] distance; //距離矩陣
15:
16: private float alpha;
17: private float beta;
18:
19: private int tourLength; //路徑長(zhǎng)度
20: private int cityNum; //城市數(shù)量
21:
22: private int firstCity; //起始城市
23: private int currentCity; //當(dāng)前城市
24:
25: public Ant(){
26: cityNum = 30;
27: tourLength = 0;
28:
29: }
30:
31: /**
32: * Constructor of Ant
33: * @param num 螞蟻數(shù)量
34: */
35: public Ant(int num){
36: cityNum = num;
37: tourLength = 0;
38:
39: }
40:
41: /**
42: * 初始化螞蟻,隨機(jī)選擇起始位置
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: * 選擇下一個(gè)城市
77: * @param pheromone 信息素矩陣
78: */
79: public void selectNextCity(float[][] pheromone){
80: float[] p = new float[cityNum];
81: float sum = 0.0f;
82: //計(jì)算分母部分
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: //計(jì)算概率矩陣
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: //輪盤賭選擇下一個(gè)城市
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: //將當(dāng)前城市改為選擇的城市
126: currentCity = selectCity;
127:
128: }
129:
130: /**
131: * 計(jì)算路徑長(zhǎng)度
132: * @return 路徑長(zhǎng)度
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; //螞蟻數(shù)量
16: private int cityNum; //城市數(shù)量
17: private int MAX_GEN; //運(yùn)行代數(shù)
18: private float[][] pheromone; //信息素矩陣
19: private int[][] distance; //距離矩陣
20: private int bestLength; //最佳長(zhǎng)度
21: private int[] bestTour; //最佳路徑
22:
23: //三個(gè)參數(shù)
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 城市數(shù)量
34: * @param m 螞蟻數(shù)量
35: * @param g 運(yùn)行代數(shù)
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 數(shù)據(jù)文件名,該文件存儲(chǔ)所有城市節(jié)點(diǎn)坐標(biāo)數(shù)據(jù)
56: * @throws IOException
57: */
58: private void init(String filename) throws IOException{
59: //讀取數(shù)據(jù)
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: //計(jì)算距離矩陣 ,針對(duì)具體問題,距離計(jì)算方法也不一樣,此處用的是att48作為案例,它有48個(gè)城市,距離計(jì)算方法為偽歐氏距離,最優(yōu)值為10628
75: for (int i = 0; i 《 cityNum - 1; i++) {
76: distance[i][i] = 0; //對(duì)角線為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: //隨機(jī)放置螞蟻
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: //打印最佳結(jié)果
139: printOptimal();
140: }
141:
142: //更新信息素
143: private void updatePheromone(){
144: //信息素?fù)]發(fā)
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應(yīng)用進(jìn)展及發(fā)展趨勢(shì)
應(yīng)用的進(jìn)展
自從ACO在一些經(jīng)典的組合規(guī)劃問題如TSP和QAP等NP難的組合優(yōu)化問題上取得成功以來,目前已陸續(xù)滲透到許多新的實(shí)際的工程領(lǐng)域中。
(1)在各種工程和工業(yè)生產(chǎn)中的應(yīng)用。例如采用ACO的思想來求解大規(guī)模集成電路綜合布線問題。在布線過程中,各個(gè)引腳對(duì)螞蟻的引力可根據(jù)引力函數(shù)來計(jì)算。各個(gè)線網(wǎng)agent根據(jù)啟發(fā)策略,像蟻群一樣在開關(guān)盒網(wǎng)格上爬行,所經(jīng)之處便布上1條金屬線,歷經(jīng)1個(gè)線網(wǎng)的所有引腳之后,線網(wǎng)便布通了。
(2) ACO在各種實(shí)際規(guī)劃問題中的應(yīng)用。例如在機(jī)器人路徑規(guī)劃中的應(yīng)用[6]。機(jī)器人作為一種智能體,在復(fù)雜工作環(huán)境下的路徑規(guī)劃問題、多機(jī)器人之間的協(xié)作策略問題,在很大程度上類似于螞蟻覓食優(yōu)選路徑以及螞蟻群體中個(gè)體之間通過信息素形成協(xié)作。路徑規(guī)劃算法是實(shí)現(xiàn)機(jī)器人控制和導(dǎo)航的基礎(chǔ)之一,試驗(yàn)證明ACO解決該問題有很大的優(yōu)越性。
另外,ACO在動(dòng)態(tài)優(yōu)化組合問題中也有應(yīng)用,具體是在有向連接的網(wǎng)絡(luò)路由和無連接網(wǎng)絡(luò)系統(tǒng)路由中的應(yīng)用。其他應(yīng)用還包括螞蟻人工神經(jīng)網(wǎng)絡(luò)、車輛路線問題(Vehicle Routine Prob-lem,VRP)、在圖像處理和模式識(shí)別領(lǐng)域的應(yīng)用等等。
存在的問題
蟻群算法的研究成果令人矚目,但作為一種較新的理論,它依然存在一些問題。
(1)對(duì)于大規(guī)模組合優(yōu)化問題,算法的計(jì)算時(shí)間而且復(fù)雜。由于蟻群算法的時(shí)間復(fù)雜度是,因此在處理較大規(guī)模的組合優(yōu)化問題時(shí),運(yùn)算量較大,時(shí)間較長(zhǎng)。
(2)算法容易在某個(gè)或某些局部最優(yōu)解的鄰域附近發(fā)生停滯現(xiàn)象,造成早熟收斂,即搜索進(jìn)行到一定程度后,所有螞蟻發(fā)現(xiàn)的解完全一致,不能繼續(xù)對(duì)解空間進(jìn)一步搜索,不利于發(fā)現(xiàn)全局最優(yōu)解。
(3)不能較好的解決連續(xù)域問題。
(4)由于蟻群算法中螞蟻個(gè)體的運(yùn)動(dòng)過程的隨機(jī)性,當(dāng)群體規(guī)模設(shè)置較大時(shí),很難在較短時(shí)間內(nèi)從雜亂無章的路徑中找出一條較好的路徑。
(5)信息素更新策略,路徑搜索策略和最優(yōu)解保留策略都帶有經(jīng)驗(yàn)性,沒有經(jīng)過嚴(yán)格的理論論證。因此基本蟻群算法的求解效率不高、收斂性較差、求解結(jié)果具有較大的分散性。
發(fā)展趨勢(shì)
隨著蟻群算法在工程實(shí)踐中應(yīng)用的深入和系統(tǒng)復(fù)雜性的增加,需要處理的數(shù)據(jù)量也越來越大,這些問題的影響日益突出,使得單純一到兩種智能方法往往不能很好的解決問題。由于蟻群算法易與其他進(jìn)化算法或者局部搜索算法結(jié)合。所以如何根據(jù)實(shí)際情況融合多種智能方法必將成為今后蟻群算法新的研究熱點(diǎn)。目前,蟻群算法的研究大多集中在算法、模型的更新,以及軟件的開發(fā)上,所處理的數(shù)據(jù)也都是靜態(tài)的。硬件的運(yùn)行速度要高于軟件,如何利用硬件的優(yōu)勢(shì),利用DSP,FPGA和PLC等硬件實(shí)現(xiàn)蟻群算法,并使它能夠應(yīng)用于實(shí)時(shí)系統(tǒng)將是以后研究的一個(gè)方向。
評(píng)論
查看更多