遺傳算法解決TSP問題(C++)

1、遺傳算法解決TSP問題（C+版）遺傳算法流程：交叉，編譯，計算適應(yīng)度，保存最優(yōu)個體。其中交叉過程是選擇最優(yōu)的兩個染色體進行交叉操作，本文采用的是輪盤賭算法。#include #include #include using namespace std;#define population 200/種群數(shù)量#define pc 0.9/交叉的概率#define pm 0.1/變異的概率#define count 200/迭代的次數(shù)#define num 10/城市的數(shù)量int* city;/存放每個個體的訪問順序int path1010 = /0, 1, 2, 3, 4, 5, 6, 7, 8,

2、9 0, 23, 93, 18, 40, 34, 13, 75, 50, 35 ,/0 23, 0, 75, 4, 72, 74, 36, 57, 36, 22 ,/1 93, 75, 0, 64, 21, 73, 51, 25, 74, 89 ,/2 18, 4, 64, 0, 55, 52, 8, 10, 67, 1 , /3 40, 72, 21, 55, 0, 43, 64, 6, 99, 74 , /4 34, 74, 73, 52, 43, 0, 43, 66, 52, 39 ,/5 13, 36, 51, 8, 64, 43, 0, 16, 57, 94 ,/6 75, 57,

3、25, 10, 6, 66, 16, 0, 23, 11 , /7 50, 36, 74, 67, 99, 52, 57, 23, 0, 42 ,/8 35, 22, 89, 1, 74, 39, 94, 11, 42, 0 /9;int* dis;/存放每個個體的訪問順序下的路徑長度double* fitness;/存放滅個個體的適應(yīng)度int min_dis = ;int min_index = -1;int* min_path;/初始化種群void init()int *a = new intnum;for (int i = 0; inum; i+)ai = i;city = new in

4、t*population;for (int i = 0; ipopulation; i+)cityi = new intnum;for (int i = 0; i= 0; j-)int n = rand() % (j + 1);/產(chǎn)出的數(shù)是0-j,保證交換的后面的數(shù)不會再被交換swap(aj, an);/保證a里面全是0-(num-1)的數(shù)，無重復(fù)的數(shù)，只是順序顛倒cityij = aj;deletea;dis = new intpopulation;fitness = new doublepopulation;min_path = new intnum;/計算適應(yīng)度void compute(

5、)/cout do compute now. endl;double total = 0;for (int i = 0; ipopulation; i+)/計算每種情況下，路徑的長度disi = 0;int a = cityi0, b;for (int j = 1; jnum; j+)b = cityij;disi += pathab;a = b;disi += pathbcityi0;fitnessi = 1.0 / disi;/以距離的倒數(shù)作為適應(yīng)度函數(shù)值total += fitnessi;/選擇適應(yīng)度高的物種，采用輪盤賭算法int select()double total = 0;for

6、 (int i = 0; ipopulation; i+)total += fitnessi;double size = rand() / (double)RAND_MAX * total;/保證不產(chǎn)生0/cout size size endl;double sum = 0;int i = 0;while (sum = size&ipopulation)sum += fitness+i;return -i;/返回被選中的個體int getMinDis()int result = dis0;int index = 0;for (int i = 1; i disi)result = disi;in

7、dex = i;return index;int getMaxDis()int result = dis0;int index = 0;for (int i = 1; ipopulation; i+)if (result disi)result = disi;index = i;return index;void save()int current_min_index = getMinDis();int current_max_index = getMaxDis();if (discurrent_min_index min_dis)min_dis = discurrent_min_index;

8、for (int i = 0; i num; i+)min_pathi =citycurrent_min_indexi;/cout current min dis is: min_dis endl;elsefor (int i = 0; inum; i+)citycurrent_max_indexi = min_pathi;discurrent_max_index = min_dis;fitnesscurrent_max_index = 1.0 / min_dis;/最優(yōu)保存算法bool isExist(int value, int* array, int len)for (int i = 0

9、; ilen; i+)if (value = arrayi)return true;return false;void convert(int p1, int p2, int* src, int* dst)int len = p2 - p1 + 1;int* temp = new intlen;for (int i = p1; i = p2; i+)tempi - p1 = srci;int j = (p2 + 1) % num;for (int i = 1; i = num; i+)int index = (i + p2) % num;if (!isExist(dstindex, temp,

10、 len)dstj = dstindex;j = (j + 1) % num;for (int i = p1; i = p2; i+)dsti = srci;deletetemp;/交叉，采用次序交叉算法void cross()/cout do cross now. endl;for (int k = 0; kpopulation; k += 2)int a = select();int b = select();while (a = b)b = select();/保證被選中的個體不是一樣的/cout same b endl;/cout choose popuilation a b endl

11、;double p = rand() / double(RAND_MAX);/cout cross rate is p endl;int* a1 = new intnum;int* a2 = new intnum;int* b1 = new intnum;int* b2 = new intnum;for (int i = 0; inum; i+)a1i = cityai;a2i = citybi;b1i = a2i;b2i = a1i;if (ppc)/滿足交叉條件/選擇交叉的兩點，并保證p1p2)swap(p1, p2);/cout choose pos p1 p2 endl;/開始交叉co

12、nvert(p1, p2, a1, b1);convert(p1, p2, a2, b2);for (int i = 0; inum; i+)cityki = b1i;cityk + 1i = b2i;elsefor (int i = 0; inum; i+)cityki = a1i;cityk + 1i = a2i;deletea1;deletea2;deleteb1;deleteb2;/變異,采用對換操作進行變異void morphis()/cout do morphis now. endl;for (int i = 0; ipopulation; i+)double p = rand()

13、 / double(RAND_MAX);/cout morphis rate is p endl;if (ppm)/執(zhí)行變異int a = -1, b = -1;while (a = b)a = rand() % num;b = rand() % num;swap(cityia, cityib);int getdis()/compute();int result = dis0;int index = 0;for (int i = 1; i disi)result = disi;index = i;return result;/釋放申請的數(shù)組的空間void dispose()for (int i = 0; ipopulation; i+)deletecityi;deletecity;deletedis;deletefitness;int main()init();/初始化種群int i = 0;srand(time(0);compute();while (icount)cross();/交叉morphis();/變異compute();/計算適應(yīng)度save(