蟻群算法源代碼

1、view plaincopy to clipboardprint?/* *作者:陳杰 *單位:四川大學(xué)計算機學(xué)院 *郵件地址:scucj *完成時間:2008年3月 */ #include<iostream> #include<math.h> #include<time.h> using namespace std; /該程序是以蟻群系統(tǒng)為模型寫的蟻群算法程序(強調(diào)：非螞蟻周模型)，以三個著名的TSP問題為測試對象 /通過微調(diào)參數(shù)，都可以獲得較好的解 /* /-(1)問題一：Oliver 30 城市 TSP 問題 best_length = 423.7406

2、; - /該程序最好的結(jié)果是423.741，可運行多次獲得 /城市節(jié)點數(shù)目 #define N 30 /城市坐標(biāo) double CN2= 2,99,4,50,7,64,13,40,18,54,18,40,22,60,24,42,25,62,25,38, 37,84,41,94,41,26,44,35,45,21,54,67,54,62,58,35,58,69,62,32, 64,60,68,58,71,44,71,71,74,78,82,7,83,46,83,69,87,76,91,38 ; /-上面參數(shù)是固定的，下面的參數(shù)是可變的- /螞蟻數(shù)量 #define M 30 /最大循環(huán)次數(shù)NcM

3、ax int NcMax = 500; /信息啟發(fā)因子，期望啟發(fā)式因子，全局信息素揮發(fā)參數(shù)，局部信息素揮發(fā)參數(shù), 狀態(tài)轉(zhuǎn)移公式中的q0 double alpha = 2, beta = 3, rou = 0.1, alpha1 = 0.1, qzero = 0.01; /-問題一結(jié)束- */ /* /-(2)問題二：Elion50 城市 TSP 問題 best_length = 427.96; - /該程序最好的結(jié)果是428.468，可運行多次獲得 /城市節(jié)點數(shù)目 #define N 50 /城市坐標(biāo) double CN2= 5,64, 5,25, 5,6, 7,38, 8,52, 10,17

4、, 12,42, 13,13, 16,57, 17,33, 17,63, 20,26, 21,47, 21,10, 25,32, 25,55, 27,68, 27,23, 30,48, 30,15, 31,62, 31,32, 32,22, 32,39, 36,16, 37,69, 37,52, 38,46, 39,10, 40,30, 42,57, 42,41, 43,67, 45,35, 46,10, 48,28, 49,49, 51,21, 52,33, 52,41, 52,64, 56,37, 57,58, 58,27, 58,48, 59,15, 61,33, 62,42, 62,6

5、3, 63,69 ; /-上面參數(shù)是固定的，下面的參數(shù)是可變的- /螞蟻數(shù)量 #define M 50 /最大循環(huán)次數(shù)NcMax int NcMax = 1000; /信息啟發(fā)因子，期望啟發(fā)式因子，全局信息素揮發(fā)參數(shù)，局部信息素揮發(fā)參數(shù), 狀態(tài)轉(zhuǎn)移公式中的q0 double alpha = 2, beta = 4, rou = 0.1, alpha1 = 0.1, qzero = 0.01; /-問題二結(jié)束- */ /-(3)問題三：Elion75 城市 TSP 問題 best_length = 542.31; /該程序最好的結(jié)果是542.309，可運行多次獲得 /城市節(jié)點數(shù)目 #define

6、 N 75 /城市坐標(biāo) double CN2= 6,25, 7,43, 9,56, 10,70, 11,28, 12,17, 12,38, 15,5, 15,14, 15,56, 16,19, 17,64, 20,30, 21,48, 21,45, 21,36, 22,53, 22,22, 26,29, 26,13, 26,59, 27,24, 29,39, 30,50, 30,20, 30,60, 31,76, 33,34, 33,44, 35,51, 35,16, 35,60, 36,6, 36,26, 38,33, 40,37, 40,66, 40,60, 40,20, 41,46, 4

7、3,26, 44,13, 45,42, 45,35, 47,66, 48,21, 50,30, 50,40, 50,50, 50,70, 50,4, 50,15, 51,42, 52,26, 54,38, 54,10, 55,34, 55,45, 55,50, 55,65, 55,57, 55,20, 57,72, 59,5, 60,15, 62,57, 62,48, 62,35, 62,24, 64,4, 65,27, 66,14, 66,8, 67,41, 70,64 ; /-上面參數(shù)是固定的，下面的參數(shù)是可變的- /螞蟻數(shù)量 #define M 75 /最大循環(huán)次數(shù)NcMax int N

