遗传算法的原理及MATLAB程序实现

《遗传算法的原理及MATLAB程序实现》由会员分享，可在线阅读，更多相关《遗传算法的原理及MATLAB程序实现（18页珍藏版）》请在金锄头文库上搜索。

1、1 遗传算法的原理1.1 遗传算法的基本思想遗传算法（genetic algorithms, GA）是一种基于自然选择和基因遗传学原理， 借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、 突变的 遗传机制的全局自适应概率搜索算法。遗传算法是从一组随机产生的初始解 （种群）开始，这个种群由经过基因编 码的一定数量的个体组成， 每个个体实际上是染色体带有特征的实体。 染色体作 为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个 体的外部表现。 因此， 从一开始就需要实现从表现型到基因型的映射， 即编码工 作。初始种群产生后， 按照优胜劣汰的原理， 逐代演化产生出

2、越来越好的近似解。 在每一代， 根据问题域中个体的适应度大小选择个体， 并借助于自然遗传学的遗 传算子进行组合交叉和变异， 产生出代表新的解集的种群。 这个过程将导致种群 像自然进化一样， 后代种群比前代更加适应环境， 末代种群中的最优个体经过解 码，可以作为问题近似最优解。计算开始时， 将实际问题的变量进行编码形成染色体， 随机产生一定数目的 个体，即种群， 并计算每个个体的适应度值， 然后通过终止条件判断该初始解是 否是最优解， 若是则停止计算输出结果， 若不是则通过遗传算子操作产生新的一 代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。 这一过程循环执行，直到满足优

3、化准则，最终产生问题的最优解。图 1-1 给出了 遗传算法的基本过程。1.2 遗传算法的特点1.2.1 遗传算法的优点 遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点：1. 遗传算法以控制变量的编码作为运算对象。 传统的优化算法往往直接利用 控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的 值，而是以控制变量的特定形式的编码为运算对象。 这种对控制变量的编码处理 方式，可以模仿自然界中生物的遗传和进化等机理， 也使得我们可以方便地处理 各种变量和应用遗传操作算子。2. 遗传算法具有内在的本质并行性。 它的并行性表现在两个方面， 一是遗传图1-1简单遗传算法

4、的基本过程算法的外在并行性，最简单的方式是让多台计算机各自进行独立种群的演化计 算，最后选择最优个体。可以说，遗传算法适合在目前所有的并行机或分布式系 统上进行并行计算处理。二是遗传算法的内在并行性，由于遗传算法采用种群的 方式组织搜索，因而可同时搜索解空间内的多个区域， 并相互交流信息。这样就 使得搜索效率更高，也避免了使搜索过程陷于局部最优解3. 遗传算法直接以目标函数值作为搜索信息。 在简单遗传算法中， 基本上不 用搜索空间的知识和其它辅助信息， 而仅用目标函数即适应度函数来评估个体解 的优劣，且适应度函数不受连续可微的约束，对该函数和控制变量的约束极少。 对适应度函数唯一的要求就是对于

5、输入能够计算出可比较的输出。4. 遗传算法是采用概率的变迁规则来指导它的搜索方向， 其搜索过程朝着搜 索空间的更优化的解区域移动， 它的方向性使得它的效率远远高于一般的随机算 法。遗传算法在解空间内进行充分的搜索， 但不是盲目的穷举或试探， 因为选择 操作以适应度为依据，因此它的搜索性能往往优于其它优化算法。5. 原理简单，操作方便，占用内存少，适用于计算机进行大规模计算，尤其 适合处理传统搜索方法难以解决的大规模、非线性组合复杂优化问题。6. 由于遗传基因串码的不连续性， 所以遗传算法处理非连续混合整数规划时 有其独特的优越性，而且使得遗传算法对某些病态结构问题具有很好的处理能 力。7. 遗

