tsp.cpp

高效率的人工智能算法

// TSP.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define M 7				//结点个数
#define N 8				//种群个数
#define GEN 1000			//进化代数
#define GEN1 50			//最优解没有改进代数
#define GEN2 200			//平均适应度未改变代数
#define PChange 0.5		//变异概率
#define PCross 0.1		//交叉概率

int currentGEN;				//当前代数
int currentOptimization;	//当前最优代数
int currentGEN2;			//平均适应度对应代数
double averageWeight;		//平均适应度值

int changNumber=(int)ceil(PChange*N);
int crossNumber=(int)ceil(PCross*N);
//int changNumber=1;
//int crossNumber=1;
int selectNumber=N-changNumber-crossNumber*2;

int newNode[N][M+1];
int optimization[M+1];	//最优解
int optimizationCost;	//最优适应度
int nodes[N][M+1] =		//所有结点
{
	{ 1,5,3,4,6,7,2,1	},
	{ 1,3,5,2,6,7,4,1	},
	{ 1,2,5,3,6,7,4,1	},
	{ 1,4,3,5,6,7,2,1	},
	{ 1,3,4,6,7,5,2,1	},
	{ 1,2,4,5,6,7,3,1	},
	{ 1,4,5,6,7,3,2,1	},
	{ 1,3,4,2,6,7,5,1	}
};
int weight[N];			//所有结点的适应度
int randBuf[N];		//随即序列


//定义路径长度
int cost[M][M] = 
{/*
	{   0, 100, 125, 100,  75 },
	{ 100,   0,  50,  75, 125 },
	{ 125,  50,   0, 100, 125 },
	{ 100,  75, 125,   0,  50 },
	{  75, 125, 125,  50,   0 }
	*/
	{   0, 100, 125, 100,  75,  40,  20 },
	{ 100,   0,  50,  75, 125,  35,  20 },
	{ 125,  50,   0, 100, 125,  20,  60 },
	{ 100,  75, 125,   0,  50,  35,  40 },
	{  75, 125, 125,  50,   0,  15,  50 },
	{  40,  35,  20,  35,  15,   0,  40 },
	{  20,  20,  60,  40,  50,  40,   0 }
};

void initGen(int n);				//初始化种群
int termination();					//是否满足停止规则。满足：0		不满足：1
void calculate();					//计算适应值
void produce();						//产生下一代
void getRand();						//产生随机数
void selectFunction();				//执行select操作
void crossFunction();				//执行cross操作
void changeFunction();				//执行change操作

int currentNewNode;					//新一代结点下标
int currentNode;					//当前可以使用的序列下标





int main(int argc, char* argv[])
{

	printf("Hello, this is a test of TSP\n");

	int i=0;

	//初始化种群
	initGen(GEN1);

	while ( termination() )
	{
		//计算最优值
		calculate();

		produce();

	}

	printf("Current GenNum is %d\n",currentGEN);
/*	printf("Current Gen is (%d,%d,%d,%d,%d,%d)\n",
		optimization[0],
		optimization[1],
		optimization[2],
		optimization[3],
		optimization[4],
		optimization[5]
		);
*/
	printf("Current Gen is (");
	for (i=0;i<M+1;i++)
		printf("%d ",optimization[i]);
	printf(")\n");

	printf("The optimization is %d\n",optimizationCost);
	printf("OK!\n");





	return 0;
}

void initGen(int n)
{
	srand( (unsigned)time( NULL ) );		//设置随机数种子

	currentGEN=0;

	optimizationCost=10000;
	currentOptimization=-1;

	currentGEN2=0;
	averageWeight=0;
}

int termination()
{
	//完成预定代数
	if (currentGEN==GEN)
		return 0;

	if (currentGEN-currentOptimization==GEN1)
		return 0;

	if (currentGEN-currentGEN2==GEN2)
		return 0;

	return 1;
}

void calculate()
{
	int i,j,k;
	for (i=k=0;i<N;i++)
	{
		for (j=0;j<M;j++)
		{
			k+=cost[nodes[i][j]-1][nodes[i][j+1]-1];
		}
		weight[i]=k;
		k=0;
	}

	//选择最优适应度解
	for (i=0;i<N;i++)
	{
		if (weight[i] < optimizationCost)
		{
			for (j=0;j<M+1;j++)
			{
				optimization[j]=nodes[i][j];
			}
			optimizationCost=weight[i];
			currentOptimization=currentGEN;
		}
	}

	//平均适应度
	double s;
	for (i=0,s=0;i<N;i++)
	{
		s+=weight[i];
	}
	if (s/N != averageWeight)
	{
		averageWeight=s/N;
		currentGEN2=currentGEN;
	}
}

