/*Simple Genetic Algorithm */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*The Definition of Constant*/
#define POPSIZE 500//population size
#define MAXIMIZATION 1 //maximization flag
#define MINIMIZATION 2 //minimization flag
/*The definition of User Data (For different problem,there are some difference.)*/
#define Cmax 100//certain maximal value
#define Cmin 0 //certain minimum value
#define LENGTH1 10 //the chromosome length of 1st variable
#define LENGTH2 10 //the chromosome length of 2nd variable
#define CHROMLENGTH LENGTH1+LENGTH2 //total length of chromosome
int FunctionMode=MAXIMIZATION; //optimization
int PopSize =80; //population size
int MaxGeneration=100000; //max. number of generation
double Pc =0.6; //probability of crossover
double Pm =0.001; //probability of mutation
/*The Definition of Data Structure*/
struct individual //data structure of individual
{
char chrom [CHROMLENGTH+1]; //a string of code representing individual
double value; //object value of this individual
double fitness; //fitness value of this individual
};
/*The Definition of Global Variables*/
int generation; //number of generation
int best_index; //index of best individual
int worst_index; //index of worst individual
struct individual bestindividual; //best individual of current generation
struct individual worstindividual; //worst individual of current generation
struct individual currentbest; //best individual by now
struct individual population [POPSIZE]; //population
/*Declaration of Prototype(原型)*/
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);
/*main program*/
void main(void)
{
time_t ts,te; //////
ts=time(NULL); ////////////
generation=0;
GenerateInitialPopulation ();
EvaluatePopulation ();
while (generation<MaxGeneration)
{
generation++;
GenerateNextPopulation ();
EvaluatePopulation ();
PerformEvolution ();
OutputTextReport ();
}
//srand((unsigned)time(NULL));
te=time(NULL);
printf("time is=%ld\n",te-ts);
}
/*Function:Generate the first population. Variable:None*/
void GenerateInitialPopulation (void)
{
int i,j;
//randomize ();
srand( (unsigned)time( NULL ) );
for (i=0;i<PopSize;i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
population[i].chrom[j]=((rand()/3276.7)<5)?'0':'1';//原文见pdf
}
population[i].chrom[CHROMLENGTH]='\0';
}
}
/*Function:Initialize the first generation. Variable: None.*/
void GenerateNextPopulation(void)
{
SelectionOperator();
CrossoverOperator();
MutationOperator();
}
/*Function:Evaluate population according to certain formula. Variable:None.*/
void EvaluatePopulation(void)
{
CalculateObjectValue(); //calculate object value
CalculateFitnessValue(); //calculate fitness value
FindBestAndWorstIndividual(); //find the best and worst individual
}
/*Function: To decode a binary chromosome into a decimal integer
Variable:None.
Note:The returned 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=0;//??????????????????????????????waht原来是OL????????????
char *pointer;
for(i=0,pointer=string+point;i<length;i++,pointer++)
{
decimal+=(*pointer-'0')<<(length-1-i);//?????????????????????
}
return(decimal);
}
/*Function: To calculate object value.
Variable:None.
Note:For different problem,user must change these code.
This example is dealing with Rosenbrock function.
Rosebrock 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<PopSize;i++)
{
temp1=DecodeChromosome(population[i].chrom,0,LENGTH1);///////meaning??????
temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2);///////meaning??????
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.Variable:None.*/
void CalculateFitnessValue(void)//????????????????
{
int i;
double temp;
for(i=0;i<PopSize;i++)
{
if(FunctionMode==MAXIMIZATION)
{
//maximization
if((population[i].value+Cmin)>0.0)
{
temp=Cmin+population[i].value;
}
else
{
temp=0.0;
}
}
else if (FunctionMode==MINIMIZATION)
{
//minimization
if(population[i].value<Cmax)
{
temp=Cmax-population[i].value;
}
else
{
temp=0.0;
}
}
population[i].fitness=temp;
}
}
/*Function:To Find out the best individual so far current generation.
Variable:None.*/
void FindBestAndWorstIndividual(void)
{
int i;
double sum=0.0;
//find the best and the worst individual of this generation
bestindividual=population[0];
worstindividual=population[0];
for(i=1;i<PopSize;i++)
{
if(population[i].fitness>bestindividual.fitness)
{
bestindividual=population[i];
best_index=i;
}
else if(population[i].fitness<worstindividual.fitness)
{
worstindividual=population[i];
worst_index=i;
}
sum+=population[i].fitness;
}
//find out the best individual so far
if(generation==0)
{
//initialize the best individual
currentbest=bestindividual;
}
else
{
if(bestindividual.fitness>currentbest.fitness)
{
currentbest=bestindividual;
}
}
}
/*Function:To perform evolution operation based on elitise model.
Elitist model is to replace the worst individual of this generation
by the current best one.
Variable:None*/
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.
Variable:None.*/
void SelectionOperator(void)
{
int i,index;
double p,sum=0.0;
double cfitness[POPSIZE];//cumulative fitness value
struct individual newpopulation[POPSIZE];
//calculate relative fitness
for(i=0;i<PopSize;i++)
{
sum+=population[i].fitness;
}
for(i=0;i<PopSize;i++)
{
cfitness[i]=population[i].fitness/sum;
}
//calculate cumulative fitness
for(i=1;i<PopSize;i++)
{
cfitness[i]=cfitness[i-1]+cfitness[i];
}
//selection operation
srand( (unsigned)time( NULL ) );
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];
}
}
/*Function: Crossover two chromosome by means of one-point crossover.
Variable:None.*/
void CrossoverOperator(void)
{
int i,j;
int index[POPSIZE];
int point,temp;
double p;
char ch;
//make a pair of individual randomly