marklink.cpp

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

double  line_length(POINT x,POINT y)
{
	return(sqrt( pow((x.x-y.x),2) + pow((x.y-y.y),2) ));
}

bool intersect_line(POINT point[],POINT point_line[])
{
  //判断point[2]所构成的线段，是否与point_line[2]所构成的直线相交
  //若相交则返回0，否则返回1
  //思想：当两点同在一条直线的一侧时，则这两点组成的线段不与直线相交

	double y0,y1;  
	double k;  //k标识直线的斜率(还要考虑斜率不存在的情况)
	
	if ( (point_line[0].x == point_line[1].x) ) 
	{
		if ((point[0].x - point_line[0].x ) * (point[1].x - point_line[0].x) >=0)
			return(true);
		else 
			return(false);
	}

	k = (point_line[0].y - point_line[1].y)/(point_line[0].x - point_line[1].x);
	y0 = k * (point[0].x - point_line[0].x) + point_line[0].y;
	y1 = k * (point[1].x - point_line[0].x) + point_line[0].y;

	if ( ((y0 - point[0].y)*(y1 - point[1].y)) >= 0)
		return (true);
	else 
		return (false);
}

bool intersect_partline (POINT point1[], POINT point2[])
   //判断两条线段是否相交
   //相交返回0，否则返回1
   //思想： 先以某两个点（假设是point1）为直线，判断另两个点（point2）是否与该直线相交，相交则返回1
   //		否则以另两个点（point2）作为直线，判断point1的两个点是否与直线相交 ，相交返回1，否则返回0
{
	if ( intersect_line( point1,point2 ) || ( intersect_line( point2,point1 ) ))
		return (true);
	else
		return (false);
}

POINT intersect_point (POINT point1[], POINT point2[])  
 //求两相交线段的交点
{
	POINT pt;
	double k1,k2;

	if ((point1[0].x - point1[1].x) == 0)
	{
		pt.x = point1[0].x;
		k2 = (point2[0].y - point2[1].y)/(point2[0].x - point2[1].x);
		pt.y = k2*(pt.x -point2[0].x) + point2[0].y;
	}
	else if ((point2[0].x - point2[1].x) == 0)
	{
		pt.x = point2[0].x;
		k1 = (point1[0].y - point1[1].y)/(point1[0].x - point1[1].x);
		pt.y = k1*(pt.x -point1[0].x) + point1[0].y;
	}
	else
	{
		k1 = (point1[0].y - point1[1].y)/(point1[0].x - point1[1].x);
		k2 = (point2[0].y - point2[1].y)/(point2[0].x - point2[1].x);
		pt.x = ((point2[0].y-point1[0].y)-(k2*point2[0].x - k1*point1[0].x))/(k1-k2);
		pt.y = k1*(pt.x-point1[0].x) + point1[0].y;
	}

	return(pt);

}

bool intersect_closure(POINT point[2],POINT closure_point[],int num ) 
  //判断point[2]中的两点构成的线段是否与closure_point[]所组成的闭合区域相交，num说明构成闭合区域的节点数
  //相交则返回0， 否则返回1
  //思想：若线段与该区域相交，则该线段必然会与组成该区域的某条边相交
{
	int i;
	if (num >3)    //当point数组中的两点是同一障碍物中的对角线，则跨越障碍物 (障碍物为三角形时则不存在此问题)
	{
		int m=-1,n=-1;
		for(i=0;i<num;i++)  
		{
			if ((point[0].x == closure_point[i].x) && (point[0].y == closure_point[i].y))  m = subscript(closure_point[i]);
			if ((point[1].x == closure_point[i].x) && (point[1].y == closure_point[i].y))  n = subscript(closure_point[i]);
		}
		if ((m>=0) && (n>=0))  //说明m，n在同一障碍物中
			if ((m != (n+1) %num ) && (m !=(n-1+num)%num))  // 当m，n不相邻时则跨越障碍物
				return (false);
	}
	for (i=0 ;i<num ; i++)
	{
		POINT pt[2];
		pt[0] = closure_point[i] ;
		pt[1] = closure_point[(i+1) % num] ;

		if ( ! (intersect_partline(point, pt)) ) return (false);
	}
	return (true);
}

bool intersect_closures(POINT point[2] ) 
{
	if(intersect_closure(point,pts1,4) && intersect_closure(point,pts2,4) && intersect_closure(point,pts3,4) && intersect_closure(point,pts4,3) && intersect_closure(point,pts5,5))
		return(true);
	else
		return(false);
}

