ga.cpp

vs2005开发 遗传算法求解144城市的旅行商问题

#include <stdio.h>
#include <iostream>
#include <stdlib.h> 
#include <fstream>
#include <math.h>
#include <time.h>
using namespace std;

#define  N  144           //城市数
#define  M  100           //种群的个体数
#define  GEN_MAX 10000      //繁殖的最多代数
#define Hybridize_Max 120  //杂交的基因最大数


int GEN;                  //繁殖的代数
#define midGMun  406            //中间个体数量
int PTOC = midGMun - 4*M;           //父代给子代
int City[N][2];            //初始城市排列

// struct Individual             //种群中个体的属性 
// {
// 	double value = 0;         //该个体的排列顺序得到的解
// 	int CityLine[N] = {0};        //该个体的城市排列，存放城市数组的下标
// };

struct Individual             //种群中个体的属性 
{
	double value;         //该个体的排列顺序得到的解
	int CityLine[N][2];        //该个体的城市排列
};

Individual Group[M];          //种群

//计算路径长度
double ComputeResult()
{
	double result = 0,disx, disy;
	for(int i = 0; i < N - 1; i++)
	{
		disx = City[i][0] - City[i+1][0];
		disy = City[i][1] - City[i+1][1];
		result = result+ sqrt( disx * disx + disy * disy );
	}
	disx = City[N-1][0] - City[0][0];
	disy = City[N-1][1] - City[0][1];
	result = result + sqrt( disx * disx + disy * disy );
/*	printf("result=%lf\n",result);*/
	return result;
}


//计算city中第n个城市与右边城市的路程
double CityComputeSqrt( Individual agen, int n )
{
	double disx, disy, SqrtResult;
	if( n == 143 || n == -1 )
	{
		disx = agen.CityLine[143][0] - agen.CityLine[n][0];
		disy = agen.CityLine[143][1] - agen.CityLine[n][1];
	}
	else
	{
		disx = agen.CityLine[n+1][0] - agen.CityLine[n][0];
		disy = agen.CityLine[n+1][1] - agen.CityLine[n][1];
	}
	SqrtResult = sqrt( disx * disx + disy *disy );
	return SqrtResult;
}

//计算路径中选定城市和相邻另个城市的距离和
//////////////////////////////////////////////////////////////////////////
double ComputeTwoCity( Individual agen, int place )
{
	double result = CityComputeSqrt( agen ,place ) + CityComputeSqrt( agen, place-1 );
	return result;
}

//变异,返回个体
//////////////////////////////////////////////////////////////////////////
Individual Aberrance( Individual agen )
{
//	int AberNum;        //染色体的变异数
	int city_statu[2];
	int i1, i2;

//	double rand_text = ( rand() % 100 ) / 100.0;           //[0,0.99)随机数
	//[0,0.8)只有一对调换位置
//	if ( rand_text < 0.7 )
//	{
	i1 = rand() % 143;
	while(1)
	{
		i2 = rand() % 143;
		if( i1 != i2 )
		{
			if( i1 == 0 )
			{
				if( i2 !=143 && i2!=1)
					break;
			}
			else if( i1 == 143)
			{
				if(i2!=0 && i2 !=142)
					break;
			}
			else
				if(i2 != i1-1 && i2 != i1+1)
					break;
		}
	}

	
	//变异前两个预交换位和附近城市的距离
	double FirDisResult = ComputeTwoCity( agen, i1 ) + ComputeTwoCity( agen, i2 );

	//两个基因互换
	city_statu[0] = agen.CityLine[i1][0];
	city_statu[1] = agen.CityLine[i1][1];
	agen.CityLine[i1][0] = agen.CityLine[i2][0];
	agen.CityLine[i1][1] = agen.CityLine[i2][1];
	agen.CityLine[i2][0] = city_statu[0];
	agen.CityLine[i2][1] = city_statu[1];
	
	//变异后两个交换位和附近城市的距离
	double SecDisResult = ComputeTwoCity( agen, i1 ) + ComputeTwoCity( agen, i2 );;

	agen.value = agen.value + SecDisResult - FirDisResult;
//	}
/*	printf("bianyiA_agen=%lf\n",agen.value);*/
	return agen;
}

