遗传算法基本原理.pptx

《遗传算法基本原理.pptx》由会员分享，可在线阅读，更多相关《遗传算法基本原理.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 遗传算法简称GAGA（Genetic Genetic AlgorithmsAlgorithms）是19621962年由美国MichiganMichigan大学的HollandHolland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：第1页/共45页（1 1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2 2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生

2、命多样性的根源。（3 3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。第2页/共45页 遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。第3页/共45页遗传算法的基本操作为：（1 1）复制（

3、Reproduction OperatorReproduction Operator）复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生0101之间均匀分布的随机数，若某串的复制概率为40%40%，则当产生的随机数在0.401.00.401.0之间时，该串被复制，否则被淘汰。第4页/共45页（2 2）交叉（Crossover OperatorCrossover Operator）复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交

4、换组合，来产生新的优良品种。交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。第5页/共45页 交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：第6页/共45页（3 3）变异(Mutation Operator)(Mutation Operator)变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码

5、的系统中，它随机地将染色体的某一个基因由1 1变为0 0，或由0 0变为1 1。第7页/共45页 若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。第8页/共45页10.2 10.2 遗传算法的特点（1 1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理；（2 2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点开始最优解

6、的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。第9页/共45页 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。（3 3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。第10页/共45页 遗传算法可应用于目标函数无法求导数或导

7、数不存在的函数的优化问题，以及组合优化问题等。（4 4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。第11页/共45页（5 5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；（6 6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适

8、合大规模复杂问题的优化。第12页/共45页10.3 10.3 遗传算法的应用领域（1 1）函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。第13页/共45页（2 2）组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。第14页/共45页（3 3）生产调度问题 在很多情况下，采用建立数学模型的方法

9、难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。第15页/共45页（4 4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。第16页/共45页（5 5）机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研

10、究和应用。（6 6）图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。第17页/共45页10.4.1 遗传算法的构成要素遗传算法的构成要素（1）染色体编码方法）染色体编码方法 基基本本遗遗传传算算法法使使用用固固定定长长度度的的二二进进制制符符号号来来表表示示群群体体中中的的个个体体，其其等等位位基基因因是是由由二二值值符符号号集集0,1所所组组成成。初初始始个个体体基基因因值值可可用用均均匀匀分分布布的的随机值生成，如随机值生成，如就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体

11、的染色体长度是18。10.4 遗传算法的优化设计第18页/共45页（2）个体适应度评价：基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值J到个体适应度f之间的转换规则。第19页/共45页（3）遗传算子：基本遗传算法使用下述三种遗传算子：选择运算:使用比例选择算子；交叉运算:使用单点交叉算子；变异运算:使用基本位变异算子或均匀变异算子。第20页/共45页（4）基本遗传算法的运行参数 有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20100；

12、G：遗传算法的终止进化代数，一般取为100500；Pc：交叉概率，一般取为0.40.99；Pm：变异概率，一般取为0.00010.1。第21页/共45页 对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；10.4.2 遗传算法的应用步骤第22页/共45页第第三三步步：确确定定表表示示可可行行解解的的染染色色体体编编码码方方法法，即即确确定定出个体的基因型出个体的基因型x x及遗传算法的搜索空间；及遗传算法的搜索空间；第第四四步步：确确定定解

13、解码码方方法法，即即确确定定出出由由个个体体基基因因型型x x到到个个体表现型体表现型X X的对应关系或转换方法；的对应关系或转换方法；第第五五步步：确确定定个个体体适适应应度度的的量量化化评评价价方方法法，即即确确定定出出由目标函数值到个体适应度的转换规则；由目标函数值到个体适应度的转换规则；第第六六步步：设设计计遗遗传传算算子子，即即确确定定选选择择运运算算、交交叉叉运运算算、变异运算等遗传算子的具体操作方法。变异运算等遗传算子的具体操作方法。第第 七七 步步：确确 定定 遗遗 传传 算算 法法 的的 有有 关关 运运 行行 参参 数数，即即M,G,Pc,PmM,G,Pc,Pm等参数。等参

14、数。第23页/共45页以上操作过程可以用图10-1来表示。图10-1 遗传算法流程图 第24页/共45页利利用用遗遗传传算算法法求求Rosenbrock函函数数的的极极大值大值10.5 遗传算法求函数极值第25页/共45页10.5.1 10.5.1 二进制编码遗传算法求函数极大值 求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法 第26页/共45页 用长度为10位的二进制编码串来分别表示两个决策变量x1,x2。10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共