6、传算法同其他算法有较好的兼容性。 如可以用其他的算法求初始解； 在 每一代种群，可以用其他的方法求解下一代新种群。1.2.2 遗传算法的缺点但是，遗传算法也存在一些缺点。1. 遗传算法是一类随机搜索型算法，而非确定性迭代过程描述，这种方式 必然会较低的计算效率。2. 对简单遗传算法的数值试验表明，算法经常出现过早收敛现象。3. 遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变 化也使得好的优良个体的性态被过早破坏，降低了各代的平均适应值。2. 遗传算法的实现2.1 初始参数种群规模 n ：种群数目影响遗传算法的有效性。种群数目太小，不能提供足 够的采样点；种群规模太大，会增加计算

7、量，使收敛时间增长。一般种群数目在 20到 160之间比较合适。交叉概率 pc ： pc 控制着交换操作的频率， pc 太大，会使高适应值的结构很 快被破坏掉，Pc太小会使搜索停滞不前，一般 Pc取0.51.0。变异概率Pm : Pm是增大种群多样性的第二个因素，Pm太小，不会产生新的基因块，Pm太大，会使遗传算法变成随机搜索，一般Pm取0.0010.1。进化代数t ：表示遗传算法运行结束的一个条件。一般的取值范围1001000b 当个体编码较长时，进化代数要取小一些，否则会影响算法的运行效率。 进化代 数的选取，还可以采用某种判定准则，准则成立时，即停止。2.2染色体编码利用遗传算法进行问题

8、求解时，必须在目标问题实际表示与染色体位串结构 之间建立一个联系。对于给定的优化问题，由种群个体的表现型集合所组成的空 间称为问题空间，由种群基因型个体所组成的空间称为编码空间。由问题空间向编码空间的映射称作编码，而由编码空间向冋题空间的映射成为解码。按照遗传算法的模式定理，De Jong进一步提出了较为客观明确的编码评估 准则，称之为编码原理。具体可以概括为两条规则：(1) 有意义积木块编码规则：编码应当易于生成与所求问题相关的且具有低 阶、短定义长度模式的编码方案。(2) 最小字符集编码规则：编码应使用能使问题得到自然表示或描述的具有 最小编码字符集的编码方案。常用的编码方式有两种：二进制

