计量经济学遗传算法ppt课件

1、 遗传算法简称遗传算法简称GAGAGenetic AlgorithmsGenetic Algorithms是是19621962年由美国年由美国MichiganMichigan大学的大学的HollandHolland教授提教授提出的模拟自然界遗传机制和生物进化论而成的出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。一种并行随机搜索最优化方法。 遗传算法是以达尔文的自然选择学说为根底遗传算法是以达尔文的自然选择学说为根底开展起来的。自然选择学说包括以下三个方面：开展起来的。自然选择学说包括以下三个方面：1 1遗传：这是生物的普遍特征，亲代把生物信息交遗传：这是生物的普遍特征，亲

2、代把生物信息交给子代，子代总是和亲代具有一样或类似的性状。生给子代，子代总是和亲代具有一样或类似的性状。生物有了这个特征，物种才干稳定存在。物有了这个特征，物种才干稳定存在。2 2变异：亲代和子代之间以及子代的不同个体之间变异：亲代和子代之间以及子代的不同个体之间的差别，称为变异。变异是随机发生的，变异的选择的差别，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。和积累是生命多样性的根源。3 3生存斗争和适者生存：具有顺应性变异的个体被生存斗争和适者生存：具有顺应性变异的个体被保管下来，不具有顺应性变异的个体被淘汰，经过一保管下来，不具有顺应性变异的个体被淘汰，经过一代代的生存

3、环境的选择作用，性状逐渐逐渐与祖先有代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演化为新的物种。所不同，演化为新的物种。 遗传算法将遗传算法将“优胜劣汰，适者生存的生物优胜劣汰，适者生存的生物进化原理引入优化参数构成的编码串联群体中，进化原理引入优化参数构成的编码串联群体中，按所选择的顺应度函数并经过遗传中的复制、按所选择的顺应度函数并经过遗传中的复制、交叉及变异对个体进展挑选，使适顺应度高的交叉及变异对个体进展挑选，使适顺应度高的个体被保管下来，组成新的群体，新的群体既个体被保管下来，组成新的群体，新的群体既承继了上一代的信息，又优于上一代。这样周承继了上一代的信息，又优于上一代。

4、这样周而复始，群体中个体顺应度不断提高，直到满而复始，群体中个体顺应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行足一定的条件。遗传算法的算法简单，可并行处置，并能到全局最优解。处置，并能到全局最优解。遗传算法的根本操作为：遗传算法的根本操作为：1复制复制Reproduction Operator 复制是从一个旧种群中选择生命力强的个体位复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高顺应度的位串更有串产生新种群的过程。具有高顺应度的位串更有能够在下一代中产生一个或多个子孙。能够在下一代中产生一个或多个子孙。 复制操作可以经过随机方法来实现。首先产生复制操作可以经

5、过随机方法来实现。首先产生01之间均匀分布的随机数，假设某串的复制概之间均匀分布的随机数，假设某串的复制概率为率为40%，那么当产生的随机数在，那么当产生的随机数在0.401.0之间之间时，该串被复制，否那么被淘汰。时，该串被复制，否那么被淘汰。2交叉交叉Crossover Operator 复制操作能从旧种群中选择出优秀者，但不复制操作能从旧种群中选择出优秀者，但不能发明新的染色体。而交叉模拟了生物进化过能发明新的染色体。而交叉模拟了生物进化过程中的繁衍景象，经过两个染色体的交换组合，程中的繁衍景象，经过两个染色体的交换组合，来产生新的优良种类。来产生新的优良种类。 交叉的过程为：在匹配池中

6、任选两个染色体，交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体交换点右边的部分，即可得到两个新的染色体数字串。色体数字串。 交叉表达了自然界中信息交换的思想。交叉交叉表达了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最根本的方法，交叉和周期交叉。一点交叉是最根本的方法，运用较广。它是指染色体切断点有一处，例：运用较广。它是指染色体切断点有一处，例：0101 0110011110 10110

