gene.cpp

用遗传算法实现的影片递送问题

#include"Gene.h"
#include<iostream.h>
#include<stdlib.h>
#include<math.h>
//////////////构造函数—〉产生初始种群//////////////
Gene::Gene()
{
	int i;
	int D[CNM_NUM ]={2,4,3,3,2};
	//int D[CNM_NUM]={2,1,2,1,2};
	chromosome[0]=( rand()*CNM_NUM /(RAND_MAX+1) ) + 1;
	for(i=1;i<CHROMOSOMELEN;i++)
	{
		chromosome[i]=( rand()*CNM_NUM /(RAND_MAX+1) ) + 1;
		if( chromosome[i] == chromosome[i-1] )
			i--;
				     
	}
}
void Gene::select()
{
	int i,n;
	int D[CNM_NUM ]={2,4,3,3,2},D0[CNM_NUM ];
	for(i=0;i<CNM_NUM;i++)
		D0[i]=D[i];
	for(i=0;i<CHROMOSOMELEN;i++)
	{
		n=chromosome[i]-1;
		D0[n]--;
	}
	for(i=0;i<CNM_NUM;i++)
		if( D0[i] < 0 )
		{
			for(i=0;i<CHROMOSOMELEN;i++)
				chromosome[i]=0;
			break;
		}
}



void Gene::ShowChrom()
{
	int i;
	for(i=0;i<CHROMOSOMELEN;i++)
		cout<<chromosome[i]<<" ";
	cout<<endl;
}

/////////交叉操作///////////////////////////////////////////////////
void Gene::operator *(Gene& mother)
{
	int i,j,k;
	int tempfather[CHROMOSOMELEN];//offspring[CHROMOSOMELEN];
	int subtour1[CHROMOSOMELEN],subtour2[CHROMOSOMELEN],subtour[CHROMOSOMELEN];//subtour2[CHROMOSOMELEN]为第二操作对象；
	int subtour_start,insert_end,insert_start;
	int subtour1_start_num,subtour2_start_num;
	int subtour1_length,subtour2_length;     //用来记录子巡回的长度；
	int lost_gene[12],over_gene[12];
	int flag_lost=0,flag_over=0;
	int temp;//position1,position2;	
	for(i=0;i<CHROMOSOMELEN;i++)
		tempfather[i]=chromosome[i];
//again:
	subtour_start=( rand() * CNM_NUM/(RAND_MAX-1) )+1;

	//获取subtour2,即mother.chromosome的子巡回；
	i=CHROMOSOMELEN-1;
	while(mother.chromosome[i] != subtour_start)
		i--;	
	j=i-1;
	subtour2_start_num=i;
	while(mother.chromosome[j] != subtour_start)
		j--;
	subtour2_length=i-j+1;	
//	if(subtour2_length==2) goto again;
	for(k=0,temp=subtour2_start_num;k<subtour2_length;k++,temp--)   //把子巡回1保存；
		subtour2[k]=mother.chromosome[temp];

	//获取subtour1,即chromosome的子巡回；
	i=CHROMOSOMELEN-1;
	while(chromosome[i] != subtour_start)
		i--;
	j=i-1;
	subtour1_start_num=i;
	while(chromosome[j] != subtour_start)
		j--;
	subtour1_length=i-j+1;
	for(k=0,temp=subtour1_start_num;k<subtour1_length;k++,temp--)   //把子巡回1保存；
		subtour1[k] = chromosome[temp];
//确定子巡回基因的异同；

	for(j=0;j<subtour2_length;j++)
		subtour[j]=subtour2[j];       //将subtour2[]做备份；
	k=0;
	for(i=0;i<subtour1_length;i++)
	{
		temp=0;
		for(j=0;j<subtour2_length;j++)
			{
				temp++;
				if(subtour2[j] ==subtour1[i] ) //找到相同的基因
				{
					subtour2[j]=0;
					break;
				}
				
				else if ( temp==subtour2_length)
				{
					lost_gene[k++]=subtour1[i];//因为subtour2中没有此基因
												 //所以使得subtour1丢失此基因；需要插入！！
					 flag_lost++;
				}
			}
	}

	k=0;
	for(j=0;j<subtour2_length;j++)
		if(subtour2[j] != 0 )
			{
				over_gene[k++]=subtour2[j];  //subtour2中有但subtour1中没有的基因
//											     //使得subtour1产生剩余；
				flag_over++;
			}
	for(i=subtour1_start_num,temp=subtour1_length;temp>0;temp--,i--)
		tempfather[i]=0;              //将father中的子巡回置为0；

	if(flag_over>0)                   //假设有多余的基因
		{
//begain:
			for(k=0;k<flag_over;k++)
			{
				for(j=CHROMOSOMELEN-1; j>0; j--)
				{
					if(tempfather[j] == over_gene[k])
					tempfather[j]=9;
					break;
				}
					
					/*
					if(tempfather[j]==over_gene[k])
					{
						for(i=j;i>0;i--)
							subtour1[i]=subtour1[i-1];
						goto begain;
					}*/
			}	
		}

	for(j=CHROMOSOMELEN-1; j>0; j--)
		if(tempfather[j] == 9)
			for(k=j;k<1;k--)
				tempfather[k]=tempfather[k-1];

	i=CHROMOSOMELEN-1;
	while( tempfather[i] != 0 )
		i--;

	for(k=subtour2_length-1 ; k>=0 ; k--)
			tempfather[i--]=subtour[k];               //将子巡回2拷贝到子巡回1中；
		                           
	
		insert_end=i;  //insert_end 代表subtour串后面的第一个地址
		insert_start=insert_end+subtour2_length;

	for(j=0;i>0;i--,j++)                           //将末尾的基因紧挨拷贝过去的子巡回2拷贝过来；
		tempfather[i]=chromosome[j];               //i+1可以用来标记丢失的基因个数；

	if(flag_lost>0)                                //将丢失的基因插入到末尾；
		{
			for(i=0;i<flag_lost;i++)
				tempfather[i]=lost_gene[i];
		}
	

for(k=0;k<CHROMOSOMELEN;k++)
	mother.chromosome[k]=tempfather[k]; 

}           

