遗传算法（Genetic Algorithm ）+C++实现解决TSP问题
生活随笔
收集整理的這篇文章主要介紹了
遗传算法（Genetic Algorithm ）+C++实现解决TSP问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
概念
項目所在github
https://github.com/Sean16SYSU/Algorithms4N
| 環境 | 適應函數 |
| 適應性 | 適應函數值 |
| 適者生存 | 適應值大的解被保留的概率大 |
| 個體 | 問題的一個解 |
| 染色體 | 解的編碼 |
| 基因 | 編碼的元素 |
| 群體 | 被選定的一組解 |
| 種群 | 按適應函數選擇的一組解（編碼表示） |
| 交配 | 以一定的方式由雙親產生后代的過程 |
| 變異 | 編碼的某些分量發生變化的過程 |
三個生成過程
- select 自然選擇
- crossover 交叉（交配）
- mutation 變異
把每個數據想象成染色體，然后從染色體到人的映射就是object function，也就是這里的適應函數。
當然可以映射到更深的程度，比如考慮人的身高之類的（可以被量化的東西）
- 染色體 這樣的比喻，會很容易理解crossover這個步驟。
- 變異這個也很好理解，避免進入到局部極小值，被控制住了。
- 自然選擇，這個根據evolutionary theory，也很容易理解
簡單遺傳算法框架
一般終止條件是：過了很久最優的適應值都不發生變化
整數編碼問題
因為如果是二進制編碼的話，會簡單很多，這里就不講了。
難點其實還是在整數編碼上。
整數編碼（簡單的實例）：
(有些問題不是排序的問題，就可以類似于之前的二進制來實現)
對于父母分別是 0 到 9整數的排序【加上長度均為10】：
要求子代也必須是這樣的排序。
- 自然選擇：不會產生子代，只是篩選子代，所以不受這個問題影響
- 交叉（crossover）：會產生子代。這里只考慮排序時候的情況
- 基于次序的交配法： 在父代1找到幾個位置，之后，找到這些數字在父代2的位置。并刪除（用空白填充）。之后這些空白按照父代1的中這些數字的順序排好。（非常簡單的方法）
- 基于位置的交配法： 在父代1找到幾個位置，父代2的數值直接替代上去，只會，沖突的位置（不在之前選的位置上沖突的位置），按順序從父代1替代。
- 部分映射的交配法： 任意選兩個位置，在父代1,2直接這兩個位置之間的序列構建序列對。然后，按照這樣的序列對的映射方式，在父代1或者父代2上做映射交換。就可以得到子代1或子代2。
- 變異（mutation）：會產生子代。
- 基于位置的變異： 隨機產生兩個變異位，然后將第二個變異位上的基因移動到第一個變異位之前。
- 基于次序的變異： 隨機的產生兩個變異位，然后交換這兩個變異位上的基因。
- 打亂變異： 隨機尋去染色體上的一段，然后打亂在該段內的基因次序。逆序交換方式是打亂變異的一個特例。
TSP問題
TSP，是貨郎擔問題，也就是中國郵遞員問題（少數世界級問問題，用中國人命名的問題hhh）。
就是n個點直接連通需要不同的代價，如果想要找到不重復的經歷完所有點，然后在回到初始點的用的代價最小。
用遺傳算法解決TSP問題
#include <iostream> #include <cmath> #include <ctime> #include <fstream> #include <cstdlib> #include <vector> #include <algorithm> using namespace std;// 隨機整數[b, e) #define RAND(b, e) (rand() % ((e)-(b)) + (b)) // 隨機浮點數 0,1 #define RANDFLOAT() ((double)rand() / double(RAND_MAX))// 種群數量 int LEN = 10; int tempLEN = 3 * LEN; // 交配的概率，編譯的概率 double pc = 0.8, pm = 0.8; // 種群的所有路徑 int **Paths; int **tempPaths; int temp_index = 0; double **Mat; double *Value, *tempValue; int globalValue_index, stay_in_global_times = 0;double globalValue; int *globalPath;// TSP節點數量 int N = 0;// 適應值函數 double CalValue(int *p) { // read onlydouble t = 0;for (int i = 1; i < N; ++i) {t += Mat[p[i - 1]][p[i]];}t += Mat[p[N - 1]][0];return t; }void initialPath(int *Path, int j); void initialPaths(); void find_min(int first = 1);// 自然選擇 void select(); // 交配 void crossover(int *p1, int* p2); // 變異 void mutation(int *Path); // void preserve(int *p1, int *p2, int v1, int v2);int main() {srand((unsigned)time(NULL));ifstream cin("data.txt");cin >> N;Mat = new double *[N];for (int i = 0; i < N; ++i) {Mat[i] = new double[N];}// read data from data.txtfor (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {cin >> Mat[i][j];}}// new Path...Paths = new int*[LEN];for (int i = 0; i < LEN; ++i) {Paths[i] = new int[N];}tempPaths = new int*[tempLEN];for (int i = 0; i < tempLEN; ++i) {tempPaths[i] = new int[N];}Value = new double[LEN];tempValue = new double[tempLEN];globalPath = new int[N];// end new Path...initialPaths(); // initialize pathswhile (true) {temp_index = 0;for (int i = 0; i < LEN; i += 2) {if (temp_index >= tempLEN) break;preserve(Paths[i], Paths[i + 1], Value[i], Value[i + 1]);if (temp_index >= tempLEN) break;if (RANDFLOAT() < pc) crossover(Paths[i], Paths[i + 1]);}for (int i = 0; i < LEN; ++i) {if (temp_index >= tempLEN) break;if (RANDFLOAT() < pm) mutation(Paths[i]);}select(); if (stay_in_global_times == 1000) { break; }}cout << globalValue << endl;for (int i = 0; i < N; ++i) {cout << globalPath[i] << " --> ";}// delete Path...delete[]tempValue;delete[]Value;for (int i = 0; i < tempLEN; ++i) {delete[]tempPaths[i];}delete[] tempPaths;for (int i = 0; i < LEN; ++i) {delete[]Paths[i];}delete[] Paths;for (int i = 0; i < N; ++i) {delete[] Mat[i];}delete[]Mat;system("pause"); }// preserve the parents. void preserve(int *p1, int *p2, int v1, int v2) {for (int i = 0; i < N; ++i) {tempPaths[temp_index][i] = p1[i];}tempValue[temp_index] = v1;//if (tempValue[temp_index] < 0) cout << "wrong\n";temp_index++;if (p2 != NULL) {for (int i = 0; i < N; ++i) {tempPaths[temp_index][i] = p2[i];}tempValue[temp_index] = v2;//if (tempValue[temp_index] < 0) cout << "wrong\n";temp_index++;} }struct enumate{double data;int index;bool operator < (const enumate& e) const {return data < e.data;} };vector<int> argsort_temp_value() {enumate * data = new enumate[temp_index];for (int i = 0; i < temp_index; ++i) { data[i].data = tempValue[i];data[i].index = i;}sort(data, data +temp_index);vector<int> ans(temp_index);for (int i = 0; i < temp_index; ++i) ans[i] = data[i].index;delete[]data;return ans; }void select() {vector<int> id = argsort_temp_value();for (int i = 0; i < temp_index; ++i) if (tempValue[i] < 0)cout << tempValue[i] << endl;for (int i = 0; i < LEN; ++i) {Value[i] = tempValue[id[i]];for (int j = 0; j < N; ++j) {Paths[i][j] = tempPaths[id[i]][j];}}if (Value[0] < globalValue) {for (int i = 0; i < N; ++i) globalPath[i] = Paths[0][i];stay_in_global_times = 0;globalValue = Value[0];}else if (Value[0] == globalValue) {stay_in_global_times++;}else {cout << "Something wrong" << Value[0]<< endl;} }// 基于次序的交配方式 void crossover(int * p1, int * p2) {// generate son from p1 and p2int crossn = RAND(0, N-1);if (crossn == 0) return;int * indexs = new int[crossn];for (int i = 0; i < crossn; ++i) {if (i == 0) indexs[i] = RAND(1, N - crossn + 1);else { indexs[i] = RAND(indexs[i - 1] + 1, N - crossn + i + 1);}}// copy from p2for (int i = 0; i < N; ++i) {tempPaths[temp_index][i] = p2[i];}int use_count = 0;for (int i = 0; i < N; ++i) {if (use_count == crossn) break;for (int j = 0; j < crossn; ++j) {if (tempPaths[temp_index][i] == p1[indexs[j]]) {tempPaths[temp_index][i] = p1[indexs[use_count]];use_count++;break;}}}// cal valuetempValue[temp_index] = CalValue(tempPaths[temp_index]);temp_index++;// copy from p1for (int i = 0; i < N; ++i) {tempPaths[temp_index][i] = p1[i];}use_count = 0;for (int i = 0; i < N; ++i) {if (use_count == crossn) break;for (int j = 0; j < crossn; ++j) {if (tempPaths[temp_index][i] == p2[indexs[j]]) {tempPaths[temp_index][i] = p2[indexs[use_count]];use_count++;break;}}}tempValue[temp_index] = CalValue(tempPaths[temp_index]);temp_index++;delete[] indexs; }// 基于次序的變異 void mutation(int * Path) {int a = RAND(1, N), b, t;if (a == N - 1) {b = RAND(1, N - 1);t = a; a = b; b = t;}else {b = RAND(a + 1, N);}for (int i = 0; i < N; ++i) {if (i == a)tempPaths[temp_index][i] = Path[b];else if ( i == b )tempPaths[temp_index][i] = Path[a];else tempPaths[temp_index][i] = Path[i];}tempValue[temp_index] = CalValue(tempPaths[temp_index]);temp_index++; }void initialPaths() {for (int i = 0; i < LEN; ++i)initialPath(Paths[i], i);find_min(); }void find_min(int first) {int temp = 0;for (int i = 1; i < LEN; ++i)if (Value[temp] > Value[i]) temp = i;if (first) {globalValue = Value[temp];for (int i = 0; i < N; ++i)globalPath[i] = Paths[temp][i];}else if (Value[temp] < globalValue) {globalValue = Value[temp];for (int i = 0; i < N; ++i)globalPath[i] = Paths[temp][i];} }void initialPath(int *Path, int j) {for (int i = 0; i < N; ++i) {Path[i] = i;}// Path[i]表示路上第i個點的標記為Path[i]// Path[0] = 0int tx, t;for (int i = 1; i < N - 1; ++i) {tx = RAND(i, N);if (tx != i) { // swapt = Path[i];Path[i] = Path[tx];Path[tx] = t;}}Value[j] = CalValue(Path);}這里用的數據跟之前的用退火算法的結果是一樣的。
模擬退火算法理論+Python解決函數極值+C++實現解決TSP問題
- 結果是也是一樣的，對于這個，我們可以設置重復多少次來停止來控制這個精度。
- 為了避免到局部最優解，也可以使用提高變異概率來設計。
- 結果是大概率收斂到較好的結果。
改進版本代碼
- 改進點：交配的嘗試會在每人之間都相互試試看。提高了隨機性，所以會更穩定的收斂到結果。因此就不用太多次的停滯就可以控制住。
總結
以上是生活随笔為你收集整理的遗传算法（Genetic Algorithm ）+C++实现解决TSP问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mysql生成100000个数据并检验索
- 下一篇： flask读取数据库(mysql)并展示