7、0 :A1110 0010100101 001010 :B3变异变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中变异运算用来模拟生物在自然的遗传环境中由于各种偶尔要素引起的基因突变，它以很小由于各种偶尔要素引起的基因突变，它以很小的概率随机地改动遗传基因表示染色体的符的概率随机地改动遗传基因表示染色体的符号串的某一位的值。在染色体以二进制编码号串的某一位的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基来由的系统中，它随机地将染色体的某一个基来由1变为变为0，或由，或由0变为变为1。 假设只需选择和交叉，而没有变异，那么假设只需选择和交叉，而没有变

8、异，那么无法在初始基因组合以外的空间进展搜索，无法在初始基因组合以外的空间进展搜索，使进化过程在早期就堕入部分解而进入终止使进化过程在早期就堕入部分解而进入终止过程，从而影响解的质量。为了在尽能够大过程，从而影响解的质量。为了在尽能够大的空间中获得质量较高的优化解，必需采用的空间中获得质量较高的优化解，必需采用变异操作。变异操作。二、二、 遗传算法的特点遗传算法的特点 1遗传算法是对参数的编码进展操作，而非遗传算法是对参数的编码进展操作，而非对参数本身，这就是使得我们在优化计算过程对参数本身，这就是使得我们在优化计算过程中可以自创生物学中染色体和基因等概念，模中可以自创生物学中染色体和基因等概

9、念，模拟自然界中生物的遗传和进化等机理；拟自然界中生物的遗传和进化等机理；2遗传算法同时运用多个搜索点的搜索信息。遗传算法同时运用多个搜索点的搜索信息。传统的优化方法往往是从解空间的单个初始点传统的优化方法往往是从解空间的单个初始点开场最优解的迭代搜索过程，单个搜索点所提开场最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜供的信息不多，搜索效率不高，有时甚至使搜索过程局限于部分最优解而停滞不前。索过程局限于部分最优解而停滞不前。 遗传算法从由很多个体组成的一个初始群体遗传算法从由很多个体组成的一个初始群体开场最优解的搜索过程，而不是从一个单一的开场最优解的搜索过程，

10、而不是从一个单一的个体开场搜索，这是遗传算法所特有的一种隐个体开场搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。含并行性，因此遗传算法的搜索效率较高。3遗传算法直接以目的函数作为搜索信息。遗传算法直接以目的函数作为搜索信息。传统的优化算法不仅需求利用目的函数值，而传统的优化算法不仅需求利用目的函数值，而且需求目的函数的导数值等辅助信息才干确定且需求目的函数的导数值等辅助信息才干确定搜索方向。而遗传算法仅运用由目的函数值变搜索方向。而遗传算法仅运用由目的函数值变换来的顺应度函数值，就可以确定进一步的搜换来的顺应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目的函数的

11、导数值等索方向和搜索范围，无需目的函数的导数值等其他一些辅助信息。其他一些辅助信息。 遗传算法可运用于目的函数无法求导数或遗传算法可运用于目的函数无法求导数或导数不存在的函数的优化问题，以及组合优化导数不存在的函数的优化问题，以及组合优化问题等。问题等。4遗传算法运用概率搜索技术。遗传算法遗传算法运用概率搜索技术。遗传算法的选择、交叉、变异等运算都是以一种概率的的选择、交叉、变异等运算都是以一种概率的方式来进展的，因此遗传算法的搜索过程具有方式来进展的，因此遗传算法的搜索过程具有很好的灵敏性。随着进化过程的进展，遗传算很好的灵敏性。随着进化过程的进展，遗传算法新的群领会更多地产生出许多新的优良

12、的个法新的群领会更多地产生出许多新的优良的个体。体。5遗传算法在解空间进展高效启发式搜索，遗传算法在解空间进展高效启发式搜索，而非盲目地穷举或完全随机搜索；而非盲目地穷举或完全随机搜索；6遗传算法对于待寻优的函数根本无限制，遗传算法对于待寻优的函数根本无限制，它既不要求函数延续，也不要求函数可微，既它既不要求函数延续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因此运用映射矩阵甚至是神经网络的隐函数，因此运用范围较广；范围较广；7遗传算法具有并行计算的特点，因此可经遗传算法具有并行计算的特点，因此可经过大规

