蚁群算法
參考內(nèi)容來自：
1.http://blog.csdn.net/zhushuai1221/article/details/51076156
2. https://www.cnblogs.com/biaoyu/archive/2012/09/26/2704456.html
3. http://blog.csdn.net/fashionxu/article/details/5484864
1.蟻群算法簡介
蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無智能或有輕微智能的個(gè)體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問題提供了一個(gè)新的可能性。蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法。它由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à)值。
蟻群算法是一種仿生學(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）），從而吸引了越來越多的螞蟻沿著這條路徑行駛。
2.TSP問題描述
蟻群算法最早用來求解TSP問題，并且表現(xiàn)出了很大的優(yōu)越性，因?yàn)樗植际教匦?#xff0c;魯棒性強(qiáng)并且容易與其它算法結(jié)合，但是同時(shí)也存在這收斂速度慢，容易陷入局部最優(yōu)（local optimal）等缺點(diǎn)。
TSP問題（Travel Salesperson Problem，即旅行商問題或者稱為中國郵遞員問題），是一種NP-hard問題，此類問題用一般的算法是很大得到最優(yōu)解的，所以一般需要借助一些啟發(fā)式算法求解，例如遺傳算法（GA），蟻群算法（ACO），微粒群算法（PSO）等等。
TSP問題可以分為兩類，一類是對(duì)稱TSP問題（Symmetric TSP），另一類是非對(duì)稱問題（Asymmetric TSP）。所有的TSP問題都可以用一個(gè)圖（Graph）來描述：
令V={C1,C2,…,Ci,…,Cn},i=1,2,…,n是所有城市的集合，Ci表示第i個(gè)城市，n為城市的數(shù)目；
E={(r,s):r,s∈V}是所有城市之間連接的集合；
C={Crs:r,s∈V}是所有城市之間連接的成本度量（一般為城市之間的距離）；
如果Crs=Csr，那么該TSP問題為對(duì)稱的，否則為非對(duì)稱的。
一個(gè)TSP問題可以表達(dá)為：
求解遍歷圖G=(V,E,C)，所有的節(jié)點(diǎn)一次并且回到起始節(jié)點(diǎn)，使得連接這些節(jié)點(diǎn)的路徑成本最低。
3.蟻群算法原理
假如蟻群中所有螞蟻的數(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)，該螞蟻行走完全程的總成本或距離（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。
（公式1）
（公式2）
（公式3）
其中pij(t)表示選擇城市j的概率，k表示第k個(gè)螞蟻，τij (t)表示城市i,j在第t時(shí)刻的信息素濃度，ηij表示從城市i到城市j的可見度，ηij=1/dij，dij表示城市i,j之間的成本（或距離）。由此可見dij越小，ηij越大，也就是從城市i到j(luò)的可見性就越大。
Δτkij表示螞蟻k在城市i與j之間留下的信息素。
Lk表示螞蟻k經(jīng)過一個(gè)循環(huán)（或迭代）鎖經(jīng)過路徑的總成本（或距離），即tourLength,α,β,Q 均為控制參數(shù)。
（3）更新信息素矩陣
令t=t+nt，按照（公式3）更新信息素矩陣phermone。
（公式4）
τij(t+n)為t+n時(shí)刻城市i與j之間的信息素濃度。ρ為控制參數(shù)，Deltaij為城市i與j之間信息素經(jīng)過一個(gè)迭代后的增量。并且有
（公式5）
其中Δτkij由公式計(jì)算得到。
（4）檢查終止條件
如果達(dá)到最大代數(shù)MAX_GEN，算法終止，轉(zhuǎn)到第（5）步；否則，重新初始化所有的螞蟻的Delt矩陣所有元素初始化為0，Tabu表清空，Allowed表中加入所有的城市節(jié)點(diǎn)。隨機(jī)選擇它們的起始位置（也可以人工指定）。在Tabu中加入起始節(jié)點(diǎn)，Allowed中去掉該起始節(jié)點(diǎn)，重復(fù)執(zhí)行（2），（3）,(4)步。
（5）輸出最優(yōu)值
4.算法流程圖
5.java實(shí)現(xiàn)
在該java實(shí)現(xiàn)中我們選擇使用tsplib上的數(shù)據(jù)att48，這是一個(gè)對(duì)稱tsp問題，城市規(guī)模為48，其最優(yōu)值為10628.其距離計(jì)算方法如圖（2）所示：
圖2 att48距離計(jì)算方法
實(shí)現(xiàn)中，使用了兩個(gè)java類，一個(gè)Ant類，一個(gè)ACO類。
Ant類
ACO類
package com.gbs.bean;import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;/*** 蟻群算法類* @author gbs**/ public class ACO {private Ant[] ants; //螞蟻private int antNum; //螞蟻數(shù)量private int cityNum; //城市數(shù)量private int MAX_GEN; //運(yùn)行代數(shù)private double[][] pheromone; //信息素矩陣private int[][] distance; //距離矩陣private int bestLength; //最佳長度private int[] bestTour; //最佳路徑//三個(gè)參數(shù)private double alpha;private double beta;private double rho;public ACO() {}public ACO(int antNum, int cityNum, int mAX_GEN, double alpha, double beta, double rho) {this.antNum = antNum;this.cityNum = cityNum;this.MAX_GEN = mAX_GEN;this.alpha = alpha;this.beta = beta;this.rho = rho;this.ants = new Ant[this.antNum];}public void init(String path) {int []x;int []y;String buffer;BufferedReader br;try {br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));this.distance = new int[this.cityNum][this.cityNum];x = new int[cityNum]; y = new int[cityNum]; //讀取城市的坐標(biāo)for (int i = 0; i < cityNum; i++) { buffer = br.readLine();String[] str = buffer.split(" +"); x[i] = Integer.valueOf(str[1]); y[i] = Integer.valueOf(str[2]); } /*** 計(jì)算距離矩陣 ，針對(duì)具體問題，距離計(jì)算方法也不一樣，此處用的是att48作為案例，* 它有48個(gè)城市，距離計(jì)算方法為偽歐氏距離，最優(yōu)值為10628*/for(int i = 0;i < this.cityNum - 1;i++) {for(int j = i + 1;j < this.cityNum;j++) {double rij = Math.sqrt(((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))/10.0);int tij = (int)Math.round(rij);if(tij < rij)tij++;this.distance[i][j] = tij;this.distance[j][i] = tij;}}this.distance[this.cityNum-1][this.cityNum-1] = 0;//初始化信息素矩陣this.pheromone=new double[this.cityNum][this.cityNum];for(int i = 0;i < this.cityNum;i++) {for(int j = 0;j < this.cityNum;j++) {this.pheromone[i][j] = 0.1d;}}//初始化最優(yōu)路徑的長度this.bestLength=Integer.MAX_VALUE;//初始化最優(yōu)路徑this.bestTour=new int[this.cityNum+1]; //隨機(jī)放置螞蟻 for(int i = 0;i < this.antNum;i++){ this.ants[i]=new Ant(this.cityNum); this.ants[i].init(this.distance, this.alpha, this.beta); } } catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}}/*** 更新信息素*/private void updatePheromone() {//信息素?fù)]發(fā) for(int i = 0;i < this.cityNum;i++) for(int j = 0;j < this.cityNum;j++) this.pheromone[i][j] = this.pheromone[i][j] * (1 - this.rho);//信息素更新for(int i = 0;i < this.cityNum;i++) {for(int j = 0;j < this.cityNum;j++) {for(int k = 0;k < this.antNum;k++) {this.pheromone[i][j] += this.ants[k].getDelta()[i][j];}}}}public void solve() {for (int g = 0; g < this.MAX_GEN; g++) {//每一只螞蟻移動(dòng)的過程for (int i = 0; i < this.antNum; i++) {for (int j = 0; j < this.cityNum; j++) {this.ants[i].selectNextCity(this.pheromone);}this.ants[i].getTabu().add(this.ants[i].getFirstCity()); // if(this.ants[i].getTabu().size() < 49) { // System.out.println(this.ants[i].toString()); // }//計(jì)算螞蟻獲得的路徑長度 this.ants[i].setTourLength(this.ants[i].calculateTourLength()); if(this.ants[i].getTourLength() < this.bestLength){ //保留最優(yōu)路徑 this.bestLength = this.ants[i].getTourLength(); System.out.println("第"+g+"代，發(fā)現(xiàn)新的解"+this.bestLength); // System.out.println("size:"+this.ants[i].getTabu().size());for(int k = 0;k < this.ants[i].getTabu().size();k++) this.bestTour[k] = this.ants[i].getTabu().get(k).intValue();; }//更新信息素變化矩陣for (int j = 0; j < this.ants[i].getTabu().size()-1; j++) {this.ants[i].getDelta()[this.ants[i].getTabu().get(j).intValue()][this.ants[i].getTabu().get(j+1).intValue()] = (double) (1.0/this.ants[i].getTourLength());this.ants[i].getDelta()[this.ants[i].getTabu().get(j+1).intValue()][this.ants[i].getTabu().get(j).intValue()] = (double) (1.0/this.ants[i].getTourLength());}}//更新信息素this.updatePheromone();//重新初始化螞蟻for(int i = 0;i < this.antNum;i++){ this.ants[i].init(this.distance, this.alpha, this.beta);}}//打印最佳結(jié)果this.printOptimal();}public void printOptimal() {System.out.println("The optimal length is: " + this.bestLength);System.out.println("The optimal tour is: ");for (int i = 0; i < this.bestTour.length; i++) {System.out.println(this.bestTour[i]);}}public Ant[] getAnts() {return ants;}public void setAnts(Ant[] ants) {this.ants = ants;}public int getAntNum() {return antNum;}public void setAntNum(int antNum) {this.antNum = antNum;}public int getCityNum() {return cityNum;}public void setCityNum(int cityNum) {this.cityNum = cityNum;}public int getMAX_GEN() {return MAX_GEN;}public void setMAX_GEN(int mAX_GEN) {MAX_GEN = mAX_GEN;}public double[][] getPheromone() {return pheromone;}public void setPheromone(double[][] pheromone) {this.pheromone = pheromone;}public int[][] getDistance() {return distance;}public void setDistance(int[][] distance) {this.distance = distance;}public int getBestLength() {return bestLength;}public void setBestLength(int bestLength) {this.bestLength = bestLength;}public int[] getBestTour() {return bestTour;}public void setBestTour(int[] bestTour) {this.bestTour = bestTour;}public double getAlpha() {return alpha;}public void setAlpha(double alpha) {this.alpha = alpha;}public double getBeta() {return beta;}public void setBeta(double beta) {this.beta = beta;}public double getRho() {return rho;}public void setRho(double rho) {this.rho = rho;}@Overridepublic String toString() {return "ACO [ants=" + Arrays.toString(ants) + ", antNum=" + antNum + ", cityNum=" + cityNum + ", MAX_GEN="+ MAX_GEN + ", pheromone=" + Arrays.toString(pheromone) + ", distance=" + Arrays.toString(distance)+ ", bestLength=" + bestLength + ", bestTour=" + Arrays.toString(bestTour) + ", alpha=" + alpha+ ", beta=" + beta + ", rho=" + rho + "]";}}Test類：
package com.gbs.test; import com.gbs.bean.ACO; public class Test {public static void main(String[] args) {ACO aco = new ACO(200, 48, 2000, 1.d, 5.d, 0.5d);aco.init("d://cities.txt");aco.solve();} }注：調(diào)試代碼時(shí)遇到一個(gè)致命的問題就是忽略了float和double的精度。浪費(fèi)了三四個(gè)小時(shí)debug居然是這個(gè)錯(cuò)誤引起的，float的精度一旦不夠，在java中會(huì)出現(xiàn)NAN和INFINITY。
https://www.cnblogs.com/zhisuoyu/archive/2016/03/24/5314541.html（此網(wǎng)址講述了NAN和INFINITY的區(qū)別）。
6.存在問題
（1）對(duì)于大規(guī)模組合優(yōu)化問題，算法的計(jì)算時(shí)間而且復(fù)雜。由于蟻群算法的時(shí)間復(fù)雜度是，因此在處理較大規(guī)模的組合優(yōu)化問題時(shí)，運(yùn)算量較大，時(shí)間較長。
（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é)果具有較大的分散性。
總結(jié)
- 上一篇： 笔记本电脑自带键盘禁用与恢复
- 下一篇： 高等代数第一章习题