遗传算法的原理及MATLAB程序实现1 遗传算法的原理1.1 遗传算法的基本思想遗传算法(genetic algorithms，GA)是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。

遗传算法是从一组随机产生的初始解(种群)开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。

染色体作为遗传物质的主要载体，其内部表现(即基因型)是某种基因组合，它决定了个体的外部表现。

因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。

初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。

在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。

这一过程循环执行，直到满足优化准则，最终产生问题的最优解。

图1-1给出了遗传算法的基本过程。

1.2 遗传算法的特点1.2.1 遗传算法的优点遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点:1. 遗传算法以控制变量的编码作为运算对象。

传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。

这种对控制变量的编码处理方式，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地处理各种变量和应用遗传操作算子。

2. 遗传算法具有内在的本质并行性。

它的并行性表现在两个方面，一是遗传开始初始化，输入原始参数及给定参数，gen=1染色体编码，产生初始群体计算种群中每个个体的适应值终止条件的判断,Ngen=gen+1选择交叉Y变异新种群输出结果结束图1-1 简单遗传算法的基本过程算法的外在并行性，最简单的方式是让多台计算机各自进行独立种群的演化计算，最后选择最优个体。

可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行计算处理。

二是遗传算法的内在并行性，由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。

这样就使得搜索效率更高，也避免了使搜索过程陷于局部最优解。

3. 遗传算法直接以目标函数值作为搜索信息。

在简单遗传算法中，基本上不用搜索空间的知识和其它辅助信息，而仅用目标函数即适应度函数来评估个体解的优劣，且适应度函数不受连续可微的约束，对该函数和控制变量的约束极少。

对适应度函数唯一的要求就是对于输入能够计算出可比较的输出。

4. 遗传算法是采用概率的变迁规则来指导它的搜索方向，其搜索过程朝着搜索空间的更优化的解区域移动，它的方向性使得它的效率远远高于一般的随机算法。

遗传算法在解空间内进行充分的搜索，但不是盲目的穷举或试探，因为选择操作以适应度为依据，因此它的搜索性能往往优于其它优化算法。

5. 原理简单，操作方便，占用内存少，适用于计算机进行大规模计算，尤其适合处理传统搜索方法难以解决的大规模、非线性组合复杂优化问题。

6. 由于遗传基因串码的不连续性，所以遗传算法处理非连续混合整数规划时有其独特的优越性，而且使得遗传算法对某些病态结构问题具有很好的处理能力。

7. 遗传算法同其他算法有较好的兼容性。

如可以用其他的算法求初始解;在每一代种群，可以用其他的方法求解下一代新种群。

1.2.2 遗传算法的缺点但是，遗传算法也存在一些缺点。

1. 遗传算法是一类随机搜索型算法，而非确定性迭代过程描述，这种方式必然会较低的计算效率。

2. 对简单遗传算法的数值试验表明，算法经常出现过早收敛现象。

3. 遗传和变异的完全随机性虽然保证了进化的搜索功能，但是这种随机变化也使得好的优良个体的性态被过早破坏，降低了各代的平均适应值。

2. 遗传算法的实现2.1 初始参数种群规模:种群数目影响遗传算法的有效性。

种群数目太小，不能提供足n 够的采样点;种群规模太大，会增加计算量，使收敛时间增长。

一般种群数目在20到160之间比较合适。

ppp交叉概率:控制着交换操作的频率，太大，会使高适应值的结构很ccc pp快被破坏掉，太小会使搜索停滞不前，一般取0.5~1.0。

cc变异概率p:p是增大种群多样性的第二个因素，p太小，不会产生新mmm的基因块，p太大，会使遗传算法变成随机搜索，一般p取0.001~0.1。

mm 进化代数:表示遗传算法运行结束的一个条件。

一般的取值范围100~1000。

t 当个体编码较长时，进化代数要取小一些，否则会影响算法的运行效率。

进化代数的选取，还可以采用某种判定准则，准则成立时，即停止。

2.2 染色体编码利用遗传算法进行问题求解时，必须在目标问题实际表示与染色体位串结构之间建立一个联系。

对于给定的优化问题，由种群个体的表现型集合所组成的空间称为问题空间，由种群基因型个体所组成的空间称为编码空间。

由问题空间向编码空间的映射称作编码，而由编码空间向问题空间的映射成为解码。

按照遗传算法的模式定理，De Jong进一步提出了较为客观明确的编码评估准则，称之为编码原理。

具体可以概括为两条规则:(1)有意义积木块编码规则:编码应当易于生成与所求问题相关的且具有低阶、短定义长度模式的编码方案。

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

常用的编码方式有两种:二进制编码和浮点数(实数)编码。

二进制编码方法是遗传算法中最常用的一种编码方法，它将问题空间的参数10，用字符集构成染色体位串，符合最小字符集原则，便于用模式定理分析，,,但存在映射误差。