8、cMax =1000; /信息啟發(fā)因子，期望啟發(fā)式因子，全局信息素揮發(fā)參數(shù)，局部信息素揮發(fā)參數(shù), 狀態(tài)轉(zhuǎn)移公式中的q0 double alpha = 2, beta = 5, rou = 0.1, alpha1 = 0.1, qzero = 0.1; /-問題三結(jié)束- /= /局部更新時候使用的的常量，它是由最近鄰方法得到的一個長度 /什么是最近鄰方法?:)就是從源節(jié)點出發(fā)，每次選擇一個距離最短的點來遍歷所有的節(jié)點得到的路徑 /每個節(jié)點都可能作為源節(jié)點來遍歷 double Lnn; /矩陣表示兩兩城市之間的距離 double allDistanceNN; /計算兩個城市之間的距離 double

9、 calculateDistance(int i, int j) return sqrt(pow(Ci0-Cj0),2.0) + pow(Ci1-Cj1),2.0); /由矩陣表示兩兩城市之間的距離 void calculateAllDistance() for(int i = 0; i < N; i+) for(int j = 0; j < N; j+) if (i != j) allDistanceij = calculateDistance(i, j); allDistanceji = allDistanceij; /獲得經(jīng)過n個城市的路徑長度 double calculat

10、eSumOfDistance(int* tour) double sum = 0; for(int i = 0; i< N ;i+) int row = *(tour + 2 * i); int col = *(tour + 2* i + 1); sum += allDistancerowcol; return sum; class ACSAnt; class AntColonySystem private: double infoNN, visibleNN;/節(jié)點之間的信息素強度,節(jié)點之間的能見度 public: AntColonySystem() /計算當(dāng)前節(jié)點到下一節(jié)點轉(zhuǎn)移的概率

