sga.cpp

最近研究遗传算法

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

long* long2binary(long codelength,long ltochange);
int CreateChromN(long popsize, long lchrom, long* &plarray);
int ChromCross(double dPcross,long * plArray,long lPopsize, long lChrom);
int ChromMutation(double dpMutation,long* plArray,long lPopsize, long lChrom);
int RWS(long* plAdapt, long* plArray,long lPopsize, long lChrom);
//整数转换为二进制
long* long2binary(long codelength,long ltochange)
{
   long* plResult=new long[codelength];
   if(plResult==NULL) return NULL;

   for(int i=0;i<codelength;i++)//从低位开始
   {
	  long aa=(long)pow(2,i);
	    if((ltochange&aa)==0)

	  plResult[codelength-1-i]=0; //但从高位开始存储
	  else 
	  plResult[codelength-1-i]=1 ;
   }
   return plResult;
}
//随机产生染色体
int CreateChromN(long popsize, long lchrom, long* &plarray)
{
	//随机选择编码组
	long *plAr= new long[popsize*lchrom];
	if(plAr==NULL) return 0;

	long *plSelection= new long[popsize];
	if(plSelection==NULL) return 0;

	long n=(long)pow(2,lchrom)-1;//可能的染色体分组
	plSelection[0]=(int)(n*rand()/RAND_MAX);//取0到popsize之间的数
	int i=0; //i从0开始
	long tempSelection;
	while(i<popsize-1)//??
	{
        int hh=0;
		tempSelection=(long)(n*rand()/RAND_MAX);
		for(int j=0;j<i+1;j++)
		{
			if(tempSelection==plSelection[j]) 
			hh=hh+1;//计数,可以稍微提高效率，不比较完毕
		}
			if(hh==0) //没有相同的数
				{
				i=i+1;	
				plSelection[i]=tempSelection;
					
				}


	}
	//然后将数转化为标准二进制编码，且存储
	long* plBinary;
	for(i=0;i<popsize;i++)
	{
      plBinary=long2binary(lchrom,plSelection[i]);
	  for(int j=i*lchrom;j<(i+1)*lchrom;j++) 
		  plAr[j]=plBinary[j-i*lchrom];
	}
    plarray=plAr;

	return 1;
	//1 还是随机选择（固定二进制编码，不用考虑优化编码）*/

//2 随机编码?比较的工作量比较大
	//return 1;

}
//operator &(long aa)
//**随机选择过程可以做成一个单独的函数
//染色体进行交配
int ChromCross(double dpCross,long *plArray,long lPopsize, long lChrom)
{
	//long plPop[20]={1,0,0,0,1,0,0,1,0,1,1,1,0,0,1,1,0,0,1,0};
    //已知初始种群，数组大小为N=lPopsize*lChrom
    //判断数组是否含有非0，1值
	for(int jj=0;jj<lPopsize*lChrom;jj++)
	{
		if((plArray[jj]!=1)&(plArray[jj]!=0))
			return 0;
	}
	//交配的种群个数
    long lPop2Cross=(long)lPopsize*dpCross;
    //保证要交配的染色体个数为偶数
	//减1比较好，如果+1,奇数个种群交配率为100%出现错误情况
    if(lPop2Cross%2) lPop2Cross=lPop2Cross-1;
    //交配位,0到lChrom之间
    long lBit2Cross=(long)(lChrom-1)*rand()/RAND_MAX;
   //随机选择其中的染色体进行交配，等概率交配，不考虑适应值
  
  //方法是：随机产生一数组（数的范围在0-(lPopsize-1)之间），相邻两个进行交配
	 long* plSelection=new long[];
	 if(plSelection==NULL) return 0;

     plSelection[0]=(long)((lPopsize-1)*rand()/RAND_MAX);//取0到(lPopsize-1)之间的数
	int i=0; //i从0开始
	long tempSelection;
	while(i<lPop2Cross-1)//
	{
        int hh=0;
		tempSelection=(long)((lPopsize-1)*rand()/RAND_MAX);
		for(int j=0;j<i+1;j++)
		{
			if(tempSelection==plSelection[j]) 
			hh=hh+1;//计数,可以稍微提高效率，不比较完毕
		}
			if(hh==0) //没有相同的数
				{
				i=i+1;	
				plSelection[i]=tempSelection;
					
				}
	}
	//plSelection[]存储的是待交配的染色体的序号

	//交配
	for(int j=0;j<lPop2Cross;j=j+2)
	{
     
	 for(long h=lBit2Cross;h<lChrom;h++)
	 {
         
		 long lTempBit;// 要交换的位
		 lTempBit=plArray[plSelection[j]*lChrom+h];
         plArray[plSelection[j]*lChrom+h]=plArray[plSelection[j+1]*lChrom+h];
		 plArray[plSelection[j+1]*lChrom+h]=lTempBit;
	 }

	}

	/*for(j=0;j<20;j++)
	{
    plArray[j]=plPop[j];
	}*/

	return 1;
}
//染色体变异
int ChromMutation(double dpMutation,long* plArray,long lPopsize,long lChrom)
{
	
	 //判断数组是否含有非0，1值
	for(int jj=0;jj<lPopsize*lChrom;jj++)
	{
		if((plArray[jj]!=1)&(plArray[jj]!=0))
			return 0;
	}
	
	//lPopsize:种群个数  lChrom:编码长度
	 long lPoptoMutation=(long)lPopsize*dpMutation;
	 if(lPoptoMutation==0) return 1;
	 long lBittoMutation;
	 lBittoMutation=(long)(lChrom-1)*rand()/RAND_MAX;

	 long* plSelection=new long[];
     plSelection[0]=(long)((lPopsize-1)*rand()/RAND_MAX);//取0到(lPopsize-1)之间的数
	int i=0; //i从0开始
	long tempSelection;
	while(i<lPoptoMutation-1)//
	{
        int hh=0;
		tempSelection=(long)((lPopsize-1)*rand()/RAND_MAX);
		for(int j=0;j<i+1;j++)
		{
			if(tempSelection==plSelection[j]) 
			hh=hh+1;//计数,可以稍微提高效率，不比较完毕
		}
			if(hh==0) //没有相同的数
				{
				i=i+1;	
				plSelection[i]=tempSelection;
					
				}
	}
	//plSelection[]存储的是发生变异的染色体的索引
	for(i=0;i<lPoptoMutation;i++)
	{
		if(plArray[plSelection[i]*lChrom+lBittoMutation]==1)
            plArray[plSelection[i]*lChrom+lBittoMutation]=0;
		else
			plArray[plSelection[i]*lChrom+lBittoMutation]=1;
	}
     
/*	for(int j=0;j<20;j++)
	{
    plArray[j]=plPop[j];
	}*/
	 return 1;

}
//轮盘赌算法
//给定N个染色体的适应值，求出染色体编码数组
int RWS(long* plAdapt, long* plArray,long lPopsize, long lChrom)
{
	//判断数组是否含有非0，1值
	for(int jj=0;jj<lPopsize*lChrom;jj++)
	{
		if((plArray[jj]!=1)&(plArray[jj]!=0))
			return 0;
	}
	
    //存储选择概率
	double* plP=new double[];
	if(plP==NULL) return 0;
	
    double dSum=0.0;
	//求适应值的和
	for(int i=0;i<lPopsize;i++)
	{
		dSum=dSum+plAdapt[i];     
	}
	//求各选择概率
	for(i=0;i<lPopsize;i++)
	{
		plP[i]=plAdapt[i]/dSum;
		
	}
	//算法理解，分别产生随机数，选择染色体,包括被重复选取
	//存储被选取的染色体序号
	long* plSelect=new long[lPopsize];
	double dRand=0.0;
	double dS=0;
	int j=0;
	srand((unsigned)time(NULL));
	for(i=0;i<lPopsize;i++) //选取个体序列
	{
		dRand=static_cast<double>((rand()%100)*0.01);//精确到小数点后2位
	
		dS=0;
		for(j=0;j<lPopsize;j++) //染色体序列
		{
			if(dS>=dRand)
			{
				plSelect[i]=j;
			    break;
			}
			dS=dS+plP[j];
		}
	}

    long* plSelectedPop=new long[lPopsize*lChrom];// 大小同于给定的初始群体
	for(i=0;i<lPopsize;i++)
	{
		for(j=0;j<lChrom;j++)
		{
			plSelectedPop[i*lChrom+j]=plArray[plSelect[i]*lChrom+j];
		}
	}
    for(j=0;j<lPopsize*lChrom;j++)
	plArray[j]=plSelectedPop[j]; //需释放
	delete []plSelectedPop;
	return 1;

}

