一个遗传算法.txt

一个遗传算法例子

/* Simple Genetic Alaorithm*/
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

/* The Definition of Constant */ 
#define POPSIZE 500 //
#define MAXIMIZATION 1 //
#define MINIMIZATION 2 //
/* The Definition of User Data (for different problem,
there are some diffrence)*/

#define Cmax 100 //
#define Cmin 0 //
#define LENGTH1 10 //
#define LENGTH2 10 //
#define CHROMLENGTH LENGTH+LENGTH2 //
int Fuction-Mode=MAXIMIZATION; //
int PopSize =80 //
int MaxGeneration = 200 //
double Pc =0.6; // here i want to change it and by means of fitness maybe
double Pm=0.001 //
/*The Definition of Data Structure */
struct individual //
{
char chrom[ CHROMLENGTH+1]; // 
double value;
double fitness; //
};
/* The Definition of Global Variables*/ 
int genetation; //
int best_index; //
int worst_index; //
struct individual bestindividual; //
struct individual worstindividual; //
struct individual currentbest; //
struct individual populaton[popsize]; //
/* declaration of Prototype */
void GenerateIntialPopulation(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); 
/*maim program*/
void main(void)
{
generation=0;
GenerateIntialPopulation();
EvaluatePopulation();
while(generation {
generation++;
GenerateNextPopulation();
EvaluatePopulation();
PerformEvolution();
OutputTextReport();
}
}
/*function:Generate the first population*/
void GenerateIntialPopulation(void)
{
int i,j;
randomize();
for(i=0;i {
for(j=0;j {
population[i].chrom[j]=(random(10)<5)?'0':'1';
}
population[i].chrom[CHROMLENGTH]='\0';
}
}
/*Function:Initialize the first generation.*/
void GenerateNextPopulation(void)
{
SelectionOperator(); 
CrossoverOperator(); 
MutationOperator(); 
}
/*Function: Evaluate population according to certain formula.*/
void EvaluatePopulation()
{
CalculateObjectValue(); //
CalculateFitnessValue(); // 
FindBestAndWorstIndividual(); //
}
/*Function: To decode a binary chromosome into a decimal integer.
note: The returmed value may be plus,or minus,For different coding method,
this value may be changed into'unsigned int'*/
long DecodeChromosome(char *string,int point,int length)
{
int i;
long decimal=0l; 
char *pointer;
for(i=0,pointer=string+point;i {
decimal+=(*pointer-'0')<<(length-1-i);
}
return(decimal);
}
/*Function:To calculate object value.
Note:For different problem,user must change these code.This example is dealing with 
Rosenbrock function. Rosenbrock function is defined as:
f(x1,x2)=100*(x1**2-x2)**2+(1-x1)**2
Its maximal value is:
f(-2.048,-2.048)=3905.926227*/
void CalculateObjectValue(void);
{
int i;
long temp1,temp2;
double x1,x2;
//Rosenbrock function
for(i=0;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);
}
}
//Function: To calculate fitness value.
void CalculateFitnessValue(void)
{
int i;
double temp;
for(i=0;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 {
temp=Cmax-population[i].value;
}
else
{
temp=0.0;
}

}
population[i].fitness=temp;
}
}
//Function:To Find out the best individual so far current generation.
void FindBestAndWorstIndividual(void)
{
int i;
double sum=0.0;
//find out the best and worst individual of this generation
bestindividual=population[0];
worstindividual=population[0];
for(i=0;i {
if(population[i].fitness>bestindividual.fitness)
{
bestindividual=population[i];
best_index=i;
}
else if(population[i].fitness worstindividual=population[i];
worst_index=i;
}
sum+=population[i].fitness;
}
//find out the best individual so far
if(generation==0)
{
currentbest=bestindividual; 
}
else
{
if(bestindividual.fitness>currentbest.fitness)
{
currentbest=bestindividual;
}
}
//Function:To perform evolution operation based on
// elitise model.Elitise model is to replace the worst individual 
//of this generation by the current best one.
void PerformEvolution(void)
{
if(bestindividual.fitness>currentbest.fitness)
{
currentbest=population[best_index];
}
else
{
population[worst_index]=currentbest;
}
}
//Function:To reproduce a chromosome by proportional selection.
void SelectionOperator(void)
{
int i,index;
double p,sum=0.0;
double cfitness[POPSIZE];//cumulative fitness value这里用的是500
struct individual newpopulation[POPSIZE];
//calculate relative fitness
for(i=0;i {
sum+=population[i].fitness;
}
for(i=0;i {
cfitness[i]=population[i].fitness/sum;
}
//calculate cumulative fitness
for(i=0;i {
cfitness[i]=cfitness[i-1]+cfitness[i];
}
//selection operation
for(i=0;i {
p=rand()%1000/1000.0;
index=0;
while(p>cfitness[index])
{
index++;
}
newpopulation[i]=population[index];
}
for(i=0;i {
population[i]=newpopulation[i];
}
} 
//Function: Crossover two chromosome by means of one-point crossover.
void CrossoverOperator(void)
{
int i,j;
int index[POPSIZE]; //ONCE AGAIN
int point,temp;
double p;
char ch;
//make a pair of individual randomly
for(i=0;i {
index[i]=i;
}
for(i=0;i {
pont=random(Popsize-i);
temp=index[i];
index[i]=index[point+1];
index[point+i]=temp;
}
//one-point crossover operation
for(i=0;i {
p=rand()%1000/1000.0;
if(p {
point=random(CHROMLENGRH-1)+1;
for(j=point;j {
ch=population[index[i]].chrom[j];
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];

}
}
}

}
//Function:Mutation of a chromosome. 
void MutationOperator(void) 
{
int i,j;
double p;
//bit mutation
for(i=0;i {
for(j=0;j {
p=rand()%1000/1000.0;
if(p {
population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
} 
}
}
}
//Function:output the result of current population.
void OutputTextReport(void) 
{
int i;
double sum;
double average;
//calculate average object value
sum=0.0;
for(i=0;i {
sum+=population[i].value;
}
average=sum/PopSize;
printf("chromosome+");
for(i=0;i {
printf("%c",currentbest.chrom[i]);
}
printf("\n");
}