遗传算法求解TSP问题

1、智能优化算法第二次作业一分析遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加

2、以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。下面用C语言模拟遗传算法模拟TSP问题TSP问题及旅行商问题,假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值1） 生成初始种群： 2） 适应度计算3） 交叉

3、4） 变异5） 选最优6） 迭代二、结果：源码：/*问题：用遗传算法求解TSP问题：为保证有解 用完全图做样例*/*洪文杰 2016-3-16. 智能优化算法 第二次作业*/#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;/-宏定义-/#define NUMBER 50 /种群规模#define GENE_NUMBER 10 /迭代次数#define G 20 /图的顶点个数#define CROSS 0.85 /交叉概率#define ABERRANCE 0.1

4、5 /变异概率/-全局变量定义-/int FigureGG; /保存图信息int UnitNUMBERG; /保存初始种群int Choose_UnitNUMBERG; /保存更新的种群int Choose_NumberNUMBER; /被选择的个体编号int CrossNUMBER; /要交叉的个体一览float select_probabilityNUMBER; /选择概率float accumula_probabilityNUMBER ; /积累概率 int hwjG; /grefenstette编码的个体、也保存最短路径int Figure_best=100000; /最短路径长度/-

5、函数声明-/void hwj_figure(); /生成完全图void hwj_initial_population(); /生成初始种群void hwj_swap(int *a,int *b); /交换两个数的值void hwj_fitness(); /计算适应度、选择概率 、积累概率void hwj_choose(); /轮盘赌选择法找到被选择的个体 int hwj_bisearch(float temp); /顺序查找 void hwj_cross(); /进行交叉 void hwj_cross2(int a,int b,int key); /利用grefenstette编码交叉 voi

6、d hwj_aberrance(); /进行变异void hwj_aberrance2(int a,int key); /利用grefenstette编码变异void hwj_best(); /找到最短路径 /-主函数-/int main()int key=0;cout<<"this is the figure:"<<endl;hwj_figure();/cout<<"-1生成完全图-"<<endl; hwj_initial_population();/cout<<"-2初始种群-&q

7、uot;<<endl;while(key!=GENE_NUMBER)hwj_fitness();/cout<<"-3适应度-"<<endl;hwj_choose();/cout<<"-4被选择的个体-"<<endl;hwj_cross();/cout<<"-5交叉后的种群-"<<endl;hwj_aberrance();/cout<<"-6变异后的种群-"<<endl; hwj_best();/ cout&l