15、有1024个不同的离散点。从离散点-2.048到离散点2.048，分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。第27页/共45页 将x1,x2分别表示的两个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。例如：表示一个个体的基因型，其中前10位表示x1，后10位表示x2。第28页/共45页（4）确定解码方法：解码时需要将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记

16、为y1和y2。依据个体编码方法和对定义域的离散化方法可知，将代码y转换为变量x的解码公式为 例如，对个体第29页/共45页 它由两个代码所组成 上述两个代码经过解码后，可得到两个实际的值（5）确定个体评价方法：由于Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即第30页/共45页选个体适应度的倒数作为目标函数（6）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（7）确定遗传算法的运行参数：群体大小M=80，终 止 进 化 代 数 G=100，交 叉 概 率Pc=0.60，变异概

17、率Pm=0.10。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。第31页/共45页 采用上述方法进行仿真，经过100步迭代，最佳样本为即当 时，Rosenbrock函数具有极大值，极大值为3905.9。仿真程序：chap5_1.m 第32页/共45页 遗传算法的优化过程是目标函数J和适应度函数F的变化过程。由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。第33页/共45页10.5.2 10.5.2 实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：（1

18、 1）确定决策变量和约束条件；（2 2）建立优化模型；（3 3）确定编码方法：用2 2个实数分别表示两个决策变量，分别将的定义域离散化为从离散点-2.0482.048到离散点2.048的SizeSize个实数。第34页/共45页（4 4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即 选个体适应度的倒数作为目标函数 第35页/共45页（5 5）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（6）确定遗传算法的运行参数：群体大小M=500M=500，终止进化代数G=200G=200，交叉概率P Pc c=0.90=0.90，采用自适应变

19、异概率即变异概率与适应度有关，适应度越小，变异概率越大。第36页/共45页 上 述 六 个 步 骤 构 成 了 用 于 求 函 数RosenbrockRosenbrock极大值的优化计算的实数编码遗传算法。十进制编码求函数RosenbrockRosenbrock极大值。仿真程序见chap10_2.mchap10_2.m。仿真程序经过200200步迭代，最佳样本为即当 ，时，函数具有极大值，极大值为3880.33880.3。第37页/共45页10.6 基于遗传算法优化的RBF网络逼近10.6.1 遗传算法优化原理 在7.3节的RBF网络逼近算法中，网络权值、高斯函数的中心矢量和基宽向量的初值难以

20、确定，如果这些参数选择不当，会造成逼近精度的下降甚至RBF网络的发散。采用遗传算法可实现RBF网络参数的优化。第38页/共45页 为获取满意的逼近精度，采用误差绝对值指标作为参数选择的最小目标函数。式中，为逼近的总步骤，为第 步RBF网络的逼近误差。在应用遗传算法时，为了避免参数选取范围过大，可以先按经验选取一组参数，然后再在这组参数的周围利用遗传算法进行设计，从而大大减少初始寻优的盲目性，节约计算量。第39页/共45页10.6.2 仿真实例 使用RBF网络逼近下列对象：在RBF网络中，网络输入信号为2个，即和 ，网络初始权值及高斯函数参数初始值通过遗传算法优化而得。第40页/共45页 遗传算

21、法优化程序为chap10_3a.m，取逼近总步骤为，每一步的逼近误差由chap10_3b.m求得。采用二进制编码方式，用长度为10位的二进制编码串来分别表示向量b b、c c和w w中的每个值。第41页/共45页 遗传算法优化中，取样本个数为Size=30，交叉概率为Pc=0.60，采用自适应变异概率，即适应度越小，变异概率越大，取变异概率为 取用于优化的RBF网络结构为2-3-1，网络权值wj的取值范围为-1,+1，高斯函数基宽向量的取值范围为0.1,3.0，高斯函数中心矢量的取值范围为-3,+3。取则共有12个参数需要优化。第42页/共45页 经过150代遗传算法进化，优化后的结果为：p=2.7732，2.6343，2.2630，1.8680，-0.0616，-0.7126，-0.3959，2.2669，-1.4047，-0.3099，0.7478，-0.3353。则RBF网络高斯基函数参数的初始值及权值的初始值为:第43页/共45页 RBF网络遗传算法优化程序包括三部分，即遗传算法优化程序chap10_3a.m、RBF网络逼近函数程序chap10_3b.m和RBF网络逼近测试程序chap10_3c.m。第44页/共45页感谢您的观看！第45页/共45页