11、double Transition(int i, int j); /局部更新規(guī)則 void UpdateLocalPathRule(int i, int j); /初始化 void InitParameter(double value); /全局信息素更新 void UpdateGlobalPathRule(int* bestTour, int globalBestLength); ; /計算當(dāng)前節(jié)點到下一節(jié)點轉(zhuǎn)移的概率 double AntColonySystem:Transition(int i, int j) if (i != j) return (pow(infoij,alpha) *

12、 pow(visibleij, beta); else return 0.0; /局部更新規(guī)則 void AntColonySystem:UpdateLocalPathRule(int i, int j) infoij = (1.0 - alpha1) * infoij + alpha1 * (1.0 / (N * Lnn); infoji = infoij; /初始化 void AntColonySystem:InitParameter(double value) /初始化路徑上的信息素強度tao0 for(int i = 0; i < N; i+) for(int j = 0; j

13、< N; j+) infoij = value; infoji = value; if (i != j) visibleij = 1.0 / allDistanceij; visibleji = visibleij; /全局信息素更新 void AntColonySystem:UpdateGlobalPathRule(int* bestTour, int globalBestLength) for(int i = 0; i < N; i+) int row = *(bestTour + 2 * i); int col = *(bestTour + 2* i + 1); inforo

14、wcol = (1.0 - rou) * inforowcol + rou * (1.0 / globalBestLength); infocolrow =inforowcol; class ACSAnt private: AntColonySystem* antColony; protected: int startCity, cururentCity;/初始城市編號，當(dāng)前城市編號 int allowedN;/禁忌表 int TourN2;/當(dāng)前路徑 int currentTourIndex;/當(dāng)前路徑索引，從0開始，存儲螞蟻經(jīng)過城市的編號 public: ACSAnt(AntColonyS

15、ystem* acs, int start) antColony = acs; startCity = start; /開始搜索 int* Search(); /選擇下一節(jié)點 int Choose(); /移動到下一節(jié)點 void MoveToNextCity(int nextCity); ; /開始搜索 int* ACSAnt:Search() cururentCity = startCity; int toCity; currentTourIndex = 0; for(int i = 0; i < N; i+) allowedi = 1; allowedcururentCity =

16、0; int endCity; int count = 0; do count+; endCity = cururentCity; toCity = Choose(); if (toCity >= 0) MoveToNextCity(toCity); antColony->UpdateLocalPathRule(endCity, toCity); cururentCity = toCity; while(toCity >= 0); MoveToNextCity(startCity); antColony->UpdateLocalPathRule(endCity, sta

17、rtCity); return *Tour; /選擇下一節(jié)點 int ACSAnt:Choose() int nextCity = -1; double q = rand()/(double)RAND_MAX; /如果 q <= q0,按先驗知識，否則則按概率轉(zhuǎn)移， if (q <= qzero) double probability = -1.0;/轉(zhuǎn)移到下一節(jié)點的概率 for(int i = 0; i < N; i+) /去掉禁忌表中已走過的節(jié)點,從剩下節(jié)點中選擇最大概率的可行節(jié)點 if (1 = allowedi) double prob = antColony->

18、;Transition(cururentCity, i); if (prob > probability) nextCity = i; probability = prob; else /按概率轉(zhuǎn)移 double p = rand()/(double)RAND_MAX;/生成一個隨機數(shù),用來判斷落在哪個區(qū)間段 double sum = 0.0; double probability = 0.0;/概率的區(qū)間點，p 落在哪個區(qū)間段，則該點是轉(zhuǎn)移的方向 /計算概率公式的分母的值 for(int i = 0; i < N; i+) if (1 = allowedi) sum += ant

19、Colony->Transition(cururentCity, i); for(int j = 0; j < N; j+) if (1 = allowedj && sum > 0) probability += antColony->Transition(cururentCity, j)/sum; if (probability >= p | (p > 0.9999 && probability > 0.9999) nextCity = j; break; return nextCity; /移動到下一節(jié)點 void

20、ACSAnt:MoveToNextCity(int nextCity) allowednextCity=0; TourcurrentTourIndex0 = cururentCity; TourcurrentTourIndex1 = nextCity; currentTourIndex+; cururentCity = nextCity; /- /選擇下一個節(jié)點，配合下面的函數(shù)來計算的長度 int ChooseNextNode(int currentNode, int visitedNode) int nextNode = -1; double shortDistance = 0.0; for

21、(int i = 0; i < N; i+) /去掉已走過的節(jié)點,從剩下節(jié)點中選擇距離最近的節(jié)點 if (1 = visitedNodei) if (shortDistance = 0.0) shortDistance = allDistancecurrentNodei; nextNode = i; if(shortDistance < allDistancecurrentNodei) nextNode = i; return nextNode; /給一個節(jié)點由最近鄰距離方法計算長度 double CalAdjacentDistance(int node) double sum =

22、 0.0; int visitedNodeN; for(int j = 0; j < N; j+) visitedNodej = 1; visitedNodenode = 0; int currentNode = node; int nextNode; do nextNode = ChooseNextNode(currentNode, visitedNode); if (nextNode >= 0) sum += allDistancecurrentNodenextNode; currentNode= nextNode; visitedNodecurrentNode = 0; wh

23、ile(nextNode >= 0); sum += allDistancecurrentNodenode; return sum; /-結(jié)束- /-主函數(shù)- int main() time_t timer,timerl; time(&timer); unsigned long seed = timer; seed %= 56000; srand(unsigned int)seed); /由矩陣表示兩兩城市之間的距離 calculateAllDistance(); /蟻群系統(tǒng)對象 AntColonySystem* acs = new AntColonySystem(); ACSA

24、nt* antsM; /螞蟻均勻分布在城市上 for(int k = 0; k < M; k+) antsk = new ACSAnt(acs, (int)(k%N); calculateAllDistance(); /隨機選擇一個節(jié)點計算由最近鄰方法得到的一個長度 int node = rand() % N; Lnn = CalAdjacentDistance(node); /各條路徑上初始化的信息素強度 double initInfo = 1 / (N * Lnn); acs->InitParameter(initInfo); /全局最優(yōu)路徑 int globalTourN2;

25、 /全局最優(yōu)長度 double globalBestLength = 0.0; for(int i = 0; i < NcMax; i+) /局部最優(yōu)路徑 int localTourN2; /局部最優(yōu)長度 double localBestLength = 0.0; /當(dāng)前路徑長度 double tourLength; for(int j = 0; j < M; j+) int* tourPath = antsj->Search(); tourLength = calculateSumOfDistance(tourPath); /局部比較，并記錄路徑和長度 if(tourLength < localBestLength | abs(localBestLength - 0.0) < 0.000001) for(int m = 0; m< N; m+) int row = *(tourPath + 2 * m); int col = *(tourPath + 2* m + 1); localTourm0 = row; loca