www.pudn.com > GA_VRPTW.rar > ga.h, change:2005-06-20,size:18802b


#ifndef ga_h 
#define ga_h 
#include<iostream> 
#include<cstdlib> 
#include<ctime> 
#include<cmath> 
#include<fstream> 
#include<iomanip> 
 
#include "head.h" 
 
#define VehicleLoad 8 
#define speed 50 
#define maxgen 500 
#define probility 0.99 
 
using namespace std; 
ofstream outfile; 
int ImportNum; 
 
void CImport::Print()  
{ 
	outfile<<left<<setw(7)<<GetOrder()<<setw(7)<<GetPointx() 
		   <<setw(7)<<GetPointy()<<setw(7)<<GetLoad() 
		   <<setw(7)<<GetTime()<<setw(7)<<GetEarlytime() 
		   <<setw(10)<<GetLatetime()<<endl; 
 
}// end of CImport::print 
 
void CVehicleExport::Print()  
{//打印出货点信息 
	outfile<<"\n CVehicleExport" 
		   <<"\n name pointx pointy VehicleNum"<<endl; 
	outfile<<left<<setw(6)<<GetName()<<setw(7)<<GetPointx() 
		   <<setw(7)<<GetPointy()<<setw(6)<<GetVehicleNum() 
		   <<endl; 
}// end of CVehicleExport::print 
 
CVehicleExport::operator CImport() 
{CImport ip; 
 int x=GetPointx(); 
 int y=GetPointy(); 
 ip.SetPointx(x); 
 ip.SetPointy(y); 
 return ip; 
} 
 
//全局变量 
struct ppp 
{ 
 int *chrom; 
 float pc,pm; 
 double sumdd; 
 double fitness; 
}; 
 
struct best 
{ 
 int *chrom; 
 int gen; 
 double sumdd; 
 double fitness; 
}; 
 
CVehicleExport PtrVE;                   
int yy,maxpp=0;; 
CImport * PtrIP;                          //动态生成 
                           
int popsize,lchrom; 
float cmutation,mmutation,Rank,VehicleRate ; 
struct ppp *oldpop,*newpop,*p1; 
struct best bestfit; 
double sumfitness,maxfitness,avgfitness,* dd; 
int gen,earlity,late; 
int *Index,*ff,maxpath,maxbest=0; 
bool success; 
 
int Randm(int x) 
{//随机数生成函数 
  return 1+rand()%x; 
} 
 
void CImport::SetTime(int x) 
{ 
 
	cout<<"\nImport["<<x+1<<"] Time "; 
		cin>>Time; 
	cout<<"\nImport["<<x+1<<"] Earlytime "; 
        cin>>Earlytime; 
	cout<<"\nImport["<<x+1<<"] Latetime "; 
        cin>>Latetime; 
 
}// end of for SetTime 
 
void InitializeExport() 
{//初始化CVehicleExport类函数 
	int x,y; 
	cout<<"\nInput VehicleExport pointx pointy\n"; 
		cin>>x>>y; 
	CVehicleExport VE('A',x,y); 
	PtrVE=VE; 
}// end of InitializeExport 
 
void InitializeCImport() 
{//初始化CImport类函数 
 cout<<"\nInput Import Number"<<endl; 
 cin>>ImportNum; 
 CImport * PIP=new CImport[ImportNum];  
 PtrIP=PIP; 
 double z;int x,y; 
 for (int i=0; i<ImportNum; i++) 
 {  
	 cout<<"\nImport ["<<i+1<<"] pointx pointy "; 
	 cin>>x>>y; 
	 cout<<"\nImport ["<<i+1<<"] Load "; 
	 cin>>z; 
	 CImport vex(x,y,i+1,z); 
	 PIP[i]=vex; 
	 PIP[i].SetTime(i); 
 }// end of for 
 
}// end of InitializeImport 
 