//////////////变异操作////////////////////////////////////////////////////////
void Gene:: operator !()
{
	int position1,position2,temp;

	position1= (rand() * CNM_NUM)/RAND_MAX;
	do
	{
		position2 = (rand() * CNM_NUM)/RAND_MAX;
	}while(position1==position2);  //2个变异点不要相同
	temp=chromosome[position1];    //2变异点交换
	chromosome[position1]=chromosome[position2];
	chromosome[position2]=temp;
	//for(k=CHROMOSOMELEN-1;k>0;k--)
	//	if(chromosome[k]==chromosome[k-1])
	//		goto C;

}
///////////////////赋值/////////////////////////////////////////////////////////
void Gene::operator =(Gene Get)
{
	int i;
	for(i=0;i<CHROMOSOMELEN;i++)
		chromosome[i]=Get.chromosome[i];
}
//交换
void Gene::operator ==(Gene& Get)
{
	int i,temp;
	for(i=0;i<CHROMOSOMELEN;i++)
	{
		temp=Get.chromosome[i];
		Get.chromosome[i]=chromosome[i];
		chromosome[i]=temp;
	}
}
//距离
double Gene::distance()
{
	int i;
	double W[CNM_NUM][CNM_NUM]={D_NAN,  3,      4,      2,     7,
								3,   D_NAN,  4,      6,     3,
								4,   4,      D_NAN,  5,     8,
								2,   6,      5,      D_NAN,  6,
								7,   3,      8,       6,     D_NAN};
	double sum=0;//距离之和
	for(i=0;i<(CHROMOSOMELEN-1);i++)
	{//前面的城市间距离
		if( chromosome[i] == chromosome[i+1])
		{
			return D_NAN;
			break;
		}
		sum+=/*sqrt(
			pow( MyCNM[chromosome[i]-1][0]-MyCNM[chromosome[i+1]-1][0] , 2 )
			+pow( MyCNM[chromosome[i]-1][1]-MyCNM[chromosome[i+1]-1][1], 2 )
			)*/W[chromosome[i]-1][chromosome[i+1]-1];
	}
	sum+=/*sqrt(
		pow( MyCNM[chromosome[CHROMOSOMELEN -1]-1][0]-MyCNM[chromosome[0]-1][0] , 2 )
		+pow( MyCNM[chromosome[CHROMOSOMELEN -1]-1][1]-MyCNM[chromosome[0]-1][1] , 2)
		)*/W[chromosome[CHROMOSOMELEN -1]] [chromosome[0]-1];
	return sum;

}
//比较是否一样
bool Gene::operator &(Gene Get)
{
	for(int i=0;i<CHROMOSOMELEN;i++)
		if(chromosome[i]!=Get.chromosome[i])
			return false;
	return true;
}
//	影院位置的定义
int Gene::MyCNM[CNM_NUM][2]={ 0, 2, 2, 2, 2, 1, 1, 0, 0, 1};