genetic.cpp

遗传算法

// Genetic.cpp : Defines the entry point for the console application.//


#include "stdafx.h"
#include "Genetic.h"
#include <time.h>
#include "iostream.h"
#include "math.h"
#include <stdlib.h>

//////////////////////////贝努利实验//////////////////////////
int flip(float probability)
{
	float  temp;
//   srand( (unsigned)time( NULL ) );
	 temp=rand()/(RAND_MAX+1.0) ;

	 if(temp<=probability)
		 return 1;
	 else
		 return 0;
}

/////////////////返回0-1之间的数//////////////////////////////

float Myrandom()
{
	float temp;
//	 srand( (unsigned)time( NULL ) );
	temp= rand()/(RAND_MAX+1.0);
	return temp;
}

////////////////////////产生新一代////////////////////////////////
void CStandardGA::Create_newgeneration()
{
 	Select();
	Crossover();
	Mutation();
	for(int i=0;i<populationsize;i++)
	{
		pop[i]=newpop[i];
	}
	Statistics();
	gen++;//进化代数
	cout<<"gen="<<gen;
	cout<<" 完成一次进化"<<endl;
}	
///////////////////////////////主函数//////////////////////////
int main(int argc, char* argv[])
{
	printf("Hello World!\n");
	int min=0;
	int max=0;
	
	srand( (unsigned)time( NULL ) );
	CStandardGA myga;
	myga.pcross=0.85;
	myga.pmutation=0.003;
	myga.gen=0;
	myga.populationsize=30;
//myga.pop=new INDIVIDUAL[myga.populationsize];

//myga.newpop=new INDIVIDUAL[myga.populationsize];
	
//myga.temppop=new INDIVIDUAL[myga.populationsize];



	if(myga.pop=new INDIVIDUAL[myga.populationsize])
	{
		if(myga.newpop=new INDIVIDUAL[myga.populationsize])
		{
			if(myga.temppop=new INDIVIDUAL[myga.populationsize])
			{
				myga.Initialize();
				
			}
		}
	}

	while(myga.gen<20)
	{
	
	  myga.Create_newgeneration();
	  
	  
	}



   return 0;
}

/////////////////////构造和析构函数////////////////////////////
CStandardGA::CStandardGA()
{
	
	sumfitness=0.0;
	averagefitness=0.0;
	
			
}

CStandardGA::~CStandardGA()
{
	delete[] pop;
	delete[] newpop;
	delete[] temppop;

}
////////////////初始化群体生成////////////////////////////////////
void CStandardGA::Initialize()
{
	srand( (unsigned)time( NULL ) );
		 for (int i=0;i<populationsize;i++)
		 {
			 for(int j=0;j<CHROMLENGTH;j++)
			 {
				 for(int k=0;k<BITLENGTH;k++)
				 {
					 pop[i].chrom[j].controlpoint[k]=(char)(65+rand()%BITMAX);
				 }
			 }
		 }
	Statistics();
	cout<<"初始群体已完成"<<endl;

}
//////////////////////////解码////////////////////////////
void CStandardGA::Decode()
{
	float bit,currentnumber;
			
	for (int i=0;i<populationsize;i++)
	 {
		 for(int j=0;j<CHROMLENGTH;j++)
		 { 
			 bit=1.0;
			 currentnumber=0.0;
			 for(int k=BITLENGTH-1;k>-1;k--)
			 {
				if(int(pop[i].chrom[j].controlpoint[k]-65))
				{
					currentnumber+=bit;
					bit=BITMAX*bit;
				}
				pop[i].chrom[j].codenumber=currentnumber;
			 }
	//		 pop[i].chrom[j].codenumber=int(pop[i].chrom[j].controlpoint[1]-65)*16 
	//			                         + int(pop[i].chrom[j].controlpoint[0]-65);
	//		 pop[i].chrom[j].codenumber -= 128;
		 }
	 }

}
/////////////////////////计算个体适应度/////////////////////////
void CStandardGA::GetFitness()
{
	Decode();//调用解码函数
	for(int i=0;i<populationsize;i++)
	{
		pop[i].fitness=0;
		for(int j=0;j<CHROMLENGTH;j++)
		{
			pop[i].fitness += abs(pop[i].chrom[j].codenumber);
		}
	}
	


}