double computedd(CImport IP,CImport VE) 
{//计算两点间距 
	int i1=IP.GetPointx(); 
	int j1=IP.GetPointy(); 
	int i2=VE.GetPointx(); 
	int j2=VE.GetPointy(); 
	int x=abs(i1-i2); 
	int y=abs(j1-j2); 
	double z=pow(x,2)+pow(y,2); 
	return sqrt(z); 
}// end of computedd 
 
 
void InitializeIE() 
{ 
    InitializeExport(); 
    InitializeCImport(); 
    double x; 
    x=0.0; 
    for (int j=0;j<ImportNum;j++) 
	{ 
	  double z=PtrIP[j].GetLoad(); 
	  x+=z;           //收货点需求的运载量和 
	}// end of for j 
 
	cout<<"\n Enter the goods Load rate(0.8~1)"<<endl; 
	cin>>VehicleRate; 
	while ((VehicleRate<0.8)||(VehicleRate>1)) 
	{ 
		cout<<"\n Enter the goods Load rate(0.8~1)"<<endl; 
	    cin>>VehicleRate; 
	} 
 
    int  m=int(x/(VehicleRate*VehicleLoad))+1; 
    PtrVE.SetVehicleNum(m); 
	PtrVE.Print(); 
	outfile<<"\n CImport" 
		   <<"\n Order pointx pointy Load loadtime earlytime latetime"<<endl; 
	for (int i=0;i<ImportNum;i++) 
        PtrIP[i].Print(); 
}// end of InitializeIE 
 
void InitializeData() 
{ 
	cout<<"\n Enter population size(140~240)"<<endl; 
	cin>>popsize; 
	cout<<"\n Enter the probility for cmutation (0.6~ 0.9)"<<endl; 
	cin>>cmutation; 
	while ((cmutation<0.0)||(VehicleRate>1)) 
	{ 
		cout<<"\n Enter the probility for cmutation (0.6~ 0.9)"<<endl; 
	    cin>>cmutation; 
	} 
    cout<<"\n Enter the probility for mmutation (0.05~ 0.1)"<<endl; 
	cin>>mmutation; 
	while ((mmutation<0.0)||(mmutation>1)) 
	{ 
		 cout<<"\n Enter the probility for mmutation (0.05~ 0.1)"<<endl; 
         cin>>mmutation; 
	} 
	cout<<"\n Enter the parameter for rank pick probility when select (0.2~ 0.5)"<<endl; 
	cin>>Rank; 
	while ((Rank<0.0)||(Rank>1)) 
	{ 
		cout<<"\n Enter the parameter for rank pick probility when select (0.2~ 0.5)"<<endl; 
       	cin>>Rank; 
	} 
	earlity=3; 
	late=6; 
}// end of InitializeData 
 
void InitializeMemory() 
{//种群分配内存 
	oldpop=new struct ppp[popsize]; 
	if (oldpop==0) 
	{ 
		cout<<"Memory allocation for oldpop fail"<<endl; 
		exit(0); 
	}// end of oldpop 
	newpop=new struct ppp[popsize]; 
	if (newpop==0) 
	{ 
		cout<<"Memory allocation for newpop fail"<<endl; 
		exit(0); 
	}// end of newpop 
	p1=new struct ppp[popsize]; 
	if (p1==0) 
	{ 
		cout<<"Memory allocation for p1 fail"<<endl; 
		exit(0); 
	}// end of p1 
}// end of InitializeMemory 
 
void InitializeDataMemory() 
{//染色体分配内存 
	lchrom=ImportNum+yy+1; 
	for (int i=0;i<popsize;i++) 
	{ 
		oldpop[i].chrom=new int[lchrom]; 
		if (oldpop[i].chrom==0) 
		{ 
			cout<<"Memory allocation for oldpop.chrom fail"<<endl; 
		    exit(0); 
		} 
        newpop[i].chrom=new int[lchrom]; 
		if (newpop[i].chrom==0) 
		{ 
			cout<<"Memory allocation for newpop.chrom fail"<<endl; 
		    exit(0); 
		} 
		p1[i].chrom=new int[lchrom]; 
		if (p1[i].chrom==0) 
		{ 
			cout<<"Memory allocation for p1.chrom fail"<<endl; 
		    exit(0); 
		} 
	}// end of for i 
	bestfit.chrom=new int[lchrom]; 
	if (bestfit.chrom==0) 
	{ 
		cout<<"Memory allocation for bestfit.chrom fail"<<endl; 
		exit(0); 
	} 
}// end of InitializeDataMemory 
 
