gp.cpp

遗传算法求解TSP问题的源码.遗传代数和种群规模比较大,所以整个求解过程比较长

#include "StdAfx.h"
#include "GP.h"
#include <math.h>
#include <string.h>

CGpTsp::CGpTsp(int nCitys, Position *position)
{
	m_nCity = nCitys;			//城市个数
	m_xyPosition = position;	//城市坐标

	m_Generation = new Individual[PEOPLE_SIZE*2];	//最好是动态分配,因为使用线程的话可能造成堆栈溢出...很隐蔽的问题!!!

	//当前代使用0-PEOPLE_SIZE-1的空间
	//下一代使用PEOPLE_SIZE-PEOPLE_SIZE*2-1的空间
	for(int i=0; i<PEOPLE_SIZE*2; i++)
		m_Generation[i].path.Citys = new int[m_nCity];
	srand( (unsigned)time(NULL) );
}

CGpTsp::~CGpTsp(void)
{
	for(int i=0; i<PEOPLE_SIZE*2; i++)
		delete[] m_Generation[i].path.Citys;
	delete[] m_Generation;
}

//随机的生成个体gene:随机的排列城市序号
void CGpTsp::InitGene(Individual *ind)
{
	for(int i=0; i<m_nCity; i++)
	{
		ind->path.Citys[i] = i;
	}

	//随机排列
	for(int i=0; i< m_nCity; i++)
	{
		int index, temp;
		index = i+rand()%(m_nCity-i);	//生成i到(n-1)的随机数

		temp  = ind->path.Citys[i];		//交换
		ind->path.Citys[i]	= ind->path.Citys[index];
		ind->path.Citys[index]	= temp;
	}
	//计算路径长度
	ind->path.Length = 0.0;
	double x = m_xyPosition[ind->path.Citys[0]].x-m_xyPosition[ind->path.Citys[m_nCity-1]].x;
	double y = m_xyPosition[ind->path.Citys[0]].y-m_xyPosition[ind->path.Citys[m_nCity-1]].y;
	ind->path.Length += sqrt(x*x +y*y);
	for( int i=1; i<m_nCity; i++)
	{
		x = m_xyPosition[ind->path.Citys[i]].x-m_xyPosition[ind->path.Citys[i-1]].x;
		y = m_xyPosition[ind->path.Citys[i]].y-m_xyPosition[ind->path.Citys[i-1]].y;
		ind->path.Length += sqrt(x*x +y*y);
	}
}

//初始化种群(并将个体按适应度从大到小的顺序排列)
void CGpTsp::InitCurGeneration()
{
	for(int i=0; i<PEOPLE_SIZE*2; i++)
	{
		InitGene(&m_Generation[i]);
	}
	Evaluate();
}



//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
////						变异,复制,交叉,选择						////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

//变异算子
//将个体gene中两个位置pos1和pos2的基因进行交换
void CGpTsp::Mutation(Individual *ind)
{
	int m1, m2;	//变异位置
	m1 = rand()%m_nCity;
	do 
	{
		m2 = rand()%m_nCity;
	} while(m2==m1);
	
	int m=m1;
	if( m1>m2)
	{
		m1 = m2;
		m2 = m;
	}
	double delta=0.0;
	double x, y;
	int pre = (m1+m_nCity-1)%m_nCity;
	int next= (m2+1)%m_nCity;

	x = m_xyPosition[ind->path.Citys[m1]].x-m_xyPosition[ind->path.Citys[pre]].x;
	y = m_xyPosition[ind->path.Citys[m1]].y-m_xyPosition[ind->path.Citys[pre]].y;
	delta += sqrt(x*x +y*y);
	x = m_xyPosition[ind->path.Citys[m2]].x-m_xyPosition[ind->path.Citys[next]].x;
	y = m_xyPosition[ind->path.Citys[m2]].y-m_xyPosition[ind->path.Citys[next]].y;
	delta += sqrt(x*x +y*y);

	//2点对调变异
	for(int i=0; i<=(m2-m1)/2; i++)
	{
		int temp = ind->path.Citys[m1+i];
		ind->path.Citys[m1+i] = ind->path.Citys[m2-i];
		ind->path.Citys[m2-i] = temp;
	}

	x = m_xyPosition[ind->path.Citys[m1]].x-m_xyPosition[ind->path.Citys[pre]].x;
	y = m_xyPosition[ind->path.Citys[m1]].y-m_xyPosition[ind->path.Citys[pre]].y;
	delta -= sqrt(x*x+y*y);
	x = m_xyPosition[ind->path.Citys[m2]].x-m_xyPosition[ind->path.Citys[next]].x;
	y = m_xyPosition[ind->path.Citys[m2]].y-m_xyPosition[ind->path.Citys[next]].y;
	delta -= sqrt(x*x+y*y);

	ind->path.Length -= delta;
}

//复制算子
//将父代的个体src复制给子代的个体dst
void CGpTsp::Copy(Individual* dst, Individual* src)
{
	dst->path.Length = src->path.Length;
	memcpy(dst->path.Citys, src->path.Citys, m_nCity*sizeof(int));
}

