精华内容
下载资源
问答
  • 遗传算法求解TSP旅行商问题C语言源代码。人工智能经典算法
  • C语言模拟遗传算法模拟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问题为例,更加深入地说明遗传算法中选择、交叉、变异等核心步骤的实现。而且这一次解决的是离散型问题,上一次解决的是连续型问题,刚好形成对照。 首先介绍一下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语言文件,c++编译通过。贪婪交叉算子,遗传算法解决TSP问题
  • 这一次,我再以经典的TSP问题为例,更加深入地说明遗传算法中选择、交叉、变异等核心步骤的实现。而且这一次解决的是离散型问题,上一次解决的是连续型问题,刚好形成对照。  首先介绍一下TSP问题...

    https://www.cnblogs.com/lyrichu/p/6152928.html

    上一次我们使用遗传算法求解了一个较为复杂的多元非线性函数的极值问题,也基本了解了遗传算法的实现基本步骤。这一次,我再以经典的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问题还是十分有效的,也说明了遗传算法的普适性。

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

    展开全文
  • 这是我自己编的用遗传算法TSP问题的代码,有不足的地方还请大家帮忙指出来。
  • C语言编写遗传算法解决TSP旅行商问题

    千次阅读 多人点赞 2015-10-22 13:22:18
    最近在上计算智能的课,老师刚刚教了遗传算法,布置了用遗传算法解决TSP的问题的作业,于是经过几小时的奋战,终于编写完成。 首先先对TSP问题进行分析。TSP问题,也就是旅行商问题,题目的大题内容是 一位旅行商,...

    最近在上计算智能的课,老师刚刚教了遗传算法,布置了用遗传算法解决TSP的问题的作业,于是经过几小时的奋战,终于编写完成。

    首先先对TSP问题进行分析。TSP问题,也就是旅行商问题,题目的大题内容是 一位旅行商,要遍游N座城市(城市数量记为NUM_CITY), 已知每两座城市之间的位置,要求每座城市必须去且只去过一次,求遍游该N座城市的最短路程。

    利用遗传算法解决该问题,步骤如下:

    1.初始化城市之间的距离

    2.生成并初始化初始种群,种群内每个个体保存着一条完整的路径(每个城市标号出现且只出现一次)

    3.计算目前种群每个个体的适应值(要求求最短路程,路径一定是个正数,故而得到每个个体中保存的路径的总路程后,取倒数,得到的数越大,适应性越高,总路程越短)

    4.找出目前最优个体,让其直接复制至下一代(即不变异)

    5.对其他个体根据发生交叉互换的概率Pc,得到参与交叉互换的个体集合

    6.使参与交叉互换的个体随机发生交叉互换(每个个体只参与一次)交叉互换的片段起始点和终点均随机产生

    7.对除最优个体外的每个个体,根据突变概率Pm发生突变,随机产生两个位置点,使这两个位置点之间的片段进行置倒(即2345变成5432)

    8.循环执行步骤34567,直到演变代数>GENERATIONS为止(暂定为5000代)


    代码如下所示,(注释部分用的printf用于测试查错,可忽视)

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    #define RAND(X) (rand()%(X))
    #define NUM_CITY	(30)
    #define GENERATIONS	(5000)
    #define MAX_SIZE	(50)
    #define LOWEST_ALIVE	(1.0/MAX_SIZE)
    typedef struct _Group{
    	int city[NUM_CITY];
    	int adapt;
    	float pAlive;
    }Group;
    
    int cityDistance[NUM_CITY][NUM_CITY];
    Group g_Group[MAX_SIZE];
    float	Pm = 0.1;
    float	Pc = 0.8;
    int bestOne;
    void getFitness(Group &group) // 得到适应值
    {
    	int distance = 0;
    	int temp;
    	int x1, x2, y1, y2;
    	int tdistance;
    	for (int i = 1; i < NUM_CITY; i++)
    	{
    		distance += cityDistance[group.city[i - 1]][group.city[i]];
    	}
    	group.adapt = distance;
    	group.pAlive = 1 / (float)distance;
    }
    void Swap(int &a, int &b) // 交换ab值
    {
    	int c;
    	c = a;
    	a = b;
    	b = c;
    }
    void Init() // 初始化
    {
    	srand((unsigned int)time(0));
    	for (int i = 0; i < NUM_CITY; i++) // 初始化城市距离
    	{
    		for (int j = i + 1; j < NUM_CITY; j++)
    		{
    			cityDistance[i][j] = RAND(100) + 1;
    			cityDistance[j][i] = cityDistance[i][j];
    		}
    	}
    	printf("城市距离如下:\n");
    	for (int i = 0; i < NUM_CITY; i++)
    	{
    		for (int j = 0; j < NUM_CITY; j++)
    		{
    			if (j < i + 1)
    				printf("    ");
    			else
    				printf("%3d ", cityDistance[i][j]);
    		}
    		printf("\n");
    	}
    	for (int i = 0; i < MAX_SIZE; i++) // 初始化样本数列
    	{
    		for (int j = 0; j < NUM_CITY; j++)
    		{
    			g_Group[i].city[j] = j;
    		}
    	}
    	int r;
    	for (int i = 0; i < MAX_SIZE; i++) // 打乱顺序
    	{
    		for (int j = 0; j < NUM_CITY; j++)
    		{
    			r = RAND(NUM_CITY);
    			Swap(g_Group[i].city[j], g_Group[i].city[r]);
    		}
    	}
    	printf("产生初始种群如下:\n");
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		printf("第%d个个体:\n", i + 1);
    		for (int j = 0; j < NUM_CITY; j++)
    		{
    			printf("%3d ", g_Group[i].city[j]);
    		}
    		printf("\n");
    	}
    
    }
    void GetAliveP() // 存活率
    {
    	float totalAlive = 0;
    	//		选择最优部分
    	totalAlive = 0;
    	for (int i = 0; i < MAX_SIZE; i++) // 计算个体适应值
    	{
    		getFitness(g_Group[i]);
    		totalAlive += g_Group->pAlive;
    	}
    	for (int i = 0; i < MAX_SIZE; i++) // 矫正个体存活率 让总和为1
    	{
    		g_Group[i].pAlive /= totalAlive;
    	}
    	bestOne = 0;
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		if (g_Group[i].pAlive > g_Group[bestOne].pAlive)
    			bestOne = i;
    	}
    	printf("目前最佳个体为:%d, 其距离为%d,其轨迹如下:\n", bestOne+1, g_Group[bestOne].adapt);
    	for (int i = 0; i < NUM_CITY; i++)
    		printf("%d ", g_Group[bestOne].city[i]);
    	printf("\n");
    }
    int isOnIt(int num, int Array[NUM_CITY], int ignorePos, int pos1, int pos2) // num是否在Array[]的pos1到pos2之间 其中跳过ignorePos(该数字的原位置)
    {
    	for (int i = pos1; i <= pos2; i++)
    	{
    		if (Array[i] == num)
    			return i;
    	}
    	return -1;
    }
    
    void Swap(int sel1,int sel2,int pos1, int pos2) // 交叉互换
    {
    	int temp;
    	int maxSize = pos2 - pos1 + 1;
    	//printf("开始初步交叉互换\n");
    	//printf("%d %d\n", pos1, pos2);
    	for (int i = pos1; i <= pos2; i++)
    	{
    		temp = g_Group[sel1].city[i];
    		g_Group[sel1].city[i] = g_Group[sel2].city[i];
    		g_Group[sel2].city[i] = temp;
    	}
    	//for (int j = 0; j < NUM_CITY; j++)
    	//	printf("%4d", g_Group[sel1].city[j]);
    	//printf("\n");
    	//for (int j = 0; j < NUM_CITY; j++)
    	//	printf("%4d", g_Group[sel2].city[j]);
    	//printf("\n");
    	int pos;
    	//printf("开始矫正重复值\n");
    	int times = 0;
    	for (int i = 0; i < NUM_CITY; i++) // 矫正重复值
    	{
    		times = 0;
    		if (i >= pos1 && i <= pos2)
    		{
    			i = pos2;
    			continue;
    		}
    		do 
    		{
    			times++;
    
    			pos = isOnIt(g_Group[sel1].city[i], g_Group[sel1].city, i, pos1, pos2);
    			if (pos != -1)
    			{/*
    				for (int j = 0; j < NUM_CITY; j++)
    					printf("%4d", g_Group[sel1].city[j]);
    				printf("\n");
    				for (int j = 0; j < NUM_CITY; j++)
    					printf("%4d", g_Group[sel2].city[j]);
    				printf("\n");
    				printf("%d %d %d %d %d\n",pos1,pos2,pos, g_Group[sel1].city[i], g_Group[sel2].city[pos]);*/
    				g_Group[sel1].city[i] = g_Group[sel2].city[pos];
    				//printf("pos:%d,pos1:%d,pos2:%d\n", pos, pos1, pos2);
    			}
    		} while (pos != -1);
    		do
    		{
    			pos = isOnIt(g_Group[sel2].city[i], g_Group[sel2].city, i, pos1, pos2);
    			if (pos != -1)
    			{
    				g_Group[sel2].city[i] = g_Group[sel1].city[pos];
    				//printf("pos:%d,pos1:%d,pos2:%d\n", pos, pos1, pos2);
    			}
    		} while (pos != -1);
    	}
    //	printf("交叉互换过程完毕\n");
    }
    void Mutation(int sel, int pos1,int pos2)//个体突变
    {
    	int maxSize = pos2 - pos1 + 1;
    	for (int i = 0; i < maxSize / 2; i++)
    	{
    		Swap(g_Group[sel].city[pos1+i], g_Group[sel].city[pos2-i]);
    	}
    }
    void Genetic() // 产生下一代种群
    {
    	int maxNum = 0, minNum = 0;	
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		if (g_Group[i].pAlive > g_Group[maxNum].pAlive)
    			maxNum = i;
    		if (g_Group[i].pAlive < g_Group[maxNum].pAlive)
    			minNum = i;
    	}
    	g_Group[minNum] = g_Group[maxNum]; // 使最大直接替换最小 
    	//printf("开始交叉\n");
    	// 交叉配对
    	int selNum;
    	int maxTimes = 0, nowTimes = 0;
    	int canSelected[MAX_SIZE]; // 可以用于交叉的个体
    	bool isCanSelected[MAX_SIZE];
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		if (i == maxNum) // 不让最优秀的个体参与配对
    			continue;
    		else if ((RAND(100)) / 100.0 < Pc) // 根据概率判断是否参与配对
    		{
    			canSelected[maxTimes++] = i;
    		}
    	}
    	for (int i = 0; i < maxTimes; i++)
    	{
    		selNum = RAND(maxTimes);
    
    		Swap(canSelected[i], canSelected[selNum]);
    	}
    	int pos1, pos2;
    	for (int i = 0; i < maxTimes; i+=2)
    	{
    		selNum = i + 1;
    		if (selNum >= maxTimes)
    			break;
    		pos1 = RAND(NUM_CITY); // 选定交叉位置
    		pos2 = RAND(NUM_CITY - pos1) + pos1;
    		if (pos1 == pos2)
    		{
    			if (pos1 > 0)
    				pos1--;
    			else
    				pos2++;
    		}/*
    		printf("%d与%d开始交叉互换\n", canSelected[i], canSelected[selNum]);*/
    		Swap(canSelected[i], canSelected[selNum], pos1, pos2);
    		/*
    				printf("第%d个体与第%d个体进行交叉配对,得到新的两个个体如下:\n", canSelected[i] + 1, canSelected[selNum] + 1);
    				printf("第%d个体:\n", canSelected[i] + 1);
    				for (int j = 0; j < NUM_CITY; j++)
    				printf("%4d", g_Group[canSelected[i]].city[j]);
    				printf("\n第%d个体:\n", canSelected[selNum] + 1);
    				for (int j = 0; j < NUM_CITY; j++)
    				printf("%4d", g_Group[canSelected[selNum]].city[j]);
    				printf("\nselNum:%d, maxTimes:%d\n",selNum,maxTimes);*/
    	}
    /*
    	printf("开始突变\n");*/
    	// 突变
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		if (i == maxNum || i == minNum)
    		{
    			continue;
    		}
    		if (RAND(100) / 100.0 < Pm) // 符合突变概率
    		{
    			pos1 = RAND(NUM_CITY); // 选择位置
    			pos2 = RAND(NUM_CITY - pos1) + pos1;
    			if (pos1 == pos2)
    			{
    				if (pos1 > 0)
    					pos1--;
    				else
    					pos2++;
    			}
    			/*printf("第%d个体突变前:\n", i + 1);
    			for (int j = 0; j < NUM_CITY; j++)
    				printf("%4d", g_Group[i].city[j]);
    			printf("\n");*/
    			Mutation(i, pos1, pos2);
    		//	printf("第%d个体突变:\n", i + 1);/*
    		//	for (int j = 0; j < NUM_CITY; j++)
    		//		printf("%4d", g_Group[i].city[j]);
    		//	printf("\n");
    		}
    	}
    }
    void Train()
    {
    	int nowGenerations = 0;
    	float totalAlive = 0;
    	do 
    	{
    		printf("第%d代种群\n", nowGenerations + 1);
    		GetAliveP();// 计算存活率
    		Genetic();// 根据遗传规律得到下一代
    		nowGenerations++;
    	} while (nowGenerations < GENERATIONS);
    	printf("经过%d次繁衍,得到的优秀个体为:\n", nowGenerations);
    	printf("其距离为%d,其轨迹如下:\n", g_Group[bestOne].adapt);
    	for (int i = 0; i < NUM_CITY; i++)
    		printf("%d ", g_Group[bestOne].city[i]);
    	printf("\n");
    	printf("其他个体如下:\n");
    	for (int i = 0; i < MAX_SIZE; i++)
    	{
    		printf("其距离为%d,其轨迹如下:\n", g_Group[i].adapt);
    		for (int j = 0; j < NUM_CITY; j++)
    		{
    			printf("%d ", g_Group[i].city[j]);
    		}
    		printf("\n");
    	}
    }
    int main()
    {
    	Init();
    	Train();
    	return 0;
    }


    展开全文
  • TSP遗传算法

    2013-06-02 11:39:24
    利用遗传算法解决旅行商问题,用c语言编程,能够很好解决问题,程序运行正常。
  • 遗传算法C语言设计

    2019-01-06 18:31:04
    遗传算法求解TSP问题 换位表达、启发式交叉、启发式变异、最优选择策略 前言 本文设计遗传算法TSP问题进行求解。首先选取100个城市作为旅行过程中要经过的点,城市的坐标已知,求解一个通过每个城市一次且总距离...
  • 遗传算法解决TSP问题

    2011-01-26 12:11:48
    遗传算法解决TSP问题代码。 VS2003 C语言。 tsp使用eil51例子。
  • 遗传算法C语言实现(二) 上一次我们使用遗传算法求解了一个较为复杂的多元非线性函数的极值问题,也基本了解了遗传算法的实现基本步骤。这一次,我再以经典的TSP问题为例,更加深入地说明遗传算法中...
  • 遗传算法解决tsp问题

    2010-11-02 00:12:42
    使用c语言解决tsp问题 适合初学者学习使用
  • 这篇文章是之前写的智能算法(遗传算法(GA)、粒子群算法(PSO))的补充。其实代码我老早之前就写完了,今天恰好重新翻到了,就拿出来给大家分享一下,也当是回顾与总结了。  首先介绍一下模拟退火算法(SA)。...
  • Matlab教程第15章混合粒子群算法TSP搜索算法,因对matlab脚本语言不是很熟悉,就用C语言(Linux环境下)实现了一下,加深自己对算法的理解,感觉效果还可以,运行速度相比matlab快多了,有兴趣的可以看一下,有疑问...
  • 改进的遗传算法求解TSP问题 本程序只是一种思想的验证 论文讲在一个月后上传 采用C语言编程
  • 旅行商问题TSP(蚁群算法Java)

    千次阅读 2018-06-07 22:20:14
    旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须...这个问题一般是使用遗传算法去解,但是蚂蚁算法要更高效.对于c++不熟悉的我,用C语言是...
  • 蚁群算法实现TSP(旅行商)问题(java)

    千次阅读 2016-05-22 08:06:57
    旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须选择...这个问题一般是使用遗传算法去解,但是蚂蚁算法要更高效.对于c++不熟悉的我,用C语言

空空如也

空空如也

1 2
收藏数 34
精华内容 13
关键字:

tsp问题遗传算法c语言

c语言 订阅