void InitializeCoordinate() 
{//初始化收货点间距离数组 
	int ll=pow(ImportNum+1,2); int y; 
	dd=new double[ll]; 
	for (int i=0;i<ll;i++) 
		dd[i]=0.0; maxpath=0; 
	for ( i=0;i<ImportNum;i++) 
	{ 
		for (int j=i+1;j<ImportNum;j++) 
		{y=(i+1)*(ImportNum+1)+j+1; 
		 int z=(j+1)*(ImportNum+1)+i+1; 
 
		 dd[z]=dd[y]=computedd(PtrIP[i],PtrIP[j]); 
		 if (dd[y]>maxpath) 
			 maxpath=dd[y]; 
 
		}// end of for j 
	}// end of for i 
	for ( i=0;i<ImportNum;i++) 
	{ 
		y=i+1; 
		int z=(i+1)*(ImportNum+1); 
 
		dd[z]=dd[y]=computedd(PtrIP[i],PtrVE); 
		if (dd[y]>maxpath) 
			 maxpath=dd[y]; 
 
	}// end of for i 
		for (i=0;i<ll;i++) 
	{ 
		int z=i/(ImportNum+1); 
		int m=i % (ImportNum+1); 
		outfile<<"\n" 
			   <<"path["<<z<<" "<<m<<"] "<<left<<setw(6)<<dd[i]; 
		if (m+1==ImportNum+1) 
			outfile<<"\n"; 
	 
	} 
    
}// end of InitializeCoordinate 
 
void InitData() 
{//初始化染色体 
	int* p5=new int[lchrom]; 
	int z=(int)(ImportNum/2); 
    for (int i=0;i<ImportNum+1;i++) 
		p5[i]=i; 
    srand(time(0)); 
	for ( i=0;i<yy-1;i++)                //插入车辆标记 
	{    
		int m=ImportNum+i-1; 
		int r=Randm(m); 
		while (r==1) r=Randm(m); 
		while ((p5[r-1]==0)||(p5[r+1]==0)||(p5[r]==0)) 
		       	r=Randm(m); 
		for (int k=ImportNum+i+1;k>r;k--)  p5[k]=p5[k-1]; 
		p5[r]=0; 
	}// end of for  
    p5[ImportNum+yy]=0;                            //p5[lchrom-1]=0 
	int j=0; 
    for (int k=0;k<lchrom;k++) 
		oldpop[j].chrom[k]=p5[k]; 
	for (j=1;j<popsize;j++)                //模拟随机产生染色体过程 
	{ 
		int j2=Randm(lchrom-2);            //1~lchrom-2之间的随机数 
		for ( k=0;k<j2+z;k++)           //z?=为什么是15 
		{ 
			int j3=Randm(lchrom-2); 
			int j4=Randm(lchrom-2); 
		    while (j3==j4) j4=Randm(lchrom-2); 
			 if (j3>j4) 
			{ 
				int q=j4; 
					j4=j3; 
				    j3=q; 
			} 
 
			if ((p5[j3-1]!=p5[j4])&&(p5[j3+1]!=p5[j4])&&(p5[j3]!=p5[j4-1])&&(p5[j3]!=p5[j4+1])||(abs(j3-j4)==1)&&(p5[j3]!=p5[j4+1])&&(p5[j4]!=p5[j3-1]))  
		 
			{ 
				int j1=p5[j3]; 
				p5[j3]=p5[j4]; 
				p5[j4]=j1; 
			}// end of for if  
		}// end of for k 
        for (int k=0;k<lchrom;k++) 
			oldpop[j].chrom[k]=p5[k];		 
	}// end of for j 
	delete[] p5; 
		p5=0; 
}// end of for InitData 
 
