遗传算法求解中国旅行商问题C语言

使用遗传算法求解中国旅行商问题（31个城市），数据从文件中（网上找到）读取。求得的最好结果是：15397.5km（不是每次都能有这个解）,比介绍算法的人工智能上说的15404km略短，编程环境Visual studio2013，所以个别函数在低版本环境下可能需要修改（例如fopen_s在低版本环境下为fopen）。

/**
*遗传算法求解中国旅行商问题
*遗传算法使用的三个算子：
*（1）选择算子：根据适应度函数，选择适应度该高的个体进行下一步的杂交，
      反应进化过程中优胜劣汰的自然规律
*（2）交叉算子：交叉过程随机选择两个个体进行排队，根据预先设定的交叉概
      率Pc（0.5~0.8），决定是否交叉，交叉方法有单点交叉，两点交叉，和均
	  匀交叉，这个类似于生物学中染色体交换基因片段
*（3）变异算子：变异算子将新个体的基因链中的某一位或者某一片段按变异概率
      Pm（0.001~0.1）进行变异
**/

#include
#include
#include
#include
#include“qsort.h“
#define INF 9999999  //指定为正无穷

//定义坐标点结构体
struct Point
{
	int x;
	int y;
};
/**********************************************
*以下过程包括：
*1. 读入31个城市的坐标位置
*2. 求任意两个城市间的距离
*3. 求一条完整路径的总长度
************************************************/
//从文件读取坐标点
Point* getPoints（int len char* filename）
{
	Point* ps = （Point*）malloc（sizeof（Point）*len）;
	FILE *infile;
	fopen_s（&infile filename “r“）;
	if （infile == NULL）
	{
		printf（“文件打开失败\n“）;
	}
	for （int i = 0; i < len; i++）
	{
		fscanf_s（infile “%d%d“ &ps[i].x &ps[i].y）;
	}
	fclose（infile）;
	return ps;
}

//求两点间的距离
float getDistance（Point p1 Point p2）
{
	return powf（powf（p1.x - p2.x 2） + powf（p1.y - p2.y 2） 0.5）;
}

//计算任意两座城市间的距离，并保存在二维数组里
float** getAnyDistance（Point* ps int len）//求任意两座城市之间的距离
{
	float** cost = （float**）malloc（sizeof（float*）*len）;
	for （int i = 0; i < len; i++）
	{
		cost[i] = （float*）malloc（sizeof（float）*len）;
	}
	for （int i = 0; i < len; i++）
	{
		for （int j = i + 1; j < len; j++）
		{
			cost[i][j] = getDistance（ps[i] ps[j]）;
			cost[j][i] = cost[i][j];
		}
		cost[i][i] = 0;
	}
	return cost;
}

//计算一条环路的总长度，本算法里面的适应度就是以环路的长度为标准，越小适应度越高
float getTotalDistance（int *path float **cost int len）
{
	float total = 0;
	for （int i = 0; i < len - 1; i++）
	{
		total += cost[path[i]][path[i + 1]];
	}
	total += cost[path[len - 1]][path[0]];
	return total;
}

void copyPath（int *path1 int *path2 int len）
{
	while （len>0）
	{
		path1[len - 1] = path2[len - 1];
		len--;
	}
}
/****************************************************/
//判断值在不在数组的start位到end位之间，在返回标号，不在-1;
int isInArray（int value int *s int start int end）
{   
	//printf（“vslue=%d start=%dend=%d\n“ valuestartend）;
	for （int i = start; i <= end; i++）
	{   
		//printf（“s[%d] = %d\n“ is[i]）;
		if （s[i] == value）
		{   
			//printf（“%d返回值：%d\n“ i s[i]）;
			return i;
		}
	}	
		return -1;		
}

//两个个体交叉，产生两个新的个体的过程
void Cross（int *f1 int *f2 int *s1 int *s2 int start int end int len）
{   
	
	if （start >= end || end >= len）
	{
		return;
	}
	int jk;
	for （int i = start; i <= end; i++）//交换start到end间的基因片段
	{
		s1[i] = f2[i];
		s2[i] = f1[i];
	}
	/**
	*理论上讲交叉过程应该保持其他部分不变化，但受制于本讨论问题中每一个城市
	*是唯一的，并且要求出现并且只能出现在回路中一次，（出发节点两次）因此交换
	*基因片段后必将影响其他部分，这里的工作就是在尽量保证不变的前提下，解决冲突
	*本算法参考博客名为 xiaoning6p14 关于巡回旅行商问题的遗传算法路径交叉的思路
	*进行编写，使用部分匹配交叉（PMX）详细算法地址为：
	*http://blog.sina.com.cn/s/blog_5d7883db0100bl04.html
	**/
	for （int i = （end+1）%len; i != start; i++i%=len）
	{   
		j = isInArray（f1[i] s1 start end）;
		if （j!=-1）
		{  
			k = isInArray（f1[j] s1 start

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-12-10 18:12  GA_TSP\
     目录           0  2013-12-04 15:47  GA_TSP\Debug\
     文件       37376  2013-12-04 17:28  GA_TSP\Debug\GA_TSP.exe
     文件      363452  2013-12-04 17:28  GA_TSP\Debug\GA_TSP.ilk
     文件      510976  2013-12-04 17:28  GA_TSP\Debug\GA_TSP.pdb
     目录           0  2013-12-04 17:28  GA_TSP\GA_TSP\
     目录           0  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\
     文件       27857  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA.obj
     文件        1857  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.log
     目录           0  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\
     文件        3902  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\CL.read.1.tlog
     文件        1670  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\CL.write.1.tlog
     文件         171  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\GA_TSP.lastbuildstate
     文件        1298  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\cl.command.1.tlog
     文件        2442  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.command.1.tlog
     文件        2660  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.read.1.tlog
     文件         580  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\GA_TSP.tlog\link.write.1.tlog
     文件        4430  2013-12-04 17:13  GA_TSP\GA_TSP\Debug\QSort.obj
     文件       60416  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\vc120.idb
     文件       86016  2013-12-04 17:28  GA_TSP\GA_TSP\Debug\vc120.pdb
     文件        7929  2013-12-04 17:28  GA_TSP\GA_TSP\GA.cpp
     文件        4188  2013-12-04 11:32  GA_TSP\GA_TSP\GA_TSP.vcxproj
     文件        1150  2013-12-04 11:32  GA_TSP\GA_TSP\GA_TSP.vcxproj.filters
     文件         796  2013-12-04 17:10  GA_TSP\GA_TSP\QSort.cpp
     文件         369  2013-12-02 13:46  GA_TSP\GA_TSP\points.txt
     文件          50  2013-12-04 13:14  GA_TSP\GA_TSP\qsort.h
     文件         338  2013-12-10 18:09  GA_TSP\GA_TSP\result.txt
     文件     2883584  2013-12-10 18:12  GA_TSP\GA_TSP.sdf
     文件         964  2013-12-04 10:04  GA_TSP\GA_TSP.sln
     文件       24064  2013-12-10 18:12  GA_TSP\GA_TSP.v12.suo