2.基本遗传算法

2.1基本遗传算法描述

2.1.1基本遗传算法的构成要素

2.1.2基本遗传算法描述

2.1.3基本遗传算法的形式化定义

2.2基本遗传算法的实现

2.2.1个体适应度评价

2.2.2比例选择算子

2.2.3单点交叉算子

2.2.4基本位变异算子

2.3基本遗传算法应用举例

2.3.1遗传算法的应用步骤

2.3.2基本遗传算法在函数优化中的应用举例

2.3.3补充解释

参考资料

2.基本遗传算法

针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。

基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（Simple Genetic Algorithms，简称SGA）。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子。它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。

2.1基本遗传算法描述

2.1.1基本遗传算法的构成要素

(1)染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基因是由二值符号集{0,1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。如：X=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。

(2)个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。

(3)遗传算子。基本遗传算法使用下述三种遗传算子：
●选择运算使用比例选择算子；
●交叉运算使用单点交叉算子；
●变异运算使用基本位变异算子或均匀变异算子。

(4)基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：
●M：群体大小，即群体中所含个体的数量，一般取为20~100；
●T：遗传运算的终止进化代数，一般取为100~500；
●Pc：交叉概率，一般取为0.4-0.99；
●Pm：变异概率，一般取为0.0001~0.1。

需要说明的是，这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。
在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。

2.1.2基本遗传算法描述

下面我们给出基本遗传算法的伪代码描述。

Procedure SGA
begininitialize P(0);        %初始化群体t=0;while (t≤T)for i=0 to M doEvaluate fitness of P(t);         %计算群体中每个个体的适应度endforfor i=1 to M doSelect operation to P(t);        %选择操作endforfor i=1 to M/2 doCrossover operation to P(t);  %交叉操作endforfor i=1 to M doMutation operation to P(t);   %变异操作endforfor i=1 to M doP(t+1)=P(t);endfort=t+1;endwhile
end

2.1.3基本遗传算法的形式化定义

基本遗传算法可定义为一个8元组：

2.2基本遗传算法的实现

根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计算机语言来实现这个基本遗传算法。

现对具体实现过程中的间题作以下说明。

2.2.1个体适应度评价

在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。

2.2.2比例选择算子

选择算子或复制算子的作用是从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。最常用和最基本的选择算子是比例选择算子。所谓比例选择算子，是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。比例选择实际上是一种有退还随机选择，也叫做赌盘( Roulette Wheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。

如下图，整个赌盘被分为大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。虽然赌盘的指针具体停止在哪一个面是无法预测的，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比：圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。

与此类似，在遗传算法中整个群体被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。

比例选择算子的具体执行过程是：
(1)先计算出群体中所有个体的适应度的总和。
(2)其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率。
(3)最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数。

2.2.3单点交叉算子

单点交叉算子是最常用和最基本的交叉操作算子。

单点交叉算子的具体执行过程如下：

(1)对群体中的个体进行两两随机配对。若群体大小为M，则共有 $\lfloor M/2 \rfloor$ 对相互配对的个体组。其中 $\lfloor x \rfloor$ 表示不大于x的最大的整数。

(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为n，则共有(n-1)个可能的交叉点位置。

(3)对每一对相互配对的个体，依设定的交叉概率Pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。

2.2.4基本位变异算子

基本位变异算子是最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0。

基本位变异算子的具体执行过程如下：
(1)对个体的每一个基因座，依变异概率Pm指定其为变异点；
(2)对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体；

2.3基本遗传算法应用举例

由前述可以知道，基本遗传算法是一个选代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近似最优解。

虽然算法的思想比较单纯，结构也比较简单，但它却也具有一定的实用价值，能够解决一些复杂系统的优化计算问题。

2.3.1遗传算法的应用步骤

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法。

第一步：确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。
第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值?)及其数学描述形式或量化方法。
第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。
第四步：确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法。
第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。
第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。
第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等参数。

由上述构造步骤可以看出，可行解的编码方法、遗传算子的设计是构造遗传算法时需要考虑的两个主要问题，也是设计遗传算法时的两个关键步骤。对不同的优化问题需要使用不同的编码方法和不同操作的遗传算子，它们与所求解的具体问题密切相关，因而对所求解问题的理解程度是遗传算法应用成功与否的关键。

2.3.2基本遗传算法在函数优化中的应用举例

【例】Rosenbrock函数的全局最大值计算。

max $f(x1,x2)=100(x1^{2}-x2)^{2}+(1-x1)^{2}$ （2-6）

遗传算法的主要构造过程如下：

下面介绍求解该问题的遗传算法的构造过程。

第一步：确定决策变量和约束条件。

式（2-7）已给出了该问题的决策变量及其约束条件。

第二步：建立优化模型。

式（2-6）已给出了该问题的数学模型。

第三步：确定编码方法。

用长度为10位的二进制编码串来分别表示两个决策变量x1、x2。10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1、x2的定义域离散化为1023个均等的区域，包含两个端点，分别有1024个不同的离散点。从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1、x2的两个10位长的二进制编码串连接在一起。组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间具有一一对应的关系。

例如

就表示一个个体的基因型，其中前10位表示x1，后10位表示x2。

第四步：确定解码方法。

解码时，需先将20位长的二进制编码串切断为两个十进制串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据前述个体编码方法和对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：

4.096×yi/1023是整个决策变量的区间长度（在1023等分），加上-2.048（区间开始的值），求得xi即为解码后的数值（在区间的约束条件内）

例如，对于前述个体 X：0000110111 1101110001 它由这样的两个代码所组成：y1=55 y2=881

经过式（2-7）的解码处理后，可得到：x1=-1.828 x2=1.476

第五步：确定个体评价方法。

由式（2-6）可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有F(X)=f(x1,x2) （2-9）

第六步：设计遗传算子。

选择运算使用比例选择算子；

交叉运算使用单点交叉算子；

变异运算使用基本位变异算子。

第七步：确定基本遗传算法的运行参数。

对于本例，设定基本遗传算法的运行参数如下：

群体大小：M=80

终止代数：T=200

交叉概率：Pc=0.6

变异概率：Pm=0.001

通过上述七个步骤可构成用于Rosenbrock函数优化计算的基本遗传算法，下图为其进化过程示例及运行结果。图中横轴表示进化代数，纵轴表示适应度（也是目标函数值），图中的两条曲线分别为各代群体中个体适应度的最大值和平均值。

在上图可以看出，在解的进化过程中，群体中个体适应度的最大值和平均值虽然有上下波动的情况，但总的来说却是呈现一种上升的趋势。

随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体越来越多，并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。

2.3.3补充解释

遗传算法可以形象化的理解：假设我们求这群山的海拔最高的点

往这群山上撒一些点，初始化群体；
然后给个海拔的要求，假如是图中的红线1，不满足要求的淘汰掉，满足要求的留下来；
然后再给个海拔的要求，假如是图中的红线2，不满足要求的淘汰掉，满足要求的留下来，依次求下去，如红线3；
随着适应度的不断提高，群体也逐渐接近最优解，也就是说遗传算法是一种全局的优化算法。