void ComputeFitness(struct ppp * pop) 
{//计算染色体的适应度 
	int *p5=new int[lchrom]; double max=0.0; 
	double fff=maxpath*pow(ImportNum,2); 
    double sumdd; double T=0.0; 
	for (int i=0;i<popsize;i++) 
	{ 
		sumdd=0.0;   
		for (int k=0;k<lchrom;k++) 
			p5[k]=pop[i].chrom[k]; 
	/*	p5[0]=0;p5[1]=8;p5[2]=5;p5[3]=7; 
		p5[4]=0;p5[5]=6;p5[6]=4;p5[7]=0; 
		p5[8]=3;p5[9]=1;p5[10]=2;p5[11]=0;*/ 
        for ( k=0;k<lchrom-1;k++) 
		{//计算路径 
			int site=p5[k]*(ImportNum+1)+p5[k+1]; 
			sumdd+=dd[site]; 
			if (p5[k+1]!=0) 
			{//时间惩罚计算 
				double TT=double(dd[site])/double(speed)+T;         //人员休息时间算在装车时间time中 
				int x=p5[k+1]-1;                        //TT实际到达时间 
				double time1=PtrIP[x].GetEarlytime();          //T累计时间 
				double time=PtrIP[x].GetTime(); 
				double time2=PtrIP[x].GetLatetime(); 
				if (TT<time1) 
				{//提前到达  车等待 
					sumdd+=(time1-TT)*5*earlity; 
					T=time1+time; 
				}// end of TT<time1 
				else if (TT>time2) 
				{//晚到  客等 
					sumdd+=(TT-time2)*5*late; 
					T=TT+time; 
				}// end of TT>time2 
				else 
				{//要求时间内到达 
					T=TT+time; 
				}//end of else  
			}//end of if 
			else  
			{//空车费用 
				T=0; 
				sumdd+=500; 
			} 
		}// end of for k 
		double subgood=0; 
		for ( k=1;k<lchrom;k++) 
		{//超载惩罚计算 
			if (p5[k]!=0) 
			{ 
				int j=p5[k]-1; 
				subgood+=PtrIP[j].GetLoad(); 
			} 
			else 
			{ 
			if ((subgood!=0)&&(subgood>VehicleLoad)) 
				sumdd+=(subgood-VehicleLoad)*20*ImportNum*5; 
				subgood=0.0; 
			} 
		}// end of for k 
			if (max<sumdd) 
			    max=sumdd; 
		//	outfile<<"sumdd="<<sumdd; 
		pop[i].sumdd=sumdd; 
	}// end of for i 
	for ( i=0;i<popsize;i++) 
	{ 
   		double y=50.0*fff/pop[i].sumdd; 
        pop[i].fitness=y; 
	} 
	delete[] p5; 
	p5=0; 
}// end of for ComputeFitness  
 
void Statistics(struct ppp * pop) 
{//统计最大与平均适应度 
 
	sumfitness=pop[0].fitness; 
	double max=pop[0].fitness; 
	double min=pop[0].fitness; 
	int minpp=0; 
        	maxpp=0; 
	 
    for (int j=1;j<popsize;j++) 
	{ 
		sumfitness+=pop[j].fitness; 
		if (pop[j].fitness>max) 
		{ 
			max=pop[j].fitness; 
			maxpp=j; 
		} 
        if (pop[j].fitness<min) 
		{ 
			min=pop[j].fitness; 
			minpp=j; 
		}  
	}// end of for j 
		if (max>bestfit.fitness) 
		{ 
			for (int k=0;k<lchrom;k++)  
				bestfit.chrom[k]=pop[maxpp].chrom[k]; 
            bestfit.fitness=max; 
			bestfit.sumdd=pop[maxpp].sumdd; 
            bestfit.gen=gen; 
			maxbest=0; 
		} 
		maxfitness=bestfit.fitness; 
		avgfitness=sumfitness/popsize; 
		maxbest++; 
 
 
 
	for (int i=0;i<lchrom;i++) 
		newpop[minpp].chrom[i]=bestfit.chrom[i]; 
 
	outfile<<"\nmaxpp="<<maxpp 
		   <<"\nbestfit.sumdd="<<bestfit.sumdd 
		   <<"\nmaxfitness="<<maxfitness 
		   <<"\navgfitness="<<avgfitness<<endl; 
 
	 
}// end of Statistics 
 
