精华内容
下载资源
问答
  • 遗传算法求解TSP旅行商问题C语言源代码。人工智能经典算法
  • 1.遗传算法是什么? 遗传算法的概念是由Holland于1973年受生物进化论的启发而首次提出的,它是一种通过模拟生物界自然选择和遗传机制的随机搜索算法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换...

    1.遗传算法是什么?

    遗传算法的概念是由Holland于1973年受生物进化论的启发而首次提出的,它是一种通过模拟生物界自然选择和遗传机制的随机搜索算法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
    如果你能看懂并理解这段话,我觉得你已经不需要再学习本文章了~~
    解释的再直白点,遗传算法是一种启发式搜索算法,不同于以前那些朴素的类似于dfs、bfs之类的算法,遗传算法的核心是在给定的解空间中搜索全局最优解,如果不能得知所有的解空间,那么显然不能应用遗传算法这一类的智能算法。

    2.TSP问题是什么?

    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。 路径的选择目标是要求得的路径路程为所有路径之中的最小值。非常难懂的数学式子就不再罗列了~~
    由tsp问题的定义可以得知,如果要用暴力求解算法,那么tsp问题的时间复杂度就是O(n!),显然这是普通的计算机无法承受的,再进一步思考,可以采用一跳的贪心算法,给定一个起点,遍历其余所有未被访问过的城市,寻找出路径最短的那个城市,更新出发点城市。当然这样的求解方法也是劣于遗传算法的。
    接下来,具体介绍遗传算法解决tsp问题

    第一步:编码+种群初始化

    编码的原理很简单,就是用一种方法(染色体)来表示所有的解空间。
    针对于TSP问题,这是一个离散化的问题,一个既定的解就是一个所走过的城市的序列,而城市的编号为从1~city_num,所以显然可以用一个数组来维护城市序列(解空间),然后需要生成初始的种群(即一开始状态下的解空间),即从1到city_num的全排列问题。
    具体生成方式采用不断交换的思路(简单易懂)

    int chrom[sizepop+5][lenchrom+5]; // 种群
    
    void init()
    {/*种群初始化,生成sizepop个路径,一个路径就是一个城市的顺序,包含lenchrom个城市*/
    	int num = 0;
    	
    	for(int i=0;i<sizepop;i++) //chrom的下标从0开始 
    		for(int j=0;j<lenchrom;j++)
    			chrom[i][j] = j+1;
    	num++;
    		
    	while(num<sizepop)
    	{                              
    		for(int i=0;i<lenchrom-1;i++) 
    		{	for(int j=i+1;j<lenchrom;j++)
    			{ //交换,进而产生不同的路径顺序 
    				
    				swap(chrom[num][j],chrom[num][i]);
    				
    				num++;
    				if(num>=sizepop)
    					break; 
    			}
    			if(num>=sizepop) break;
    		}
    		
    	/*如果经过上述方式后,还是无法生成足够的染色体,则需要通过随机交换的方式进行补充*/
    		while(num<sizepop)
    		{
    			double r1 = ((double)rand()/(RAND_MAX+1.0)); //0~1之间的小数(不会等于1) 
    			double r2 = ((double)rand()/(RAND_MAX+1.0));
    			int p1 = (int)(lenchrom*r1); //位置1,范围为 [0,lenchrom-1],因为下标从0开始,所以不会等于lenchrom 
    			int p2 = (int)(lenchrom*r2); //位置2
    		
    			swap(chrom[num][p1],chrom[num][p2]);
    			num++; 
    		}
    	}	
    } 
    

    第二步:确定适应度函数

    进化论中的适应度,是表示某一个体对环境的适应能力,也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数,是用来判断群体中的个体的优劣程度的指标,它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息,仅用评估函数来评估个体或解的优劣,并作为以后遗传操作的依据。
    简单来说就是,遗传算法选择后代的依据就是适应度函数,一个种群中谁的适应度高,我就选择谁留下来! 而针对TSP问题,一个个体的适应度显然就是它从第一个城市出发,游历一周后回到出发点城市所走过的距离的倒数(距离越小,适应度越大)

    double distance(double *city1,double *city2)
    { // 计算两个城市(即两个点)的距离 
    	double x1,x2,y1,y2,dis;
    	x1 = *city1; x2 = *city2;
    	y1 = *(city1+1); y2 = *(city2+1);
    	
    	dis = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    	return dis; 
    }
    
    double path_len(int *arr)
    { //求解一条路径的长度,它的倒数即为适应度
    	double path = 0;//初始化路径长度
    	int index = *arr;   //定位到第一个城市的序号(从1开始的,所以下面定位到数组时要注意减1) 
    	
    	for(int i=0;i<lenchrom-1;i++)
    	{
    		int index1 = *(arr+i); //下标为i的城市 
    		int index2 = *(arr+i+1);// city_pos储存某个城市的x坐标,y坐标 
    		double dis = distance(city_pos[index1-1],city_pos[index2-1]);
    		path+=dis;
    	} 
    /*
    注意:tsp问题要求最后要回到起始位置
    */	int last_index = *(arr+lenchrom-1);//最后一个城市的序号
    	int first_index = *arr;//第一个城市的序号
    	double last_dis = distance(city_pos[last_index-1],city_pos[first_index-1]);
    	path+=last_dis;
    	
    	return path; //返回走完这条路径所需要的总长度 
    } 
    
    

    第三步:选择操作

    个体被选中的概率与适应度成正比,适应度越高,个体被选中的概率越大。最简单直接的选择算子就是轮盘赌算法,求出每个个体的适应度概率,再求出每个个体的累积适应度概率,生成一个随机数,与累积适应度概率进行比较,从而确定选择哪个个体保留下来!不懂轮盘赌算法的可以去查阅资料,这里只通过代码来介绍。

    void choice()
    { // 选择操作 
    	double pick;//随机数选择概率 
    	double choice_arr[sizepop+5][lenchrom+5];//中间变量,存储选择到的个体 
    	double fit_pro[sizepop]; //每个个体适应度占总适应度和的概率 
    	double sum = 0;   //该种群所有个体的适应度之和 
    	double fit[sizepop+5]; //适应度函数的数组(距离的倒数)
    	
    	for(int j=0;j<sizepop;j++)
    	{
    		double path = path_len(chrom[j]);//第j个个体的路径长度
    		double fitness = 1/path; //适应度
    		fit[j] = fitness; 
    		sum+=fit[j];	 //总适应度
    	} 
    	
    	for(int j=0;j<sizepop;j++)
    		fit_pro[j] = fit[j]/sum; //适应度的概率数组 
    	
    //开始轮盘赌(注意是累计概率)
    	for(int i=0;i<sizepop;i++)
    	{
    		pick = ((double)rand())/RAND_MAX; //0-1之间的随机数	
    		
    		while(pick<0.0001)  //如果生成的随机数太小,则需要抛弃 
    			pick = ((double)rand())/RAND_MAX;
    		
    		for(int j=0;j<sizepop;j++)
    		{
    			pick-=fit_pro[j];
    			if(pick<=0)
    			{
    				for(int k=0;k<lenchrom;k++)
    					choice_arr[i][k] = chrom[j][k];//选中一个个体
    				break; 
    			}
    		}
    	} 
    	
    //轮盘赌结束后,把数组重新转移到chrom中
    	for(int i=0;i<sizepop;i++)
    		for(int j=0;j<lenchrom;j++)
    			chrom[i][j] = choice_arr[i][j]; 
    } 
    

    第四步:交叉操作

    交叉操作是遗传算法最重要的操作,是产生新个体的主要来源,直接关系到算法的全局寻优能力。
    我采用的交叉算子是Partial-Mapped Crossover (PMX)部分交叉,但是注意:编写代码的时候要合理地变通,因为会存在多对多映射的关系,所以我采用单个交换,交换多次的思想,然后只需要解决一个冲突,从而避免了出现多对多映射的状况。

    
    void cross()
    {
    	double pick;
    	double pick1;
    	int choice1,choice2;//选择的个体的序号
    	int pos1;  
    	int move = 0; //当前移动的位置
    	
    	while(move<sizepop-1)
    	{
    		pick = ((double)rand())/RAND_MAX; //0-1之间的随机数	
    		
    		if(pick<pcross)
    		{
    			move+=2;
    			continue; //本次不进行交叉操作	
    		}	
    	//采用部分映射方法进行交叉 
    		choice1 = move; //用于选取交叉的两个父代 
    		choice2 = move+1;  //注意避免下标越界 
    		
    		int cross_num = lenchrom/2;
    		
    		while(cross_num--)
    		{
    			pick1 = ((double)rand()/(RAND_MAX+1.0)); //0~1之间的小数(不会等于1) 
    			pos1 = (int)(pick1*lenchrom); //杂交点的第一个位置,[0,lenchrom-1] 
    			
    			swap(chrom[choice1][pos1],chrom[choice2][pos1]);//单点交换,执行多次 
    	
    			for(int i=0;i<lenchrom;i++)
    			{//解决冲突,因为一个染色体中,一个城市的序号只能出现一次!
    				if(i == pos1) continue;
    				if(chrom[choice1][i] == chrom[choice1][pos1])
    					chrom[choice1][i] = chrom[choice2][pos1];
    				if(chrom[choice2][i] == chrom[choice2][pos1])
    					chrom[choice2][i] = chrom[choice1][pos1];
    			}		
    		} 
    		move+=2;
    	} 
    }  
    

    第五步:变异操作

    变异操作比较简单,对于某个给定的染色体(即城市序列),随机选择两个position,交换这两个位置上的城市编号即可,代码实现比较简单。
    遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时,利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象。此时收敛概率应取较大值。

    
    void mutation()
    {
    	double pick,pick1,pick2;
    	int pos1,pos2,temp;
    	
    	for(int i=0;i<sizepop;i++)
    	{
    		pick = ((double)rand())/RAND_MAX; //0-1之间的随机数	
    		
    		if(pick>pmutation)
    			continue;
    		pick1 = ((double)rand()/(RAND_MAX+1.0)); //0~1之间的小数(不会等于1) 
    		pick2 = ((double)rand()/(RAND_MAX+1.0)); //0~1之间的小数(不会等于1) 
    		pos1 = (int)(lenchrom*pick1); //变异位置的选取 
    		pos2 = (int)(lenchrom*pick2); 
    		
    		while(pos1>lenchrom-1)
    		{//当然,此情况不可能发生 
    			pick1 = ((double)rand())/(RAND_MAX+1.0);
                pos1 = (int)(pick1*lenchrom);	
    		} 
    		while(pos2 > lenchrom-1)
            {
                pick2 = ((double)rand())/(RAND_MAX+1.0);
                pos2 = (int)(pick2*lenchrom);
            }
    		swap(chrom[i][pos1],chrom[i][pos2]);
    	}
    }
    

    第六步: 进化逆转操作

    参考资料:https://www.cnblogs.com/lyrichu/p/6152928.html
    具体思路为:对于给定的一个染色体(城市序列),随机生成一个区间(即两个随机数之间),然后逆转这个区间的城市序号,操作即完成!

    
    void reverse()
    {
    	double pick1,pick2;
    	double dis,reverse_dis;//逆转前的距离,逆转后的距离。如果逆转后的距离变大了,显然不保留此次逆转结果
    	int n;
        int flag,pos1,pos2,temp;
        int reverse_arr[lenchrom];//暂时储存逆转后的城市序列
        
        for(int i=0;i<sizepop;i++)
        { //对所有的个体都要进行一遍逆转操作 
        	flag = 0; //用于控制本次逆转是否有效(如果无效则不会进行逆转)
    		int re_num = 0; 
    		while(flag == 0)
    		{
    			pick1 = ((double)rand())/(RAND_MAX+1.0);//[0,1) 之间的浮点数 
                pick2 = ((double)rand())/(RAND_MAX+1.0);	
                pos1 = (int)(pick1*lenchrom); // 选取进行逆转操作的位置
                pos2 = (int)(pick2*lenchrom);//得到的结果为 [0,lenchrom-1] 
    
                while(pos1 > lenchrom-1)
                { //我认为是没有作用的操作!!! 
                    pick1 = ((double)rand())/(RAND_MAX+1.0);
                    pos1 = (int)(pick1*lenchrom);
                }
                while(pos2 > lenchrom -1)
                {
                    pick2 = ((double)rand())/(RAND_MAX+1.0);
                    pos2 = (int)(pick2*lenchrom);
                }
                
    			if(pos1 > pos2)
                	swap(pos1,pos2);// 交换使得pos1 <= pos2
                
                if(pos1<pos2)
                {//如果pos1==pos2,也就没有逆转的必要了
    				for(int j=0;j<lenchrom;j++)
    					reverse_arr[j] = chrom[i][j]; //先复制一遍chrom数组
    				
    				n = 0;//逆转进行的元素数目
    				
    				for(int j=pos1;j<=pos2;j++)
    				{
    					reverse_arr[j] = chrom[i][pos2-n];
    					n++;	
    				} 
                	
                	reverse_dis = path_len(reverse_arr); //逆转后的距离 
                	dis = path_len(chrom[i]); //初始没有逆转前的距离 
    				if(reverse_dis<dis)
    				{
    					for(int j=0;j<lenchrom;j++)
    						chrom[i][j] = reverse_arr[j]; //更新个体 
    					flag = 1;   
    				} 
    			}
    			re_num++;
    			if(re_num==10) break;// 防止因一直没有更好的逆转路径而陷入死循环 
    		} 
    	}
    }
    

    最后确定终止条件,可以设置终止代数maxgen=200,然后综合调用这些函数即可求得结果。虽然有时候遗传算法因为算子的原因无法做到逐代收敛,但是对于全局最优解的求解结果还是不错的!

    展开全文
  • 遗传算法解决TSP问题

    2013-12-12 21:28:41
    本实验采用遗传算法实现了旅行商问题的模拟求解,并在同等规模问题上用最小生成树算法做了一定的对比工作。遗传算法在计算时间和占用内存上,都远远优于最小生成树算法。 程序采用Microsoft visual studio 2008 结合...
  • 这一次,我再以经典的TSP问题为例,更加深入地说明遗传算法中选择、交叉、变异等核心步骤的实现。而且这一次解决的是离散型问题,上一次解决的是连续型问题,刚好形成对照。 首先介绍一下TSP问题TSP(traveling ...

    上一次我们使用遗传算法求解了一个较为复杂的多元非线性函数的极值问题,也基本了解了遗传算法的实现基本步骤。这一次,我再以经典的TSP问题为例,更加深入地说明遗传算法中选择、交叉、变异等核心步骤的实现。而且这一次解决的是离散型问题,上一次解决的是连续型问题,刚好形成对照。

         首先介绍一下TSP问题。TSP(traveling salesman problem,旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还没有找到一个多项式时间的有效算法。TSP问题可以描述为:已知n个城市之间的相互距离,某一旅行商从某一个城市出发,访问每个城市一次且仅一次,最后回到出发的城市,如何安排才能使其所走的路线最短。换言之,就是寻找一条遍历n个城市的路径,或者说搜索自然子集X={1,2,...,n}(X的元素表示对n个城市的编号)的一个排列P(X)={V1,V2,....,Vn},使得Td=∑d(Vi,Vi+1)+d(Vn,V1)取最小值,其中,d(Vi,Vi+1)表示城市Vi到Vi+1的距离。TSP问题不仅仅是旅行商问题,其他许多NP完全问题也可以归结为TSP问题,如邮路问题,装配线上的螺母问题和产品的生产安排问题等等,也使得TSP问题的求解具有更加广泛的实际意义。

      再来说针对TSP问题使用遗传算法的步骤。

      (1)编码问题:由于这是一个离散型的问题,我们采用整数编码的方式,用1~n来表示n个城市,1~n的任意一个排列就构成了问题的一个解。可以知道,对于n个城市的TSP问题,一共有n!种不同的路线。

      (2)种群初始化:对于N个个体的种群,随机给出N个问题的解(相当于是染色体)作为初始种群。这里具体采用的方法是:1,2,...,n作为第一个个体,然后2,3,..n分别与1交换位置得到n-1个解,从2开始,3,4,...,n分别与2交换位置得到n-2个解,依次类推。(如果这样还不够初始种群的数量,可以再考虑n,n-1,...,1这个序列,然后再按照相同的方法生成,等等)

      (3)适应度函数:设一个解遍历初始行走的总距离为D,则适应度fitness=1/D.即总距离越高,适应度越低,总距离越低(解越好),适应度越高。

      (4) 选择操作:个体被选中的概率与适应度成正比,适应度越高,个体被选中的概率越大。这里仍然采用轮盘赌法。

        (5) 交叉操作:交叉操作是遗传算法最重要的操作,是产生新个体的主要来源,直接关系到算法的全局寻优能力,这里采用部分映射交叉。比如对于n=10的情况,对于两个路径:            1 2 4 5 6 3   9 10 8 7

                                  3 9 7 6 8 10 5  1  2  4

    随机产生两个[1,10]之间的随机数r1,r2,代表选择交叉的位置,比如r1=2,r2=4,如上图标红的位置,将第一个个体r1到r2之间的基因(即城市序号)与第二个个体r1到r2之间的基因交换,交换之后变为:

                                  1 9 7 6 6 3   9 10 8 7

                                  3 2 4 5 8 10 5  1  2  4

    黄色部分表示交叉过来的基因,这个时候会发现可能交叉过来的基因与原来其他位置上的基因有重复,容易直到,第一个个体重复基因的数目与第二个个体重复基因的数目是相同的(这里都是3个),只需要把第一个个体重复的基因(用绿色标识)与第二个个体重复的基因做交换,即可以消除冲突。消除冲突之后的解如下:

                                  1 9 7 6 5 3   2 10 8 4

                                  3 2 4 5 8 10 6  1  9  7

       (6)变异操作:变异操作采取对于一个染色体(即个体)随机选取两个基因进行交换的策略。比如对于染色体:

                          2 4 6 10 3 1 9 7 8 5

    随机选取了两个位置p1=3,p2=8(标红位置),交换这两个位置的基因,得到新的染色体为:

                          2 4 7 10 3 1 9 6 8 5

    (7) 进化逆转操作:这个是标准的遗传算法没有的,是我们为了加速进化而加入的一个操作。这里的进化是指逆转操作具有单向性,即只有逆转之后个体变得更优才会执行逆转操作,否则逆转无效。具体的方法是,随机产生[1,10](这里仍然以10个城市为例)之间的两个随机数r1和r2(其实也是允许相同的,只是r1,r2相同之后,逆转自然无效,设置交叉变异都是无效的,但是这不会经常发生),然后将r1和r2之间的基因进行反向排序。比如对于染色体:

              1 3 4 2 10  9 8 7 6 5

    r1=3,r2=5,它们之间的基因(标红位置)反向排列之后得到的染色体如下:

              1 3 10 2 4  9 8 7 6 5

     

    根据以上的步骤,我们就可以比较容易写出用遗传算法求解TSP问题的具体代码了,这里仍然使用C语言。先以规模比较小的城市为例,这里取14个,城市之间的距离会直接在代码中给出。代码如下:

    /*
     *遗传算法(GA) 解决TSP 问题
     *案例参考自《MATLAB 智能算法30个案例分析》
     *本例以14个城市为例,14个城市的位置坐标如下(括号内第一个元素为X坐标,第二个为纵坐标):1:(16.47,96.10)  2:(16.47,94.44)  3:(20.09,92.54)
     *4:(22.39,93.37) 5:(25.23,97.24)  6:(22.00,96.05) 7:(20.47,97.02)  8:(17.20,96.29) 9:(16.30,97.38) 10:(14.05,98.12) 11:(16.53,97.38)
     *12:(21.52,95.59)  13:(19.41,97.13)  14:(20.09,92.55)
     *遗传算法实现的步骤为:(1)编码 (2) 种群初始化 (3) 构造适应度函数 (4) 选择操作 (5) 交叉操作 (6) 变异操作 (7) 进化逆转操作
     * 具体实现的步骤这里不详细说,参考《MATLAB 智能算法30个案例分析》P38 - P40
     * update in 16/12/4
     * author:Lyrichu
     * email:919987476@qq.com
     */
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<time.h>
    #define maxgen 200  // 最大进化代数
    #define sizepop 100 // 种群数目
    #define pcross 0.6 // 交叉概率
    #define pmutation 0.1 // 变异概率
    #define lenchrom 14 // 染色体长度(这里即为城市个数)
    double city_pos[lenchrom][2] = {{16.47,96.10},{16.47,94.44},{20.09,92.54},{22.39,93.37},{25.23,97.24},{22.00,96.05},{20.47,97.02},
        {17.20,96.29},{16.30,97.38},{14.05,98.12},{16.53,97.38},{21.52,95.59},{19.41,97.13},{20.09,92.55}}; // 定义二维数组存放14个城市的X、Y坐标
    int chrom[sizepop][lenchrom]; // 种群
    int best_result[lenchrom]; // 最佳路线
    double min_distance; // 最短路径长度
    
    // 函数声明
    void init(void); // 种群初始化函数
    double distance(double *,double *); // 计算两个城市之间的距离
    double * min(double *); // 计算距离数组的最小值
    double path_len(int *); // 计算某一个方案的路径长度,适应度函数为路线长度的倒数
    void Choice(int [sizepop][lenchrom]); // 选择操作
    void Cross(int [sizepop][lenchrom]); // 交叉操作
    void Mutation(int [sizepop][lenchrom]); // 变异操作
    void Reverse(int [sizepop][lenchrom]); // 逆转操作
    
    // 种群初始化
    void init(void)
    {
        int num = 0;
        while(num < sizepop)
        {
            for(int i=0;i<sizepop;i++)
                for(int j=0;j<lenchrom;j++)
                    chrom[i][j] = j+1;
            num++;
            for(int i=0;i<lenchrom-1;i++)
            {
                for(int j=i+1;j<lenchrom;j++)
                {
                    int temp = chrom[num][i];
                    chrom[num][i] = chrom[num][j];
                    chrom[num][j] = temp; // 交换第num个个体的第i个元素和第j个元素
                    num++;
                    if(num >= sizepop)
                        break;
                }
                if(num >= sizepop)
                    break;
            }
            // 如果经过上面的循环还是无法产生足够的初始个体,则随机再补充一部分
            // 具体方式就是选择两个基因位置,然后交换
            while(num < sizepop)
            {
                double r1 = ((double)rand())/(RAND_MAX+1.0);
                double r2 = ((double)rand())/(RAND_MAX+1.0);
                int p1 = (int)(lenchrom*r1); // 位置1
                int p2 = (int)(lenchrom*r2); // 位置2
                int temp = chrom[num][p1];
                chrom[num][p1] = chrom[num][p2];
                chrom[num][p2] = temp;    // 交换基因位置
                num++;
            }
        }
    }
    
    // 距离函数
    double distance(double * city1,double * city2)
    {
        double x1 = *city1;
        double y1 = *(city1+1);
        double x2 = *(city2);
        double y2 = *(city2+1);
        double dis = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        return dis;
    }
    // min()函数
    double * min(double * arr)
    {
        static double best_index[2];
        double min_dis = *arr;
        double min_index = 0;
        for(int i=1;i<sizepop;i++)
        {
            double dis = *(arr+i);
            if(dis < min_dis)
            {
                min_dis = dis;
                min_index = i;
            }
        }
        best_index[0] = min_index;
        best_index[1] = min_dis;
        return best_index;
    }
    
    // 计算路径长度
    double path_len(int * arr)
    {
        double path = 0; // 初始化路径长度
        int index = *arr; // 定位到第一个数字(城市序号)
        for(int i=0;i<lenchrom-1;i++)
        {
            int index1 = *(arr+i);
            int index2 = *(arr+i+1);
            double dis = distance(city_pos[index1-1],city_pos[index2-1]);
            path += dis;
        }
        int last_index = *(arr+lenchrom-1); // 最后一个城市序号
        int first_index = *arr; // 第一个城市序号
        double last_dis = distance(city_pos[last_index-1],city_pos[first_index-1]);
        path = path + last_dis;
        return path; // 返回总的路径长度
    }
    
    // 选择操作
    void Choice(int chrom[sizepop][lenchrom])
    {
        double pick;
        double choice_arr[sizepop][lenchrom];
        double fit_pro[sizepop];
        double sum = 0;
        double fit[sizepop]; // 适应度函数数组(距离的倒数)
        for(int j=0;j<sizepop;j++)
        {
            double path = path_len(chrom[j]);
            double fitness = 1/path;
            fit[j] = fitness;
            sum += fitness;
        }
        for(int j=0;j<sizepop;j++)
        {
            fit_pro[j] = fit[j]/sum; // 概率数组
        }
        // 开始轮盘赌
        for(int i=0;i<sizepop;i++)
        {
            pick = ((double)rand())/RAND_MAX; // 0到1之间的随机数  
            for(int j=0;j<sizepop;j++)
            {
                pick = pick - fit_pro[j];
                if(pick<=0)
                {
                    for(int k=0;k<lenchrom;k++)
                        choice_arr[i][k] = chrom[j][k]; // 选中一个个体
                    break;    
                }
            }
    
        }
        for(int i=0;i<sizepop;i++)
        {
            for(int j=0;j<lenchrom;j++)
                chrom[i][j] = choice_arr[i][j];
        }
    }
    
    //交叉操作
    void Cross(int chrom[sizepop][lenchrom])
    {
        double pick;
        double pick1,pick2;
        int choice1,choice2;
        int pos1,pos2;
        int temp;
        int conflict1[lenchrom]; // 冲突位置
        int conflict2[lenchrom];
        int num1,num2;
        int index1,index2;
        int move = 0; // 当前移动的位置
        while(move<lenchrom-1)
        {
            pick = ((double)rand())/RAND_MAX; // 用于决定是否进行交叉操作
            if(pick > pcross)
            {
                move += 2;
                continue; // 本次不进行交叉
            }
            // 采用部分映射杂交
            choice1 = move; // 用于选取杂交的两个父代
            choice2 = move+1; // 注意避免下标越界
            pick1 = ((double)rand())/(RAND_MAX+1.0);
            pick2 = ((double)rand())/(RAND_MAX+1.0);
            pos1 = (int)(pick1*lenchrom); // 用于确定两个杂交点的位置
            pos2 = (int)(pick2*lenchrom); 
            while(pos1 > lenchrom -2 || pos1 < 1)
            {
                pick1 = ((double)rand())/(RAND_MAX+1.0);
                pos1 = (int)(pick1*lenchrom);
            }
            while(pos2 > lenchrom -2 || pos2 < 1)
            {
                pick2 = ((double)rand())/(RAND_MAX+1.0);
                pos2 = (int)(pick2*lenchrom);
            }
            if(pos1 > pos2)
            {
                temp = pos1;
                pos1 = pos2;
                pos2 = temp; // 交换pos1和pos2的位置
            }
            for(int j=pos1;j<=pos2;j++)
            {
                temp = chrom[choice1][j];
                chrom[choice1][j] = chrom[choice2][j];
                chrom[choice2][j] = temp; // 逐个交换顺序
            }
            num1 = 0;
            num2 = 0;
            if(pos1 > 0 && pos2 < lenchrom-1)
            {
                for(int j =0;j<=pos1-1;j++)
                {
                    for(int k=pos1;k<=pos2;k++)
                    {
                        if(chrom[choice1][j] == chrom[choice1][k])
                        {
                            conflict1[num1] = j;
                            num1++;
                        }
                        if(chrom[choice2][j] == chrom[choice2][k])
                        {
                            conflict2[num2] = j;
                            num2++;
                        }
                    }
                }
                for(int j=pos2+1;j<lenchrom;j++)
                {
                    for(int k=pos1;k<=pos2;k++)
                    {
                        if(chrom[choice1][j] == chrom[choice1][k])
                        {
                            conflict1[num1] = j;
                            num1++;
                        }
                        if(chrom[choice2][j] == chrom[choice2][k])
                        {
                            conflict2[num2] = j;
                            num2++;                     
                        }                 
                    }
    
                }
            }
            if((num1 == num2) && num1 > 0)
            {
                for(int j=0;j<num1;j++)
                {
                    index1 = conflict1[j];
                    index2 = conflict2[j];
                    temp = chrom[choice1][index1]; // 交换冲突的位置
                    chrom[choice1][index1] = chrom[choice2][index2];
                    chrom[choice2][index2] = temp;
                }
            }
            move += 2;
        }
    }
    
    // 变异操作
    // 变异策略采取随机选取两个点,将其对换位置
    void Mutation(int chrom[sizepop][lenchrom])
    {
        double pick,pick1,pick2;
        int pos1,pos2,temp;
        for(int i=0;i<sizepop;i++)
        {
             pick = ((double)rand())/RAND_MAX; // 用于判断是否进行变异操作
            if(pick > pmutation)
                continue;
            pick1 = ((double)rand())/(RAND_MAX+1.0);
            pick2 = ((double)rand())/(RAND_MAX+1.0);
            pos1 = (int)(pick1*lenchrom); // 选取进行变异的位置
            pos2 = (int)(pick2*lenchrom);
            while(pos1 > lenchrom-1)
            {
                pick1 = ((double)rand())/(RAND_MAX+1.0);
                pos1 = (int)(pick1*lenchrom);
            }
            while(pos2 > lenchrom-1)
            {
                pick2 = ((double)rand())/(RAND_MAX+1.0);
                pos2 = (int)(pick2*lenchrom);
            }
            temp = chrom[i][pos1];
            chrom[i][pos1] = chrom[i][pos2];
            chrom[i][pos2] = temp;
        }
    }
    
    // 进化逆转操作
    void Reverse(int chrom[sizepop][lenchrom])
    {
        double pick1,pick2;
        double dis,reverse_dis;
        int n;
        int flag,pos1,pos2,temp;
        int reverse_arr[lenchrom];
        
        for(int i=0;i<sizepop;i++)
        {
            flag = 0; // 用于控制本次逆转是否有效
            while(flag == 0)
            {
                pick1 = ((double)rand())/(RAND_MAX+1.0);
                pick2 = ((double)rand())/(RAND_MAX+1.0);
                pos1 = (int)(pick1*lenchrom); // 选取进行逆转操作的位置
                pos2 = (int)(pick2*lenchrom);
                while(pos1 > lenchrom-1)
                {
                    pick1 = ((double)rand())/(RAND_MAX+1.0);
                    pos1 = (int)(pick1*lenchrom);
                }
                while(pos2 > lenchrom -1)
                {
                    pick2 = ((double)rand())/(RAND_MAX+1.0);
                    pos2 = (int)(pick2*lenchrom);
                }
                if(pos1 > pos2)
                {
                    temp = pos1;
                    pos1 = pos2;
                    pos2 = temp; // 交换使得pos1 <= pos2
                }
                if(pos1 < pos2)
                {
                    for(int j=0;j<lenchrom;j++)
                        reverse_arr[j] = chrom[i][j]; // 复制数组
                    n = 0; // 逆转数目
                    for(int j=pos1;j<=pos2;j++)
                    {
                        reverse_arr[j] = chrom[i][pos2-n]; // 逆转数组
                        n++; 
                    }
                    reverse_dis = path_len(reverse_arr); // 逆转之后的距离
                    dis = path_len(chrom[i]); // 原始距离
                    if(reverse_dis < dis)
                    {
                        for(int j=0;j<lenchrom;j++)
                            chrom[i][j] = reverse_arr[j]; // 更新个体
                    }
                }
                flag = 1;
            }    
    
        }   
    }
    
    // 主函数
    int main(void)
    {
        time_t start,finish;
        start = clock(); // 开始计时
        srand((unsigned)time(NULL)); // 初始化随机数种子
        init(); // 初始化种群
    
        int best_fit_index = 0; //最短路径出现代数
        double distance_arr[sizepop];
        double dis;
        for(int j=0;j<sizepop;j++)
        {
            dis = path_len(chrom[j]);
            distance_arr[j] = dis;
        }
        double * best_index = min(distance_arr); // 计算最短路径及序号
        min_distance = *(best_index+1); // 最短路径
        int index = (int)(*best_index); // 最短路径序号
        for(int j=0;j<lenchrom;j++)
            best_result[j] = chrom[index][j]; // 最短路径序列
    
        // 开始进化
        double * new_arr;
        double new_min_dis;
        int new_index;
        for(int i=0;i<maxgen;i++) 
        {
            Choice(chrom); // 选择
            Cross(chrom); //交叉
            Mutation(chrom); //变异
            Reverse(chrom); // 逆转操作
            for(int j=0;j<sizepop;j++)
                distance_arr[j] = path_len(chrom[j]); // 距离数组
            new_arr = min(distance_arr);
            new_min_dis = *(new_arr+1); //新的最短路径
            if(new_min_dis < min_distance)
            {
                min_distance = new_min_dis; // 更新最短路径
                new_index =(int)(*new_arr);
                for(int j=0;j<lenchrom;j++)
                    best_result[j] = chrom[new_index][j]; // 更新最短路径序列
                best_fit_index = i+1; // 最短路径代数
            }
        }
    finish = clock(); // 计算结束
    double duration = ((double)(finish-start))/CLOCKS_PER_SEC; // 计算耗时
    printf("本程序使用遗传算法求解规模为%d的TSP问题,种群数目为:%d,进化代数为:%d\n",lenchrom,sizepop,maxgen);
    printf("得到最短路径为:%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d-->%d\n",best_result[0],best_result[1],best_result[2],
            best_result[3],best_result[4],best_result[5],best_result[6],best_result[7],best_result[8],best_result[9],best_result[10],best_result[11],
            best_result[12],best_result[13]);
    printf("最短路径长度为:%lf,得到最短路径在第%d代.\n",min_distance,best_fit_index);
    printf("程序耗时:%lf秒.\n",duration);
    return 0;
    }

    这里取种群数目为100,最大进化代数为200,在ubuntu16.04下使用gcc编译器得到结果如下:

    经过多次求解发现,在到了一定代数之后最优解保持不变,而且多次求解得到的最优路径相同,可以认为求得了问题的实际最优解。但是这里城市个数只有14个,属于规模较小的TSP问题,我决定再将问题规模变大来测试遗传算法优化的性能。这里选用规模为31的中国TSP问题,首先保持种群数目和进化代数不变,得到结果如下:

    可以发现遗传算法得到的最短路径大概为16136.633514,而已知的中国TSP问题的最优解为15377,还是有一定的差距,并且算法有的时候收敛过早,陷入了局部最优解,并且稳定性较差,每次运行得到的结果波动较大。为了解决这个问题,我们决定将种群数目和进化代数增大,种群数目变为500,进化代数变为1000,重新运行程序得到的结果如下:

    多次运行程序给出的最优解相近,波动很小,其中最好的一次为上图中的15380.515324,与真实最优解15377十分接近,这说明在增大种群规模以及进化代数之后遗传算法的优化能力又得到了进一步地提高,而且不易陷入局部最优解,总是能找到接近最优解的次优解,这也充分说明了遗传算法对于求解TSP问题还是十分有效的,也说明了遗传算法的普适性。

    当然,遗传算法也有其局限性,比如对于大规模的寻优问题容易早熟,陷入局部最优等等,如果有机会我后面还会再补充这方面的内容,以及遗传算法在其他领域的应用。


    转自:http://www.cnblogs.com/lyrichu/p/6152928.html

    展开全文
  • C语言模拟遗传算法模拟TSP问题 有完整c写的程序代码可编译 有完整论文
  • #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<time.h> #define cities 10 //城市的个数 #define MAXX 100 //迭代次数 #define pc 0.8 //交配概率 ...
  • #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<time.h> #define cities 10 //城市的个数 #define MAXX 100//迭代次数 #define pc 0.8 //交配概率 ...
  • 基于Hopfield神经网络模型求解TSP问题算法,于慧,徐慧,本文给出了一种基于Hopfield神经网络模型求解TSP问题算法。Hopfield网络是一种网状网络,网络中的每个神经元都可以和其他神经元双向�
  • 遗传算法解决TSP问题(c++实现)

    万次阅读 2017-09-02 22:25:45
    遗传算法遗传算法简介  遗传算法(Genetic Algorithms,简称 GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目标的优化。遗传算法的实质是通过...

    遗传算法


    遗传算法简介

      遗传算法(Genetic Algorithms,简称 GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术,根据适者生存的原则逐代进化,最终得到最优解或准最优解。它必须做以下操作:初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对,通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体,按此方法使群体逐代进化,直到满足进化终止条件。其实现方法如下:

    1.根据具体问题确定可行解域,确定一种编码方法,能用数值串或字符串表示 可行解域的每一解。
    2.对每一解应有一个度量好坏的依据,它用一函数表示,叫做适应度函数。
    3.确定进化参数群体规模M,交叉概率 pc 、变异概率 pm 、进化终止条件。

      表2列出了生物遗传概念在遗传算法中的对应关系:

    image


    遗传算法求解TSP问题

      问题:给定平面上20个点的名称与坐标,两个点之间的距离为它们的欧几里得距离。求一条路径,刚好经过每个点1次,使其路径长度最短。

      参数设定如下:

    • 种群大小:M=50
    • 最大代数:G=1000
    • 交叉率: pc=1 ,交叉率为1能保证种群的充分进化
    • 变异率: pm=0.1 ,一般而言,变异发生的可能性较小

      在该问题中,每一条路径就是所谓的染色体(解的编码),每条路径的长度就是该个体的适应性(路径长度越短,适应性越强)。交叉操作就是选择两条路径,取一个分界点k,将两条路径分别以分界点k分成前后两段,并且将两条路径重新组合得到新的两条路径。这里的交叉操作蕴含了变异操作,但是能够让子代继承父代的优良特性。变异操作也是实现群体多样性的一种手段,也是全局寻优的保证,具体实现为,按照给定的变异率,对选定的变异的个体,随机的选取三个整数u

    遗传算法c++实现

      写了一整个下午加晚上,终于搞出来了。。仅供参考。下面是c++实现的遗传算法解决TSP问题的代码:

    输入文件 in.txt:

    20
    A 2.5 4.0
    B 1.2 -2.4
    C 8.7 1.2
    D 3.6 12.1
    E -5.5 0.94
    F -6.6 -12.6
    G 0.18 5.219
    H 12.5 14.3609
    I 22.5 -5.26
    J 1.61 4.5
    K 2.1 -5.6
    L 0 25
    M 9.2 -32
    N -1 7
    O -5 -8
    P 21 35
    Q 16 7.5
    R -21 5
    S -7 -25.5
    T 12 17.5

    c++代码:

    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <deque>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int maxn = 1e2 + 7;
    const int INF = 0x7fffffff;
    const double PI = acos(-1);
    struct Point { //点类
        string name;
        double x, y;
        int i; //编号
    };
    vector<Point> p;
    double d[maxn][maxn]; //距离矩阵
    int n;
    double sum = 0; //当前最短路径长度
    
    double dist(Point a, Point b) { //计算两点距离
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }
    
    double get_sum(vector<Point> a) { //返回路径长度
        double sum = 0;
        for (int i = 1; i < a.size(); i++) {
            sum += d[a[i].i][a[i - 1].i];
        }
        sum += d[a[0].i][a[a.size()-1].i];
        return sum;
    }
    
    void init() {                    //初始化
        srand((unsigned)time(NULL)); //设置随机数种子
        cin >> n;
        p.clear();
        for (int i = 0; i < n; i++) {
            Point t;
            cin >> t.name >> t.x >> t.y;
            t.i = i;
            p.push_back(t);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                d[i][j] = d[j][i] = dist(p[i], p[j]);
            }
        }
        sum = get_sum(p);
    }
    
    void show() { //显示当前结果
        cout << "路径长度: " << sum << endl;
        cout << "路径:";
        for (int i = 0; i < n; i++)
            cout << ' ' << p[i].name;
        puts("");
    }
    
    int w = 100;                  //限定种群只能活100个个体
    vector<vector<Point>> group; //种群,也就是染色体列表
    
    void Improve_Circle() { //改良圈法得到初始序列
        vector<Point> cur = p;
        for (int t = 0; t < w; t++) {     //重复50次
            for (int i = 0; i < n; i++) { //构造随机顺序
                int j = rand() % n;
                swap(cur[i], cur[j]);
            }
            int flag = 1;
            while (flag) {
                flag = 0;
                //不断选取uv子串,尝试倒置uv子串的顺序后解是否更优,如果更优则变更
                for (int u = 1; u < n - 2; u++) {
                    for (int v = u + 1; v < n - 1; v++) {
                        if (d[cur[u].i][cur[v + 1].i] + d[cur[u - 1].i][cur[v].i] <
                            d[cur[u].i][cur[u - 1].i] + d[cur[v].i][cur[v + 1].i]) {
                            for (int k = u; k <= (u + v) / 2; k++) {
                                swap(cur[k], cur[v - (k - u)]);
                                flag = 1;
                            }
                        }
                    }
                }
            }
            group.push_back(cur);
            double cur_sum = get_sum(cur);
            if (cur_sum < sum) {
                sum = cur_sum;
                p = cur;
            }
        }
    }
    
    vector<int> get_randPerm(int n) { //返回一个随机序列
        vector<int> c;
        for (int i = 0; i < n; i++) {
            c.push_back(i);
        }
        for (int i = 0; i < n; i++) {
            swap(c[i], c[rand() % n]);
        }
        return c;
    }
    
    //排序时用到的比较函数
    bool cmp(vector<Point> a, vector<Point> b) { return get_sum(a) < get_sum(b); }
    
    int dai = 200; //一共进行200代的进化选择
    int c[maxn];
    double bylv = 0.1; //变异率
    
    void genetic_algorithm() { //遗传算法
        vector<vector<Point>> A = group, B, C;
        // A:当前代的种群  B:交配产生的子代  C:变异产生的子代
        for (int t = 0; t < dai; t++) {
            B = A;
            vector<int> c = get_randPerm(A.size());
            for (int i = 0; i + 1 < c.size(); i += 2) {
                int F = rand() % n; //基因划分分界点
                int u=c[i],v=c[i+1];
                for (int j = F; j < n;
                     j++) { //交换随机选的2个个体的基因后半段,也就是交配
                    swap(B[u][j], B[v][j]);
                }
                //交换后可能发生冲突,需要解除冲突
                //保留F前面的部分不变,F后面的部分有冲突则交换
                int num1[1000]={0},num2[1000]={0};
                for(int j=0;j<n;j++){
                    num1[B[u][j].i]++;
                    num2[B[v][j].i]++;
                }
                vector<Point> v1;
                vector<Point> v2;
                for(int j=0;j<n;j++){
                    if(num1[B[u][j].i]==2){
                        v1.push_back(B[u][j]);
                    }
                }
                for(int j=0;j<n;j++){
                    if(num2[B[v][j].i]==2){
                        v2.push_back(B[v][j]);
                    }
                }
                int p1=0,p2=0;
                for(int j=F;j<n;j++){
                    if(num1[B[u][j].i]==2){
                        B[u][j]=v2[p2++];
                    }
                    if(num2[B[v][j].i]==2){
                        B[v][j]=v1[p1++];
                    }
                }
    
            }
            C.clear();
            int flag=1;
            for (int i = 0; i < A.size(); i++) {
                if (rand() % 100 >= bylv * 100)
                    continue;
                //对于变异的个体,取3个点u<v<w,把子串[u,v]插到w后面
                int u, v, w;
                u = rand() % n;
                do {
                    v = rand() % n;
                } while (u == v);
                do {
                    w = rand() % n;
                } while (w == u || w == v);
                if (u > v)
                    swap(u, v);
                if (v > w)
                    swap(v, w);
                if (u > v)
                    swap(u, v);
    
                vector<Point> vec;
                for (int j = 0; j < u; j++)
                    vec.push_back(A[i][j]);
                for (int j = v; j < w; j++)
                    vec.push_back(A[i][j]);
                for (int j = u; j < v; j++)
                    vec.push_back(A[i][j]);
                for (int j = w; j < n; j++)
                    vec.push_back(A[i][j]);
                C.push_back(vec);
            }
            //合并A,B,C
            for (int i = 0; i < B.size(); i++) {
                A.push_back(B[i]);
            }
            for (int i = 0; i < C.size(); i++) {
                A.push_back(C[i]);
            }
            sort(A.begin(), A.end(), cmp); //从小到大排序
            vector<vector<Point>> new_A;
            for (int i = 0; i < w; i++) {
                new_A.push_back(A[i]);
            }
            A = new_A;
        }
        group = A;
        sum = get_sum(group[0]);
        p = group[0];
    }
    
    int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
        init();
        cout << "初始";
        show();
        cout << "改良圈法";
        Improve_Circle();
        show();
        cout << "遗传算法";
        genetic_algorithm();
        show();
        return 0;
    }

    运行结果(每次不一样,多调用几次取最好的):

    初始路径长度: 501.075路径: A B C D E F G H I J K L M N O P Q R S T改良圈法路径长度: 224.548
    路径: A J G N R E B K O F S M I C Q H T P L D
    遗传算法路径长度: 221.983
    路径: J G N D L P T H Q I M S F O R E B K C A
    展开全文
  • 遗传算法解决10城市TSP问题程序源代码
  • 使用遗传算法求解中国旅行商问题(31个城市),数据从文件中(网上找到)读取。求得的最好结果是:15397.5km(不是每次都能有这个解),比介绍算法的人工智能上说的15404km略短,编程环境Visual studio2013,所以个别...
  • 量子遗传算法代码

    2016-08-30 11:32:30
    量子遗传算法,一步一步,注释详尽
  • c语言文件,c++编译通过。贪婪交叉算子,遗传算法解决TSP问题
  • 1.2 TSP问题也称为货郎担问题,是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的典型难题。 1.3 TSP是一个具有广泛的应用背景和重要理论...

    一、实验原理

    1. 巡回旅行商问题
      1.1给定一组n个城市和俩俩之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。
      1.2 TSP问题也称为货郎担问题,是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的典型难题。
      1.3 TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来,有很多解决该问题的较为有效的算法不断被推出,例如Hopfield神经网络方法,模拟退火方法以及遗传算法方法等。
    2. 用遗传算法求解TSP问题
      TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解,对于常规方法和现有的计算工具而言,存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题,是很自然的想法。
      2.1基本遗传算法可定义为一个8元组:
      (SGA)=(C,E,P0,M,Φ,Г,Ψ,Τ)
      C ——个体的编码方法,SGA使用固定长度二进制符号串编码方法;
      E ——个体的适应度评价函数;
      P0——初始群体;
      M ——群体大小,一般取20—100;
      Ф——选择算子,SGA使用比例算子;
      Г——交叉算子,SGA使用单点交叉算子;
      Ψ——变异算子,SGA使用基本位变异算子;
      Т——算法终止条件,一般终止进化代数为100—500;
      2.2问题的表示
      对于一个实际的待优化问题,首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP,一个旅程很自然的表示为n个城市的排列,但基于二进制编码的交叉和变异操作不能适用。
      路径表示是表示旅程对应的基因编码的最自然,最简单的表示方法。它在编码,解码,存储过程中相对容易理解和实现。例如:旅程(5-1-7-8-9-4-6-2-3)可以直接表示为(5 1 7 8 9 4 6 2 3)
      2.3产生初始种群
      一是完全随机产生,它适合于对问题的解无任何先验知识的情况。随机性较强,因而也较公正
      二是某些先验知识可转变为必须满足的一组要求,然后在满足这些要求的解中在随机地选取样本。这样选择初始种群可使遗传算法更快的达到最优解。种群有一定的目标性和代表性,但取例不如完全随机的广泛,而且先验知识是否可靠也是一个问题.
      2.4适应度函数
      遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短,路径总长度的倒数就可以为TSP的适应度函数:
      2.5选择
      一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。
      2.6交叉
      基于路径表示的编码方法,要求一个个体的染色体编码中不允许有重复的基因码,也就是说要满足任意一个城市必须而且只能访问一次的约束。基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件。
      部分匹配交叉操作要求随机选取两个交叉点,以便确定一个匹配段,根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。
      2.7变异
      遗传算法解决TSP 问题基于二进值编码的变异操作不能适用,不能够由简单的变量的翻转来实现
      在TSP问题中个体的编码是一批城市的序列,随机的在这个序列抽取两个城市,然后交换他们的位置。这样就实现了个体编码的变异,算法如下:
      产生两个0到1之间的随机实数;
      将这两个随机实数转化为0到n(城市数)-1之间的随机整数;
      将这两个随机整数指代的城市进行交换;

    二、实验内容

    1.N>=8。
    2.随即生成N个城市间的连接矩阵。
    3.指定起始城市。
    4.给出每一代的最优路线和总路线长度。
    5.以代数T作为结束条件,T>=50。

    三、实验源码

    #include <cstdint>
    #include <cstdio>
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    #include <time.h>
    #include <vector>
    using namespace std;
    
    const int city_num = 8;   //城市数量
    const int unit_num = 100; //群体规模
    double ps = 0.01;        //变异概率
    const int genmax = 50;   //最大迭代数
    //城市间距离矩阵
    int length_table[city_num][city_num] = {
        {0, 2, 3, 4, 5, 7, 3, 1},
        {2, 0, 2, 6, 3, 5, 4, 2},
        {3, 2, 0, 1, 9, 8, 7, 6},
        {4, 6, 1, 0, 5, 4, 3, 2},
        {5, 3, 9, 5, 0, 2, 1, 6},
        {7, 5, 8, 4, 2 ,0, 3, 6},
        {3, 4, 7, 3, 1, 3, 0, 5},
        {1, 2, 6, 2, 6, 6, 5, 0}
    };
    
    class Unit {
        public:
            int path[city_num+1]; //个体路径信息
            int length;         //个体代价
    };
    bool cmp(Unit u1, Unit u2) { return u1.length < u2.length; }
    bool IsEqual(Unit u1, Unit u2) {
        for (int j = 0; j < city_num; j++)
            if (u1.path[j] != u2.path[j])
                return false;
        return true;
    }
    bool IsExist(vector<Unit> temp, Unit u) {
        for (int i = 0; i < temp.size(); i++)
            if(IsEqual(temp[i],u))
                return true;
        return false;
    }
    void PrintPath(Unit u) {
        for (int j = 0; j <= city_num; j++)
            printf("%d ", u.path[j]);
    }
    class Group {
        public:
            Group();
            Unit group[unit_num];
            Unit best;
            double alllength;
            int best_gen;
            void assess();//对每个个体进行评估
            void choose_copy();
            int sort_group();
            void cross(Unit &father, Unit &mother);//交叉
            void mutation(Unit &t);//突变  
            void print();//输出信息
            void work();//种群进化
        private:
    
    };
    Group::Group() {//随机产生N个染色体组成每个种群
        best.length = 0x3f3f3f3f;
        best_gen = 0;
        int start_city;
        cout << "Please input the start city, and it should be in a range of 0~" << city_num - 1<<" : ";
        cin >> start_city;
        for (int i = 0; i < unit_num; i++) {
            group[i].path[0]=start_city;
            bool flag[city_num] = {};
            flag[start_city]=true;
            for (int j = 1; j < city_num; j++) {
                int t_city = rand() % city_num;
                while (flag[t_city])
                    t_city = rand() % city_num;
                flag[t_city] = true;
                group[i].path[j] = t_city;
            }
            group[i].path[city_num] = group[i].path[0];
        }
    }
    void Group::assess() {//计算每个个体的适应度的倒数
        alllength = 0;
        for (int k = 0; k < unit_num; k++) {
            group[k].length = 0;
            for (int i = 0; i < city_num; i++)
                group[k].length += length_table[group[k].path[i]][group[k].path[i+1]];
            alllength += 1.0/group[k].length;
        }
        //cout << "alllength: " << alllength << endl;
    }
    int Group::sort_group(){
        Unit *u = group;
        sort(u, u + unit_num, cmp); //根据评估结果排序
        return u->length;
    }
    void Group::choose_copy(){//选择-复制
        for (int i = 0; i < unit_num;i++){
            double m = 0;
            double p;
            double r = (double)rand()/RAND_MAX; //r为0至1的随机数
            for (int j = 0; j < unit_num; j++) {
                p = 1.0 / (group[j].length * alllength);
                m = m + p;
                if (r <= m){
                    for (int t = 0; t <= city_num;t++)
                        group[i].path[t] = group[j].path[t];
                    group[i].length = group[j].length;
                    //printf("第%d个个体选择的是%d\n", i+1, j+1);
                    break;
                }
            }
        }
    }
    void Group::cross(Unit &father, Unit &mother) __attribute__ ((__MINGW_ATTRIB_NO_OPTIMIZE)) {//交叉   
        bool flag1[city_num] = {};
        bool flag2[city_num] = {};
        int l = 1 + (rand() % (city_num - 1));
        int r = 1 + (rand() % (city_num - 1));
        if (l > r)
            swap(l, r);
        Unit son1, son2;
        for (int i = l; i <= r; i++){
            son1.path[i] = father.path[i];
            flag1[father.path[i]]=true;
            son2.path[i] = mother.path[i];
            flag2[mother.path[i]]=true;
        }
        for (int i = 0; i < l; i++) {//找到l~r中映射的城市,并在子种群中确定城市
            if(!flag1[mother.path[i]])
                son1.path[i] = mother.path[i];
            else {
                int temp = mother.path[i];
                int j;
                while (flag1[temp]) {
                    for (j = l; j <= r; j++)
                        if (father.path[j] == temp)
                            break;
                    temp=mother.path[j];
                }
                son1.path[i]=temp;
            }
            if(!flag2[father.path[i]])
                son2.path[i] = father.path[i];
            else {
                int temp = father.path[i];
                int j;
                while (flag2[temp]) {
                    for (j = l; j <= r; j++)
                        if (mother.path[j] == temp)
                            break;
                    temp=father.path[j];
                }
                son2.path[i]=temp;
            }
        }
        for (int i = r + 1; i <= city_num; i++){//找到l~r中映射的城市,并在子种群中确定城市
            if(!flag1[mother.path[i]])
                son1.path[i] = mother.path[i];
            else {
                int temp = mother.path[i];
                int j;
                while (flag1[temp]) {
                    for (j = l; j <= r; j++)
                        if (father.path[j] == temp)
                            break;
                    temp=mother.path[j];
                }
                son1.path[i]=temp;
            }
            if(!flag2[father.path[i]])
                son2.path[i] = father.path[i];
            else {
                int temp = father.path[i];
                int j;
                while (flag2[temp]) {
                    for (j = l; j <= r; j++)
                        if (mother.path[j] == temp)
                            break;
                    temp=father.path[j];
                }
                son2.path[i]=temp;
            }
        }
        for (int i = 0; i <= city_num;i++){
            mother.path[i] = son1.path[i];
            father.path[i] = son2.path[i];
        }
    }
    void Group::mutation(Unit &t) {//变异
        int one = 1 + (rand() % (city_num - 1));
        int two = 1 + (rand() % (city_num - 1));
        while (two == one)
            two = rand() % city_num;
        swap(t.path[one], t.path[two]); 
    }
    void Group::print(){
        for (int i = 0; i < unit_num; i++){
            printf("第%d个个体,路径信息为", i+1);
            PrintPath(group[i]);
            printf(";总权值:%d;\n", group[i].length);
        }
        printf("最优个体,路径信息为:\n");
        vector<Unit> temp;
        int length=sort_group();
        for (int i = 0; i < unit_num; i++) {
            if(group[i].length==length &&(!IsExist(temp, group[i]))){
                PrintPath(group[i]);
                cout << endl;
                temp.push_back(group[i]);
            }
        }
        printf("总权值:%d;\n", length);
        temp.clear();
    }
    void Group::work() {//遗传算法
        for (int i = 0; i < genmax; i++) {
            assess(); //评估
            if(i+1<=2||(i+1)%10==0){
                printf("第%d代:\n", i + 1);
                print();
            }
            if (best.length > group[0].length) {//
                memcpy(&best, &group[0], sizeof(group[0]));
                best_gen = i+1;
            }
            choose_copy();//选择复制
            for (int j = 0; j + 1 < unit_num; j += 2)//交叉
              cross(group[j], group[j + 1]);
            for (int j = 0; j < unit_num; j++){//变异
                int temp = rand() % 100;
                if(temp==j)
                    mutation(group[j]);
            }
            
        }
    }
    
    Unit group[unit_num]; //种群变量
    Unit bestone;         //记录最短路径
    int generation_num;   //记录当前达到了第几代
    
    int main() {
        srand((int)time(0));
        Group g;
        g.work();
        printf("求解结果路径信息为:");
        PrintPath(g.best);
        printf("; 总权值:%d; 第%d代;\n", g.best.length, g.best_gen);
        return 0;
    }
    

    四、实验结果

    第一代

    在这里插入图片描述

    第二代

    在这里插入图片描述

    第50代

    在这里插入图片描述

    展开全文
  • TSP问题 遗传算法

    2010-01-09 16:27:27
    以10个结点的TSP问题为例,用遗传算法加以求解。输出结果为迭代200次,种群规模为50时的最后一代的结果,以及本次迭代的最好的解。最优解为:0 3 5 4 9 8 1 7 6 2 0 路径长度是175.804576
  • C++TSP遗传算法

    2018-01-04 19:45:56
    在使用easyX画出城市遍历路径时需要用到easyX插件,运行文件夹内的exe可安装easyX。另提供了144个城市坐标。
  • 遗传算法C语言实现(二)

    万次阅读 2017-05-14 18:19:21
    这一次,我再以经典的TSP问题为例,更加深入地说明遗传算法中选择、交叉、变异等核心步骤的实现。而且这一次解决的是离散型问题,上一次解决的是连续型问题,刚好形成对照。  首先介绍一下TSP问题TSP...
  • 遗传算法C语言设计

    2019-01-06 18:31:04
    遗传算法求解TSP问题 换位表达、启发式交叉、启发式变异、最优选择策略 前言 本文设计遗传算法TSP问题进行求解。首先选取100个城市作为旅行过程中要经过的点,城市的坐标已知,求解一个通过每个城市一次且总距离...
  • TSP),又译为旅行推销员问题、货担郎问题,简称为TSP问题,是最基本的路线问题。假设有n个可直达的城市,一销售商从其中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能的路径中求出路径长度...
  • 遗传算法TSP问题中的应用 什么是TSP问题TSP问题是典型的组合优化问题,其也是遗传算法界中最为经典的优化问题之一。在遗算法成熟之前也一直困扰着科研人员,TSP问题又称为名旅行商问题,其定义为设有N个城市,...
  • 1、算法描述 1、介绍   商人需要经过某几个城市, 但是城市之间的距离不一, 如何规划路径, 成了一个复杂的问题。如果计算每一条可行的路径, 就需要相当大的计算资源。   代码中将20个城市ID命名为0-19,0-1-2表示...
  • 改进的遗传算法求解TSP问题 本程序只是一种思想的验证 论文讲在一个月后上传 采用C语言编程
  • 利用遗传算法解决TSP问题(C++) 本次文章的初衷 前段时间完成C++大作业,老师要求大家使用遗传算法解决TSP问题并将结果输出出来。在到处查阅资料之后发现那些破玩意也跑不了啊。于是在这里分享给大家利用C++解决该...
  • 遗传算法求解10城市的旅行商问题c语言
  • 这是我自己编的用遗传算法TSP问题的代码,有不足的地方还请大家帮忙指出来。
  • 基于C语言实现的遗传算法解决TSP背包问题 源代码.rar.rar
  • 用 C++ 和 C语言实现遗传算法 计算TSP背包问题 全部源代码.rar.rar

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 127
精华内容 50
关键字:

tsp问题遗传算法c语言

c语言 订阅