ga.h

C++解决VRPTW的源码,采用遗传算法编写

	}// 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