void InitializeReport() 
{//输出初始参数 
	outfile<<"\n ---------Genetic Algorithm Parameters:------------"; 
	outfile<<"\n ----------------------------------------------------- "; 
	outfile<<"\n Population size="<<popsize 
	       <<"\n The probility for cmutation="<<cmutation 
		   <<"\n The probility for mmutation="<<mmutation 
		   <<"\n The parameter for rank pick probility when select="<<Rank<<endl; 
	outfile<<"\n ----------------------------------------------------- "; 
}// end of for InitializeReport 
 
void Report() 
{//输出遗传结果 
	outfile<<"\n -----THE BEST RESULE OF THE GENERATION OF     "<<gen<<"------------"<<endl; 
	outfile<<"\n THE BEST FITNESS="<<left<<bestfit.fitness<<"\n\n"; 
		    
	for (int i=0;i<lchrom;i++) 
	{ 
		outfile<<bestfit.chrom[i]<<" "; 
		 
	} 
	outfile<<"\nbestgen="<<bestfit.gen<<endl; 
	outfile<<"\n***************************************************************"; 
	outfile<<"\n***************************************************************"; 
}//end of Report 
 
void Initializepop() 
{ 
	yy=PtrVE.GetVehicleNum();      //车辆数 
	InitializeDataMemory(); 
	InitializeCoordinate(); 
	InitData(); 
	for (int i=0;i<popsize;i++) 
	{ 
		oldpop[i].pc=cmutation; 
    	oldpop[i].pm=mmutation; 
	} 
	ComputeFitness(oldpop); 
	bestfit.fitness=0; 
    bestfit.gen=0; 
	Statistics(oldpop); 
	Report(); 
}// end of Initializepop  
 
void select() 
{//选择父染色体进行遗传函数 
    ff=new int[popsize]; 
	double *Q=new double[popsize]; 
	double *p=new double[popsize]; 
	double *f=new double[popsize]; 
	Index=new int[popsize]; 
    double sum=0.0; 
	for (int i=0;i<popsize;i++) 
	{ 
		Q[i]=oldpop[i].fitness; 
		ff[i]=i;               //ff记录排序后的各染色体对应位置 
	} 
 
	quicksort(Q,popsize);      //Q数组进行排序 
	double m=2-Rank; 
	for ( i=0;i<popsize;i++) 
	{ 
		double j=(m-Rank)*i/(popsize-1); 
		p[i]=(j+Rank)/popsize; //p记录染色体的排序选择概率 
	} 
	f[0]=p[0];                 //f选择概率求和 
	for ( i=1;i<popsize;i++) 
		f[i]=f[i-1]+p[i]; 
	srand(time(0)+gen); 
	for ( i=0;i<popsize;i++) 
	{ 
		double r=double(Randm(5000))/double(5001); 
		int j=0; 
		while ((r>f[j])&&(j<popsize)) j++; 
		if (j==popsize) Index[i]=maxpp; 
		else 
			Index[i]=j;            //Index记录被选择的染色体序号  第j个染色体是谁要靠ff识别 
	} 
 
  	for (i=0;i<popsize;i++) 
	{ 
		int j=Index[i]; 
		for (int k=0;k<lchrom;k++) 
			newpop[i].chrom[k]=oldpop[j].chrom[k]; 
		newpop[i].pc=oldpop[j].pc; 
		newpop[i].pm=oldpop[j].pm; 
		newpop[i].fitness=oldpop[j].fitness; 
		newpop[i].sumdd=oldpop[j].sumdd; 
	} 
	delete[] Q; 
	Q=0; 
	delete[] p; 
	p=0; 
	delete[] f; 
	f=0; 
    delete[] Index; 
	Index=0; 
}// end of for select 
 
void ComputeCM(int flag) 
{//统计进行杂交变异的染色体序号 
	double p; 
	ff=new int[popsize]; 
	srand(time(0)+gen); 
	for (int i=0;i<popsize;i++) 
	{ 
		p=double(Randm(5000))/double(5001); 
		double m=0.0; 
		if (flag==1) 
			m=newpop[i].pc; 
		else 
            m=newpop[i].pm; 
		if (p<m) 
			ff[i]=1;          //ff再被利用记录被选择出的杂交变异的染色体序号 
		else 
			ff[i]=0; 
	}// end of for i 
 
}// end of ComputeCM 
 
