遗传算法解决TSP问题(C++)

实用文档遗传算法解决TSP问题（C+版）遗传算法流程：交叉，编译，计算适应度，保存最优个体。其中交叉过程是选择最优的两个染色体进行交叉操作，本文采用的是轮盘赌算法。#include #include #include using namespace std;#define population 200/种群数量#define pc 0.9/交叉的概率#define pm 0.1/变异的概率#define count 200/迭代的次数#define num 10/城市的数量int* city;/存放每个个体的访问顺序int path1010 = /0, 1, 2, 3, 4, 5, 6, 7, 8, 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, 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;/存放灭个个体的适应度int min_dis = 1000000;int min_index = -1;int* min_path;/初始化种群void init()int *a = new intnum;for (int i = 0; inum; i+)ai = i;city = new int*population;for (int i = 0; ipopulation; i+)cityi = new intnum;for (int i = 0; i= 0; j-)int n = rand() % (j + 1);/产出的数是0-j,保证交换的后面的数不会再被交换swap(aj, an);/保证a里面全是0-(num-1)的数，无重复的数，只是顺序颠倒cityij = aj;deletea;dis = new intpopulation;fitness = new doublepopulation;min_path = new intnum;/计算适应度void compute()/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;/以距离的倒数作为适应度函数值total += fitnessi;/选择适应度高的物种，采用轮盘赌算法int select()double total = 0;for (int i = 0; ipopulation; i+)total += fitnessi;double size = rand() / (double)RAND_MAX * total;/保证不产生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;index = 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;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;/最优保存算法bool isExist(int value, int* array, int len)for (int i = 0; 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, 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;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;/开始交叉convert(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() / double(RAND_MAX);/cout morphis rate is p endl;if (ppm)/执行变异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;/释放申请的数组的空间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();/计算适应度save()