////////////////////////统计适应度/////////////////////////////
void CStandardGA::Statistics()
{
	GetFitness();//调用适应度计算函数
	

	fmin_individual.fitness=0;
	fmax_individual.fitness=0;
	sumfitness=0.0;
	sumdecimalexpectation=0.0;
    /////求适应度最大和最小的个体//
	for(int i=0;i<populationsize;i++)
	{
		if(pop[i].fitness<fmin_individual.fitness)
		{
			fmin_individual.fitness=pop[i].fitness;
		}
		else if(pop[i].fitness>fmax_individual.fitness)
		{
			fmax_individual.fitness=pop[i].fitness;
			fmax_individual=pop[i];
		}


		sumfitness=sumfitness+pop[i].fitness;
	
	
	
	}
	////求期望值////
	averagefitness=sumfitness/populationsize;
	for(i=0;i<populationsize;i++)
	{
		pop[i].expectation = populationsize * pop[i].fitness / sumfitness;
		pop[i].int_expectation = (int)pop[i].expectation;
		pop[i].decimal_expectation = pop[i].expectation - pop[i].int_expectation;
		sumdecimalexpectation += pop[i].decimal_expectation;
		
	}
	
	cout<<" sumdecimalexpectation="<<sumdecimalexpectation;
	cout<<"  averagefitness="<<averagefitness;
	cout<<"  fmax_individual.fitness="<<fmax_individual.fitness<<endl;;

		
		
}



/////////////////////////////(期望值选择操作)/////////////////////////////
void CStandardGA::Select()
{
	int n=0;
	
	    /////选取整数部分//////
		for(int i=0;i<populationsize;i++)
		{
			 int j=1;
			
			while( j<=pop[i].int_expectation)
			{
				temppop[n]=pop[i];
				n++;
				j++;
				
			}
		}
		
	
		///////选取小数部分//////
		float randnumber;
		float tempnumber;
		while(n<populationsize)
		{
			i=0;
			tempnumber=0.0;
			randnumber=Myrandom()*sumdecimalexpectation;
			while((i<populationsize) && (randnumber>tempnumber))
			{
				tempnumber += pop[i].decimal_expectation;
				i=i+1;
			}
			temppop[n]=pop[i-1];
			n++;
			
		}



/*		while(n<populationsize)
		{
			for(i=0;i<populationsize;i++)
			{
			
				if(flip (pop[i].decimal_expectation) )
				{
					temppop[n]=pop[i];
					n++;
				}
				
				if(n==populationsize)
				{
					break;
				}
			}
		}
*/
        //////////把个体顺序打乱///////

		// 第一步， 生成不重复的、小于群体大小的随机数列,
		//   如：3 6 2 1 0 8 7 9 4 5 
		//   以便对选择的个体重排列  
	srand( (unsigned)time( NULL ) );
	int array[60]={60*40};   /////60是群体大小
	int a;
	 i=1;
	array[0]=rand()%populationsize;
	while( i<populationsize)
	{
		bool flag=1;
		a=rand()%populationsize;
		for(int j=0;j<i;j++)
		{
			
			if(a==array[j])
			{
				flag=0;
				//a=rand()%30;
				break;
			}
		}
		if(flag==1)
		{
			array[i]=a;
			i++;
		}
	}

	////第二步，形成新一代毛胚（顺序已打乱）
	for(i=0;i<populationsize;i++)
	{
		newpop[i]=temppop[array[i]];
	
	}
	
}

//////////////////////////(单点）交叉操作///////////////////////////////
void CStandardGA::Crossover()
{
	char temp;
	
	int a; //交叉点
	int crossbit; //交叉点位于某个控制点的其中一个“位”上
	for(int i=0;i<populationsize-1;i+=2)
	{
		if(flip(pcross))
		{
			a=rand()%(BITLENGTH*CHROMLENGTH);
			int flag=a%BITLENGTH;
			
				for(int j=0;j<=a/BITLENGTH;j++)//完成部分交叉
				{
					for(int k=0;k<BITLENGTH;k++)
					{
						temp = newpop[i].chrom[j].controlpoint[k];
						newpop[i].chrom[j].controlpoint[k] = newpop[i+1].chrom[j].controlpoint[k];
						newpop[i+1].chrom[j].controlpoint[k] = temp;
					}
				}
		
			if(flag!=0)//控制点会被拆开
			{
				crossbit=a-flag*BITLENGTH;
				j=j+1;
				for(int k=0;k<crossbit;k++)
				{
						temp = newpop[i].chrom[j].controlpoint[k];
						newpop[i].chrom[j].controlpoint[k] = newpop[i+1].chrom[j].controlpoint[k];
						newpop[i+1].chrom[j].controlpoint[k] = temp;
				}
				
			}
		}
	}
}
/////////////////////////////变异操作///////////////////////////////
void CStandardGA::Mutation()
{
	srand( (unsigned)time( NULL ) );
	 for(int i=0;i<populationsize;i++)
	 {
		 for(int j=0;j<CHROMLENGTH;j++)
		 {
			 for(int k=0;k<BITLENGTH;k++)
			 {
				 if(flip(pmutation))
				 {
					 newpop[i].chrom[j].controlpoint[k]=(char)(65+rand()%16);
				 }
			 }
		 }
	 }
}