13、模并行计算来提高计算速度，适宜大规过大规模并行计算来提高计算速度，适宜大规模复杂问题的优化。模复杂问题的优化。 三、三、 遗传算法的运用领域遗传算法的运用领域1 1函数优化。函数优化。 函数优化是遗传算法的经典运用领域，也是函数优化是遗传算法的经典运用领域，也是遗传算法进展性能评价的常用算例。尤其是对遗传算法进展性能评价的常用算例。尤其是对非线性、多模型、多目的的函数优化问题，采非线性、多模型、多目的的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以用其他优化方法较难求解，而遗传算法却可以得到较好的结果。得到较好的结果。2 2组合优化。组合优化。 随着问题的增大，组合优化问题的搜索空间

14、随着问题的增大，组合优化问题的搜索空间也急剧扩展，采用传统的优化方法很难得到最也急剧扩展，采用传统的优化方法很难得到最优解。遗传算法是寻求这种称心解的最正确工优解。遗传算法是寻求这种称心解的最正确工具。例如，遗传算法曾经在求解游览商问题、具。例如，遗传算法曾经在求解游览商问题、背包问题、装箱问题、图形划分问题等方面得背包问题、装箱问题、图形划分问题等方面得到胜利的运用。到胜利的运用。3 3消费调度问题消费调度问题 在很多情况下，采用建立数学模型的方法难在很多情况下，采用建立数学模型的方法难以对消费调度问题进展准确求解。在现实消费以对消费调度问题进展准确求解。在现实消费中多采用一些阅历进展调度。

15、遗传算法是处理中多采用一些阅历进展调度。遗传算法是处理复杂调度问题的有效工具，在单件消费车间调复杂调度问题的有效工具，在单件消费车间调度、流水线消费车间调度、消费规划、义务分度、流水线消费车间调度、消费规划、义务分配等方面遗传算法都得到了有效的运用。配等方面遗传算法都得到了有效的运用。4 4自动控制。自动控制。 在自动控制领域中有很多与优化相关的问题在自动控制领域中有很多与优化相关的问题需求求解，遗传算法曾经在其中得到了初步的需求求解，遗传算法曾经在其中得到了初步的运用。例如，利用遗传算法进展控制器参数的运用。例如，利用遗传算法进展控制器参数的优化、基于遗传算法的模糊控制规那么的学习、优化、基

16、于遗传算法的模糊控制规那么的学习、基于遗传算法的参数辨识、基于遗传算法的神基于遗传算法的参数辨识、基于遗传算法的神经网络构造的优化和权值学习等。经网络构造的优化和权值学习等。5 5机器人机器人 例如，遗传算法曾经在挪动机器人途径规划、例如，遗传算法曾经在挪动机器人途径规划、关节机器人运动轨迹规划、机器人构造优化和行关节机器人运动轨迹规划、机器人构造优化和行为协调等方面得到研讨和运用。为协调等方面得到研讨和运用。6 6图像处置图像处置 遗传算法可用于图像处置过程中的扫描、特遗传算法可用于图像处置过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法征提取、图像分割等的优化计算。目前遗传算法曾