void Invert(int *p1,int *p2) 
{//杂交操作 交换父染色体中的基因生成子染色体 
	int *f1=new int[lchrom];  
	int *f2=new int[lchrom]; 
    for (int i=0;i<lchrom;i++)   //f1 f2 为两个副本 
	{ 
		f1[i]=p1[i]; 
		f2[i]=p2[i]; 
	} 
srand(time(0)+gen); 
   int r1,r2; 
    r1=Randm(lchrom-2); 
   if (p1[r1]==0) 
    { 
     for (int i=r1+1;((i<lchrom)&&(p1[i]!=0));i++); 
     if (i==lchrom-1)  
        for (i=r1-1;((i>0)&&(p1[i]!=0));i--); 
     r2=i; 
    }// end of p1[r1]==0 
   else 
     { 
       for (int i=r1+1;((i<lchrom)&&(p1[i]!=0));i++); 
       if (i==lchrom-1)  
       {   
           
          for (i=r1-1;((i>0)&&(p1[i]!=0));i--); 
          r2=i; 
          for (i=r2-1;((i>0)&&(p1[i]!=0));i--); 
          r1=i; 
       }// end of i==lchrom-1 
        else 
       {r1=i; 
        for (int i=r1+1;((i<lchrom)&&(p1[i]!=0));i++); 
        if (i==lchrom-1)  
           for (i=r1-1;((i>0)&&(p1[i]!=0));i--);  
        r2=i; 
       } 
     } 
     int j1,j2; 
      j1=r1<r2? r1:r2; 
      j2=r2>r1? r2:r1;     
	 
	    	int *pp=new int[lchrom];               //临时染色体 
	    	for ( i=j1;i<=j2;i++) 
		    	pp[i]=p1[i]; 
	    	int m=j2-j1; 
	    	int j3=0; int j4=0; 
		    for (i=1;i<lchrom-m-1;i++) 
			{   
		    	if (f2[i]==0) 
				{ 
			    	for (int j=i;(f2[j+1]!=0)&&(j<lchrom);j++) ; //寻找对应长度上的车辆位置 
			    	if ((m+i-1==j)&&(f2[j+1]==0)&&(j+1!=lchrom-1)) 
					{ 
				    	j3=i; 
				    	j4=j+1; 
						break; 
					} 
				}// end of if 
			}// end of for i 
		    if ((j3!=0)||(j4!=0)) 
			{ 
	    		for (int i=j3;i<lchrom-1;i++) 
			    	f2[i]=f2[i+1];                                   //销去对应长度上的车辆标记 
			    for (i=j4-1;(i!=lchrom-2)&&(i<lchrom-2);i++) 
			    	f2[i]=f2[i+1];  
		    	for (i=j1+1;i<j2;i++) 
				{ 
					int m=1; 
		        	for (int j=1;j<lchrom-1;j++) 
					{ 
			        	if (f2[j]==p1[i]) 
						{ 
				        	for (int k=j;k<lchrom-2-m;k++)       //销去相同的收货点标记 
					        	f2[k]=f2[k+1];                 //m只是出于效率的考虑 
							m++; 
							break; 
						} 
					} 
				}//end of for i 
 
					i=0;int j=j2+1; 
	            	while (i<j1) 
					{ 
		            	pp[i]=f2[i]; 
		            	i++; 
					} 
	    	        while ((j>j2)&&(j<lchrom)) 
		            	pp[j++]=f2[i++]; 
				 
 
				for (i=0;i<lchrom;i++) 
		    	p1[i]=pp[i]; 
			 
 
 
			for ( i=j3;i<=j4;i++) 
		      pp[i]=p2[i]; 
	     
		 
	    		for ( i=j1;i<lchrom-1;i++) 
			    	f1[i]=f1[i+1];                                   //销去对应长度上的车辆标记 
			    for (i=j2-1;(i!=lchrom-2)&&(i<lchrom-2);i++) 
			    	f1[i]=f1[i+1];  
		    	for (i=j3+1;i<j4;i++) 
				{ 
					int m=1; 
		        	for (int j=1;j<lchrom-1;j++) 
					{ 
			        	if (f1[j]==p2[i]) 
						{ 
				        	for (int k=j;k<lchrom-2-m;k++)       //销去相同的收货点标记 
					        	f1[k]=f1[k+1];                 //m只是出于效率的考虑 
							m++; 
							break; 
						} 
					} 
				}//end of for i 
 
					i=0; j=j4+1; 
	            	while (i<j3) 
					{ 
		            	pp[i]=f1[i]; 
		            	i++; 
					} 
	    	        while ((j>j4)&&(j<lchrom)) 
		            	pp[j++]=f1[i++]; 
				 
 
				for (i=0;i<lchrom;i++) 
		    	p2[i]=pp[i]; 
			}// end of if j3<>0 j4<>0 
	    	delete[] pp; 
	    	pp=0; 
	 
	delete[] f1; 
	f1=0; 
	delete[] f2; 
	f2=0; 
}// end of Invert 
 