m取决于需要的精采用二进制编码，将决策变量编码为二进制，编码串长i ab,xx度。

例如，的值域为，而需要的精度是小数点后5位，这要求将得值,,iiii6ba,，10xm域至少分为份。

设所需要的字串长为，则有: ，，iiiimm,16ii2102,,，,ba (2.1) ，，iiba,iix那么二进制编码的编码精度为，将由二进制转为十进制可按下,,imi21, 式计算:xadecimalsubstring,，，(), (2.2) iiidecimalsubstring()xsubstring其中，表示变量的子串的十进制值。

染色体编码iiiNmm,的总串长。

,ii,1若没有规定计算精度，那么可采用定长二进制编码，即m可以自己确定。

i 二进制编码方式的编码、解码简单易行，使得遗传算法的交叉、变异等操作实现方便。

但是，当连续函数离散化时，它存在映射误差。

再者，当优化问题所求的精度越高，如果必须保证解的精度，则使得个体的二进制编码串很长，从而导致搜索空间急剧扩大，计算量也会增加，计算时间也相应的延长。

浮点数(实数)编码方法能够解决二进制编码的这些缺点。

该方法中个体的每个基因都要用参数所给定区间范围内的某一浮点数来表示，而个体的编码长度则等于其决策变量的总数。

遗传算法中交叉、变异等操作所产生的新个体的基因值也必须保证在参数指定区间范围内。

当个体的基因值是由多个基因组成时，交叉操作必须在两个基因之间的分界字节处进行，而不是在某一基因内的中间字节分隔处进行。

2.3 适应度函数适应度函数是用来衡量个体优劣，度量个体适应度的函数。

适应度函数值越大的个体越好，反之，适应值越小的个体越差。

在遗传算法中根据适应值对个体进行选择，以保证适应性能好的个体有更多的机会繁殖后代，使优良特性得以遗传。

一般而言，适应度函数是由目标函数变换而成的。

由于在遗传算法中根据适应度排序的情况来计算选择概率，这就要求适应度函数计算出的函数值(适应度)不能小于零。

因此，在某些情况下，将目标函数转换成最大化问题形式而且函数值非负的适应度函数是必要的，并且在任何情况下总是希望越大越好，但是许多实际问题中，目标函数有正有负，所以经常用到从目标函数到适应度函数的变换。

考虑如下一般的数学规划问题:min ()fxs.t. ()0gx,()hh,,hxminmax变换方法一:F()xf()x(1)对于最小化问题，建立适应度函数和目标函数的映射关系:CffC,,()()xx,maxmaxF()x, (2.3) ,0()fCx,max,C式中，既可以是特定的输入值，也可以选取到目前为止所得到的目标函数maxf()x的最大值。

(2)对于最大化问题，一般采用下述方法:fCfC()()xx,,,minmin (2.4) F()x,,0()fCx,min,C式中，既可以是特定的输入值，也可以选取到目前为止所得到的目标函数min的最小值。

f()x变换方法二:fx()(1)对于最小化问题，建立适应度函数f()x和目标函数的映射关系:1 (2.5) Fccfx()0,()0x,,，,1()，，cfx(2)对于最大化问题，一般采用下述方法:1 (2.6) Fxccfx()0,()0,,,,1()，,cfx式中，为目标函数界限的保守估计值。

c2.4 约束条件的处理在遗传算法中必须对约束条件进行处理，但目前尚无处理各种约束条件的一般方法，根据具体问题可选择下列三种方法，其罚函数法、搜索空间限定法和可行解变换法。

2.4.1 罚函数法罚函数的基本思想是对在解空间中无对应可行解的个体计划其适应度时，处以一个罚函数，从而降低该个体的适应度，使该个体被选遗传到下一代群体中的概率减小。

可以用下式对个体的适应度进行调整:F()Uxx,,' (2.7) F()x,,FP()()Uxxx,,,'F()xP()x其中，为原适应度函数，为调整后的新的适应度函数，为罚函F()x 数，U为约束条件组成的集合。

如何确定合理的罚函数是这种处理方法难点之所在，在考虑罚函数时，既要度量解对约束条件不满足的程度，由要考虑计算效率。

2.4.2 搜索空间限定法搜索空间限定法的基本思想是对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中的表示一个可行解的点有一一对应的关系。

对一些比较简单的约束条件通过适当编码使搜索空间与解空间一一对应，限定搜索空间能够提高遗传算法的效率。

在使用搜索空间限定法时必须保证交叉、变异之后的解个体在解空间中有对应解。

2.4.3 可行解变换法可行解变换法的基本思想:在由个体基因型到个体表现型的变换中，增加使其满足约束条件的处理过程，其寻找个体基因型与个体表现型的多对一变换关系，扩大了搜索空间，使进化过程中所产生的个体总能通过这个变换而转化成解空间中满足约束条件的一个可行解。