//杂交
//输入：两个个体的引用
//选取第一个个体中随机两个整数之间的基因，对第二个个体中相同的基因按顺序交换
//////////////////////////////////////////////////////////////////////////
void Hybridize( Individual &agen_1, Individual &agen_2 )
{
/*	printf("agen1=%lf,agen2=%lf\n",agen_1.value, agen_2.value );*/
	int agen_1_length, agen_1_left;
	agen_1_length = rand() % ( Hybridize_Max -1 ) + 2;    //长度[2,hybeidize_max];
	agen_1_left = rand() % ( 145 - agen_1_length );
	int agen_1_right = agen_1_left + agen_1_length -1;

	double agen_1_preLong = 0;          //第一个个体交换之前要交换城市段的路径长度
	double agen_1_sitLong = 0;          //第一个个体交换之后要交换城市段的路径长度
	int agen_2_place[Hybridize_Max];    //第二个个体预交换城市在排列中的位置
	double agen_2_preLong = 0;          //第二个个体交换前预交换城市与相邻城市的距离和
	double agen_2_sitLong = 0;          //第二个个体交换后预交换城市与相邻城市的距离和
	
	int k = 0;                            //交换城市的计数器
/*	printf("我是分界线*******************************\n");*/
	for( int i = agen_1_left -1; i <= agen_1_right; i++ )
	{
		
		agen_1_preLong= agen_1_preLong + CityComputeSqrt( agen_1, i );
		if( i != agen_1_left - 1 )
		{
			for( int j = 0; j < N; j++ )
			{
				//被选中城市在个体2中的位置
				if( agen_1.CityLine[i][0] == agen_2.CityLine[j][0] )  
				{
					if(agen_1.CityLine[i][1] == agen_2.CityLine[j][1])
					{
						agen_2_place[k] = j;                        //个体2第k个城市的位置
////*						printf("i=%d,j=%d,agen_2_place[k]=%d\n",i,j,agen_2_place[k] );*/
/*						agen_2_preLong = agen_2_preLong + ComputeTwoCity( agen_2, j );*/
						k++;
						break;
					}
					
					
				}
			}
		}
	}

	//对agen_2_place进行排序，从小到大
	for( int i = 0; i < agen_1_length; i++ )
	{
		for( int j = 0; j < agen_1_length - i -1; j++ )
		{
			if( agen_2_place[j] > agen_2_place[j+1] )
			{
				int k = j + 1;
				int temp = agen_2_place[j];
				agen_2_place[j] = agen_2_place[k];
				agen_2_place[k] = temp;
			}
		}
	}


	int TempHbriCity[2];                      //临时存放城市坐标
// 	for( int i = 0; i < agen_1_length; i++ )
// 	{
// 		printf("agen_2_place[%d] = %d\n",i,agen_2_place[i]);
// 	}
	//等位基因互换
	for( int i = 0; i < agen_1_length; i++ )
	{
		//选中的城市放入临时数组中
		TempHbriCity[0] = agen_1.CityLine[ agen_1_left + i ][0];
		TempHbriCity[1] = agen_1.CityLine[ agen_1_left + i ][1];

		int place2i = agen_2_place[i];
		//将个体2中的等位基因与之互换
		agen_1.CityLine[ agen_1_left + i ][0] = agen_2.CityLine[place2i][0];
		agen_1.CityLine[ agen_1_left + i ][1] = agen_2.CityLine[place2i][1];

		//临时数组导入个体2
		agen_2.CityLine[place2i][0] = TempHbriCity[0];
		agen_2.CityLine[place2i][1] = TempHbriCity[1];
// 
// 		//计算个体2交换后的被交换城市和相邻城市的距离和
// 		agen_2_sitLong = agen_2_sitLong + ComputeTwoCity( agen_2, agen_2_place[i] );
	}
	//计算个体1交换后被交换城市的距离和
 	for( int i = agen_1_left -1; i <= agen_1_right; i++ )
 	{
 		agen_1_sitLong= agen_1_sitLong + CityComputeSqrt( agen_1, i );
 	}
// 
// 	//计算个体2交换后的被交换城市和相邻城市的距离和
// 	for(int i = 0; i < agen_1_length; i++ )
// 	{
// 		agen_2_sitLong = agen_2_sitLong + ComputeTwoCity( agen_2, agen_2_place[i] );
// 
// 	}
	double result = 0,disx, disy;
// 	for(int i = 0; i < N - 1; i++)
// 	{
// 		disx = agen_1.CityLine[i][0] - agen_1.CityLine[i+1][0];
// 		disy = agen_1.CityLine[i][1] - agen_1.CityLine[i+1][1];
// 		result = result+ sqrt( disx * disx + disy * disy );
// 	}
// 	disx = agen_1.CityLine[N-1][0] - agen_1.CityLine[0][0];
// 	disy = agen_1.CityLine[N-1][1] - agen_1.CityLine[0][1];
// 	result = result + sqrt( disx * disx + disy * disy );
// 	agen_1.value=result;
// 	
// 	result = 0;
	for(int i = 0; i < N - 1; i++)
	{
		disx = agen_2.CityLine[i][0] - agen_2.CityLine[i+1][0];
		disy = agen_2.CityLine[i][1] - agen_2.CityLine[i+1][1];
		result = result+ sqrt( disx * disx + disy * disy );
	}
	disx = agen_2.CityLine[N-1][0] - agen_2.CityLine[0][0];
	disy = agen_2.CityLine[N-1][1] - agen_2.CityLine[0][1];
	result = result + sqrt( disx * disx + disy * disy );
	agen_2.value=result;
	
// 	//个体1、2杂交之后的值
 	agen_1.value = agen_1.value + agen_1_sitLong - agen_1_preLong;
// 	agen_2.value = agen_2.value + agen_2_sitLong - agen_2_preLong;
}