bool neighbor(POINT point[2])
{
	int i,j;
	POINT pt[2];	
	for(i=0; i< num_barrier_node-1;i++)         
		for(j =0; j< num_barrier_node-1;j++)    
		{
			if (link_graph[i][j])  
			{
 				pt[0]=barrier[i+1].vertex;
				pt[1]=barrier[j+1].vertex;
				if ( !intersect_partline(point,pt)) return(false);
			}
		}
	return(true);
}

int subscript(POINT point)  //通过坐标点返回该点的下标，即该节点的编号
{
	int i;
	for (i=1; i<num_barrier_node;i++)
	{
		if ((barrier[i].vertex.x == point.x) && (barrier[i].vertex.y == point.y)) return(i);
	}

}

void quick_sort(mark_link a[],int left, int right)  //对temp数组进行快速排序，num_link_line为数组的大小
{
	int l,r;
	mark_link temp;
	double pivot;

	l=left;
	r=right;
	pivot=a[(left+right)/2].length;  //取中位值做分界线

	while(l<r)
	{
		while(a[l].length < pivot) ++l;
		while(a[r].length > pivot) --r;
		
		if (l>=r) break;

		temp = a[l];
		a[l] = a[r];
		a[r] = temp;
		if(l!= pivot) --r;
		if(r!= pivot) ++l;
	}
	if (l ==r) l++;
	if (left<r) quick_sort(a,left,l-1);
	if (l<right) quick_sort(a,r+1,right);
}

void quick_sort_m_node(m_node a[],int left, int right)  //对与每条dijsktra路径相交的链接线按交点x坐标由小到大排序
{
	int l,r;
	m_node temp;
	double pivot;

	l=left;
	r=right;
	pivot=a[(left+right)/2].vertex.x;  //取中位值做分界线

	while(l<r)
	{
		while(a[l].vertex.x < pivot) ++l;
		while(a[r].vertex.x > pivot) --r;
		
		if (l>=r) break;

		temp = a[l];
		a[l] = a[r];
		a[r] = temp;
		if(l!= pivot) --r;
		if(r!= pivot) ++l;
	}
	if (l ==r) l++;
	if (left<r) quick_sort_m_node(a,left,l-1);
	if (l<right) quick_sort_m_node(a,r+1,right);
}

int  optimal(int i,int j)   //i,j 为顶点在barrier数组中的下标
    //即判断以i为顶点，在加入链接线i－j后是否达到最优
	//也即以i为顶点的各链接线之间的夹角均小于180度
	//即各链接线的每相邻的两个端点之间的连线不会跨越顶点i所在的障碍物
	//返回1时表示i节点已经最优，返回2时表示加入节点j后达最优
{	
	int u,w;  //存储与i在同一障碍物中的相邻的两个节点在barrier数组中的下标
	
	if (barrier[i].id == barrier[i+1].id)
		u = i+1;
	else
	{
		u =i-1;
		while(barrier[i].id == barrier[u].id)  {u--;}
		u++;
	}//end if

	if(barrier[i].id == barrier[i-1].id)
		w= i-1;
	else
	{
		w = i+1;
		while(barrier[i].id == barrier[w].id) {w++;}
		w--;
	}//end if

	double k1,k2,k3;   //k1定义u,i两点构成的直线的斜率，k2定义w,i构成的直线的斜率(反正切值)
	k1 = atan2((barrier[u].vertex.y - barrier[i].vertex.y),(barrier[u].vertex.x - barrier[i].vertex.x));
	if (k1<0) k1 = k1+2*pi;
	k2 = atan2((barrier[w].vertex.y - barrier[i].vertex.y),(barrier[w].vertex.x - barrier[i].vertex.x));
	if (k2<0) k2=k2+2*pi;   //k1，k2的值都在[0,2*pi]范围内
	//u以顺时针方向旋转到v的夹角会大于180度（即u顺时针旋转到v比v顺时针旋转到u角度要大）
	
	int t;  
	if (k1<k2)  //u表示角度较大的一点
	{
		t =u;    //u,w表示的节点互换
		u = w;
		w = t;

		k3 = k1;  //k1,k2的值互换
		k1=k2;
		k2=k3;
	}

	if ((k1 -k2)<pi)    //始终保持k1顺时针旋转到k2为要插入链接线的角度
	{
		k3 = k1-2*pi;  //k1,k2的值互换，且把k2的值减2*pi;
		k1=k2;
		k2 = k3;

		t =u;    //u,w表示的节点互换
		u = w;
		w = t;
	}
	int m;
	for(m =1; m< num_barrier_node;m++)
	{
		if (link_graph[i-1][m-1])
		{
			k3 = atan2((barrier[m].vertex.y - barrier[i].vertex.y),(barrier[m].vertex.x - barrier[i].vertex.x));
			if (k2 >0 && k3 <0) k3 = k3+2*pi;  //k1一定会>k2,k2则可能>0或<0 ，当k2>0 则均在【0，2×pi】的范围内讨论
			
			if (k3 <= k2) continue;
			if (k3 > k1)
			{
				k3 = k3 -2*pi;
				if (k3 <=k2)  continue;
			}  //至此k2<k3<k1 一定成立

			if (difference(k1,k3) >= difference(k3,k2) )
			{
				if (difference(k1,k3) >= pi)
				{
					w =m;
					k2 = k3;
				}
				else return(1);
			}
			else 
			{
				if (difference(k3,k2) >= pi)
				{
					u = m;
					k1 =k3;
				}
				else return(1);
			}
		}//end if
	}//end for m

	k3 = atan2((barrier[j].vertex.y - barrier[i].vertex.y),(barrier[j].vertex.x - barrier[i].vertex.x));
	if (k2 >0 && k3 <0) k3 = k3+2*pi;  //k1一定会>k2,k2则可能>0或<0 ，当k2>0 则均在【0，2×pi】的范围内讨论

	if (k3 <= k2) return(0);
	if (k3 > k1)
	{
		k3 = k3 -2*pi;
		if (k3 <=k2)  return(0);
	}  //至此k2<k3<k1 一定成立

	if (difference(k1,k3) >= difference(k3,k2))
	{
		if (difference(k1,k3) >= pi)
		{
			w = m;
			k2 = k3;
		}
		else return(2);
	}
	else 
	{
		if (difference(k3,k2) >= pi)
		{
			u = m;
			k1 =k3;
		}
		else return(2);
	}
}