17、经在方式识别、图像恢复、图像边缘特征提取曾经在方式识别、图像恢复、图像边缘特征提取等方面得到了运用。等方面得到了运用。就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是18。001011011001110010 x以上操作过程可以用图以上操作过程可以用图1 1来表示。来表示。 图图1 1 遗传算法流程图遗传算法流程图 )2 , 1(048. 2048. 2)1 ()(100),(212221212ixxxxxxfi1101110001 0000110111:x)2 , 1(048. 21023096. 4iyxii1101110001 0000110111:x476.

18、 1,828. 121xx881,5521yy),()(21xxfxF)(1)(xFxJ0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 BestS2.0480 2.0480 21,xx5.2 5.2 实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：1 1确定决策变量和约束条件；确定决策变量和约束条件；2 2建立优化模型；建立优化模型；3 3确定编码方法：用确定编码方法：用2 2个实数分别表示两个个实数分别表示两个决策变量，分别将的定义域离散化为从离散点决策变量，分别将的定义域离散化为从离散点-2

19、.048-2.048到离散点到离散点2.0482.048的的SizeSize个实数。个实数。4确定个体评价方法：确定个体评价方法： 个体的顺应度直接取为对应的目的函数值，个体的顺应度直接取为对应的目的函数值，即即 选个体顺应度的倒数作为目的函数选个体顺应度的倒数作为目的函数 ),()(21xxfxF)(1)(xFxJ5设计遗传算子：选择运算运用比例选择设计遗传算子：选择运算运用比例选择算子，交叉运算运用单点交叉算子，变异运算算子，交叉运算运用单点交叉算子，变异运算运用根本位变异算子。运用根本位变异算子。6确定遗传算法的运转参数：群体大小确定遗传算法的运转参数：群体大小M=500，终止进化代数，

20、终止进化代数G=200，交叉概率，交叉概率Pc=0.90，采用自顺应变异概率，采用自顺应变异概率即变异概率与顺应度有关，顺应度越小，变异即变异概率与顺应度有关，顺应度越小，变异概率越大。概率越大。 0.01/SizeSize:1:1-0.10mP 上 述 六 个 步 骤 构 成 了 用 于 求 函 数上 述 六 个 步 骤 构 成 了 用 于 求 函 数RosenbrockRosenbrock极大值的优化计算的实数编码遗传极大值的优化计算的实数编码遗传算法。算法。 十进制编码求函数十进制编码求函数RosenbrockRosenbrock极大值。仿极大值。仿真程序见真程序见chap10_2.mc

21、hap10_2.m。 仿真程序经过仿真程序经过200200步迭代，最正确样本为步迭代，最正确样本为即当即当 ， 时，函数具时，函数具有极大值，极大值为有极大值，极大值为3880.33880.3。2.044- -2.0438 BestS2.0438 1x2.044 2x6.1 遗传算法优化原理遗传算法优化原理 在在7.3节的节的RBF网络逼近算法中，网络权网络逼近算法中，网络权值、高斯函数的中心矢量和基宽向量的初值值、高斯函数的中心矢量和基宽向量的初值难以确定，假设这些参数选择不当，会呵斥难以确定，假设这些参数选择不当，会呵斥逼近精度的下降甚至逼近精度的下降甚至RBF网络的发散。采用网络的发散。

22、采用遗传算法可实现遗传算法可实现RBF网络参数的优化。网络参数的优化。 为获取称心的逼近精度，采用误差绝对值目为获取称心的逼近精度，采用误差绝对值目的作为参数选择的最小目的函数。的作为参数选择的最小目的函数。 式中，式中， 为逼近的总步骤，为逼近的总步骤， 为第为第 步步RBF网络的网络的逼近误差。逼近误差。 在运用遗传算法时，为了防止参数选取范围在运用遗传算法时，为了防止参数选取范围过大，可以先按阅历选取一组参数，然后再在过大，可以先按阅历选取一组参数，然后再在这组参数的周围利用遗传算法进展设计，从而这组参数的周围利用遗传算法进展设计，从而大大减少初始寻优的盲目性，节约计算量。大大减少初始寻

23、优的盲目性，节约计算量。 NiieJ1100N iei6.2 仿真实例仿真实例 运用运用RBF网络逼近以下对象：网络逼近以下对象：23) 1(1) 1()()(kykykuky 在在RBF网络中，网络输入信号为网络中，网络输入信号为2个，即个，即和和 ，网络初始权值及高斯函数参数初始，网络初始权值及高斯函数参数初始值经过遗传算法优化而得。值经过遗传算法优化而得。)(ku)(ky 遗传算法优化程序为遗传算法优化程序为chap10_3a.mchap10_3a.m，取逼，取逼近总步骤为，每一步的逼近误差由近总步骤为，每一步的逼近误差由chap10_3b.mchap10_3b.m求得。采用二进制编码方式，用求得。采用二进制编码方式，用长度为长度为1010位的二进制编码串来分别表示向量位的二进制编码串