智能控制技术(第7章-遗传算法)

第七章遗传算法

遗传算法简称GA（GeneticAlgorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法的基本原理遗传算法自然选择学说包括以下三个方面：（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。遗传算法的基本原理遗传算法

遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。遗传算法的基本原理遗传算法遗传算法的基本操作为：（1）复制（ReproductionOperator）复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生0~1之间均匀分布的随机数，若某串的复制概率为40%，则当产生的随机数在0.40~1.0之间时，该串被复制，否则被淘汰。遗传算法的基本操作遗传算法（2）交叉（CrossoverOperator）复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。遗传算法遗传算法的基本操作

交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：遗传算法遗传算法的基本操作（3）变异(MutationOperator)

变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。遗传算法遗传算法的基本操作

若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。遗传算法遗传算法的基本操作（1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理；（2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。遗传算法的特点遗传算法

遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。（3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。遗传算法遗传算法的特点

遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。（4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。遗传算法遗传算法的特点（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；（6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。遗传算法遗传算法的特点（1）函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。遗传算法的应用领域遗传算法（2）组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。遗传算法遗传算法的应用领域（3）生产调度问题在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。遗传算法遗传算法的应用领域（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。遗传算法遗传算法的应用领域（5）机器人例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。（6）图像处理遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。遗传算法遗传算法的应用领域遗传算法的构成要素（1）染色体编码方法基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集{0,1}所组成。初始个体基因值可用均匀分布的随机值生成，如就可表示一个个体，该个体的染色体长度是18。遗传算法的优化设计遗传算法（2）个体适应度评价：基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值J到个体适应度f之间的转换规则。遗传算法遗传算法的优化设计（3）遗传算子：基本遗传算法使用下述三种遗传算子：①选择运算:使用比例选择算子；②交叉运算:使用单点交叉算子；③变异运算:使用基本位变异算子或均匀变异算子。遗传算法遗传算法的优化设计（4）基本遗传算法的运行参数有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20~100；G：遗传算法的终止进化代数，一般取为100~500；Pc：交叉概率，一般取为0.4~0.99；Pm：变异概率，一般取为0.0001~0.1。遗传算法遗传算法的优化设计

对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；遗传算法的应用步骤遗传算法第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。遗传算法遗传算法的应用步骤遗传算法流程图

遗传算法的操作过程遗传算法

利用遗传算法求Rosenbrock函数的极大值遗传算法求函数极值遗传算法二进制编码遗传算法求函数极大值求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法遗传算法遗传算法求函数极值

用长度为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。遗传算法遗传算法求函数极值（4）确定解码方法：解码时需要将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据个体编码方法和对定义域的离散化方法可知，将代码y转换为变量x的解码公式为例如，对个体遗传算法遗传算法求函数极值

它由两个代码所组成上述两个代码经过解码后，可得到两个实际的值（5）确定个体评价方法：由于Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即遗传算法遗传算法求函数极值选个体适应度的倒数作为目标函数（6）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（7）确定遗传算法的运行参数：群体大小M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。遗传算法遗传算法求函数极值

采用上述方法进行仿真，经过100步迭代，最佳样本为即当时，Rosenbrock函数具有极大值，极大值为3905.9。遗传算法遗传算法求函数极值

遗传算法的优化过程是目标函数J和适应度函数F的变化过程。由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。遗传算法遗传算法求函数极值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法：用2个实数分别表示两个决策变量，分别将的定义域离散化为从离散点-2.048到离散点2.048的Size个实数。遗传算法遗传算法求函数极值（4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即

选个体适应度的倒数作为目标函数

遗传算法遗传算法求函数极值（5）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（6）确定遗传算法的运行参数：群体大小M=500，终止进化代数G=200，交叉概率Pc=0.90，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。

遗传算法遗传算法求函数极值

上述六个步骤构成了用于求函数Rosenbrock极大值的优化计算的实数编码遗传算法。十进制编码求函数Rosenbrock极大值。仿真程序经过200步迭代，最佳样本为即当，时，函数具有极大值，极大值为3880.3。遗传算法遗传算法求函数极值

在RBF网络逼近算法中，网络权值、高斯函数的中心矢量和基宽向量的初值难以确定，如果这些参数选择不当，会造成逼近精度的下降甚至RBF网络的发散。采用遗传算法可实现RBF网络参数的优化。遗传算法的优化原理遗传算法

