sga00.cpp

遗传算法

#include <iostream>
#include <cstdlib>
#include <ctime>
#include "string.h"
using namespace std;

#define popsize 80
#define LENGTH1 10
#define LENGTH2 10
#define lengthOfChrom LENGTH1+LENGTH2

int MaxGeneration=200;
double pc=0.6;
double pm=0.001;
int numberOfGeneration;

class Generation
{
public:
	Generation();
	void initialize();
	void mutation();
	long decode(char * string,int point,int length);
	void computeObject();
	void computeFitness();
	void evaluate();
    void select();
	void crossover();
	void generateNextGeneration();
	void printResult();
	void Findbestandworst();
	void performEvolution();
	~Generation();
private:
	char population[popsize][lengthOfChrom+1];
	double fitness[popsize];
	double cfitness[popsize];
	double value[popsize];
    double currentBest;
	int current_index;
	int best_index,bad_index;
	char bestpopulation[lengthOfChrom+1];
};

Generation::Generation()
{
}

void Generation::initialize()
{
	int i,j;
	srand((unsigned)time(NULL));
	double p;
	for(i=0;i<popsize;i++)
	{
		for(j=0;j<lengthOfChrom;j++)
		{
			p=rand()%100/100.0;
            population[i][j]=(p<0.5)? '0':'1';
			//cout<<population[i][j];
		}
		population[i][lengthOfChrom]='\0';
	}
}

long Generation::decode(char *string,int point,int length)
{
	long decimal=0l;
	int i;
	char *pointer;
	for(i=0,pointer=string+point;i<length;i++,pointer++)
		decimal+=(*pointer-'0')<<(length-1-i);
	return(decimal);
}

void Generation::computeObject()
{
	int i,temp1,temp2;
	double x1,x2,f;
	for(i=0;i<popsize;i++)
	{
		temp1=decode(population[i],0,LENGTH1);
	    temp2=decode(population[i],LENGTH1,LENGTH2);
	    x1=-2.048+temp1*4.096/1023.0;
	    x2=-2.048+temp2*4.096/1023.0;
	    f=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
	    value[i]=f;
	}
}

void Generation::computeFitness()
{
//调整fitness的值使之>0
	int i;
	for(i=0;i<popsize;i++)
	{
		fitness[i]=value[i];
	}

}

void Generation::Findbestandworst()
{
    int i;
//	double sum=0.0;
	double bestIndividual,badIndividual;
	best_index=0,bad_index=0;
//	strcpy(bestIndividual,population[0]);
//	strcpy(badIndividual,population[0]);
    bestIndividual=fitness[0];
	badIndividual=fitness[0];
	for(i=1;i<popsize;i++)
	{
		if(fitness[i]>bestIndividual)
		{
			bestIndividual=fitness[i];
			best_index=i;
		}
		else
		{
			 if(fitness[i]<=badIndividual)
			 {
				 badIndividual=fitness[i];
				 bad_index=i;
			 }
		}
//		sum+=fitness[i];
	}
	if(numberOfGeneration==0)
	{
		currentBest=bestIndividual;
		strcpy(bestpopulation,population[best_index]);
//		bestvalue=value[best_index];
		current_index=best_index;
	}
	else
	{
		if(fitness[best_index]>currentBest)
		{
			currentBest=bestIndividual;
			strcpy(bestpopulation,population[best_index]);
//			bestvalue=value[best_index];
			current_index=best_index;
		}
	}
}

void Generation::performEvolution()
{
	if(fitness[best_index]>currentBest)
	{
		strcpy(population[current_index],population[best_index]);
		fitness[current_index]=fitness[best_index];
	}
	else
	{
		strcpy(population[bad_index],bestpopulation);
		fitness[bad_index]=currentBest;
	}
}

void Generation::evaluate()
{
	computeObject();
	computeFitness();
	Findbestandworst();
}

