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

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

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

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

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

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

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

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

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

9、码方法，它将问题空间的参 数用字符集10构成染色体位串，符合最小字符集原则，便于用模式定理分析， 但存在映射误差。采用二进制编码，将决策变量编码为二进制，编码串长 m取决于需要的精 度。例如，人的值域为q,bj ,而需要的精度是小数点后5位，这要求将人得值 域至少分为b ai 106份。设凶所需要的字串长为m，则有：2m 1 bi ai 106 2mi(2.1)那么二进制编码的编码精度为bim，将Xi由二进制转为十进制可按下2耳1式计算：xi a decimal(substri ngj(2.2)其中，decimal(substringj表示变量x的子串substringi的十进制值。染色体编N

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

11、。当个体的基因值是由多个基因组 成时，交叉操作必须在两个基因之间的分界字节处进行，而不是在某一基因内 的中间字节分隔处进行。2.3适应度函数适应度函数是用来衡量个体优劣，度量个体适应度的函数。适应度函数值 越大的个体越好，反之，适应值越小的个体越差。在遗传算法中根据适应值对 个体进行选择，以保证适应性能好的个体有更多的机会繁殖后代，使优良特性 得以遗传。一般而言，适应度函数是由目标函数变换而成的。由于在遗传算法 中根据适应度排序的情况来计算选择概率，这就要求适应度函数计算出的函数 值(适应度)不能小于零。因此，在某些情况下，将目标函数转换成最大化问题形 式而且函数值非负的适应度函数是必要的，并

12、且在任何情况下总是希望越大越 好，但是许多实际问题中，目标函数有正有负，所以经常用到从目标函数到适 应度函数的变换。考虑如下一般的数学规划问题：min f(x)s.t. g(x) 0maxhmin h(X)变换方法(1)对于最小化问题，建立适应度函数 F(x)和目标函数f(x)的映射关系:F(x)Cmaxf(x) f(x) Cmax0f(x) Cmax(2.3)式中，Cmax既可以是特定的输入值，也可以选取到目前为止所得到的目标函数f (x)的最大值。(2)对于最大化问题，一般采用下述方法:F(x)f(x)Cminf(X) Cmin f(x) Cmin(2.4)式中，Cmin既可以是特定的输入

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

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

15、件通过适当编码使搜索空间与解空间一一对 应，限定搜索空间能够提高遗传算法的效率。在使用搜索空间限定法时必须保 证交叉、变异之后的解个体在解空间中有对应解。243可行解变换法可行解变换法的基本思想：在由个体基因型到个体表现型的变换中，增加 使其满足约束条件的处理过程，其寻找个体基因型与个体表现型的多对一变换 关系，扩大了搜索空间，使进化过程中所产生的个体总能通过这个变换而转化 成解空间中满足约束条件的一个可行解。可行解变换法对个体的编码方式、交 叉运算、变异运算等无特殊要求，但运行效果下降。2.5遗传算子遗传算法中包含了 3个模拟生物基因遗传操作的遗传算子：选择（复制）、 交叉（重组）和变异（突

16、变）。遗传算法利用遗传算子产生新一代群体来实现群 体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的 基本工具。2.5.1选择操作遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪 些个体遗传到下一代群体中的一种遗传运算。遗传算法使用选择（复制）算子 来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体 中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。选择操 作建立在对个体适应度进行评价的基础之上。选择操作的主要目的是为了避免 基因缺失、提高全局收敛性和计算效率。常用的选择方法有转轮法、排序选择法、两两竞争法1）轮盘赌法。简单的选择

17、方法为轮盘赌法：通常以第i个个体入选种群的概率以及群体规 模的上限来确定其生存与淘汰，这种方法称为轮盘赌法。轮盘赌法是一种正比 选择策略，能够根据与适应函数值成正比的概率选出新的种群。轮盘赌法由以 下五步构成：1. 计算各染色体Vk适应值F（vQ ；2. 计算种群中所有染色体的适应值的和;FallF(Vk)k 1(2.6)3. 计算各染色体Vk的选择概率Pk ；Pkeva,k i,2,K,nFall4.计算各染色体Vk的累计概率qk ；kqkPj ,k 1,2,K , nj i(2.7)(2.8)5.在0,1区间内产生一个均匀分布的伪随机数 r，若r q，则选择第一个 染色体V1 ;否则，选择

18、第k个染色体，使得qk 1 r qk成立。2）排序选择法。排序选择法的主要思想是：对群体中的所有个体按其适应度大小进行排序， 基于这个排序来分配各个个体被选中的概率。排序选择方法的具体操作过程是：1. 对群体中的所有个体按其适应度大小进行降序排序。2. 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次 序分配给各个个体。3. 以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于 这些概率值用轮盘赌法来产生下一代群体。3）两两竞争法。锦标赛选择法的基本做法是：在选择时先随机的在种群中选择k个个体进行 锦标赛式的比较，从中选出适应值最好的个体进入下一代，复用这种方法进行 直

19、到下一代个体数为种群规模时为止。这种方法也使得适应值好的个体在下一 代具有较大的“生存”机会，同时它只能使用适应值的相对值作为选择的标准, 而与适应值的数值大小不成直接比例，所以，它能较好的避免超级个体的影响, 一定程度的避免过早收敛现象和停滞现象。2.5.2交叉操作在遗传算法中，交叉操作是起核心作用的遗传操作，它是生成新个体的主 要方式。交叉操作的基本思想是通过对两个个体之间进行某部分基因的互换来实 现产生新个体的目的。常用交叉算子有：单点交叉算子、两点交叉算子和多点交 叉算子、均匀交叉算子和算术交叉算子等等。1）单点交叉算子交叉过程分两个步骤：首先对配对库中的个体进行随机配对；其次，在配

20、对个体中随机设定交叉位置，配对个体彼此交换部分信息。个体川10011111 一 1001000新个体才个体Foonlooo 一 0011111新个体F交叉点图2-1单点交叉示意2）两点交叉算子具体操作是随机设定两个交叉点，互换两个父代在这两点间的基因串，分 别生成两个新个体。3）多点交叉算子多点交叉的思想源于控制个体特定行为的染色体表示信息的部分无须包含 于邻近的子串中，多点交叉的破坏性可以促进解空间的搜索，而不是促进过早 的收敛。4）均匀交叉算子均匀交叉式指通过设定屏蔽字来决定新个体的基因继承两个个体中那个个 体的对应基因，当屏蔽字中的位为 0时，新个体A继承旧个体A中对应的基因, 当屏蔽字

21、位为1时，新个体A继承旧个体B中对应的基因，由此可生成一个完 整的新个体A，同理可生成新个体B。旧个体捏旧个体月001111111100屏蔽字010101新个体N 新个体那011110101101图2-2均与交叉示意图2.5.3变异操作变异操作是指将个体染色体编码串中的某些基因座的基因值用该基因座的 其他等位基因来替代，从而形成一个新的个体。变异运算是产生新个体的辅助 方法，它和选择、交叉算子结合在一起，保证了遗传算法的有效性，使遗传算 法具有局部的随机搜索能力，提高遗传算法的搜索效率；同时使遗传算法保持 种群的多样性，以防止出现早熟收敛。在变异操作中，为了保证个体变异后不 会与其父体产生太大

22、的差异，保证种群发展的稳定性，变异率不能取太大，如 果变异率大于0.5,遗传算法就变为随机搜索，遗传算法的一些重要的数学特性 和搜索能力也就不存在了。变异算子的设计包括确定变异点的位置和进行基因 值替换。变异操作的方法有基本位变异、均匀变异、边界变异、非均匀变异等。1）基本位变异基本位变异操作是指对个体编码串中以变异概率Pm随机指定的某一位或某几位基因作变异运算，所以其发挥的作用比较慢，作用的效果也不明显。基本 位变异算子的具体执行过程是：1. 对个体的每一个基因座，依变异概率 Pm指定其为变异点。2. 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来 代替，从而产生出一个新个体

23、。2）均匀变异均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小 的概率来替换个体编码串中各个基因座上的原有基因值。均匀变异的具体操作 过程是：1. 依次指定个体编码串中的每个基因座为变异点。2. 对每一个变异点，以变异概率Pm从对应基因的取值范围内取一随机数来替代原有基因值。假设有一个个体为 vk v1v2K vkK vm，若vk为变异点，其取值范围为 Vk,min,Vk,max，在该点对个体Vr进行均匀变异操作后，可得到一个新的个体： VkV1V2K VkK Vm，其中变异点的新基因值是IVk Vk ,minr (Vk ,max Vk,min )(2.9)式中，r为0,1范围

24、内符合均匀概率分布的一个随机数。均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地 移动，从而可以增加群体的多样性。2.5.4倒位操作所谓倒位操作是指颠倒个体编码串中随机指定的二个基因座之间的基因排 列顺序，从而形成一个新的染色体。倒位操作的具体过程是：1. 在个体编码串中随机指定二个基因座作为倒位点；2. 以倒位概率颠倒这二个倒位点之间的基因排列顺序。2.6搜索终止条件遗传算法的终止条件有以下两个，满足任何一个条件搜索就结束。1)遗传操作中连续多次前后两代群体中最优个体的适应度相差在某个任意 小的正数 所确定的范围内，即满足：FnewFoid(2.10)

25、式中，Fnew为新产生的群体中最优个体的适应度；Fold为前代群体中最优个体的适应度。2)达到遗传操作的最大进化代数t o3具体数学规划问题的遗传算法实现利用遗传算法求解下列数学规划问题：minf (Xi,X2)s.tgl(Xi,X2) hi(xix)0 x-i,x22X1X1232X22x2X2210,洛2(3.1)3.1初始化针对上述冋题利用 MATLAB编写遗传算法程序求解，程序的主函数是GA.m。首先，确定程序初始化中所需要的参数和对应的值。其中求解精度是指决 策变量的求解精度，由于题目中没有给出，所以这是我自己设定的参数。程序 中涉及到得参数名称、符号和相应的值如下表所示。表3-1遗