//产生下一代结点
void produce()
{
	int i,j,k;

	currentNode=0;
	currentNewNode=0;

	getRand();

	//change
	changeFunction();

	//cross
	crossFunction();

	//select
	selectFunction();

	for (i=0;i<N;i++)
	{
		for (j=0;j<M+1;j++)
		{
			nodes[i][j]=newNode[i][j];
		}
	}

	currentGEN++;

	for (i=0;i<N;i++)
	{
		printf("Gen %d:\t",i);
		for (j=0;j<M+1;j++)
		{
			printf("%d ",nodes[i][j]);
		}
		printf("\n");
	}
	printf("--------------------------------------\n");
}

//产生N个(0--(N-1))随机数
void getRand()
{
	int i,j,k;
	for (i=0;i<N;i++)
		randBuf[i]=-1;

	for (i=0;i<N;i++)
	{
lab:	k=rand()%N;
		for (j=0;j<i;j++)
		{
			if (randBuf[j]==k)
			{
				goto lab;
			}
		}
		randBuf[i]=k;
	}
}

void changeFunction()
{
	int i,j,k,s;
	int tempArray[M+1];

	for (i=0;i<changNumber;i++)
	{
		int sub;
		sub=randBuf[currentNode++];			//对原sub代执行变异操作

		//获取要处理的结点
		for (j=0;j<M+1;j++)
			tempArray[j]=nodes[sub][j];

lab2:	j=rand()%M;			//第j位变异
		k=rand()%M+1;
		if ( j==0 ||j==M || k==1 || k==tempArray[j] )
			goto lab2;

		for (s=0;s<M+1;s++)
		{
			if (tempArray[s] == k)
			{
				tempArray[s]=tempArray[j];
				break;
			}
		}
		tempArray[j]=k;		//第j位变异为k

		for (k=0;k<M+1;k++)
			newNode[currentNewNode][k]=tempArray[k];

		currentNewNode++;

		if (tempArray[0]!=1)
		{
			printf("Change error and j is %d\n",j);
			exit(0);
		}

	}
}

void crossFunction()
{
	int i,j,k,s;
	int tempArray1[M+1],tempArray2[M+1];
	
	for (i=0;i<crossNumber;i++)
	{
		int sub1,sub2;
		sub1=randBuf[currentNode++];
		sub2=randBuf[currentNode++];

		//获取要处理的结点
		for (i=0;i<M+1;i++)
		{
			tempArray1[i]=nodes[sub1][i];
			tempArray2[i]=nodes[sub2][i];
		}
		
		j=rand()%(M-1)+1;			//从第j位开始交叉
		
		for (s=j;s<M+1;s++)
		{
			k=tempArray1[s];
			tempArray1[s]=tempArray2[s];
			tempArray2[s]=k;
		}

		//交叉后去除重复数字
		for (i=1;i<j;i++)
		{
lab3:		for (s=1;s<M+1;s++)
			{
				if (i==s)
					continue;
				if (tempArray1[i]==tempArray1[s])
				{
					k=rand()%M+1;
					tempArray1[i]=k;
					goto lab3;
				}
			}

lab4:		for (s=1;s<M+1;s++)
			{
				if (i==s)
					continue;
				if (tempArray2[i]==tempArray2[s])
				{
					k=rand()%M+1;
					tempArray2[i]=k;
					goto lab4;
				}
			}
		}
		
		for (i=0;i<M+1;i++)
		{
			newNode[currentNewNode][i]=tempArray1[i];
			newNode[currentNewNode+1][i]=tempArray2[i];
		}

		currentNewNode+=2;

		if (tempArray1[0]!=1 || tempArray2[0]!=1)
		{
			printf("Cross error\n");
			exit(0);
		}

	}
}

void selectFunction()
{
	int i,j,k,s;
	int sub;
	
	for (i=0;i<selectNumber;i++)
	{
		sub=randBuf[currentNode++];
		for (j=0;j<M+1;j++)
		{
			newNode[currentNewNode][j]=nodes[sub][j];
		}
		currentNewNode++;
	}
}