marklink.cpp

蚁群算法和遗传算法程序c语言代码

#include <math.h>
#include <stdlib.h>
#include <time.h>
#include  <iostream.h>
#include "stdio.h"

#define pi 3.14
#define num_ants  10
#define num_cycle 200 
#define num_sections  10
#define f 1  //信息量指数
#define v  2//能见度指数
#define e  5
#define Q  100
#define c  0.1   //初始信息量
#define s  0.85

#define MAX 100
#define infinite  1000

	typedef struct POINT
	{
		double x;
		double y;
	}POINT;

	typedef struct m_node
	{
		POINT vertex;
		int id1;
		int id2;
	}m_node; //链接线中点

	typedef struct b_node
	{
		POINT vertex;
		int id;  //标识此障碍物顶点属于哪个障碍物
	}b_node;  //障碍物顶点

	typedef struct mark_link
	{
		int id;  //按节点i到其他顶点的长度从短到长存储顶点的序号，即barrier数组的下标
		double length;  //length[m]表示节点i到节点m的距离
	}mark_link;
	

	POINT pts1[4],pts2[4],pts3[4],pts4[3],pts5[5];  //每个数组存储一个障碍物区域
	POINT start,end;  //定义起点和终点坐标
	b_node barrier[MAX];  //存储起点、终点及障碍物顶点的坐标
	m_node middle[MAX];   //存储起点、终点及中点的坐标
	POINT vertex[MAX][2];  //包括起点和中点，及其他路径点的相关中点

	int  num_barrier ;  //定义障碍物的数目
	int  num_barrier_node ;   //定义障碍物的顶点总数,是从0开始计数
	int  num_middle_node;   //定义中点的总数，从0开始计数，包括起点和终点
	int  num_path_node;   //定义需要调节的节点数
	int  num_dijkstra_path_node ;   //定义求得的最短路径上节点数

	double adjlist[MAX][MAX];  //	存储各中点到其他顶点的最短距离的邻接矩阵
	int final[MAX];  //存储从终点到起点的节点的id号（此id号是m_node中的m_id)
	int dijkstra_node[MAX];  //存储由dijkstra算法求得的从终点到起点的节点的id号（此id号是m_node中的m_id)
	bool link_graph[MAX][MAX];  //当link_graph[i][j] ＝ true时，说明节点i+1到j+1之间已存在链接线
	int subscript(POINT point);  //通过坐标点返回该点的下标，即该节点的编号

	void initial_coordinate();   //初始化障碍物及起点和终点坐标
	void initial_m_node();       //初始化障碍物中点，及其邻接矩阵
	void initial_map();
	void  get_path();

	double acs_improve();
	double acs();
	double acs_1();
	double acs_2();
	double ant_path();
	double ant_path_improve();	
	double line_length(POINT x,POINT y);
	double length_best_path;  //存储最优路径的长度
	double  difference(double k1,double k2);

	POINT intersect_point (POINT point1[], POINT point2[]); 
	bool intersect_line(POINT  point[],POINT point_line[]);
	bool intersect_partline(POINT point1[],POINT point2[]);
	bool intersect_closure(POINT point[],POINT closure_point[],int num);
	bool intersect_closures(POINT point[]);
	bool neighbor(POINT point[]);
	
	void quick_sort_m_node(m_node a[],int left, int right);  //对与每条dijsktra路径相交的链接线按交点x坐标由小到大排序
	void quick_sort(mark_link a[],int left, int right);  //对temp数组进行排序，num_link_line为数组的大小
	int optimal(int i,int j);

	////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////遗传算法定义的变量//////////////////////////////////////////////////////////////////////
	#define POPSIZE 100//population size
	#define alfa 0.5

	//The Definition of User Data
	//(For different problem,there are some difference.)

	int PopSize=50; //population size
 	int MaxGeneration=200; //max.number of generation
	double Pc=0.3; //probalility of crossover
	double Pm=0.05; //probalility of mutation

	//The definition of Data Structure


	struct individual //data structure of individual 
	{
	float chrom[9];//a string of code representing individual

	double value; //object value of this individual
	double fitness; //fitness value of this individual 
	};

	//The definition of Global Variables 
	int CHROMLENGTH=6;  //number of path node
	int	LENGTH=3;
	int generation; //number of generation
	int best_index; //index of best individual
	int worst_index;//index of worst individual
	int best_generation; //index of best generation
	double average[200];//每代中各个体的平均值
	double devi[200];//每代的标准偏差值

	struct individual bestindividual;
	//best individual of current generation
	struct individual worstindividual; 
	//worst individual of current generation
	struct individual currentbest ; //best individual by now 
	struct individual population [POPSIZE]; //population
	//Declaration of Prototype

	void GenerateInitialPopulation (void);
	void GenerateNextPopulation (void );
	void EvaluatePopulation (void);
	long DecodeChromosome (char*,int,int);
	void CalculateObjectValue(void);
	void CalculateFitnessValue(void);
	void FindBestAndWorstIndividual(void);
	void PerformEvolution(void);
	void SelectionOperator(void);
	void CrossoverOperator(void);
	void MutationOperator(void);
	void OutputTextReport(void);
	void genetic(void);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void initial_coordinate()
{
	num_barrier = 5;
	num_barrier_node = 0;

	start.x =15;
	start.y =15;
	barrier[num_barrier_node].id = 0;
	barrier[num_barrier_node].vertex.x = 15;
	barrier[num_barrier_node++].vertex.y = 15;

 	pts1 [0].x =40;
	pts1 [0].y =62;
	barrier[num_barrier_node].id = 1;
	barrier[num_barrier_node].vertex.x = 40;
	barrier[num_barrier_node++].vertex.y = 62;
	pts1 [1].x =66;
	pts1 [1].y =62;
	barrier[num_barrier_node].id = 1;
	barrier[num_barrier_node].vertex.x = 66;
	barrier[num_barrier_node++].vertex.y = 62;
	pts1 [2].x =66;
	pts1 [2].y =199;
	barrier[num_barrier_node].id = 1;
	barrier[num_barrier_node].vertex.x = 66;
	barrier[num_barrier_node++].vertex.y = 199;
	pts1 [3].x =40;
	pts1 [3].y =199;
	barrier[num_barrier_node].id = 1;
	barrier[num_barrier_node].vertex.x = 40;
	barrier[num_barrier_node++].vertex.y = 199;

	pts2 [0].x =115;
	pts2 [0].y =75;
	barrier[num_barrier_node].id = 2;
	barrier[num_barrier_node].vertex.x = 115;
	barrier[num_barrier_node++].vertex.y = 75;
	pts2 [1].x =95;
	pts2 [1].y =136;
	barrier[num_barrier_node].id = 2;
	barrier[num_barrier_node].vertex.x = 95;
	barrier[num_barrier_node++].vertex.y = 136;
	pts2 [2].x =123;
	pts2 [2].y =187;
	barrier[num_barrier_node].id = 2;
	barrier[num_barrier_node].vertex.x = 123;
	barrier[num_barrier_node++].vertex.y = 187;
	pts2 [3].x =170;
	pts2 [3].y =105;
	barrier[num_barrier_node].id =2;
	barrier[num_barrier_node].vertex.x = 170;
	barrier[num_barrier_node++].vertex.y = 105;

	pts3 [0].x =90;
	pts3 [0].y =244;
	barrier[num_barrier_node].id = 3;
	barrier[num_barrier_node].vertex.x =90;
	barrier[num_barrier_node++].vertex.y = 244;
	pts3 [1].x =90;
	pts3 [1].y =305;
	barrier[num_barrier_node].id = 3;
	barrier[num_barrier_node].vertex.x = 90;
	barrier[num_barrier_node++].vertex.y = 305;
	pts3 [2].x =183;
	pts3 [2].y =305;
	barrier[num_barrier_node].id = 3;
	barrier[num_barrier_node].vertex.x = 183;
	barrier[num_barrier_node++].vertex.y = 305;
	pts3 [3].x =183;
	pts3 [3].y =244;
	barrier[num_barrier_node].id = 3;
	barrier[num_barrier_node].vertex.x = 183;
	barrier[num_barrier_node++].vertex.y = 244;

	pts4 [0].x =238;
	pts4 [0].y =39;
	barrier[num_barrier_node].id = 4;
	barrier[num_barrier_node].vertex.x = 238;
	barrier[num_barrier_node++].vertex.y = 39;
	pts4 [1].x =212;
	pts4 [1].y =102;
	barrier[num_barrier_node].id = 4;
	barrier[num_barrier_node].vertex.x = 212;
	barrier[num_barrier_node++].vertex.y =102;
	pts4 [2].x =274;
	pts4 [2].y =82;
	barrier[num_barrier_node].id = 4;
	barrier[num_barrier_node].vertex.x = 274;
	barrier[num_barrier_node++].vertex.y =82;
	
	pts5 [0].x =258;
	pts5 [0].y =145;
	barrier[num_barrier_node].id = 5;
	barrier[num_barrier_node].vertex.x =258;
	barrier[num_barrier_node++].vertex.y = 145;
	pts5 [1].x =234;
	pts5 [1].y =160;
	barrier[num_barrier_node].id = 5;
	barrier[num_barrier_node].vertex.x = 234;
	barrier[num_barrier_node++].vertex.y = 160;
	pts5 [2].x =234;
	pts5 [2].y =239;
	barrier[num_barrier_node].id = 5;
	barrier[num_barrier_node].vertex.x = 234;
	barrier[num_barrier_node++].vertex.y = 239;
	pts5 [3].x =296;
	pts5 [3].y =239;
	barrier[num_barrier_node].id = 5;
	barrier[num_barrier_node].vertex.x = 296;
	barrier[num_barrier_node++].vertex.y = 239;
	pts5 [4].x =296;
	pts5 [4].y =213;
	barrier[num_barrier_node].id = 5;
	barrier[num_barrier_node].vertex.x = 296;
	barrier[num_barrier_node++].vertex.y = 213;

	end.x = 315;
	end.y = 315;
	barrier[num_barrier_node].id = 0;   //0 标识为起点或终点
	barrier[num_barrier_node].vertex.x = 315;
	barrier[num_barrier_node].vertex.y = 315;
}