26、传算法初始化参数参数名称符号值最大进化代数tmax100种群规模n100交叉概率Pc0.8变异概率pm0.1求解精度dec104变量上限值xmax10变量下限值xmi n03.2染色体编码本程序米用二进制编码，将决策变量编码为二进制，其串长取决于问题要求的求解精度，但本题并没有给出精度要求，只是限定了X1为整数，不妨假设求解精度为10 4，两个变量均采用二进制编码，x,为整数这个限制条件在可在计 算出小数值后作四舍五入取整处理，因此可按照假设的求解精度将决策变量的 值域分成105份，则有：x Xminx2mi 1 (xmax xmi n) 105 2mi(3.2)由于所有变量的求解精度一样，那

27、么，决策变量的串长m1 20、m2 20，于是染色体的总长m m1 m2 40，求解二进制编码串长的程序时len.m。那么, 二进制编码精度为9.5368 10(3.3)100T2021根据二进制编码的串长以及种群规模可生成初始种群，为计算种群中的各个个体的适应值，应先将基因型转换成表现型，其程序为cod in g.m。首先，将二进制值转换为十进制值，其公式为m1(bib2K bmi)2bi 2i 1 x(3.4)那么，对应的变量值为(3.5)3.3计算适应值首先确定适应度函数。根据目标函数和约束条件可选择适应度函数的变换 方式。由于目标函数f（x） 0，为了避免出现适应值大于1的情况，于是根

