sga1.cpp

遗传算法求解函数极值

//基本遗传算法,求最大最小值问题,根据遗传算法原理及其应用(周明)书中程序,修改了随机数产生语句,使得该程序能在vc中使用  由于随机数的原因，结果有时对，有时不对（结果应为二十个零）,具体原因还没有弄明白，请各位试试，大家交流一下。


由于随机数的原因，结果有时对，有时不对（结果应为二十个零）

具体原因还没有弄明白，请各位试试，大家交流一下。

#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h" 
//定义常量
#define	 POPSIZE   500
#define	 MAXIMIZATION 1
#define MINIMIZATION 2
//定义使用数据,对于不同问题而不同
#define Cmax 100
#define Cmin 0
#define LENGTH1  10
#define LENGTH2 10
#define CHROMLENGTH LENGTH1+LENGTH2
int FunctionMode=MAXIMIZATION;
int PopSize=80;
int MaxGeneration=200;
double Pc=0.6;
double Pm=0.001;
//定义数据结构
struct individual 
{
	char chrom[CHROMLENGTH];
	double value;
	double fitness;
};
//定义全局变量
int generation;
int best_index;
int worst_index;
struct individual bestindividual;
struct individual worstindividual;
struct individual currentbest;
struct individual population[POPSIZE];
//函数声明
void GenerateInitialPopulation(void);
void GenerateNextPopulation(void);
void EvaluatePopulation(void);
long DecodeChromosome(char*,int,int);
void CalculateObjectValue(void);
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossOverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);
//主函数
void main(void)
{
	//srand((unsigned)time(NULL)); 
	generation=0;
     GenerateInitialPopulation();
	 EvaluatePopulation();
	 while(generation<MaxGeneration){
		 generation++;
		 GenerateNextPopulation();
		 EvaluatePopulation();
		 PerformEvolution();
		 OutputTextReport();
	 }
}
//初始化,第一代
void GenerateInitialPopulation(void)
{
	int i,j;
	srand((unsigned)time(NULL));   
	    for(i=0;i<PopSize;i++){
		for(j=0;j<CHROMLENGTH;j++){
			population[i].chrom[j]=(((rand()%10)<5)?'0':'1');
		}
		population[i].chrom[CHROMLENGTH]='\0';
	}
}
//产生下一代
void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossOverOperator();
	MutationOperator();
}
//评价
void EvaluatePopulation(void)
{
    CalculateObjectValue();
	CalculateFitnessValue();
	FindBestAndWorstIndividual();
}
//把二进制解码为十进制
long DecodeChromosome(char *string,int point,int length)
{
	int i;
    long decimal=0;//
	char *pointer;
	for(i=0,pointer=string+point;i<length;i++,pointer++)
	{
		decimal+=(*pointer-'0')<<(length-1-i);
	}
return(decimal);
}
//计算目标值
void CalculateObjectValue(void)
{
	int i;
	long temp1,temp2;
    double x1,x2;
	for(i=0;i<PopSize;i++)
	{
		temp1=DecodeChromosome(population[i].chrom,0,LENGTH1);
		temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2);
		x1=4.096*temp1/1023.0-2.048;
		x2=4.096*temp2/1023.0-2.048;
		population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
	}
}
//计算适应度
void CalculateFitnessValue(void)
{
	int i;
	double temp;
	for(i=0;i<PopSize;i++)
	{
		if(FunctionMode==MAXIMIZATION){
			if((population[i].value+Cmin)>0.0){
                     temp=Cmin+population[i].value;
			}
			else{
				temp=0.0;
			}
		}
		else if(FunctionMode==MINIMIZATION){
			if(population[i].value<Cmax){
				temp=Cmax-population[i].value;
			}else{
				temp=0.0;
			}
		}
		population[i].fitness=temp;
	}
}
//在当前代寻找最好个体
void FindBestAndWorstIndividual(void)
{
	int i;
	double sum=0.0;
	bestindividual=population[0];
	worstindividual=population[0];
	for(i=1;i<PopSize;i++){
		if(population[i].fitness<worstindividual.fitness){
			worstindividual=population[i];
			worst_index=i;
		}
		sum+=population[i].fitness;
	}
	if(generation==0){
		currentbest=bestindividual;
	}else{
		if(bestindividual.fitness>currentbest.fitness){
			currentbest=bestindividual;
		}
	}
}
//用最好个体替代最差个体
void PerformEvolution(void)
{
	if(bestindividual.fitness>currentbest.fitness){
		currentbest=population[best_index];
	}else{
		population[worst_index]=currentbest;
	}
}
//比例选择产生染色体
void SelectionOperator(void)
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];
	struct individual newpopulation[POPSIZE];
	//计算相对适应度
	for(i=0;i<PopSize;i++){
		sum+=population[i].fitness;
	}
	for(i=0;i<PopSize;i++){
		cfitness[i]=population[i].fitness/sum;
	}
	//计算累积适应度
	for(i=1;i<PopSize;i++){
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}
	//选择
		for(i=0;i<PopSize;i++){
         
		p=rand()%1000/1000.0;
		index=0;
		while(p>cfitness[index]){
			index++;
		}
		newpopulation[i]=population[index];
	}
	for(i=0;i<PopSize;i++){
		population[i]=newpopulation[i];
	}
}
//交叉
void CrossOverOperator(void)
{ 
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;
		//任意配对
	for(i=0;i<PopSize;i++)
	{
		index[i]=i;
	}

	//for(i=0;i<PopSize;i++)
//	{
		
	//	point=rand()%PopSize-1;
	//	temp=index[i];
	//	index[i]=index[point+1];
	//	index[point+1]=temp;
//	}
	//一点交叉

	for(i=0;i<PopSize-1;i+=2)
	{
           p=rand()%1000/1000.0;
	
        if(p<Pc){
 
	point=rand()%CHROMLENGTH+1;
	for(j=point;j<CHROMLENGTH;j++)
	{
		ch=population[index[i]].chrom[j];
		population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
		population[index[i+1]].chrom[j]=ch;
	}
	
}
}
}
//变异
void MutationOperator(void)
{

	int i,j;
	double p;
	for(i=0;i<PopSize;i++){
		for(j=0;j<CHROMLENGTH;j++){
			p=rand()%1000/1000.0;
			if(p<Pm){
				population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
			}
		}
	}
}
//输出结果
void OutputTextReport(void)
{
	int i;
	double sum;
	double average;
    sum=0.0;
	for(i=0;i<PopSize;i++){
		sum+=population[i].value;
	}
	average=sum/PopSize;
    printf("gen=%d,avg=%f,best=%f,",generation,average,currentbest.value);
	printf("chromsome=");
	for(i=0;i<CHROMLENGTH;i++){
		printf("%c",currentbest.chrom[i]);
	}
	printf("\n");
}