遗传算法简介及代码详解.doc

遗传算法简述及代码详解
声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。
遗传算法基本内容
遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。

遗传学与遗传算法中的基础术语比较
染色体(chromosome)
数据，数组，序列
基因(gene)
单个元素，位
等位基因(allele)
数据值，属性，值
基因座(locus)
位置，iterator位置
表现型(phenotype)
参数集，解码结构，候选解

染色体：又可以叫做基因型个体(individuals)
群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数
量叫做群体大小。
初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。
适应度(fitness)：各个个体对环境的适应程度
优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。

遗传算法的准备工作:
1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)
2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。非常重要的过程。

遗传算法基本过程为:
1) 编码，创建初始群体
2) 群体中个体适应度计算
3) 评估适应度
4) 根据适应度选择个体
5) 被选择个体进行交叉繁殖
6) 在繁殖的过程中引入变异机制
7) 繁殖出新的群体，回到第二步

实例一：（建议先看实例二）
求 范围内的的最小值
1) 编码算法选择为"将转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。(等位基因的值为0 or 1)。
2) 计算适应度的方法是：先将个体串进行解码，转化为int型的x值，然后使用 作为其适应度计算合适(由于是最小值，所以结果越小，适应度也越好)。
需要说明，将原目标函数设置为适应度函数是一种选择，但未必是最贴切的方法。
3) 正式开始，先设置群体大小为4，然后初始化群体 => (在[0，31]范围内随机选取4个整 数就可以编码)
4) 计算适应度Fi(由于是求解最小值，可以选取一个大的基准线1000
）
5) 计算每个个体的选择概率，选择概率要能够反映个体的优秀程度。这里用一个很简单的 方法来确定选择概率

6) 选择
根据所有个体的选择概率进行淘汰选择。这里使用的是一个赌轮的方式进行淘汰选择。先按照每个个体的选择概率创建一个赌轮，然后选取4次，每次先产生一个0-1的随机小数，然后判断该随机数落在那个段内就选取相对应的个体。这个过程中，选取概率高的个体将可能被多次选择，而概率低的就可能被淘汰。
下面是一个简单的赌轮的例子
13% 35% 15% 37%
----------|----------------------------|------------------|---------------------------------|
个体1 个体2 个体3 ^0.67 个体4
随机数为0.67落在了个体4的端内，本次选择了个体4。
被选中的个体将进入配对库(mating pool，配对群体)准备开始繁殖。
7) 简单交叉
先对配对库中的个体进行随机配对，然后在配对的2个个体中设置交叉点，交换2个个体的信息后产生下一代。
比如( | 代表简单串的交叉位置)
( 0110|1，1100|0 ) --交叉--> (01100，11001)
( 01|000，11|011 ) --交叉--> (01011，11000)
2个父代的个体在交叉后繁殖出了下一代的同样数量的个体.
复杂的交叉在交叉的位置，交叉的方法，双亲的数量上都可以选择.其目的都在于尽可能的培育出更优秀的后代
8) 变异
变异操作时按照基因座来的，比如说每计算2万个基因座就发生一个变异(我们现在的每个个体有5个基因座。也就是说要进化1000代后才会在其中的某个基因座发生一次变异)变异的结果是基因座上的等位基因发生了变化。我们这里的例子就是把0变成1或则1变成0。
至此，我们已经产生了一个新的(下一代)群体，然后回到第4步，周而复始，生生不息下去。

实例二：
为了便于理解，手工计算来简单地模拟遗传算法的各个主要执行步骤：

（1） 个体编码
遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数（编码方式较多）来表示。
因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。
例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。
个体的表现型x和基因型X之间可通过编码和解码程序相互转换。

(2) 初始群体的产生
遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据。
本例中，群体规模的大小（随机选取）取为4，即群体由4个个体组成，每个个体可通过随机方法产生。
如：011101，101011，011100，111001

(3) 适应度汁算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。
本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度（适应度函数可以有许多）。

(4) 选择运算
选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。
本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：
• 先计算出群体中所有个体的适应度的总和 ；
• 其次计算出每个个体的相对适应度的大小，它即为每 个个体被遗传到下一代群体中的概率；
• 每个概率值组成一个区域，全部概率值之和为1；
• 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率 区域内来确定各个个体被选中的次数。（详见下图）