为获取满意的逼近精度，采用误差绝对值指标作为参数选择的最小目标函数。

式中，为逼近的总步骤，为第步RBF网络的逼近误差。在应用遗传算法时，为了避免参数选取范围过大，可以先按经验选取一组参数，然后再在这组参数的周围利用遗传算法进行设计，从而大大减少初始寻优的盲目性，节约计算量。遗传算法遗传算法的优化原理7.2、基本遗传算法

基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数

编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。函数优化示例求下列一元函数的最大值：

x∈[-1,2]，求解结果精确到6位小数。SGA对于本例的编码

由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222

，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。几个术语基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因初始种群SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。

适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。选择算子

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。轮盘赌选择方法

轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。交叉算子

所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。单点交叉运算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点变异算子

所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。基本位变异算子

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点运行参数（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次7.3遗传算法的实现技术

80年代以后，遗传算法得到了广泛的使用，在实践过程中，人们对遗传算法的实施提出了许多改进。本节分别予以介绍。编码方法

[编码的重要性]

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步骤。

•编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法;

•

编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。[编码原则]

针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，DeJong

曾提出了两条操作性较强的实用编码原则(又称为编码规则)：

•编码原则一(有意义积木块编码原则)：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。

•编码原则二(最小字符集编码原则)：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。

由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：

二进制编码方法浮点数编码方法符号编码方法

二进制编码方法二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。

(1)编码假设某一参数的取值范围是[umax,umin]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：

00000000…00000000＝0umin

00000000…00000001＝1umin+

……11111111…11111111=2l–1umax

二进制编码的编码精度为：=Umax

umin2l

1(2)解码

假设某一个体的编码是：

x：blbl-1bl-2……b2b1

则对应的解码公式为：

例如，对于x

[0,1023]，若用10位长的二进制编码表示该参数的话，则下述符号串：

x：0010101111就可表示一个个体，它所对应的参数值是x＝175。编码精度为

=1。

x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1

(3)二进制编码方法的优点：

Ⅰ.编码、解码操作简单易行；

Ⅱ.

交叉、变异等遗传操作便于实现；

Ⅲ.

符合最小字符集编码原则（使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。）；

Ⅳ.

便于利用模式定理对算法进行理论分析。格雷码编码方法

格雷码编码方法是二进制编码方法的一种变形。

(1)格雷码编码：其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。如图所示。

(2)优点：

•便于提高遗传算法的局部搜索能力；

•交叉、变异等遗传操作便于实现；

•符合最小字符集编码原则；

•便于利用模式定理对算法进行理论分析。4浮点数编码方法

(1)二进制编码的缺点

•二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较短时，可能达不到精度要求；个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索空间急剧扩大。

•二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。

(2)浮点数编码方法个体的每个基因值用某一范围内的一个浮点数来表示；个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。

例如，如果一个优化问题含有5个变量xi(i＝1,2,…,5)，每个变量都有其对应的上下限[Uimin,Uimax]，则：5.806.903.503.805.00x:

表示一个体的基因型，其对应的表现型是：x：[5.80，6.90，3.50，3.80，5.00]T。(3)注意事项：

•

在浮点数编码方法中:

必须保证基因值在给定的区间限制范围内；遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。

•当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。

(4)浮点数编码方法的优点：

•适合于在遗传算法中表示范围较大的数；

•适合于精度要求较高的遗传算法；

•便于较大空间的遗传搜索；

•改善了遗传算法的计算复杂性，提高了运算效率；

•便于遗传算法与经典优化方法的混合使用；

•便于设计针对问题的专门知识的知识型遗传算子；

•便于处理复杂的决策变量约束条件。符号编码方法

(1)编码方法个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集可以是一个字母表，如{A,B,C,D,…}；也可以是一个数宇序号表，如{1,2,3,4,5,…}；还可以是一个代码表，如{Al,A2,A3,A4,A5,…}等等。

例如：对于旅行商问题，假设有n个城市分别记为C1,C2,…,Cn，将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体，如：

X：[C1,C2,…,Cn]

若将各个城市按其代号的下标进行编号，则这个个体也可表示为：

