#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.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 = 300;
double Pc = 0.6;
double Pm =0.001;
struct individual //结构变量和函数定义
{
char chrom[CHROMLENGTH +1];
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);
int random(int n) //随机数产生函数
{
int ret=rand()%n;
return ret;
}
void main(void) //主函数
{
generation =0;
GenerateInitialPopulation();
EvaluatePopulation();
while(generation < MaxGeneration)
{
generation++;
GenerateNextPopulation();
EvaluatePopulation();
PerformEvolution();
OutputTextReport();
}
}
//---------------------------------------------------
void GenerateInitialPopulation(void) //产生初始群体
{
int i ,j;
for( i=0;i<PopSize;i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
population[i].chrom[j]=(random(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 =0L;
char * pointer;
int nstr=strlen(string);
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>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;
}
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 =random(PopSize-i);
temp =index[i];
index[i] =index[point+i]; //swap
index[point+i] =temp;
}
for(i=0;i<PopSize-1;i+=2)
{
p =rand()%1000/1000.0;
if(p<Pc)
{
point =random(CHROMLENGTH-1)+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("Chromosome=");
for(i=0;i<CHROMLENGTH;i++)
{
printf("%c",currentbest.chrom[i]);
}
printf("\n");
}