(5) 交叉运算
交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。
本例采用单点交叉的方法，其具体操作过程是：
• 先对群体进行随机配对；
• 其次随机设置交叉点位置；
• 最后再相互交换配对染色体之间的部分基因。
(6) 变异运算
变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。
本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
• 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
其中的数字表示变异点设置在该基因座处；
• 然后依照某一概率将变异点的原有基因值取反。

对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。

从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。

[注意]
需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中，有可能需要一定的循环次数才能达到这个最优结果。

选择要能够合理的反映“适者生存”的自然法则，而交叉必须将有利的基因尽量遗传给下一代 (这是算法的关键！)

算法过程当中有几个随机过程：
（1） 初始种群的产生是随机产生，但有时为了更好迭代，知道解在某一个值附近，可以认
为设定初始种群
（2） 确定个体被选中次数时，运用到轮赌法，其产生的数据为随机数据
（3） 交叉点
（4） 变异点
伪代码:
//Init population
foreach individual in population
{
individual = Encode(Random(0,31));
}
while (App.IsRun)
{
//计算个体适应度
int TotalF = 0;
foreach individual in population
{
individual.F = 1000 - (Decode(individual)-10)^2;
TotalF += individual.F;
}
//------选择过程,计算个体选择概率-----------
foreach individual in population
{
individual.P = individual.F / TotalF;
}
//选择
for(int i=0;i<4;i++)
{
//SelectIndividual(float p)是根据随机数落在段落计算选取哪个个体的函数
MatingPool[i] = population[SelectIndividual(Random(0,1))];
}
//-------简单交叉---------------------------
//由于只有4个个体,配对2次
for(int i=0;i<2;i++)
{
MatingPool.Parents[i].Mother = MatingPool.RandomPop();
MatingPool.Parents[i].Father = MatingPool.RandomPop();
}
//交叉后创建新的集团
population.Clean();
foreach Parent in MatingPool.Parents
{
//注意在copy 双亲的染色体时在某个基因座上发生的变异未表现.
child1 = Parent.Mother.DivHeader + Parent.Father.DivEnd;
child2 = Parent.Father.DivHeader + Parent.Mother.DivEnd;
population.push(child1);
population.push(child2);
}
}

完整代码如下：
#include "stdafx.h"
#include <stdio.h>
#include<stdlib.h>
#include<time.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 =100; //最大世代数，即最大迭代数
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);
void CalculateObjectValue(void);
long DecodeChromosome(char *,int,int); //译码
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossoverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);
void main(void)
{
generation=0;
GenerateInitialPopulation(); //初始种群生成

EvaluatePopulation(); //计算种群值，即计算种群适应度
while(generation<MaxGeneration)
{
generation++;
GenerateNextPopulation(); //产生下一代种群
EvaluatePopulation(); //计算种群值，即计算种群适应度
PerformEvolution();
OutputTextReport();
}
}

void GenerateInitialPopulation(void) //随机产生初始种群，且用0,1表示
{
int i,j;
for(i=0;i<PopSize; i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
population[i].chrom[j]=(rand()%10<5)?'0':'1'; //rand()%n产生一个
// ~n-1的数
}
population[i].chrom[CHROMLENGTH]='\0';
}
}
void GenerateNextPopulation(void)
{
SelectionOperator();
CrossoverOperator();
MutationOperator();
}
void EvaluatePopulation()
{
CalculateObjectValue();
CalculateFitnessValue();
FindBestAndWorstIndividual();
}
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);
}
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.0 *temp1/1023.0-2.0 ; //x[a, b]；
x2=4.0 *temp2/1023.0-2.0 ; //
population[i].value=100*(x1*x2+x2)*(x1*x2-x2)*x2;// 函数表达式
}
}
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=rand()%(PopSize-i);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for (i=0;i<PopSize-1;i+=2)
{
p=rand()%1000/1000.0; //随机产生交叉概率
if (p<Pc)
{
point=rand()%(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()%1001/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]);
}
Long temp1=DecodeChromosome(population[i].chrom,0,LENGTH1);
//从染色体中读取基因
long temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2);
double x1=4.0*temp1/1023.0-2.0;//基因型换为表现型

double x2=4.0*temp2/1023.0-2.0;
printf(" x1=%f,x2=%f",x1,x2);
printf("\n");
}