9、编码和浮点数(实数)编码。二进制编码方法是遗传算法中最常用的一种编码方法，它将问题空间的参数用字符集10，构成染色体位串，符合最小字符集原则，便于用模式定理分析， 但存在映射误差。采用二进制编码，将决策变量编码为二进制，编码串长 m取决于需要的精 度。例如，Xi的值域为b，b ,而需要的精度是小数点后5位，这要求将Xi得值 域至少分为(b -q产106份。设Xi所需要的字串长为m,则有：2m_1 (bj -1 0c m2(2.1)那么二进制编码的编码精度为6 =匕打a，将x由二进制转为十进制可按下2m -1式计算：N 二色 decimal(substringj 、(2.2)其中，decimal

10、(substring)表示变量x的子串substringi的十进制值。染色体编码N的总串长m = x mi i =1若没有规定计算精度，那么可采用定长二进制编码，即 m可以自己确定。二进制编码方式的编码、解码简单易行，使得遗传算法的交叉、变异等操作 实现方便。但是，当连续函数离散化时，它存在映射误差。再者，当优化问题所 求的精度越高，如果必须保证解的精度，则使得个体的二进制编码串很长，从而 导致搜索空间急剧扩大，计算量也会增加，计算时间也相应的延长。浮点数(实数)编码方法能够解决二进制编码的这些缺点。该方法中个体的 每个基因都要用参数所给定区间范围内的某一浮点数来表示，而个体的编码长度则等于其

11、决策变量的总数。遗传算法中交叉、变异等操作所产生的新个体的基因 值也必须保证在参数指定区间范围内。 当个体的基因值是由多个基因组成时， 交 叉操作必须在两个基因之间的分界字节处进行， 而不是在某一基因内的中间字节 分隔处进行。2.3适应度函数适应度函数是用来衡量个体优劣，度量个体适应度的函数。适应度函数值越 大的个体越好，反之，适应值越小的个体越差。在遗传算法中根据适应值对个体 进行选择，以保证适应性能好的个体有更多的机会繁殖后代， 使优良特性得以遗 传。一般而言，适应度函数是由目标函数变换而成的。 由于在遗传算法中根据适 应度排序的情况来计算选择概率，这就要求适应度函数计算出的函数值(适应度

12、)不能小于零。因此，在某些情况下，将目标函数转换成最大化问题形式而且函数 值非负的适应度函数是必要的，并且在任何情况下总是希望越大越好， 但是许多 实际问题中，目标函数有正有负，所以经常用到从目标函数到适应度函数的变换。考虑如下一般的数学规划问题：min f (x) s.t. g(x)=0h min变换方法对于最小化问题，建立适应度函数F (x)和目标函数f (x)的映射关系:00max 一 f(X)(2.3)f ( x 厂:Cmaxf (x) - Cmax式中，Cmax既可以是特定的输入值，也可以选取到目前为止所得到的目标函数f( x)的最大值。(2)对于最大化问题，一般采用下述方法:0(2

13、.4)F(x)= f( %f( x) CminI 0f(X) Cmin式中，Cmin既可以是特定的输入值，也可以选取到目前为止所得到的目标函数f( X )的最小值。变换方法二:(1)对于最小化问题，建立适应度函数 f (X)和目标函数f(x)的映射关系:F(x)二11 c f(x)(2.5)(2)对于最大化问题，一般采用下述方法:F(x) =11 c - f (x)(2.6)式中，c为目标函数界限的保守估计值。2.4约束条件的处理在遗传算法中必须对约束条件进行处理，但目前尚无处理各种约束条件的一 般方法，根据具体问题可选择下列三种方法，其罚函数法、搜索空间限定法和可 行解变换法。2.4.1罚函

14、数法罚函数的基本思想是对在解空间中无对应可行解的个体计划其适应度时，处以一个罚函数，从而降低该个体的适应度，使该个体被选遗传到下一代群体中的 概率减小。可以用下式对个体的适应度进行调整：(2.7)F(xF(X ) lF(x)P(x)其中，F(x)为原适应度函数，F(x)为调整后的新的适应度函数，P(x)为罚函数，U为约束条件组成的集合。如何确定合理的罚函数是这种处理方法难点之所在，在考虑罚函数时，既要度量解对约束条件不满足的程度，由要考虑计算效率。2.4.2搜索空间限定法搜索空间限定法的基本思想是对遗传算法的搜索空间的大小加以限制，使得 搜索空间中表示一个个体的点与解空间中的表示一个可行解的点

15、有一一对应的 关系。对一些比较简单的约束条件通过适当编码使搜索空间与解空间一一对应， 限定搜索空间能够提高遗传算法的效率。在使用搜索空间限定法时必须保证交 叉、变异之后的解个体在解空间中有对应解。2.4.3 可行解变换法可行解变换法的基本思想： 在由个体基因型到个体表现型的变换中， 增加使 其满足约束条件的处理过程，其寻找个体基因型与个体表现型的多对一变换关 系，扩大了搜索空间， 使进化过程中所产生的个体总能通过这个变换而转化成解 空间中满足约束条件的一个可行解。 可行解变换法对个体的编码方式、 交叉运算、 变异运算等无特殊要求，但运行效果下降。2.5 遗传算子遗传算法中包含了 3 个模拟生物基因遗传操作的遗传算子：选择（复制） 、 交叉（重组）和变异（突变） 。遗传算法利用遗传算子产生新一代群体来实现群 体进化，算子的设计是遗传策略的主要组成部分， 也是调整和控制进化过程的基 本工具。2.5.1 选择操作 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。 遗传算法使用选择 （复制） 算子来 对群体中的个体进行优胜劣汰操作： 适应度较高的个体被遗传到下一代群体中的 概率较大