ga_tsp.cpp

50个城市以内的TSP问题, 用遗传算法, 算子采用了pmx和ox算子。

#include "stdafx.h"
#include "GA_TSP.h"
#include <time.h>
#include <math.h>

#define min(a, b)  (((a) < (b)) ? (a) : (b)) 
#define max(a, b)  (((a) > (b)) ? (a) : (b)) 

//全局的CGA_TSP对象, 供线程来完成遗传算法。
extern CGA_TSP tspProblem;

//用来产生min到max之间的一个四位小数的随机数
double AverageRandom(double min,double max)
{
	int minInteger = (int)(min*10000);
	int maxInteger = (int)(max*10000);
	int diffInteger = maxInteger - minInteger;
	int randInteger = rand()*rand();
	int resultInteger = randInteger % diffInteger + minInteger;
	return resultInteger/10000.0;
}

CGA_TSP::CGA_TSP()
{
	int i;
	//在(0, 500)*(0,500)的平面内随机产生的五十个点, 代表五十个城市
	POINT pt[50]=
	{
		59,245,    419,95,    249,157,    412,275,    12,477,
		162,430,   374,169,   290,201,    407,35,     325,190,
		364,128,   399,426,   486,326,    6,431,      374,220,
		486,364,   342,252,   289,147,    133,130,    184,323,
		239,225,   316,329,   483,152,    170,362,    330,51,
		419,7,     169,26,    105,206,    9,333,      30,72,
		324,296,   302,98,    131,379,    426,207,    395,132,
		197,144,   405,35,    304,130,    422,167,    18,250,
		114,255,   250,60,    343,80,     63,123,     432,457,
		235,240,   444,194,   371,193,    137,218,    87,468,
	};

	memcpy(city, pt, CNUM * sizeof(POINT));

	//求一条1, 2, ..., CNUM的路径作为初始最优解值
	for( i = 0; i < CNUM; i++ )
		bestPath[i] = i;

	lowestDistance = 0 ;
	long   x, y;
	for( i = 0; i < CNUM; i++)
	{
		x = city[ bestPath[i] ].x - city[ bestPath[ (i+1)%CNUM ] ].x ;
		y = city[ bestPath[i] ].y - city[ bestPath[ (i+1)%CNUM ] ].y ;
		lowestDistance += sqrt(x*x + y*y) ;
	}
}

CGA_TSP::~CGA_TSP()
{
}

//产生由POP个解组成的初始种群
void CGA_TSP::InitPopulation()
{
	int i, j, temp;
	int rNum[2], OnePath[CNUM];

	//产生1,2, ... , CNUM的一条规则路径;
	for(j = 0; j < CNUM; j++)
		OnePath[j] = j;

	//把上面这条路径变为一条随机路径;
	for(j = 0; j < 500; j++)
	{
		rNum[0] = rand()%CNUM;
		rNum[1] = rand()%CNUM;
		temp = OnePath[ rNum[0] ];
		OnePath[ rNum[0] ] = OnePath[ rNum[1] ];
		OnePath[ rNum[1] ] = temp;
	}

	//在这条随机路径的基础上产生POP条路径
	for(i = 0; i < POP; i++)
	{
		for(j = 0; j < 100; j++)
		{
			rNum[0] = rand()%CNUM;
			rNum[1] = rand()%CNUM;
			temp = OnePath[ rNum[0] ];
			OnePath[ rNum[0] ] = OnePath[ rNum[1] ];
			OnePath[ rNum[1] ] = temp;			
		}
		memcpy(path[i], OnePath, CNUM * sizeof(int));
	}
}

//评估函数, 计算各解的路径长度
void CGA_TSP::Evaluation()
{
	int i, j ;
	long x, y ;
	double distSum ;

	for( i = 0; i < POP; i++)
	{
		distSum = 0 ;

		for( j = 0; j < CNUM; j++)
		{
			x = city[ path[i][j] ].x - city[ path[i][ (j+1)%CNUM ] ].x ;
			y = city[ path[i][j] ].y - city[ path[i][ (j+1)%CNUM ] ].y ;
			distSum += sqrt(x*x + y*y) ;
		}
		distance[i] = distSum ;
	}
}

//保存最优解
void CGA_TSP::KeepTheBest()
{
	for(int i = 0; i < POP; i++)
		if( distance[i] < lowestDistance)
		{
			lowestDistance = distance[i];
			memcpy(bestPath, path[i], CNUM * sizeof(int));
		}
}