8、t;<"-7找到最短路径-"<<endl; key+; cout<<" The shortest path length is:"<<Figure_best<<endl; cout<<" Shortest path is :"<<endl; for(int i=0;i<G;i+) cout<<hwji<<' ' cout<<endl;return 0;/-生成完全图-/void hwj_figure(

9、)srand(time(NULL);int i,j;for( i=0;i<G;i+)for(j=i+1;j<G;j+)Figureij=rand()%100+1; /只需要上三角信息cout<<Figureij<<' 'cout<<endl;/-交换两个数的值-/void hwj_swap(int *a,int *b)if(*a != *b) / 异或操作交换两个数字的位置 *a = *b; *b = *a; *a = *b; /-生初始种群-/void hwj_initial_population()srand(time(NUL

10、L);int aG;int i,j;for(j=0;j<G;j+)aj=j;for(i=0;i<NUMBER;i+)for(j=0;j<G;j+)hwj_swap(&aj, &aj+rand()%(G-j); Unitij=aj;/cout<<Unitij<<' ' /输出验证完全不一样的种群且个体没有重复基因/cout<<endl;/-计算适应度、选择概率、积累概率-/void hwj_fitness()int i,j;int sumNUMBER; /保存个体环路长度int temp;float SUM=0

11、.0;for(i=0;i<NUMBER;i+)temp=0;for(j=0;j<G-1;j+)if(Unitij>Unitij+1)temp+=FigureUnitij+1Unitij;elsetemp+=FigureUnitijUnitij+1; if(Uniti0>UnitiG)sumi=temp+FigureUnitiGUniti0; /计算每个个体的环路长度elsesumi=temp+FigureUniti0UnitiG; /cout<<sumi<<endl;SUM+=sumi;SUM=100000-SUM;select_probabil

12、ity0=(2000-sum0)/(SUM);accumula_probability0=select_probability0;for(i=1;i<NUMBER;i+)select_probabilityi=(2000-sumi)/(SUM); /计算选择概率accumula_probabilityi=accumula_probabilityi-1+select_probabilityi;/计算累积概率/cout<<accumula_probabilityi<<endl;/-顺序查找-/int hwj_bisearch(float temp)for(int i=

13、0;i<NUMBER;i+)if(temp<=accumula_probabilityi&&temp>accumula_probabilityi-1)return i;return -1; /-轮盘赌选择法找到被选择的个体-/void hwj_choose()int i,j;float temp=0.0;srand(time(NULL);for(i=0;i<NUMBER;i+)temp=(rand()%1000+1)/1000.0;/cout<<temp<<endl;Choose_Numberi=hwj_bisearch(temp

14、);/ cout<<Choose_Numberi<<endl; for(j=0;j<G;j+)Choose_Unitij=UnitChoose_Numberij;/cout<<Choose_Unitij<<' '/cout<<endl;/-进行交叉-/void hwj_cross()int i,j;float temp=0.0;int sum=0;int key; /交叉点int a,b;i=j=0;srand(time(NULL);for(i=0;i<NUMBER;i+)temp=(rand()%1000

15、)/1000.0;if(temp<CROSS)Crossi=1;sum+;/cout<<Crossi<<' 'i=0;/cout<<endl;if(sum%2=1)while(Crossi!=0)i+;Crossi=1; /当交叉个体数为奇数时，多增加一个交叉的个体/cout<<i<<' '<<Crossi;for(i=0;i<NUMBER;)if(Crossi=1)a=i;j=i+1;if(j<NUMBER)while(Crossj!=1)j+;b=j;i=j+1; ke

16、y=rand()%G;/ cout<<key<<endl; hwj_cross2(a,b,key);/ cout<<a<<' '<<b<<endl;elsei+;/hwj_cross2(i-1,i-1-q,key);/-利用grefenstette编码交叉-/void hwj_cross2(int a,int b,int key)int hwj1G,hwj2G; /grefenstette编码的个体int CG; /顺序表int i,j;int temp;for(i=0;i<G;i+)Ci=0;hwj

17、1i=hwj2i=0;/cout<<Choose_Unitai<<' 'for(i=0;i<G;i+)temp=0;for(j=0;j<Choose_Unitai;j+)if(Cj=0)temp+;CChoose_Unitai=1;hwj1i=temp; /grefenstette编码/cout<<hwj1i<<' '/cout<<Choose_Unitai<<' '/cout<<endl;for(i=0;i<G;i+)Ci=0;/ cout&l

18、t;<Choose_Unitbi<<' 'for(i=0;i<G;i+)temp=0;for(j=0;j<Choose_Unitbi;j+)if(Cj=0)temp+;CChoose_Unitbi=1;hwj2i=temp; /grefenstette编码/cout<<hwj2i<<' '/cout<<endl; for(i=0;i<G;i+)if(i<=key)temp=hwj1i;hwj1i=hwj2i;hwj2i=temp; /进行交叉/cout<<endl;/cou

19、t<<endl;for(i=G-1;i>=0;i-)for(j=i-1;j>=0;j-)if(hwj1j<=hwj1i)hwj1i+;Choose_Unitai=hwj1i; /反grefenstette编码/cout<<Choose_Unitai<<' '/cout<<endl;for(i=G-1;i>=0;i-)for(j=i-1;j>=0;j-)if(hwj2j<=hwj2i)hwj2i+;Choose_Unitbi=hwj2i; /反grefenstette编码/cout<<

20、Choose_Unitbi<<' '/cout<<endl;/-进行变异-/void hwj_aberrance()int i,j;int key1,key2; /双点变异float temp=0.0;int a;srand(time(NULL);for(i=0;i<NUMBER;i+)temp=(rand()%1000)/1000.0;if(temp<ABERRANCE)while(key1=rand()%G)=(key2=rand()%G)a=Choose_Unitikey1;Choose_Unitikey1=Choose_Unitike

21、y2;Choose_Unitikey2=a;/hwj_aberrance2(a,key);/-利用grefenstette编码变异-/void hwj_aberrance2(int a,int key)int CG; /顺序表int i,j;int temp;for(i=0;i<G;i+)Ci=0;hwji=0;cout<<Choose_Unitai<<' 'cout<<endl;for(i=0;i<G;i+)temp=0;for(j=0;j<Choose_Unitai;j+)if(Cj=0)temp+;CChoose_Unitai=