sga.cpp

基本遗传算法,用来求解函数的最大值!在VC和TC下均可实现.

/*
* 基本遗传算法解决函数优化问题：
* Max f(x1,x2)=100*(x1**2-x2)**2+(1-x1)**2
* s.t. -2.048 <= xi <= 2.048 (i=1,2)
* 其中 "**2" 为2次方
* 2004-12-26 21:05
*/
#include <iostream>
#include <cstdlib>
#include <vector>
#include <valarray>                 // for valarray
#include <cmath>
#include <ctime>
using namespace std;

const int Length1=20;
const int Length2=20;
const int ChromLength=40;
const int PopSize=80;
const int MaxGeneration=150;
const double Pc=0.6;
const double Pm=0.001;
int Cmax=100;
int Cmin=0;
int best_index=0;
int worst_index=0;	


class SGA{
public:
	SGA(){
//		srand(time(0));
		for(int i=0; i<ChromLength; i++)
			_chrom.push_back(0);
		fitness=0.0;
		value=0.0;
		x1=0;
		x2=0;
	}
	void PopulationInitiate(){
		//srand(time(0));
		for(int i=0; i<ChromLength; i++)
			_chrom[i]=rand()%2;
	}
	void DecodeChromosome();
	void CaculateObjectValue();
	void CaculateFitnessValue();
	void SetPopulation(int x, int y){_chrom[x]=y;}
	void view(){
		for(int i=0; i<ChromLength; i++) cout<<_chrom[i];
		cout<<" fitness: "<<fitness;
		cout<<" "<<x1<<" "<<x2<<endl;
	}
	int Return_chrom(int x){return _chrom[x];}
	double Return_fitness(){return fitness;}
	double Return_value(){return value;}
private:
	vector<int> _chrom;
	double fitness;
	double value;
	double x1,x2;//精确到小数点后三位
};

void SGA::DecodeChromosome(){
	int sum1=1,sum2=1;
	int temp1=0,temp2=0;
	for(int i=0; i<Length1; i++){/////
		sum1=1;
		if(_chrom[i]==1){
			for(int j=0; j<i; j++)				
				sum1=sum1*2;
		}
		else sum1=0;
		temp1=temp1+sum1;
	}    ///////////////////////////前面十二位表示X1
	for(int k=Length1; k<ChromLength; k++){
		sum2=1;
		if(_chrom[k]==1){
			for(int j=Length1; j<k; j++)
				sum2=sum2*2;
		}
		else sum2=0;
		temp2=temp2+sum2;
	}///////////////////////////////后面十二位表示X2
	x1=temp1;
	x2=temp2;
}

void SGA::CaculateObjectValue(){
	x1=10*(x1/1048575);
	x2=10*(x2/1048575)-10;
	value=20+x1*cos(x2)+x2*sin(x1);
}

void SGA::CaculateFitnessValue(){
	fitness=value;
}


void FindBestAndWorstIndividual(SGA, SGA &, SGA &, SGA &);
void SelectionOperator(SGA, SGA,SGA &);
void CrossoverOperator(SGA);
void MutationOperator(SGA);


void FindBestAndWorstIndividual(SGA *population, SGA &bestindividual, 
								SGA &worstindividual, SGA &currentbest)
{
	double temp=population[0].Return_fitness();
	for(int i=1; i<PopSize; i++){
		if(population[i].Return_fitness()>temp){
			temp=population[i].Return_fitness();
			best_index=i;
		}
	}
	bestindividual=population[best_index];
	temp=population[0].Return_fitness();
	for(int j=1; j<PopSize; j++){
		if(population[j].Return_fitness()<temp){
			temp=population[j].Return_fitness();
			worst_index=j;
		}
	}
	worstindividual=population[worst_index];
	population[worst_index]=currentbest;
	if(bestindividual.Return_fitness()>currentbest.Return_fitness())
		currentbest=bestindividual;
}

void SelectionOperator(SGA *population, SGA *population2, SGA &currentbest){
	double sum,temp;
	int index;
	double individual[PopSize];
	sum=0;
	for(int i=0; i<PopSize; i++)
		sum=sum+population[i].Return_fitness();
	individual[0]=population[0].Return_fitness()/sum;
	for(int j=1; j<PopSize; j++)
		individual[j]=individual[j-1]+(population[j].Return_fitness()/sum);
	for(int k=0; k<PopSize; k++){//轮盘赌选择
		temp=rand()%1000/1000.0;
		index=0;
		while(temp>individual[index]){
			index++;
		}
		population2[k]=population[index];
	}
	for(int h=0; h<PopSize; h++)
		population[h]=population2[h];
}

void CrossoverOperator(SGA *population){
	int index[PopSize];
	int point,temp=PopSize;
	int tem,i,p,ch;
	for(i=0; i<PopSize; i++)
		index[i]=i;
	for(i=0; i<PopSize; i++){
		point=rand()%(temp-i);
		tem=index[i];
		index[i]=index[i+point];
		index[i+point]=tem;
	}
	for(i=0; i<PopSize; i+=2){
		p=rand()%1000/1000.0;
		if(p<Pc){
			point=rand()%ChromLength;
			for(int j=point; j<ChromLength; j++){
				ch=population[index[i]].Return_chrom(j);
				population[index[i]].SetPopulation(j,population[index[i+1]].Return_chrom(j));
				population[index[i+1]].SetPopulation(j,ch);
			}
		}
	}
}

void MutationOperator(SGA *population){
	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].SetPopulation(j,(population[i].Return_chrom(j)==0 ? 1 : 0));
		}
	}
}

int main(){
	int generation;
	srand(time(0));
	SGA bestindividual;
	SGA worstindividual;
	SGA currentbest;
	SGA population2[PopSize];
	SGA population[PopSize];
	for(int i=0; i<PopSize; i++){
		population[i].PopulationInitiate();
		population[i].DecodeChromosome();
		population[i].CaculateObjectValue();
		population[i].CaculateFitnessValue();
	}
	for(generation=1; generation<=MaxGeneration; generation++){
		FindBestAndWorstIndividual(population, bestindividual, 
			worstindividual, currentbest);
		SelectionOperator(population, population2, currentbest);
		CrossoverOperator(population);
		MutationOperator(population);
		for(int i=0; i<PopSize; i++){
			population[i].DecodeChromosome();
			population[i].CaculateObjectValue();
			population[i].CaculateFitnessValue();
		}
		cout<<"Generation "<<generation<<": ";
		population[best_index].view();
	}
	cout<<"\n"<<endl;
	currentbest.view();
	return 0;
};