//选择策略
void CGA_TSP::Rotate_Wheel_Select()
{
	int    selectPath[POP][CNUM];
	double reverse_distance[POP], max_distance;
	double proportion[POP], posInWheel[POP];
	double totalValue = 0;
	int i, j;

	//对距离进行改造, 将最小值改造成最大值以构造轮盘;
	//简单的策略, 用最大值减每个值, 使最短路径变为最大值以得到最大的选择机会;
	max_distance = distance[0];
	for(i = 1; i < POP; i++)
	{
		if(distance[i] > max_distance)
			max_distance = distance[i];
	}
	for(i = 0; i < POP; i++)
	{
		reverse_distance[i] = max_distance - distance[i];
		totalValue += reverse_distance[i];
	}
	for(i = 0; i < POP; i++)
		proportion[i] = reverse_distance[i] / totalValue;

	//构造轮盘
	posInWheel[0] = proportion[0];
	for( i = 1; i < POP; i++)
		posInWheel[i] = posInWheel[i-1] + proportion[i];

	//轮盘赌
	for(i = 0; i < POP; i++)
	{
		int r = rand();
		double result = (double)r;
		while(result > 1)
			result /= 10;
		for(j = 0; j < POP; j++)
		{
			if (result <= posInWheel[j])
				break;
		}
		memcpy(selectPath[i], path[j], CNUM * sizeof(int));
	}
	memcpy(path, selectPath, POP * CNUM * sizeof(int));
}


//PMX杂交算子
void CGA_TSP::PMX()
{
	int i, j, k, select;
	int tempPath[2][CNUM];

	for(i = 0, select = 0; i < POP; i ++)
	{
		double d = AverageRandom(0, 1);
		if(d < PC)
		{
			if(select == 0)
				select = i;
			else
			{
				int r1 = rand() % CNUM;
				int r2 = rand() % CNUM;
				if( r1 == r2 )
				{
					select = 0;
					continue;
				}
				int r = min( r1, r2);
				r2 = max(r1, r2);
				r1 = r;
				
				//初始化两后代为全-1, 用来标记后来出现的冲突;
				for( j = 0; j < CNUM; j++)
				{
					tempPath[0][j] = -1;
					tempPath[1][j] = -1;
				}
				
				//填入交换的切割段
				for(j = r1; j < r2; j++)
				{
					tempPath[0][j] = path[select][j];
					tempPath[1][j] = path[i][j];
				}
				
				//化简映射集
				//求映射, 如果两个切割段之间有相同的数, 则映射个数不是r2-r1;
				int number = 0;
				int tras[2][CNUM];
				for(j = 0; j < r2-r1; j++)
				{
					tras[0][j] = tempPath[0][j+r1];
					tras[1][j] = tempPath[1][j+r1];
				}
				for(j = 0; j < r2-r1; j++)
				{
					if(tras[0][j] == -1)
						continue;
					if(tras[0][j] == tras[1][j])
					{
						tras[0][j] = tras[1][j] = -1;
						continue;
					}
					for(k = 0; k < r2-r1; k++)
					{
						if(tras[0][j] == tras[1][k])
						{
							tras[1][k] = tras[1][j];
							tras[0][j] = -1;
							tras[1][j] = -1;
							break;
						}
					}
				}
				number = r2 - r1;
				for(j = 0; j < number; j++)
				{
					if(tras[0][j] == -1)
					{
						for(k = j; k < r2 - r1 - 1; k++)
						{
							tras[0][k] = tras[0][k+1];
							tras[1][k] = tras[1][k+1];
						}
						j--;
						number--;
					}
				}
				
				
				//从父体中填入剩下无冲突的城市, 
				for(j = 0; j < CNUM; j++)
				{
					//第一个
					if(j >= r1 && j < r2)
						continue;  //跳过已填好的切割段
					for(k = r1; k < r2; k++)
					{
						if( tempPath[0][k] == path[i][j] )
							break;//冲突, 跳过不填
					}
					if( k == r2)
						tempPath[0][j] = path[i][j];
					
					//第二个
					for(k = r1; k < r2; k++)
					{
						if( tempPath[1][k] == path[select][j])
							break;//冲突, 跳过不填
					}
					if( k == r2)
						tempPath[1][j] = path[select][j];
				}
				
				//解决出现的冲突
				for(j = 0; j < CNUM; j++)
				{
					if(tempPath[0][j] == -1)//现在还未填入, 说明有冲突
					{
						for( k = 0; k < number; k++)
						{
							if(path[i][j] == tras[0][k] )
							{
								tempPath[0][j] = tras[1][k];
							}
						}
					}
					if(tempPath[1][j] == -1)//现在还未填入, 说明有冲突
					{
						for( k = 0; k < number; k++)
						{
							if(path[select][j] == tras[1][k] )
							{
								tempPath[1][j] = tras[0][k];
							}
						}
					}
				}
				
				//保存这两个后代
				memcpy(path[i], tempPath[0], CNUM * sizeof(int));
				memcpy(path[select], tempPath[1], CNUM * sizeof(int));

				select = 0;
			}
		}
	}
}

