ga.c

清华大学《人工智能导论》课程电子教案,给大家看看

//采用遗传算法求解TSP问题
//作者：马少平
//时间：2007年5月
//说明：该程序没有考虑程序的运行效率和灵活性，重点在于展示遗传算法的核心部分，力求程序简练

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <memory.h>

#define MAXN	100			//最大城市数
#define N       400			//种群规模，要求是偶数
#define GEN		500			//进化代数
#define PM		0.2			//变异概率
#define PC		0.6			//杂交概率

int		n;					//城市数
char	name[MAXN];			//以字母命名的城市名组
double	pos[MAXN][2];		//每个城市的x、y坐标
double	dis[MAXN][MAXN];	//任意两个城市间的距离
int		group[N][MAXN];		//种群
int     pool[N][MAXN];		//用于做中间变量用，在选择种群时

double Rand01()
{
	return 1.0*rand()/RAND_MAX;
}

int Init(FILE *pFile)		//读取数据文件，计算两两城市间的距离
{
	int i, j;

	fscanf(pFile, "%d", &n);

	for (i = 0; i < n; i++)
	{
		fscanf(pFile, " %c %lf %lf", &name[i], &pos[i][0], &pos[i][1]);
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			dis[i][j] = sqrt((pos[i][0] - pos[j][0])*(pos[i][0] - pos[j][0]) + 
				             (pos[i][1] - pos[j][1])*(pos[i][1] - pos[j][1]));
		}
	}

	return n;
}

double Len(int n, int path[])		//计算给定路径的长度
{
	double len = 0.0;
	int i;

	for (i = 0; i < n; i++)
	{
		len += dis[path[i]][path[(i+1)%n]];
	}
	return len;
}

int PathCopy(int path1[], int path2[], int n)
{
	int i;
	for (i = 0; i < n; i++) path1[i] = path2[i];
	return 0;
}

double InitPath(int n, int path[])		//随机生成一条路径，n为城市数，在path中得到一条路径, 返回路径长度
{
	int i, p, m;

	for(i = 0; i < n; i++) path[i] = i;

	for (i = 0; i < n; i++)
	{
		p = rand()%n;
		m = path[i];
		path[i] = path[p];
		path[p] = m;
	}

	return Len(n, path);
}


double Copulation(int n, int path1[], int path2[], int newpath[])
//杂交过程，由path1和path2杂交，产生一个后代newpath
//杂交方法：从path1的start开始连续取len个复制到newpath中，其他的按照path2中的顺序进行填充
//n是城市数
//返回后代的路径长度
{
	int used[MAXN] = {0};
	int i, j, k;
	int start, len;

	start = rand()%n;
	len = rand()%(n-1) + 1;

	for (i = 0; i < len; i++)	//复制start开始的len位
	{
		j = (i+start)%n;
		newpath[j] = path1[j];
		used[path1[j]] = 1;
	}

	k = 0;
	for (i = 0; i < n-len; i++)
	{
		j = (j+1)%n;
		while (used[path2[k]]) k++;
		newpath[j] = path2[k++];
	}

	return Len(n, newpath);
}

double Variation(int n, int path1[], int path2[])		
//变异操作，n是城市数，path1是当前路径，path2是变异后的新路径，返回值为新路径长度
//u、v（u<v）表示在u、v之间交换。为了顾及到两端的情况，交换前对path1进行一次循环位移
{
	int i, j, p;
	int u, v;
	
	p = rand()%n;

	for (i = p; i < n; i++)
	{
		path2[i-p] = path1[i];
	}
	for (i = 0; i < p; i++)
	{
		path2[n-p+i] = path1[i];
	}

	do {
		u = rand()%n;
		v = rand()%n;
	} while ((v-u) <= 2);

	i = u+1;
	j = v-1;
	
	while (i < j)
	{
		p = path2[i];
		path2[i] = path2[j];
		path2[j] = p;
		i++;
		j--;
	}

	return Len(n, path2);
}

void PrintPath(int n, int path[])
{
	int i;
	for (i = 0; i < n; i++)
	{
		printf("%c", name[path[i]]);
	}
	printf("\n");
}

int Fitness(int n, int group[][MAXN], double f[]) //计算适应值，采用非线性加速的方法
{
	int i;
	double min = 1E20;

	for (i = 0; i < N; i++)
	{
		f[i] = Len(n, group[i]);
		if (min > f[i]) 
		{
			min = f[i];
		}
	}

	for (i = 0; i < N; i++)
	{
		if (f[i]-min < 5E-5) f[i] = 20;
		else f[i] = 1/(f[i] - min);
	}

	return 0;
}

int Select(int n, int group[][MAXN], double f[])	
//采用轮盘赌的方式，从种群group中选择，生成新的种群
//n是城市数, N是种群规模, f[]是适应值
{
	double sum = 0.0;
	int i, j;
	double y, x;

	for (i = 0; i < N; i++)
	{
		sum += f[i];
	}

	for (i = 0; i < N; i++)  //得到概率
	{
		f[i] = f[i]/sum;

	}

	for (i = 0; i < N; i++) //轮盘赌的方法进行选择
	{
		y = Rand01();
		x = 0;
		for (j = 0; j < N; j++)
		{
			x += f[j];
			if (y < x || j == N-1)  //由于实数表示误差的关系，有可能一个也选择不到（出现这种情况的可能性极小），
				                    //所以，当前面都不被选择时，默认选最后一个
			{
				PathCopy(pool[i], group[j], n);
				break;
			}
		}
	}

	for (i = 0; i < N; i++)
	{
		PathCopy(group[i], pool[i], n);
	}

	return 0;
}

void PrintGen(int n, int group[][MAXN])
{
	int i = 0;
	for (i = 0; i < N; i++)
	{
		PrintPath(n, group[i]);
	}
}

double GA(int n, int bestpath[])  //n为城市数，path得到路径，返回值为路径的长度
{
	int i, k, j;
	double best = 0;
	double bestlen = 1.0E20;
	double x;
	int temp1[MAXN], temp2[MAXN];
	double f[N];

	for (i = 0; i < N; i++)
	{
		x = InitPath(n, group[i]);
	}

	for (i = 0; i < GEN; i++)  //进化GEN代
	{
		Fitness(n, group, f);

		j = 0;
		best = 0;
		for (k = 0; k < N; k++)  //找出当前种群的最优解
		{
			if (best <= f[k])
			{
				best = f[k];
				j = k;
			}
		}
		
		x = Len(n, group[j]);  
		if (x < bestlen) 
		{
			bestlen = x;  //目前为止的最优解
			PathCopy(bestpath, group[j], n);
		}

		Select(n, group, f);

		for (k = 0; k < N; k+=2)
		{
			if (Rand01() < PC) //杂交
			{
				Copulation(n, group[k], group[k+1], temp1);
				Copulation(n, group[k+1], group[k], temp2);
				PathCopy(group[k], temp1, n);
				PathCopy(group[k+1], temp2, n);
			}
		}

		for (k = 0; k < N; k++)
		{
			if (Rand01() < PM)  //变异
			{
				Variation(n, group[k], temp1);
				PathCopy(group[k], temp1, n);
			}
		}

	}

	return bestlen;
}

int main()
{
	int path[MAXN];
	int i;
	FILE *pFile = NULL;

	double len;

	srand(time(NULL));

	pFile = fopen("TSP20.txt", "r");
	Init(pFile);
	fclose(pFile);

	for (i = 0; i < 10; i++)
	{
		len = GA(n, path);
		PrintPath(n, path);
		printf("len = %f\n", len);
	}
}