void initial_m_node()
{
	int i,j;

	for(i=0; i< num_barrier_node-1;i++)         //注：此时的link_graph应不包含起点和终点，即此时i，j与
		for(j =0; j< num_barrier_node-1;j++)    //barrier数组中相应的点的下标是i＋1，j＋1
		{
			link_graph[i][j] = false;
		}
	//初始化边界值
	link_graph[0][12] = true; link_graph[12][0] =true;
	link_graph[3][9]  = true; link_graph[9][3]  = true;
	link_graph[10][18]  = true; link_graph[18][10]  = true;
	link_graph[19][14]  = true; link_graph[14][19]  = true;

	for(i=1; i< num_barrier_node;i++)  //num_barrier_node 是从0开始计数的，且包括起点和终点,此时的i，j是barrier数组的下标
	{
		if (i==1 || i==4 || i== 10 || i== 11 ||i==19 ||i== 20 ||i==15||i==13)
			continue;   //当i是边界上的顶点时则不需考虑

		mark_link temp[MAX];   //存储有关以i为顶点的链接线的另一端点在barrier数组中的下标及长度
		int num_link_line = 0;   //以i为顶点的链接线数目
		
		POINT point[2];
		point[0] = barrier[i].vertex ;
		for(j =1; j< num_barrier_node;j++)
		{
 			point[1] = barrier[j].vertex;
			
			if (i!=j && !link_graph[i-1][j-1] && intersect_closures(point))   //当此链接线还没有加入，才考虑该条链接线
			{							
				temp[num_link_line].id = j;
				temp[num_link_line++].length = line_length(barrier[i].vertex,barrier[j].vertex);
			}//end if
		}// end for j
		
		quick_sort(temp,0,num_link_line-1);

		int flag=0;  //此时flag作为标志位，当flag不为0时说明该点已达到最优
		int m;
		int n=0;
		while(!flag && n < num_link_line)  
		{					
			for(m = n; m< num_link_line; m++)
			{
				if ( (optimal(i,temp[m].id) == 2) )   //判定这两个顶点组成的链接线是否为最优链接线
				{
				flag = temp[m].id;
				link_graph[i-1][temp[m].id-1] = true;
				break;
				}//end if 
			}//end for m

			if(!flag)
			{
				link_graph[i-1][temp[n].id-1] = true;  //当不存在一条链接线使i节点达最优 则将最短的一条添加进去
				n=n+1;
			}//end if
		}//end while
	}//end for i

	for(i=0; i< num_barrier_node-1;i++)         //删除多余链接线
		for(j =0; j< num_barrier_node-1;j++)    
		{
			if (link_graph[i][j])  link_graph[j][i] = true;												
		}

	for(i=0; i< num_barrier_node-1;i++)         
		for(j =0; j< num_barrier_node-1;j++)    
		{
			if (link_graph[i][j])  	
			{
				link_graph[i][j] = false;	
				if ((optimal(i+1,j+1) != 1) || (optimal(j+1,i+1) !=1 ))  link_graph[i][j] = true;
			}
		}
			
	num_middle_node = 0;
	
	middle[num_middle_node].id1 = 0;
	middle[num_middle_node].id2 = 0;
	middle[num_middle_node++].vertex =barrier[0].vertex;

	for	(i=1; i< num_barrier_node;i++)  //添加中点
		for(j=1; j<num_barrier_node; j++)
		{
			if (link_graph[i-1][j-1])
			{
				middle[num_middle_node].id1 = i;
				middle[num_middle_node].id2 = j;
				middle[num_middle_node].vertex.x = (barrier[i].vertex.x +barrier[j].vertex.x) /2;
				middle[num_middle_node++].vertex.y = (barrier[i].vertex.y +barrier[j].vertex.y) /2;	
				link_graph[j-1][i-1] = false;
			}
		}

 	middle[num_middle_node].id1 = num_barrier_node;
	middle[num_middle_node].id2 = num_barrier_node;
	middle[num_middle_node].vertex =barrier[num_barrier_node].vertex;
}