X：[1，2，…，n][旅行商问题(TravelingSalesmanProblem，简称TSP)可描述为；已知n个城市之间的相互距离。现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短?]

(2)符号编码的主要优点：

•符合有意义积木块编码原则。

•便于在遗传算法中利用所求解问题的专门知识。

•便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。7.3.2适应度函数

•

在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。

•与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。

度量个体适应度的函数称为适应度函数。目标函数与适应度函数遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。

最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值F(x)的转换方法：

•对于求最大值的问题，作下述转换：F(X)=f(X)+Cminiff(X)+Cmin>00

iff(X)+Cmin≤0•对于求最小值问题，变换如下：F(X)=Cmax-f(X)

iff(X)

Cmax0

iff(X)

Cmax适应度尺度变换

(1)适应度尺度变换的原因在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来确定的，应用实践表明，仅使用以上两式来计算个体适应度时，有些遗传算法会收敛得很快，也有些遗传算法会收敛得很慢。

•

在遗传算法运行的初期阶段

群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若按照常用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下一代群体中占有很高的比例，在极端情况下或当群体现模较小时，新的群体甚至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产生出新的个体，如下所示：A:101010101010101010101010B:101010101010101010101010单点交叉

这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象（或称早期收敛)，使遗传算法所求到的解停留在某一局部最优点上。

因此，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制数量，以维护群体的多样性。

•

在遗传算法运行的后期阶段

群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。

因此，我们希望在遗传算法运行的后期阶段，算法能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。(2)适应度尺度变换定义在遗传算法运行的不同阶段，有时需要对个体的适应度进行适当的扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。(3)适应度尺度变换方法目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变换和指数尺度变换。

Ⅰ.线性尺度变换。线性尺度变换的公式如下:F’=aF+b

式中F——原适应度；

F’——变换后的新适应度；

a,b——系数。系数a,b直接影响到这个尺度变换的大小，所以对其选取有一定的要求，一般希望它们满足下面两个条件:条件1：尺度变换后全部个体的新适应度的平均值F’avg要等于其原适应度平均值Favg

即：F’avg=Favg

这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数量被遗传到下一代群体中。

条件2：尺度变换后群体中新的最大适应度F’max要等于其原平均适应度Favg的指定

倍数。即：F’max=CFavg

式中，C为最佳个体的期望复制数量，对于群体规模大小为50~100个个体的情况，一般取C=1.2~2。这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中。如下图所示。

最小适应度为负时的处理：在遗传算法执行的后期，个别劣质个体的适应度远远小于群体平均适应度及最大适应度，并且后两者比较接近。这时按上述方法缩放适应度会使低适应度变成负值，如图所示。这将会给后面的处理过程带来不便，必须避免这种情况的发生，解决这个问题的方法是：把原最小适应度Fmin映射为Fmin=0，并且保持原平均适应度Favg与新的平均适应度F’avg相等。

综上所述，参数a,b的计算方法如下：

(1)计算适应度非负判别式：Fmin>C·Favg-FmaxC-1

若不等式满足，则执行(2)，否则执行(3)。

(2)正常情况下的缩放：C-1a

=Fmax-FavgFavgFmax-C·Favgb

=Fmax-FavgFavg(3)负适应度时的缩放：a

=FavgFavg-Fminb

=Favg·FminFavg-FminⅡ.乘幂尺度变换乘幂尺度变换的公式为：

F’=Fk

即新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。

Ⅲ.指数尺度变换

指数尺度变换的公式为：

F’＝exp(-

F)

即新的适应度是原有适应度的某个指数。式中系数

决定了选择的强制性，

越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较大，亦即越增加了选择该个体的强制性。7.3.3约束条件的处理方法实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行能力，选用不同的处理方法。在构造遗传算法时，处理约束条件的常用方法主要有如下三种：

搜索空间限定法罚函数法可行解变换法

(1)搜索空间限定法

[基本思想]

对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。此时的搜索空间与解空间的对应关系如图所示。

[对一些比较简单的约束条件(如a<x＜b之类)]

在个体染色体的编码方法上着手，就能够达到这种搜索空间与解空间之间的对应的要求。

•用这种处理方法能够在遗传算法中设置最小的搜索空间，所以它能够提高遗传算法的搜索效率。

•但需要注意的是：除了在编码方法上想办法之外，也必须保证经过交叉、变异