void Generation::select()
{
	int i,j,point;
	double p,sum=0.0;
	char temp[lengthOfChrom+1];
	//extern double cfitness[popsize];
	double bfitness[popsize],cvalue[popsize];
	char newGeneration[popsize][lengthOfChrom+1];
	
	for(i=0;i<popsize;i++)
	{
		sum+=value[i];
	}
	for(i=0;i<popsize;i++)
	{
		fitness[i]=value[i]/sum;
		//cout<<fitness[i]<<endl;
	}
	cfitness[0]=fitness[0];
    for(i=1;i<popsize;i++)
	{
		cfitness[i]=fitness[i]+cfitness[i-1];
	 //  cout<<fitness[i]<<  cfitness[i]<<endl;
    }
	for(i=0;i<popsize;i++)
	{
		p=rand()%1000/1000.0;
		j=0;
		while(p>cfitness[j])
		{
			if(j<popsize)
			{
				j++;
			}
			else 
				break;
		}
	/*	if(j==popsize)
		{
            int point=rand()%lengthOfChrom;
			j=point;
		}*/
        strcpy(newGeneration[i],population[j]);
		bfitness[i]=fitness[j];
		cvalue[i]=value[j];
	}
	
	for(i=0;i<popsize;i++)
	{
		strcpy(population[i],newGeneration[i]);
		fitness[i]=bfitness[i];
		value[i]=cvalue[i];
	}
	for(i=0;i<popsize;i++)
	{
		point=rand()%(popsize-i);
		strcpy(temp,population[i]);
		strcpy(population[i],population[(i+point)]);
		strcpy(population[(i+1)],temp);
		bfitness[0]=fitness[i];
		fitness[i]=fitness[(i+point)];
		fitness[(i+point)]=bfitness[0];
		cvalue[0]=value[i];
		value[i]=value[(i+point)];
		value[(i+point)]=cvalue[0];
	}
}

void Generation::crossover()
{
    char ch;
	int i=0,j;
	int point;
	double p;
//	for(i=0;i<popsize-1;i+=2)
    do
	{
		p=rand()%1000/1000.0;
		if(p<pc)
		{
		    point=rand()%lengthOfChrom;
		    for(j=point;j<lengthOfChrom;j++)
			{
		        ch=population[i][j];
				//cout<<ch;//此处有问题，输出的字符里有ｚ，ｗ之类的字母
		        population[i][j]=population[i+1][j];
				population[i+1][j]=ch;
			}
		}
		i+=2;
	}while(i<popsize-1);
}

void Generation::mutation()
{
    int i,j;
	double p;
	for(i=0;i<popsize;i++)
	for(j=0;j<lengthOfChrom;j++)
	{
	    p=rand()%1000/1000.0;
	    if(p<pm)
		{
			//point=rand()%lengthOfChrom;
	        population[i][j]=(population[i][j]=='0')?'1':'0';	
		}
	}
}

void Generation::printResult()
{
	double sum=0.0;
	double average;
	int i;
	//int j;
	for(i=0;i<popsize;i++) 
	{
		sum+=fitness[i];
	}
	average=sum/popsize;
	cout<<"numberOfGeneration="<<numberOfGeneration<<endl
		<<"average="<<average<<endl
		<<"current_index="<<current_index<<endl
		<<"目标函数值是"<<currentBest<<endl;
    cout<<"自变量X1的值是："<<decode(bestpopulation,0,LENGTH1)<<endl
		<<"自变量X2的值是："<<decode(bestpopulation,LENGTH1,LENGTH2)<<endl;
//		<<"currentBestValue="<<bestvalue<<endl<<endl;
    /*for(j=0;j<lengthOfChrom;j++)
	{
		cout<<currentBest[j];
	}*/
    puts(bestpopulation);
	cout<<endl;

}
void Generation::generateNextGeneration()
{
    select();
	crossover();
	mutation();
}


Generation::~Generation()
{
}

void main()
{
	numberOfGeneration=0;
	Generation generation;
	generation.initialize();
	generation.evaluate();
//	generation.printResult();
	while(numberOfGeneration++<MaxGeneration)
	{
		generation.generateNextGeneration();
		generation.evaluate();
		generation.performEvolution();
		generation.printResult();
	}
	
}