double  difference(double k1,double k2)   //返回两个角度之间的差值
{
	double t = k1-k2;
	
	while(t >= 2*pi)
	{
		t=t-2*pi;
	}

	while (t<= -2*pi)
	{
		t=t+2*pi;
	}

	return(t);
}

void genetic(void)
{
	generation=0;
	GenerateInitialPopulation();
	EvaluatePopulation();
	while(generation<MaxGeneration)
	{
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();
 		printf("\n");
	}
}
 
//Function:Generate the first population.
//Variable:None

void GenerateInitialPopulation(void)
{
	int i,j;

	//randomize();
	srand(time(0));
	for (i=0;i<PopSize; i++)
	{
		for(j=0;j<CHROMLENGTH;j++)
		{
//			population[i].chrom[j]=(rand()%100)/99.0;
			population[i].chrom[j]=0.5;
		}
		population[i].chrom[CHROMLENGTH]='\0';
	}
}

//Function; Initialize the next generation.
//Variable:None.

void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}

//Function:Evaluate population according to certain formula.
//Variable; None.

void EvaluatePopulation(void)
{
	CalculateObjectValue(); //Calculate object value
//	CalculateFitnessValue();//calculate fitness value
	FindBestAndWorstIndividual();//find the best and worst individual
}

//Function:To decode a binary chromosome into a decimal integer.
//Varible:None.
//Note; The returned value may be plus,of minus.
//For different coding method,this value may 
//be changed int "undigned int".
long DecodeChromsome(char *string ,int point,int length)
{
	int i;
	long decimal=0L;
	char*pointer;

	for(i=0,pointer=string+point;i<length;i++,pointer++)
	{if(*pointer-'0')
	decimal +=(long)pow(2,i);
	}
	return (decimal);

}

//Function :to calculate objectvalue
//Variable: None.
void CalculateObjectValue(void)   //计算每个个体的路径（value）和适应度（fitness）
{
	int i;
	//Rosebrock function 
	for (i=0; i<PopSize; i++)
	{	
		double length=0;
		POINT x,y;
		x = vertex[0][0];
		for (int j=0;j<CHROMLENGTH;j++)
		{
			y.x = vertex[j+1][0].x + (vertex[j+1][1].x - vertex[j+1][0].x)*population[i].chrom[j];  //因为j中没有考虑起点和终点，vertex中考虑了起点