//OX杂交算子
void CGA_TSP::OX()
{
	int i, j, k, select;
	int tempPath[2][CNUM];

	for(i = 0, select = 0; i < POP; i++)
	{	
		double d = AverageRandom(0, 1);
		if(d < PC)
		{
			if(select == 0)
				select = i;
			else
			{
				int r1 = rand() % CNUM;
				int r2 = rand() % CNUM;
				if( r1 == r2 )
				{
					select = 0;
					continue;
				}

				int r = min( r1, r2);
				r2 = max(r1, r2);
				r1 = r;
				
				//复制切割串;
				for(j = r1; j < r2; j++)
				{
					tempPath[0][j] = path[i][j];
					tempPath[1][j] = path[select][j];
				}
				
				//复制剩余串
				//第一个后代		
				for(j = r2, k = r2; k < r2 + CNUM; k++)
				{
					for(int m = r1; m < r2; m++)
					{
						if( tempPath[0][m] == path[select][k%CNUM] )
							break;
					}
					if( m == r2 )
					{
						tempPath[0][j%CNUM] = path[select][k%CNUM];
						j++;
					}
				}
				
				//第二个后代
				j = r2;
				for(k = r2; k < r2 + CNUM; k++)
				{
					for(int m = r1; m < r2; m++)
					{
						if( tempPath[1][m] == path[i][k%CNUM] )
							break;
					}
					
					if( m == r2 )
					{
						tempPath[1][j%CNUM] = path[i][k%CNUM];
						j++;
					}
				}
				
				//保存这两个后代
				memcpy(path[i], tempPath[0], CNUM * sizeof(int));
				memcpy(path[select], tempPath[1], CNUM * sizeof(int));	
				
				select = 0;
			}
		}
		
	}
}

//类似于模拟退火, t为演化代数, 用来模拟温度
bool CGA_TSP::MY_SA(int t)
{
	double r = AverageRandom(0, 1);
	if(r < (1 - t/(2*Gen)))
		return true;
	return false;
}

//计算某条路径的长度
double CGA_TSP::CalPathLongth(int p[CNUM])
{
	int j, x, y;
	double distSum = 0 ;
	
	for( j = 0; j < CNUM; j++)
	{
		x = city[ p[j] ].x - city[ p[ (j+1)%CNUM ] ].x ;
		y = city[ p[j] ].y - city[ p[ (j+1)%CNUM ] ].y ;
		distSum += sqrt(x*x + y*y) ;
	}
	return distSum;
}

//变异, 采用倒序变换
void CGA_TSP::Mutation(int g)
{
	int i, j, k;
	int tempPath[CNUM];
	for(i = 0; i < POP; i++)
	{
		double d = AverageRandom(0, 1);
		if(d < PM)
		{
			memcpy(tempPath, path[i], sizeof(int)*CNUM);
			int r1 = rand() % CNUM;
			int r2 = rand() % CNUM;
			if( r1 == r2 )
				continue;
			int r = min( r1, r2);
			r2 = max(r1, r2);
			r1 = r;	
			
			for(j = r1, k = r2-1; j < k; j++, k--)
			{
				r = tempPath[j];
				tempPath[j] = tempPath[k];
				tempPath[k] = r;
			}
			double oldP = CalPathLongth(path[i]);
			double newP = CalPathLongth(tempPath);

			if(newP < oldP)
			{
				memcpy(path[i], tempPath, sizeof(int)*CNUM);
				return;
			}
			if(MY_SA(i))
				memcpy(path[i], tempPath, sizeof(int)*CNUM);
		}
	}
}


//遗传算法主体框架函数, 供窗体调用来生成计算线程
DWORD WINAPI EvolveProc(LPVOID lpParameter)
{
	HWND hWnd = (HWND)lpParameter;
	CGA_TSP * pTSP = &tspProblem;
	srand( (unsigned)time( NULL ) );    //初始化随机数

	pTSP->InitPopulation();             //初始化种群
	pTSP->Evaluation();                 //求适应值
	pTSP->KeepTheBest();                //保留最优解
//	MessageBox(NULL, NULL, NULL, MB_OK);
	for(int i = 0; i <= Gen; i++)       //Gen是演化代数
	{
		pTSP->Rotate_Wheel_Select();    //轮盘选

#ifdef PMX_OPERATER						//////////////////////////////
		pTSP->PMX();					//  决定是用pmx算子，		//
#else									//	还是ox算子。			//
		pTSP->OX();						//	在头文件的预定义中		//
#endif									//  集中控制。				//
										//////////////////////////////

		pTSP->Mutation(i);				//简单反序变异算子
		pTSP->Evaluation();				//再评估，求适应值。
		pTSP->KeepTheBest();			//保留最优解

		if(i % REDRAW == 0)					//更新窗体
		{
			SendMessage(hWnd, WM_USER1, i, 0);//通知主窗体取数据
			InvalidateRect(hWnd, NULL, true); //通知主窗体重画
		}
	}
	return 0;
}