void Ox() 
{//进行最大保留杂交操作 
	int m=0; int *f=new int[popsize]; 
	for (int i=0;i<popsize;i++) 
	{ 
		if (ff[i]==1) 
		{ 
			m++;            //进行杂交的染色体个数 
	    	f[m-1]=i;           //进行杂交的染色体序号 i 
		} 
	} 
	if (m%2!=0) m-=1;       //杂交操作须偶数个染色体 
	int *pp1=new int[lchrom]; 
	int *pp2=new int[lchrom]; 
	if (m>=2) 
	{ 
		 
		for (int j=0;j<m;j+=2) 
		{ 
			for (int i=0;i<lchrom;i++) 
			{ 
				pp1[i]=newpop[f[j]].chrom[i]; 
                pp2[i]=newpop[f[j+1]].chrom[i]; 
			} 
 
		 
			Invert(pp1,pp2);  //杂交 
			for ( i=0;i<lchrom;i++) 
			{ 
				newpop[f[j]].chrom[i]=pp1[i]; 
                newpop[f[j+1]].chrom[i]=pp2[i]; 
			} 
		}// end of for j 
	 
	}// end of if 
	delete[] pp1; 
	pp1=0; 
	delete[] pp2; 
	pp2=0; 
	delete[] f; 
	f=0; 
}// end of Ox 
 
void Varyity() 
{//变异操作 
    int *f1=new int[lchrom];  
	srand(time(0)+gen); 
   	for (int i=0;i<popsize;i++) 
		if (ff[i]==1) 
		{    
			for (int j=0;j<lchrom;j++) 
			    f1[j]=newpop[i].chrom[j]; 
			int j1=Randm(lchrom-2); 
			int j2=Randm(lchrom-2); 
			while (j1==j2) j2=Randm(lchrom-2); 
			if ((f1[j1]!=f1[j2])&&(f1[j1]!=f1[j2-1])&&(f1[j1]!=f1[j2+1])&&(f1[j2]!=f1[j1-1])&&(f1[j2]!=f1[j1+1])) 
			{ 
				int low,high,temp; 
				if (j1<j2) {low=j1; high=j2;} 
			    	else {low=j2; high=j1;} 
				for (;low<high;low++,high--) 
				{ 
					temp=f1[low]; 
                    f1[low]=f1[high]; 
					f1[high]=temp; 
				}// end of for  
			}// end of j1!=j2 
            for (j=0;j<lchrom;j++) 
			    newpop[i].chrom[j]=f1[j]; 
		}// end of if  
}// end of Varyity 
 
void generate()      
{//进行遗传操作 
	if (yy>2) 
	{//用车数多于两量时才可能进行杂交操作 
		ComputeCM(1); 
		Ox(); 
	}// end of yy>=2; 
	//进行变异操作 
    ComputeCM(0); 
	Varyity(); 
}// end of for generate 
#endif