void initial_map()           //dijkstra 算法实现的最短路径
{
	int m,n,i;
	int path[MAX];   //用于存储所走路径的节点号  path[m]=n 表示过m顶点的苦境路径必定经过n点
	double d[MAX];   //d[n] 表示顶点n到起点的目前的最短距离
	bool visited[MAX];   //表示该节点是否已访问
	double  min;

/*	for (m=0; m<= num_middle_node; m++)
	{
		POINT PT[2],pt[2];
		
		PT[0] = start;             //起点与其它点直接的距离
		PT[1] = barrier[middle[m].id1].vertex;
		pt[0] = start;
		pt[1] = barrier[middle[m].id2].vertex;
		if( intersect_closures(PT) && intersect_closures(pt))
			{
				adjlist[m][0]=line_length(start,middle[m].vertex);
				adjlist[0][m]=adjlist[m][0];
			}
			else
			{
				adjlist[m][0]=infinite;
				adjlist[0][m]=infinite;
			}
	
		PT[0] = end;             //起点与其它点直接的距离
		PT[1] = barrier[middle[m].id1].vertex;
		pt[0] = end;
		pt[1] = barrier[middle[m].id2].vertex;
		if( intersect_closures(pt) && intersect_closures(PT) )
			{
				adjlist[m][num_middle_node]=line_length(middle[m].vertex,end);
				adjlist[num_middle_node][m]=adjlist[m][num_middle_node];
			}
			else
			{
				adjlist[m][num_middle_node]=infinite;
				adjlist[num_middle_node][m]=infinite;
			}
	}
*/
	for (m=0; m<=num_middle_node;m++)
	{
		adjlist[0][m] = infinite;
		adjlist[m][0] = infinite;
		adjlist[num_middle_node][m]=infinite;
		adjlist[m][num_middle_node]=infinite;
		if (m==1)