//将路径path中第index个位置的数旋转到第一个位置.path总共有n个数据.
void CGpTsp::Turn(int *path, int index, int n)
{
	int *temp = new int[n];
	memcpy(temp, path, n*sizeof(int));
	memcpy(path, temp+index, (n-index)*sizeof(int));
	memcpy(path+(n-index), temp, index*sizeof(int));
	delete[] temp;
}
//路径中第index个点与第index+1个点之间的距离
double CGpTsp::Distance(int *path, int index1, int index2)
{
	double x = m_xyPosition[path[index1]].x-m_xyPosition[path[index2]].x;
	double y = m_xyPosition[path[index1]].y-m_xyPosition[path[index2]].y;
	return sqrt(x*x+y*y);
}
//在大小为n的path中查找value所在的位置
int CGpTsp::Find(int *path, int value, int n)
{
	int posi;
	for(posi=0; posi<n; posi++)
	{
		if(path[posi]==value)
			break;
	}
	return posi;
}
//交叉算子
//启发式交叉算子
void CGpTsp::Crossover(Individual* ind1, Individual* ind2)
{
	int index=1+rand()%(m_nCity-2);	//交叉的初始位置
	Turn(ind1->path.Citys, index, m_nCity);

	int city = ind1->path.Citys[0];
	for(index=0; index<m_nCity; index++)
	{
		if(ind2->path.Citys[index]==city)
			break;
	}
	Turn(ind2->path.Citys, index, m_nCity);	//对其第一个城市

	ind1->path.Length = 0.0;
	ind2->path.Length = 0.0;
	for(int i=1; i<m_nCity; i++)
	{
		double d1 = Distance(ind1->path.Citys, i-1, i);
		double d2 = Distance(ind2->path.Citys, i-1, i);
		if(d1<d2)
		{
			ind1->path.Length += d1;
			int posi=Find(ind2->path.Citys+i, ind1->path.Citys[i], m_nCity-i);
			Turn(ind2->path.Citys+i, posi, m_nCity-i);
		}
		else
		{
			ind1->path.Length += d2;
			int posi=Find(ind1->path.Citys+i, ind2->path.Citys[i], m_nCity-i);
			Turn(ind1->path.Citys+i, posi, m_nCity-i);
		}
	}
	ind1->path.Length += Distance(ind1->path.Citys, m_nCity-1, 0);
	ind2->path.Length = ind1->path.Length;
}
/*
//简单交叉策略
void CGpTsp::Crossover(Individual* ind1, Individual* ind2)
{
	int *temp1, *temp2;
	temp1 = new int[m_nCity];
	temp2 = new int[m_nCity];
	memcpy(temp1, ind1->path.Citys, m_nCity*sizeof(int));
	memcpy(temp2, ind2->path.Citys, m_nCity*sizeof(int));
	int c=1+rand()%(m_nCity-2);

	int i,j, next;
	for(i=0, next=c; i<m_nCity; i++)
	{
		for(j=0; j<c; j++)
		{
			if(temp2[i] == temp1[j])
				break;
		}
		if( j==c )
		{
			ind1->path.Citys[next]=temp2[i];
			next++;
		}
	}
	for(i=0, next=c; i<m_nCity; i++)
	{
		for(j=0; j<c; j++)
		{
			if(temp1[i] == temp2[j])
				break;
		}
		if( j==c )
		{
			ind2->path.Citys[next]=temp1[i];
			next++;
		}
	}
	//计算路径长度
	double x, y;
	ind1->path.Length = 0.0;
	x = m_xyPosition[ind1->path.Citys[0]].x-m_xyPosition[ind1->path.Citys[m_nCity-1]].x;
	y = m_xyPosition[ind1->path.Citys[0]].y-m_xyPosition[ind1->path.Citys[m_nCity-1]].y;
	ind1->path.Length += sqrt(x*x +y*y);
	for( int i=1; i<m_nCity; i++)
	{
		x = m_xyPosition[ind1->path.Citys[i]].x-m_xyPosition[ind1->path.Citys[i-1]].x;
		y = m_xyPosition[ind1->path.Citys[i]].y-m_xyPosition[ind1->path.Citys[i-1]].y;
		ind1->path.Length += sqrt(x*x +y*y);
	}
	ind2->path.Length = 0.0;
	x = m_xyPosition[ind2->path.Citys[0]].x-m_xyPosition[ind2->path.Citys[m_nCity-1]].x;
	y = m_xyPosition[ind2->path.Citys[0]].y-m_xyPosition[ind2->path.Citys[m_nCity-1]].y;
	ind2->path.Length += sqrt(x*x +y*y);
	for( int i=1; i<m_nCity; i++)
	{
		x = m_xyPosition[ind2->path.Citys[i]].x-m_xyPosition[ind2->path.Citys[i-1]].x;
		y = m_xyPosition[ind2->path.Citys[i]].y-m_xyPosition[ind2->path.Citys[i-1]].y;
		ind2->path.Length += sqrt(x*x +y*y);
	}
	delete[] temp1;
	delete[] temp2;
}
*/
//轮盘赌选择法
int CGpTsp::Select()
{
	double pro=(rand()%1001)/1000.0;
	if( pro<m_Generation[0].fitness)
		return 0;
	for(int i=1; i<PEOPLE_SIZE; i++)
		if( m_Generation[i-1].fitness<=pro && pro<m_Generation[i].fitness )
			return i;
	return PEOPLE_SIZE-1;
}