//初始化初始种群
//////////////////////////////////////////////////////////////////////////
void InitGroup()
{
	int i, j, k, jj;


	//初始化最早祖先
	//////////////////////////////////////////////////////////////////////////

	Individual ancestor;                //最早祖先，自身变异形成初始种群
	ancestor.value = ComputeResult();
/*	printf("ancestor.value=%lf\n",ancestor.value);*/
	for( i = 0; i < N; i++ )
	{
		ancestor.CityLine[i][0] = City[i][0] ;
		ancestor.CityLine[i][1] = City[i][1] ;
	}

//	ancestor.CityLine = City;

	//变异形成初始种群
	//////////////////////////////////////////////////////////////////////////
	Group[0] = Aberrance( ancestor );
	for( i = 1; i < M; i++ )
	{
		Individual agen;
		agen = Aberrance( ancestor );
		for( j = 0; j < i; j++ )
		{
			if( agen.value < Group[j].value )
				break;
		}
		jj = j;
		k = 0;
		for( ; j < i; j++ )
		{
			Group[i-k] = Group[i-k-1];
			k++;
		}
		Group[jj] = agen;

	}
// 	for( i = 0; i<M;i++)
// 	{
// 		printf("%lf\n",Group[i].value);
// 	}
	
}

//杂交100次，找出最好个体
Individual abercy(Individual agen)
{
	Individual aberBest = agen;
	Individual temp;
	for(int i = 0; i < 100; i++ )
	{
		temp = Aberrance(agen);
		if( temp.value < aberBest.value)
			aberBest = temp;
	}
	return aberBest;
}

