人工智能--遗传算法（旅行商问题）
人工智能是研究使計算機來模擬人的某些思維過程和智能行為（如學習、推理、思考、規劃等）的學科，主要包括計算機實現智能的原理、制造類似于人腦智能的計算機，使計算機能實現更高層次的應用。人工智能將涉及到計算機科學、心理學、哲學和語言學等學科。可以說幾乎是自然科學和社會科學的所有學科，其范圍已遠遠超出了計算機科學的范疇，人工智能與思維科學的關系是實踐和理論的關系，人工智能是處于思維科學的技術應用層次，是它的一個應用分支。從思維觀點看，人工智能不僅限于邏輯思維，要考慮形象思維、靈感思維才能促進人工智能的突破性的發展，數學常被認為是多種學科的基礎科學，數學也進入語言、思維領域，人工智能學科也必須借用數學工具，數學不僅在標準邏輯、模糊數學等范圍發揮作用，數學進入人工智能學科，它們將互相促進而更快地發展。
遺傳算法是計算數學中用于解決最佳化的搜索算法，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。遺傳算法通常實現方式為一種計算機模擬。對于一個最優化問題，一定數量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統上，解用二進制表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之后一代一代發生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體（基于它們的適應度），通過自然選擇和突變產生新的生命種群，該種群在算法的下一次迭代中成為當前種群。
- 上機題簡介
-
用C++語言編寫和調試一個用遺傳算法解旅行商TSP問題的程序。目的是學會運用知識表示方法和搜索策略求解一些考驗智力的簡單問題，熟悉簡單智能算法的開發過程并理解其實現原理。
用遺傳算法解旅行商TSP問題：假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
在遺傳算法解旅行商TSP問題當中程序總體圍繞了遺傳算法的三個主要步驟：選擇--復制，交叉，變異。給定了10個種群，即10條染色體，每條染色體都是除首位外不重復的點組成，首尾相同保證路線是閉合的，所以一條染色體包含11個點。
遺傳算法解旅行商TSP問題實驗原理：
TSP問題就是尋找一條最短的遍歷n個城市的最短路徑，即搜索自然數子集W={1,2..n}(W的元素表示對n個城市的編號)的一個排列。
遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。它的基本處理流程如圖1所示。由此流程圖可見，遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。選擇( Selection)、交叉(Crossover)和變異(Mutation) 是遺傳算法的3個主要操作算子，它們構成了所謂的遺傳操作( genetic operation),使遺傳算法具有了其它傳統方法所沒有的特性。遺傳算子包含如下6個基本因素:
(1)參數編碼:由于遺傳算法不能直接處理解空間的解數據，因此必須通過編碼將它們表示成遺傳空間的基因型串結構數據。
(2)生成初始群體:由于遺傳算法的群體型操作需要，所以必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是通過隨機方法產生。
( 3)適應度評估檢測:遺傳算法在搜索進化過程中一般不需要其他外部信息,僅用適應度( fitness) 值來評估個體或解的優劣，并作為以后遺傳操作的依據。
(4)選擇(selection): 選擇或復制操作是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。個體適應度越高，其被選擇的機會就越多。此處采用與適用度成比例的概率方法進行選擇。具體地說，就是首先計算群體中所有個體適應度的總和,再計算每個個體的適應度所占的比例，并以此作為相應的選擇概率。
(5)交叉操作:交叉操作是遺傳算法中最主要的遺傳操作。簡單的交叉(即一點交叉)可分兩步進行:首先對種群中個體進行隨機配對:其次，在配對個體中隨機設定交叉處，配對個體彼此交換部分信息。
（6）變異:變異操作是按位(bit) 進行的，即把某一位的內容進行變異。變異操作同樣也是隨機進行的。一般而言，變異概率P都取得較小。變異操作是十分微妙的遺傳操作，它需要和交叉操作配合使用，目的是挖掘群體中個體的多樣性，克服有可能限于局部解的弊病。
遺傳算法解旅行商TSP問題程序功能結構圖：
流程圖：
數據結構定義:
//定義染色體的結構
struct Chrom
{
int cityArr[cityNum]; //染色體的基因編碼
char name; //染色體的名稱
float adapt; //染色體的適應度
int dis; //染色體的路徑長度
};
struct Chrom genes[popSize]; //定義基因庫（結構體數組）
struct Chrom genesNew[popSize]; //重新建立一個新的種群
struct Chrom temp; //定義臨時公用結點
?names[cityNum] = {'A','B','C','D','E','F','G','H','I','J'}; //城市名稱
?distance[cityNum][cityNum] ??//城市距離矩陣
函數方法定義：
initGroup() ???//初始化基因庫
popFitness() ??//計算種群所有染色體的個體適應度
chooseBest() ?//返回最優秀的一條染色體
select() ??????// 選擇操作
cross() ??????//交叉操作
mutation() ???//變異操作
遺傳算法解旅行商TSP問題C語言代碼：
#include "stdio.h" #include "stdlib.h" #include "windows.h" #include "time.h"#define cityNum 10 //城市數量（基因數量）（染色體長度） #define popSize 10 //種群大小（尺寸） #define croRate 0.85 //交叉概率 #define mutRate 0.1 //變異概率 #define MAX 999 //進化代數//定義染色體的結構 struct Chrom { int cityArr[cityNum]; //染色體的基因編碼char name; //染色體的名稱float adapt; //染色體的適應度int dis; //染色體的路徑長度 }; struct Chrom genes[popSize]; //定義基因庫（結構體數組） struct Chrom genesNew[popSize]; //重新建立一個新的種群 struct Chrom temp; //定義臨時公用結點char names[cityNum] = {'A','B','C','D','E','F','G','H','I','J'}; //城市名稱int distance[cityNum][cityNum] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, //城市距離矩陣{ 1, 0, 1, 2, 3, 4, 5, 6, 7, 8 },{ 2, 1, 0, 1, 2, 3, 4, 5, 6, 7 },{ 3, 2, 1, 0, 1, 2, 3, 4, 5, 6 },{ 4, 3, 2, 1, 0, 1, 2, 3, 4, 5 },{ 5, 4, 3, 2, 1, 0, 1, 2, 3, 4 },{ 6, 5, 4, 3, 2, 1, 0, 1, 2, 3 },{ 7, 6, 5, 4, 3, 2, 1, 0, 1, 2 },{ 8, 7, 6, 5, 4, 3, 2, 1, 0, 1 },{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }}; //最優解為18void initGroup() {//初始化基因庫 int i,j,k;int t = 0;int flag = 0;srand(time(NULL));//初始化隨機種子,防止隨機數每次重復，常常使用系統時間來初始化,當srand()的參數值固定的時候，rand()獲得的數也是固定的for(i = 0; i < popSize; i ++){//使用臨時結點開始賦值temp.name = names[i];temp.adapt = 0.0f;temp.dis = 0;//產生10個不相同的數字for(j = 0; j < cityNum;){t = rand()%cityNum; //隨機產生0-9的數flag = 1;for(k = 0; k < j; k ++){if(genes[i].cityArr[k] == t){flag = 0;break;}}if(flag){temp.cityArr[j] = t;genes[i] = temp;//存入結構體數組，產生一個個體j++;}} } }//計算種群所有染色體的個體適應度 void popFitness() {int i,n1,n2;for(i = 0; i < popSize; i ++){genes[i].dis = 0;for(int j = 1;j < cityNum; j ++){n1 = genes[i].cityArr[j-1];n2 = genes[i].cityArr[j];genes[i].dis += distance[n1][n2]; }genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum-1]];genes[i].adapt = (float)1/genes[i].dis; //每條染色體的路徑總和(個體適應度) } }//返回最優秀的一條染色體 int chooseBest() {int choose = 0;float best = 0.0f;best = genes[0].adapt;for(int i = 0; i < popSize; i ++){if(genes[i].adapt < best){best = genes[i].adapt;choose = i;} }return choose; }// 選擇操作 void select() {float biggestSum = 0.0f;float adapt_pro[popSize];float pick = 0.0f;int i;for(i = 0; i < popSize; i ++){biggestSum += genes[i].adapt; // 總概率}for(i = 0; i < popSize; i ++){adapt_pro[i] = genes[i].adapt / biggestSum; // 概率數組}// 輪盤賭for(i = 0;i < popSize; i ++){pick = (float)rand()/RAND_MAX; // 0到1之間的隨機數for(int j = 0; j < popSize; j ++){pick = pick - adapt_pro[j];if(pick <= 0){genesNew[i] = genes[j]; break; }}}for(i = 0;i < popSize; i++){ genes[i] = genesNew[i]; } }void cross() // 交叉操作 { float pick;int choice1,choice2;int pos1,pos2;int temp;int conflict1[popSize]; // 沖突位置int conflict2[popSize];int num1;int num2;int index1,index2;int move = 0; // 當前移動的位置while(move < popSize-1){pick = (float)rand()/RAND_MAX; // 用于決定是否進行交叉操作if(pick > croRate) //兩條染色體是否相愛{move += 2;continue; // 本次不進行交叉}// 采用部分映射雜交choice1 = move; // 用于選取雜交的兩個父代choice2 = move+1; // 注意避免下標越界pos1 = rand()%popSize;pos2 = rand()%popSize;while(pos1 > popSize -2 || pos1 < 1)//如果位置在開頭或結尾(因為全部交換無意義){pos1 = rand()%popSize; }while(pos2 > popSize -2 || pos2 < 1){pos2 = rand()%popSize;}if(pos1 > pos2){temp = pos1;pos1 = pos2;pos2 = temp; // 交換pos1和pos2的位置}for(int j = pos1;j <= pos2; j++)// 逐個交換順序{temp = genes[choice1].cityArr[j];genes[choice1].cityArr[j] = genes[choice2].cityArr[j];genes[choice2].cityArr[j] = temp; }num1 = 0;num2 = 0;if(pos1 > 0 && pos2 < popSize - 1)//分三段{for(int j =0;j < pos1;j++){for(int k = pos1; k <= pos2; k++){if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k]){conflict1[num1] = j;num1 ++;}if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k]){conflict2[num2] = j;num2 ++;}}}for(j = pos2 + 1;j < popSize;j++){for(int k = pos1; k <= pos2; k ++){if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k]){conflict1[num1] = j;num1 ++;} if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k]){conflict2[num2] = j;num2 ++; } }}}if((num1 == num2) && num1 > 0){for(int j = 0;j < num1; j ++){index1 = conflict1[j];index2 = conflict2[j];temp = genes[choice1].cityArr[index1]; // 交換沖突的位置genes[choice1].cityArr[index1] = genes[choice2].cityArr[index2];genes[choice2].cityArr[index2] = temp;}}move += 2;} }//變異操作 void mutation() {double pick;int pos1,pos2,temp;for(int i = 0;i < popSize; i ++){pick = (float)rand()/RAND_MAX; // 用于判斷是否進行變異操作if(pick > mutRate){continue;}pos1 = rand()%popSize;pos2 = rand()%popSize;while(pos1 > popSize - 1){pos1 = rand()%popSize; }while(pos2 > popSize - 1){pos2 = rand()%popSize;}int a = genes[i].dis;temp = genes[i].cityArr[pos1];genes[i].cityArr[pos1] = genes[i].cityArr[pos2];genes[i].cityArr[pos2] = temp;popFitness();//更新數據//此步驟的作用在于檢查是否變異后得到的個體比變異前更優秀了，如若往壞的方向變化了，那還不如不變異了//（強制返回，雖然有點違背事物的客觀發展規律，但為了增強程序的收斂性，該操作還是有必要的）（偷笑）if(genes[i].dis > a){temp = genes[i].cityArr[pos1];genes[i].cityArr[pos1] = genes[i].cityArr[pos2];genes[i].cityArr[pos2] = temp; }} }int main() {char c = 0; printf("\n\t\t******************************** 遺傳算法求解TSP(旅行商)問題 *********************************\n");initGroup(); //初始化popFitness(); //更新數據//輸出配置信息printf("\n\t\t基因長度:%d",cityNum);printf("\t種群大小:%d",popSize);printf("\t交叉概率:%.2f",croRate);printf("\t變異概率:%.2f",mutRate);printf("\t進化代數:%d",MAX);printf("\t預設最優解：18");printf("\n\n\t\t**********************************************************************************************\n");//輸出距離矩陣printf("\n\n\t\t--------- 城市距離矩陣 ---------\n");printf("\t\t");int i,j;for(i = 0; i < cityNum; i ++){for(j = 0;j < cityNum; j ++){printf(" %d",distance[i][j]);}printf("\n\t\t");}printf("--------------------------------\n");//輸出路徑信息printf("\n\t\t-------- 初始種群基因庫 --------\n");printf("\t\t ");for(i = 0; i < cityNum; i ++){printf(" %c",genes[i].name);}printf("\n\t\t");for(i = 0;i < cityNum; i ++){printf("%c",genes[i].name);for(j = 0; j < cityNum; j ++){printf(" %d",genes[i].cityArr[j]); }printf("\n\t\t");}printf("--------------------------------\n");do{printf("\n\t\t尋求最優解中：");//通過不斷進化，直到達到定義的進化代數for(i = 0; i < MAX; i ++){select();cross();popFitness();//更新數據mutation();popFitness();//更新數據int temp = (int)MAX/20;}printf("完成");printf("\n\n\t\t最優路徑：");for(i = 0; i < cityNum ; i++){printf("%d-->",genes[chooseBest()].cityArr[i]);}printf("%d",genes[chooseBest()].cityArr[0]);printf("\n\n\t\t路徑長度:%d",genes[chooseBest()].dis);printf("\n\n\t\t是否再試一次?(Y/y) 是/(N/n) 否：");fflush(stdin);c = getchar(); fflush(stdin);if(c=='N'||c=='n'){break;}}while(1);printf("\n\t\t");return 0; }- 總結體會
在旅行商問題當中由遺傳算法對以上情況的求解(10座城市)，可以看出，用傳算法來求解TSP問題是可行的。用遺傳算法求解時，增加選代次數，可以得到更加優良的結果，但是會需要更長的時間，即一個優良的結果往往是以時間力代價的，這種情況要依據具體問題具體分析，平衡兩者在問題求解時的比重。參數設置得好壞往往對遺傳算法的性能和結果有著重要的影響，往往在解決某一問題的時候，需要設定的參數很多，如何獲得最佳的參數組合是一個很重要的問題。另外，對選擇算法進行優化，會提高遺傳算法的性能，這些都需要在實踐中不斷科累和廣泛涉獵優良算法。最后，遺傳算法得到的未必是最優解，我們可以根據需要進行多次求解，從而比較得出符合要求的結果。
?
轉載于:https://www.cnblogs.com/951201193-wzc/p/10294928.html
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的人工智能--遗传算法（旅行商问题）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python中字符串编码转换
- 下一篇： 隐写