ga.cpp

一个简单的改进的遗传算法

	x1=(int)(80.*st->varible[0]/(pow(2,(double)lchrom)-1)+0.+0.3);
	x2=(int)(50.*st->varible[1]/(pow(2,(double)lchrom)-1)+0.+0.3);
	x3=(int)(60.*st->varible[2]/(pow(2,(double)lchrom)-1)+0.+0.3);
	x4=(int)(70.*st->varible[3]/(pow(2,(double)lchrom)-1)+0.+0.3);
	x5=(int)(80.*st->varible[4]/(pow(2,(double)lchrom)-1)+0.+0.3);
	st->varible[0]=x1;
	st->varible[1]=x2;
	st->varible[2]=x3;
	st->varible[3]=x4;
	st->varible[4]=x5;
	if(5.8*x1+3.4*x2+6.8*x3+4.2*x4+8.7*x5>1000)
		st->fitness=0;
	else
		st->fitness=0.36*x1+0.62*x2+0.78*x3+0.54*x4+0.97*x5;
	
}
void CGA::VCstatistics(pINDIVIDUAL st)//计算种群最佳适应度,并填充bestfit
{
	int i,j;
    sumfitness = 0.0;
    min =st[0].fitness;
    max =st[0].fitness;
    for(j=0;j<popSize;j++)//计算最大、最小和累计适应度
    {
        sumfitness = sumfitness + st[j].fitness;            
        if(st[j].fitness > max){max = st[j].fitness;}
	    if(st[j].fitness < min){min = st[j].fitness;}
		if(st[j].fitness > bestfit.fitness[0])//new global best-fit individual
		{//0:最佳个体适应度;1:F1;2:F1/dGA[1];3:L;4:L/dGA[2]
            bestfit.fitness[0]=st[j].fitness;
			for(i=0;i<chromsize;i++)
				bestfit.chrom[i]=st[j].chrom[i];
		    for(i=0;i<varibleSize;i++)
				bestfit.varible[i]=st[j].varible[i];  
            bestfit.generation=gen;
			KBestGen=gen;
            bestfit.Ki=Ki;
		}
	}
	avg = sumfitness/popSize;/* 计算平均适应度 */
}
void CGA::generation()
{
  int mate1, mate2, jcross, j = 0;
	prselect();/*  每代运算前进行预选 */
  do/* 选择, 交叉, 变异 */
  {
	  mate1 = select();//挑选交叉配对
      mate2 = select();
	  if(mate1==bestIndex[0]||mate2==bestIndex[0]||mate1==bestIndex[1]||mate2==bestIndex[1])
	  {
		  newpop[j]=oldpop[bestIndex[0]];
		  newpop[j+1]=oldpop[bestIndex[1]];
		  newpop[j].fitness=oldpop[bestIndex[0]].fitness;
		  newpop[j+1].fitness=oldpop[bestIndex[1]].fitness;
		  /*for(int i=0;i<varibleSize;i++)
		  {
			  newpop[j].varible[i]=oldpop[bestIndex[0]].varible[i];
			  newpop[j+1].varible[i]=oldpop[bestIndex[1]].varible[i];
		  }
		  for(i=0;i<chromsize;i++)
		  {
				newpop[j].chrom[i]=oldpop[bestIndex[0]].chrom[i];
				newpop[j+1].chrom[i]=oldpop[bestIndex[1]].chrom[i];
		  }*/
	  
      }
	  else
	  {
		  //交叉和变异
		  jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
		  mutation(newpop[j].chrom);
		  mutation(newpop[j+1].chrom);
		  Dobjfunc(&(newpop[j]));//解码, 计算适应度
		  newpop[j].parent[0] = mate1+1;//记录亲子关系和交叉位置
		  newpop[j].xsite = jcross;
		  newpop[j].parent[1] = mate2+1;
		  Dobjfunc(&(newpop[j+1]));
		  newpop[j+1].parent[0] = mate1+1;
		  newpop[j+1].xsite = jcross;
		  newpop[j+1].parent[1] = mate2+1;  
	  }
	 j=j+2;
    }while(j<(popSize-1));
	
}
void CGA::prselect()
{
    int j;
    sumfitness = 0;
    for(j = 0; j < popSize; j++) sumfitness += oldpop[j].fitness;
}
int CGA::select()//轮盘赌选择
{
    //extern double randomperc();//得到一个随机数
	int i;
    double sum, pick;
    pick = randomperc();
    sum = 0;
    if(sumfitness != 0)
	{
		for(i=0;(sum<pick)&&(i<popSize);i++)sum+=oldpop[i].fitness/sumfitness;
    }
    else i=randLow_high(1,popSize);
    return(i-1);
}
int CGA::crossover(unsigned int *parent1, unsigned int *parent2, unsigned int *child1, unsigned int *child2)
//由两个父个体交叉产生两个子个体
{
    int j, jcross, k;
    unsigned mask, temp;
    if(flip(pcross))
    {
        jcross = randLow_high(1 ,(lchrom - 1));//Cross between 1 and l-1 
        ncross++;
        for(k = 1; k <= chromsize; k++)
        {
            if(jcross >=(int)(k*(8*sizeof(unsigned))))
            {
                child1[k-1] = parent1[k-1];
                child2[k-1] = parent2[k-1];
            }
            else if((jcross <(int)(k*(8*sizeof(unsigned)))) && (jcross >(int)((k-1)*(8*sizeof(unsigned)))))
            {
                mask = 1;
                for(j=1;j<=(int)(jcross-1-((k-1)*(8*sizeof(unsigned)))); j++)
                {
                    temp = 1;
                    mask = mask<<1;
                    mask = mask|temp;
                }
                child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
                child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
            }
            else
            {
                child1[k-1] = parent2[k-1];
                child2[k-1] = parent1[k-1];
            }
        }
    }
    else
    {
        for(k = 0; k < chromsize; k++)
        {
            child1[k] = parent1[k];
            child2[k] = parent2[k];
        }
        jcross = 0;
    }
    return(jcross);
}
void CGA::mutation(unsigned int *child)//变异操作
{
    int j, k, stop;
    unsigned mask, temp = 1;
    for(k = 0; k < chromsize; k++)
    {
        mask = 0;
        if(k==(chromsize-1))
			stop=lchrom-(k*(8*sizeof(unsigned)));
        else 
			stop = 8*sizeof(unsigned);
        for(j = 0; j < stop; j++)
        {
            if(flip(pmutation))
			{mask=mask|(temp<<j);nmutation++;}
        }
        child[k]=child[k]^mask;
    }
}
void CGA::writechrom(unsigned *chrom,CString str[])
{
    int i,j, k, stop;
    unsigned mask = 1, tmp;
	for(i=0;i<=lchrom-1;i++)
		str[i]="";
	i=0;
    for(k=0;k<chromsize;k++)
    {
        tmp=chrom[k];
        if(k==(chromsize-1))
			stop=varibleSize*lchrom-(k*(8*sizeof(unsigned)));
        else 
			stop=8*sizeof(unsigned);
        for(j=0;j<stop;j++)
        {
            if(tmp&mask)//i/lchrom表示第几个变量
				str[i/lchrom]="1"+str[i/lchrom];
            else 
				str[i/lchrom]="0"+str[i/lchrom];
			i+=1;
            tmp = tmp>>1;
        }
    }
}
void CGA::resultStrOut(CDC *pDC,CString str[])
{
	str[0]="输入参数：基本遗传算法---SGA Optimizer";
	str[1].Format("   种群(popsize)=%d(20-100)偶数;交叉率(pcross)=%4.3g(0.2-0.9);变异率(pmutation)=%4.3g(0.01-0.1)",popSize,pcross,pmutation);
	str[2].Format("   每个变量染色体长度(lchrom)=%d(8-40);最少进化代数(genMax)=%d;重复计算%d ",lchrom,genMax,Kmax);
	str[3].Format("\n");
	
	str[4].Format("当前群的参数：正在计算第%d次----随机种子=%5.4f;   ",Ki,oldrand[55]);
	str[5].Format("      第%d代;选取的随机数=%d    ",gen,jrand);
	str[6].Format("      适应度最大=%10.5g;最小=%10.5g;平均=%10.5g;累计=%10.5g      ",max,min,avg,sumfitness);
	str[7].Format("      交叉操作次数:%d；变异操作次数:%d       ",ncross,nmutation);
	str[8].Format("迄今发现的最佳个体：第%d次计算;第%d代时产生的；其适应度:%10.7g     ",bestfit.Ki,bestfit.generation,bestfit.fitness[0]);
	CString str1[60];//可以修改
	CString X[5];
	
	X[0].Format("%f",bestfit.varible[0]);
	X[1].Format("%f",bestfit.varible[1]);
	X[2].Format("%f",bestfit.varible[2]);
	X[3].Format("%f",bestfit.varible[3]);
	X[4].Format("%f",bestfit.varible[4]);
	writechrom((&bestfit)->chrom,str1);
	str[9]="x1="+X[0]+"   "+str1[0];
	str[10]="x2="+X[1]+"   "+str1[1];
	str[11]="x3="+X[2]+"   "+str1[2];
	str[12]="x4="+X[3]+"   "+str1[3];
	str[13]="x5="+X[4]+"   "+str1[4];
	for(int i=0;i<15;i++)
		pDC->TextOut(0,i*15,str[i]);
}
void CGA::BestWorseIndex(pINDIVIDUAL st,int index1[],int index2[])//计算种群的最大适应度和最小适应度的脚标
{
	double max1,min1,min2=0.,max2=0.;
    min1 =st[0].fitness;
    max1 =st[0].fitness;
   	index1[0]=index2[0]=0;
    for(int j=0;j<popSize;j++)
    {
        if(st[j].fitness > max1)
		{
			max1 = st[j].fitness; 
			index1[0]=j;
		}
	    else if(st[j].fitness < min1)
		{
			min1 = st[j].fitness;
			index2[0]=j;
		}
	}
	Outfitness[gen-1]=max1;
	if(index1[0]!=0)index1[1]=0; 
	else index1[1]=1;
	max2 =st[index1[1]].fitness;

	if(index2[0]!=0)index2[1]=0; 
	else index2[1]=1;
	min2 =st[index2[1]].fitness;
	for(j=0;j<popSize;j++)
	{
		if(max2<st[j].fitness&&st[j].fitness!=max1)
		{
			max2 = st[j].fitness; 
			index1[1]=j;
		}
		if(st[j].fitness < min2&&st[j].fitness!=min1)
		{
			min2 = st[j].fitness;
			index2[1]=j;
		}
	}
}