//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

//按长度从小到大的顺序排列个体
void CGpTsp::Sort()
{
	int i,j;
	Individual temp;
	for(i=1; i<PEOPLE_SIZE*2; i++)
	{
		memcpy(&temp, &m_Generation[i], sizeof(Individual));
		for(j=i-1; j>=0 && temp.path.Length<m_Generation[j].path.Length; j--)
		{
			memcpy(&m_Generation[j+1], &m_Generation[j], sizeof(Individual));
		}
		memcpy(&m_Generation[j+1], &temp, sizeof(Individual));
	}
}

//评估个体:按照适应度的比例组成轮盘,同时确定了每个个体所在的区间
//当概率满足m_Generation[i-1].fitness<=pro && pro<m_Generation[i].fitness
//即概率落在区间i,亦即选中第i个个体
void CGpTsp::Evaluate()
{
	Sort();

	int i;
	double fsum=0;
	for(i=0; i<PEOPLE_SIZE*2; i++)
		fsum += 1/m_Generation[i].path.Length;
	for(i=0; i<PEOPLE_SIZE*2; i++)
		m_Generation[i].fitness = 1/(fsum*m_Generation[i].path.Length);  //相对适应值
	for(i=1; i<PEOPLE_SIZE*2; i++)
		m_Generation[i].fitness += m_Generation[i-1].fitness;  //轮盘选择的概率(范围)
}
//产生新的一代
//新一代使用PEOPLE_SIZE~PEOPLE_SIZE*2-1的空间
void CGpTsp::Reproduce()
{
	int i;
	for(i=PEOPLE_SIZE*2-1; i>=PEOPLE_SIZE; i--)
	{	
		int index0, index1;
		//选择
		index0 = Select();
		do 
		{
			index1=Select();
		} while( index1==index0 );
		
		//复制
		Copy(&m_Generation[i], &m_Generation[index0]);
		Copy(&m_Generation[i-1], &m_Generation[index1]);
		
		//交叉
		double pro=(rand()%10001)/10000.0;
		if(pro<=P_CROSS)
		{
			Crossover(&m_Generation[i], &m_Generation[i-1]);
		}
		
		//变异
		pro=(rand()%10001)/10000.0;
		if(pro<=P_MUTATION)
		{
			Mutation(&m_Generation[i]);
		}
	}
	Evaluate();
}

/*
void CGpTsp::Reproduce()
{
	int i,NumSave=(int)(PEOPLE_SIZE*0.1);
	for(i=PEOPLE_SIZE-NumSave; i<PEOPLE_SIZE; i++)	//保存前NumSave个适应度较高的个体
	{
		Copy(&m_NewGeneration[i], &m_CurGeneration[i]);
	}
	
	double pro;

	for(i=0; i<PEOPLE_SIZE-NumSave; )
	{
		pro=(rand()%1001)/1000.0;
		if( pro<=0.8 )  //交叉概率0.8
		{
			int index0, index1;
			
			index0 = Select();
			Copy(&m_NewGeneration[i], &m_CurGeneration[index0]);
			i++;
			if(i<PEOPLE_SIZE-NumSave)
			{
				do 
				{
					index1=Select();
				} while( index1==index0 );
				Copy(&m_NewGeneration[i], &m_CurGeneration[index1]);
				Crossover(&m_NewGeneration[i-1], &m_NewGeneration[i]);
				i++;
			}
		}
		else if(pro>=0.9)  //变异概率0.1
		{
			int index = Select();
			Copy(&m_NewGeneration[i], &m_CurGeneration[index]);
			Mutation(&m_NewGeneration[i]);
			i++;
		}
		else
		{
			int index = Select();
			Copy(&m_NewGeneration[i], &m_CurGeneration[index]);
			i++;
		}
	}
	Individual *temp= m_NewGeneration;
	m_NewGeneration = m_CurGeneration;
	m_CurGeneration = temp;

	Evaluate();
}
*/


//返回找到的最优路径和权值
void CGpTsp::GetBestPath(Path *bestpath)
{
	int i;
	InitCurGeneration();
	for(i=0; i<NGene; i++)
	{
		Reproduce();
	}
	Individual *temp = &m_Generation[0];	//适应度最大的个体

	//返回路径
	bestpath->Length = temp->path.Length;
	memcpy(bestpath->Citys, temp->path.Citys, m_nCity*sizeof(int));
}