28、据目 标函数的特点在设计适应度函数时，在分母上加上2,分子上剩以4,如式（3.1所示；又根据优化问题的约束条件，利用约束条件处理方法中的罚函数法设计 了相应的罚函数c，那么适应度函数为(3.6)10000其中，c max0, gi(Xi,X2)5max0,| 入(捲，x?) 4|，按照上述方法计算种群中各个个体的适应值，如果适应值趋近于1,那么对 应的个体即为最佳个体，计算适应值的程序是fitn ess.m。3.4遗传算子3.4.1选择操作本程序选择轮盘赌法来实现选择操作。根据之前计算的各个个体的适应值， 利用式（2.6）计算种群中所有个体的适应值的和Fall;然后按照如式（2.7）、（2.8

29、）计算每个个体的选择概率p和累计概率q。旋转轮盘100次（种群规模），每次生 成一个0到1的随机数r，用这个随机数与种群中的个体的累积概率q作比较，如果这个随机数落在了这个概率区间，那么就保留该个体，这就完全模拟了轮 盘赌的思想，若个体的选择概率大，那么它被选到遗传到下一代的概率也就大 一些。选择操作的程序是selec.m。3.4.2交叉操作对经过选择操作产生的群体作交叉操作。本程序采用均匀交叉的方式，首 先打乱种群中所有个体的原有排列顺序，这样体现了随机抽取的概念，然后把 种群分成两部分new_genA和new_genB；分别从这两个部分选择一个个体配成 对进行均匀交叉，其程序为cross.

30、m。343变异操作对经过交叉操作产生的群体作变异操作。本程序采用基本位变异方法实现变异操作，依据变异概率对新种群中的个体实施基本位变异， 具体程序为mut.m在最初编写的程序中还包含倒位操作，具体程序是inverse.m，原理类似于 基本位变异，只是具体操作上有差异。在调试时，我比较了有倒位操作和没有 倒位操作作用于程序对计算结果的影响，在有倒位操作时并没有改善算法在搜 索到最优解方面的性能，于是我在最终的程序中取掉了这一操作。3.5搜索终止判断本程序采用了达到最大进化代数时停止搜索的方法，由于本问题比较简单, 所以采用此法是可行的。但是，对于复杂的问题，也许要求更加有效的判断手 段，所以这是需要改进的地方。3.6运行调试调试阶段解决了两个问题：第一，最佳个体的适应值很快就达到一个稳定 的值而不再变化；第二，适应度函数的设计存在缺陷。针对第一个问题，考虑 到交叉操作是产生新个体的主要操作，所以将交叉概率从0.8调到0.9,增加对种群的交叉操作，产生更多的新个体，保持了种群的多样性，这就使得最优个 体是