void main()
{
	
//	cout<<0.5*((int)(rand()/RAND_MAX))<<endl;
    cout<<pow(2,3)<<endl;

    printf("%d\n",8&1);
	printf("%d\n",8&2);
    printf("%d\n",8&4);
	printf("%d\n",8&8);
    printf("%d\n",8&16);
	long* hehe=long2binary(5,8);
	cout<<hehe[0]<<hehe[1]<<hehe[2]<<hehe[3]<<endl;//从高位到低位输出

/*	int hehe[4];
	for(int i=0;i<4;i++)
	{
		if(8&&pow(2,i)==0) hehe[3-i]=0;
			else  hehe[4-i]=1;
	}
*/
	long* Result=new long[];
	CreateChromN(8, 5, Result); 
	for(int i=0;i<20;i++)
		cout<<Result[i]<<endl;
	 delete[] Result;
	 ////////////////////////
	//long* plResultofCross=new long[20];
     long plPop[20]={1,0,0,0,1,0,0,1,0,1,1,1,0,0,1,1,0,0,1,0};
	//交配算法调试
	 /*ChromCross(0.5,plPop,4,5);
     for(i=0;i<20;i++)
		cout<<(long)plPop[i]<<endl;*/
   
    	
	 ///////////////////////
	 //变异算法调试
	 //为验证算法,pMutation取较大值,且要屏蔽交配算法，因交配算法修改了plPop
	/* ChromMutation(0.25,plPop,4,5);	 
     for(i=0;i<20;i++)
		cout<<(long)plPop[i]<<endl;
   */
	 //轮盘赌法验证
	 
	 long lAdapt[4]={32,18,160,100};
     RWS(lAdapt,plPop,4,5);
     for(i=0;i<20;i++)
		cout<<(long)plPop[i]<<endl;
   ////
	  srand( (unsigned)time(NULL));
       double yyyy;
   /* Display 10 numbers. *////随机数产生不对
     for( i = 0; i < 10;i++ )
	 {
	     yyyy=static_cast<double>((rand()%100)*0.01);
		 printf( "%.2f\n",yyyy);
	 }
	   
 
}