int main()
{
	int b, i;
	//打开文件并初始化路径
	ifstream ifs("CHN144.txt");
	ifs >> b;
	for( i = 0; i < N; ++i)
	{
		ifs >> b ;
		ifs >> City[i][0];
		ifs >> City[i][1];
	}
	clock_t start,finish;
	start = clock();
	
	//初始化随机种子
	srand( (unsigned)time( NULL ) );//使用当前的系统时间初始化随机数种子

	InitGroup();

	double pi[M];                   //概率
	double roulette[M];             //轮盘中个体的概率空间
	roulette[0] = 0;

	Individual MidGroup[midGMun];
	/*printf("%lf\n,")*/
	int s = 0;
	double best ;
	//繁殖最多GEN_MAX代
	for( GEN = 0; GEN < GEN_MAX; GEN++ )
	{

		if( s == 30 )
		{
			break;
		}

		best = Group[0].value;

/*		printf("gen=%d   best=%lf\n",GEN, best);*/

		double piTotal = 0;             //适应度和
		//求适应度和
		for( int i = 0; i < M; i++ )
		{
			piTotal = piTotal + Group[i].value;
		}
/*		printf("pitotal=%lf\n");*/
		//求各个个体的繁殖概率
		for( int i = 0; i < M; i++ )
		{
			pi[i] = Group[i].value / piTotal;
			if( i != M-1 )
				roulette[i+1] = roulette[i] + pi[i];
/*			printf("pi[%d]=%lf\n",i,pi[i]);*/
		}
		
		//把种群中前midGMun-2*M个放入中间种群
		for(int i = 0; i<PTOC; i++ )
		{
			int k = 0;
			MidGroup[i] = Group[k];
			k++;
		}
		int l = PTOC;
/*		int l = 0;*/
		//以概率繁殖M次
		for( int j = 0; j < M; j++)
		{
			int k = 0;
			double first = double( rand() ) / RAND_MAX;
			int i = 0;
			//第i-1个被选择group[i-1]
			while( roulette[i] <= first && i < M )
			{
				i++;
			}
/*			printf("first=%lf,i=%d,roulette[%d]=%lf\n",first,i,i-1,roulette[i-1]);*/
			while(1)
			{
				double sec = double( rand() ) / RAND_MAX;
				k = 0;
				//第k-1个被选择group[k-1]
				while( roulette[k] <= sec && k < M )
				{
					k++;
				}
				break;
			}


			//放入中间个体种群数组
			MidGroup[l] = Group[i-1];
			int ll = l+1;
			MidGroup[ll] = Group[k-1];
			
			MidGroup[l+2]=MidGroup[l];
			MidGroup[l+3]=MidGroup[ll];

/*			printf("fist:midgroup[1]+2=%lf,%lf\n",MidGroup[l].value,MidGroup[ll].value);*/

			Hybridize( MidGroup[l], MidGroup[ll] );
/*			printf("sec:midgroup[1]+2=%lf,%lf\n",MidGroup[l].value,MidGroup[ll].value);*/
// 			Individual aberBest = MidGroup[l];
// 			Individual temp;
// 			for(int i = 0; i < 100; i++ )
// 			{
// 				temp = Aberrance(MidGroup[l]);
// 				if( temp.value < aberBest.value)
// 					aberBest = temp;
// 			}
			MidGroup[l] = abercy( MidGroup[l] );
			MidGroup[ll] = abercy( MidGroup[ll] );
			l = l+4;
/*			printf("*******%d次\n",j);*/
		}


		//排序
		for( int i = 0; i < midGMun; i++ )
		{
			for( int j = 0; j < midGMun - 1 - i; j++ )
			{
				if( MidGroup[j].value > MidGroup[j+1].value )
				{
					Individual temp = MidGroup[j];
					MidGroup[j] = MidGroup[j+1];
					MidGroup[j+1] = temp;
				}
			}
		}

		for( int i = 0; i < M; i++ )
		{
			Group[i] = MidGroup[i];
/*			printf("group[%d]=%lf\n",i,Group[i].value);*/
		}

		if( best - Group[0].value < 0.00000001 )
		{
			s = s + 1;
		}
		else
			s = 0;
/*		printf("gen=%d  s=%d best=%lf\n",GEN,s, best);*/
	}
	finish = clock();
	double duration = (double)(finish - start) / CLOCKS_PER_SEC;        //转换成时间
	
	for( int k = 0;k < N-1; k++ )
	{
		printf("<%d,%d>--",Group[0].CityLine[k][0], Group[0].CityLine[k][0] );
	}
	printf("<%d,%d>\n\n",Group[0].CityLine[N-1][0], Group[0].CityLine[N-1][0] );
	printf("finResult:%lf\n\n",Group[0].value);
	printf("use time: %lfs",duration);
	getchar();
	return 0;
}