【⼈⼯智能】遗传算法（GA）⼊门—以求解⼀元函数最⼤值的优化问题为例前⾔
遗传算法有很多优化和变形，本⽂将从最基本的遗传算法出发，以⼀个简单的优化问题作为例⼦来说明遗传算法的代码实现，⽐较适合已经学了相关理论知识的初学者进⾏实践学习。
⼀、问题描述
⽤GA求解⼀元函数的最⼤值：
f(x) = x sin(10πx) + 2.0, x∈[-1,2]
⼆、编码
变量x可以视为遗传算法的表现型形式，我们采⽤⼆进制编码形式。如果设定求解精度要精确到6位⼩数，由于区间长度为3，故将区间分为3*10^6等份，因为：
2097152 = 2^21 < 3*10^6 < 2^22 = 4194304
所以编码的⼆进制串长⾄少为22位。
我们采⽤⼆进制编码，将⼀个⼆进制串与区间[Left,Right]间对应的实数值建⽴对应：
假设⼆进制串b的⼗进制值为x’，则：
x = (Right-Left)*x'/(2^22-1.0)+Left;
三、产⽣初始种群
我们通过随机产⽣⼀些个体（即随机产⽣⼀些⼆进制串），来初始化我们的种群。
/*****function:generation the first popolation初始化群体*****/
void GenerateInitialPopulation (void)
{
int i,j;
srand((unsigned)(time(NULL)));
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';
}
}
四、对种群进⾏评估
/****function: evaluate population according to certain formula衡量群体*****/
void EvaluatePopulation (void)
{
CalculateObjectValue ();
CalculateFitnessValue ();
FindBestAndWorstIndividual ();
炮灰女配修仙记}
1.计算⽬标函数值
/*****function: to decode a binary chromosome into a decimal integer*****/
long DecodeChromosome (char *string,int point,int length)
{
int i;
long decimal=0L;
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 f(x) = x sin(10πx) + 2.0 *****/
void CalculateObjectValue (void)
{
int i;
long temp;
double x;
/*** ronbrock function***/
for (i=0;i<PopSize;i++)
{
temp=DecodeChromosome (population[i].chrom,0,CHROMLENGTH);
为什么月经一直不干净怎么办x=(Right-Left)*temp/(pow(2,CHROMLENGTH)-1.0)+Left;
population[i].value=x*sin(10*PI*x)+2.0;//函数值
population[i].x=x;//对应的⾃变量
}
}
2.计算适应值
在本例中，⽬标函数在定义域内⼤于0，⽽且求函数的最⼤值，所以我们直接引⽤⽬标函数作为适应度函数。
/******function: to calculate fitness value *******/
void CalculateFitnessValue (void)
{
int i;
for(i=0;i<PopSize;i++)
{
population[i].fitness=population[i].value;
}
}
3.找出局部最优个体与局部最差个体，并更新全局最优个体
/*****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=1;i<PopSize;i++)
{
if (population[i].fitness>bestindividual.fitness)
{bestindividual=population[i];best_index=i;}
el 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){ currentbest=bestindividual;}
el
{
if(bestindividual.fitness>currentbest.fitness) {currentbest=bestindividual;}
}
}
五、遗传操作
我们按照轮盘赌的⽅式来选择⼦个体，对选出来的个体，两两进⾏交叉操作，随机选择⼀个交叉点。交叉之后进⾏变异操作，在⼆进制编码中，变异体现在位翻转上。
/*****function: generate the next generation产⽣新种群*****/
void GenerateNextPopulation (void)
{
SelectionOperator ();
CrossoverOperator ();
MutationOperator ();
}
/*****function: to reproduce a chromosome by roulette wheel clection*****/
void SelectionOperator (void)
{
int i,j,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];}
/
***lection operation***/
for(i=0;i<PopSize;i++)
{
p=random(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*****/
void CrossoverOperator (void)
{
int i,j;
int index[POPSIZE];
int point,temp;
double p;
char ch;
/***make a pair of individual randomly***/
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];
index[point+i]=temp;
}
/***one-point crossover operation***/
for(i=0;i<PopSize-1;i+=2)
{
p=random(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;
}
}
}
}
/*****function: mutation of a chromosome*****/
void MutationOperator (void)
{
int i,j;
double p;
/*** bit mutation***/
for(i=0;i<PopSize;i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
p=random(1000)/1000.0;
if(p<Pm){population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';}
}
}
}
六、进化
/*****function:to perform evolution operation bad on eliti mode. elitist 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];}
el{population[worst_index]=currentbest;}
汽车美容知识}
七、模拟结果
我们设定种群⼤⼩为80，交叉概率为Pc=0.6，变异概率为Pm=0.001，按照标准的遗传算法SGA，在运⾏到200代时获得的最佳个体为：
x=1.850549
f(x)=3.850275
chromosome=1111001100111111001011
这个个体对应的解与微分⽅程预计的最优解的情况吻合。
附录
完整代码
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <math.h>
/****** the definition of constant******/
# define PI 3.14159
# define POPSIZE 80
/****** the definition of ur data*****/
# define LEFT -1
# define RIGHT 2
# define CHROMLENGTH 22
# define random(x) rand()%x
const int MaxGeneration=200;
const double Pc=0.6;
const double Pm=0.001;
/***** the definition of data structure*****/
struct individual
{
char chrom[CHROMLENGTH+1];//基因
double x; //⾃变量
double value;//⽬标函数值
double fitness;//适应度
};
/***** the definition of global variables*****/
int generation;
int best_index;
int worst_index;
struct individual bestindividual; //局部最优个体
struct individual worstindividual; //局部最差个体
struct individual currentbest; //全局最优个体
struct individual population[POPSIZE];//种群
/*****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*****/
外公生日祝福语int main (void)
{
generation=0;
