简明遗传算法课件

1、遗传算法及其应用Genetic Algorithm & its Aplication 遗传算法的概念 遗传算法及其应用 遗传算法与传统优化方法的比较 遗传算法的应用 群体智能优化方法简介 1 遗传算法的概念1.1 遗传算法的起源自然进化 化石记录表明：复杂结构生命是在相对短的时间内进化而来的！进化理论的一般特性进化过程是发生在染色体上，而不是在它们所编码的生物体上；自然选择把染色体以及由它们所译成的结构的表现联系起来，那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会；繁殖过程是进化发生的那一刻。变异可以使生物体子代染色体不同于它们父代染色体。通过结合两个父代染色体中的物质，重组

2、（杂交、交叉）过程可以在子代中产生有很大差异的染色体；生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好地适应它们的环境。 大多数生物体是通过自然选择和有性繁殖进行演化的。自然选择决定群体中那些个体能够存活并繁殖；有性繁殖保证了后代基因中的混合和重组。自然选择原则达尔文进化论 适者生存，优胜劣汰！1 遗传算法的概念遗传算法的起源 是一族通过模拟自然进化过程搜索最优解的方法。1940年代，生物模拟已成为计算科学的组成部分；1960年代，美国Michigan大学John Holland在从事自适应系统研究时，注意到学习也可以通过一个群体的许多

3、代进化适应发生。1960年代中期，Holland开发了一种编程技术遗传算法，其基本思想是利用类似于自然选择的方式来设计计算机程序1975年Holland出版了专著Adaptation in Natural and Artificial Systems, 遗传算法逐渐为人所知。染色体编码，生成初始种群遗传代数：NEra0计算每个个体的适应度收敛否 ?ny 进行选择、杂交pc、变异pm和保留等遗传操作，生成新一代种群NEraNEra1解码输出结果1 遗传算法的概念1.2 遗传算法描述基本遗传算法框图主要步骤确定表示方案 染色体串映射搜索空间确定适应值度量确定控制算法的参数和变量 种群规模Mc、最大

4、进化代数MEra、pc、pm(pcpm)、保留个体数等4.确定指定结果的方法和停止运行准则 选择一个个体选择遗传算子pmpc执行变异操作获得子代一个新个体ii1选择两个个体执行杂交操作获得子代两个新个体ii1iMc？yn保留若干最优个体基因干预人机交互1 遗传算法的概念染色体编码 yf(x), x(x-, x+)x为0,1：二进制编码x为整数：二进制/十进制编码x为实数：二进制/十进制/实数编码 编码原则：完备性。问题空间中所有点（侯选解）都能用遗传算法空间中的点（染色体）表现；健全性。遗传算法空间中的染色体都能对应问题空间中的所有侯选解；非冗余性。染色体和侯选解一一对应。染色体编码，生成初始

5、种群遗传代数：NEra0计算每个个体的适应度收敛否 ?ny 进行选择、杂交pc、变异pm和保留等遗传操作，生成新一代种群NEraNEra1解码输出结果1 遗传算法的概念染色体编码，生成初始种群遗传代数：NEra0计算每个个体的适应度收敛否 ?ny 进行选择、杂交pc、变异pm和保留等遗传操作，生成新一代种群NEraNEra1解码输出结果生成初始种群 根据染色体编码，随机确定染色体中的各段基因值；也可根据研究问题空间特点指定部分基因段。适应度函数的确定作用：评价种群中个体的优劣；基于适应度函数值的选择。求极小值问题：求极大值问题：选择一个个体选择遗传算子pmpc执行变异操作获得子代一个新个体ii

6、1选择两个个体执行杂交操作获得子代两个新个体ii1iMc？yn保留若干最优个体基因干预人机交互0.6910.6360.1441.00.0个体301000个体211000个体101101个体410011赌轮选择1 遗传算法的概念遗传操作选择(复制) 选择算子根据是每个个体对应的优化问题目标函数转换成的适应度函数值的大小进行复制，体现了自然界中适者生存法则，是遗传算法的关键。适应度函数值比例法（赌轮法） 个体被选取的概率适应值的比例变换法 期望值法（个体不多时） 排位次法（个体适应度相近时）个体编码适应度函数值选择率累积选择率1011011690.1440.1442110005760.4920.6

7、36301000640.0550.6914100113610.3091.0001 遗传算法的概念遗传操作杂交(交叉) GA的根本所在。通过模拟生物界中的有性繁殖，能把注意力集中到搜索空间中期望值最高的部分。方法：一点杂交、二点杂交和多点杂交遗传操作变异 模拟生物进化过程中偶然的基因突变现象，能保持群体的多样性，避免陷于局部最优，并可以在当前解的附近找到更好的解。选择一个个体选择遗传算子pmpc执行变异操作获得子代一个新个体ii1选择两个个体执行杂交操作获得子代两个新个体ii1iMc？yn保留若干最优个体基因干预人机交互杂交前 A1=11000 A2=10011杂交后 A1=11011 A2=1

8、0000变异前 A1=11001变异后 A1=11011选择一个个体选择遗传算子pmpc执行变异操作获得子代一个新个体ii1选择两个个体执行杂交操作获得子代两个新个体ii1iMc？yn保留若干最优个体基因干预人机交互1 遗传算法的概念遗传操作保留 使得遗传算法能以概率1收敛到全局最优解。 对种群进行简单的选择(复制)、杂交和变异操作是遗传算法的精髓！停止运行准则 最大困难所在！ 1）达到最大进化代数 2）连续多代没有改进时染色体编码，生成初始种群遗传代数：NEra0计算每个个体的适应度收敛否 ?ny 进行选择、杂交pc、变异pm和保留等遗传操作 生成新一代种群NEraNEra1解码输出结果1

9、遗传算法的概念1.3 遗传算法的基本定理模式定理 在考虑选择、交叉和变异作用下，一个特定模式H在下一代中期望产生的数目可近似表示为其中，(H)为模式定义长度，指模式H中第一个常数位置与最后一个常数位置之间的距离；O(H)为模式的阶，指出现在模式H中常数位置的个数。 模式定义长度短、低阶且适应值在群体平均适应值以上的模式，在遗传算法迭代过程中将按指数增长率被采样。1 遗传算法的概念1.3 遗传算法的基本定理隐含并行性 串长为L、规模为N的二进制群体中，包含有2L到N2L个模式。模式数是按二项式分布的，由于杂交算子会破坏那些定义长度相对较长的模式，因此，按有效方式被处理的模式数目与群体规模的立方成

10、正比，即NsO(N3)。 此即：每一代中除了仅对N个染色体处理外，遗传算法实际上处理大约O(N3)个模式，从而每代只执行与群体规模成比例的计算量，就可以同时收到并行地对大约O(N3)个模式进行有效处理的目的，并且无须额外的存储。 Holland称之为遗传算法的隐含并行性2 遗传算法与传统优化方法的比较2.1 传统数学优化方法线性规划 (LP_Linear Programming) 在满足一组线性约束条件下，寻求多变量线性目标函数的极大/小值。 求解方法：单纯形法、线性混合整数规划法（分枝定界法、割平面法、隐枚举法）和内点法。非线性规划 (NP_Nonlinear Programming) 目标

11、函数或约束条件：一个或多个非线性函数。 求解方法：微分法、拉格朗日乘子法、牛顿法、梯度法、变尺度法以及基于变分法的优化方法等。 要求函数连续、甚至可导2 遗传算法与传统优化方法的比较2.1 传统数学优化方法动态规划 (DP_Dynamic Programming) 运筹学的重要分支，由美国数学家贝尔曼（R. Bellman）等人在1950年代提出，是研究多阶段决策过程最优化的一种有效方法。 动态规划将整个优化问题转化为一个多阶段优化序列来处理，通过合理选择各个阶段决策的集合，使整个过程总体达到最优。 要求所求解的问题具有明显的阶段性，它对目标函数的形态没有特殊的要求，理论上可以真正获得全局最优

12、解。缺点是容易出现“维数灾”和“后效”问题。2 遗传算法与传统优化方法的比较2.2 遗传算法的特点不是直接作用于参变量集上，而是利用参变量的某种编码，通用性强；采用群体搜索策略，同时对多个解进行评估。因而具有全局优化和隐含并行性；不用搜索空间的知识或其它辅助信息，仅用适应度函数值来评价个体。适应度函数无连续可导限制，定义域任意，特别适用于求解非连续变量结构优化问题；采用概率转移规则指导搜索方向(概率选择、概率交叉、概率变异)，而非确定性规则，鲁棒性强；逐代进化，易于通过基因干预提高收敛速度；可同时获得最优解和若干次优解，便于决策分析。3 遗传算法的应用3.1 遗传算法的应用领域自适应系统自适应

13、下棋程序模式识别函数优化管道优化医学图像变换囚犯困境游戏分类系统喷气发动机涡轮设计(10010387)导航、躲避和跟踪主要应用领域搜索优化机器学习电力系统中： 规划设计、建设施工和运行控制 各环节3 遗传算法的应用3.2 GA在电力系统电源规划中的应用3.2.1 何谓是电源规划？核心：4W问题，即：WhenWhereWhatHow 典型的组合排序问题特点高维数：m个待优选电站，m!组合方案m38，m!38!5.231044 (约1.661037年!)非线性：目标函数、约束条件是非线性的整数性：变量是整数型的不确定性：基础数据（负荷、燃料、设备价格、水电风电出力、贴现率等）不确定3 遗传算法的应

14、用电源规划为什么要进行电源规划？按英国1997年装机水平：1.18kW13.6亿16亿kW3 遗传算法的应用电源规划3.2.2 GA电源规划模型目标函数约束条件待建电站建设施工约束系统可靠性约束系统/分区电力电量平衡约束电站运行约束3 遗传算法的应用电源规划3.2.2 GA电源规划模型总体框图待选电源数据 染色体编码，生成初始种群：MC遗传代数：NEra0 投资决策子模型：优化各个体的投资决策 运行优化子模型：优化各个体的运行成本 计算各个体的适应度 收敛否 ?ny 进行选择、杂交、变异和保留等遗传操作，生成新一代种群NEraNEra1 解码，输出电源规划优化结果现有系统数据负荷预测数据各种约

15、束数据染色体编码，生成初始种群遗传代数：NEra0计算每个个体的适应度收敛否 ?ny 进行选择、杂交pc、变异pm和保留等遗传操作，生成新一代种群NEraNEra1解码输出结果3 遗传算法的应用电源规划3.2.3 整数向量染色体编码与初始种群的生成染色体编码（电源规划方案） 整数向量m 电源规划方案可以编码为长度为N的整数向量m(m1, m2, , mN)。 其中，mk表示向量m的第k个元（顺序第k位投建的待优选电站序号）。电源规划初始方案集（初始种群MC）生成动态模板整数向量染色体编码法k随机数j 1, Nk1动态模板mb选中电站序号染色体编码mi1412345644*2412356545*

16、3212362452*4313664526*5113145261*61334526133 遗传算法的应用电源规划3.2.4 适应度函数值的计算种群中方案i的适应度函数值AFi3.2.5 遗传操作选择算子 适应度函数值比例法（赌轮法）3 遗传算法的应用电源规划3.2.5 遗传操作杂交算子1) 次序杂交（OCOrdering Crossover）例：mF1( 9, 2,13, 4, 6,12, 3, 8, 1,10,15, 5,14, 7,11)mF2( 4, 6, 9,11, 5, 2,14, 1, 7, 3,13,15,10,12, 8)杂交位置 ( 0, 0, *, *, 0, 0, 0,

17、*, 0, *, 0, 0, 0, 0, 0)mS1( 9, 2,13, 4, 6,12,11, 8, 1,10,15, 5,14, 7, 3)mS2(13, 6, 9,11, 5, 2,14, 1, 7, 3, 4,15, 8,12,10)2) 位置杂交（LCLocating Crossover）例：mF1( 9, 2,13, 4, 6,12, 3, 8, 1,10,15, 5,14, 7,11)mF2( 4, 6, 9,11, 5, 2,14, 1, 7, 3,13,15,10,12, 8)杂交位置 ( 0, 0, *, *, 0, 0, 0, *, 0, *, 0, 0, 0, 0, 0

18、)mS1( 2,13, 9,11, 4, 6,12, 1, 8, 3,10,15, 5,14, 7)mS2( 6, 9,13, 4,11, 5, 2, 8,14,10, 1, 7, 3,15,12)3 遗传算法的应用电源规划3.2.5 遗传操作杂交算子3) 映射杂交（MCMapping Crossover）例：mF1( 9, 2,13, 4, 6,12, 3, 8, 1,10,15, 5,14, 7,11)mF2( 4, 6, 9,11, 5, 2,14, 1, 7, 3,13,15,10,12, 8)杂交位置 ( 0, 0, 0, 0, *, *, *, *, 0, 0, 0, 0, 0,

19、0, 0)mS1( 9,12,13, 4, 5, 2,14, 1, 8,10,15, 6, 3, 7,11)mS2( 4, 5, 9,11, 6,12, 3, 8, 7,14,13,15,10, 2, 1)4) 循环杂交（CCCycling Crossover）例：mF1( 9, 2,13, 4, 6,12, 3, 8, 1,10, 11, 5,14, 7,15)mF2( 4, 6, 9,11, 5, 2,14, 1, 7, 3, 13,15,10,12, 8)mS1( 4, 2, 9,11, 6,12, 3, 8, 1,10, 13, 5,14, 7,15)mS2( 9, 6,13, 4,

20、5, 2,14, 1, 7, 3, 11,15,10,12, 8)3 遗传算法的应用电源规划3.2.5 遗传操作变异算子作用：在群体中提供和保持多样性以使其它的算子可以继续起作用；本身也可以使遗传算法具有局部随机搜索能力。1）位置变异：随机选择染色体向量上的两个元，然后将第二个元放在第一个元之前。2）次序变异：随机选择染色体向量上的两个元，然后交换其位置。3）打乱变异：随机选择染色体向量上的两个元一段，然后打乱在这个段内元的次序。 GA电源规划模型中直接采用位置变异算子3 遗传算法的应用电源规划3.2.6 算例及其结果原始数据3 遗传算法的应用电源规划3.2.6 算例及其结果原始数据3 遗传算

21、法的应用电源规划3.2.6 算例及其结果优化结果优化结果表明：能够获得全局最优解。 计算的基本参数：种群规模 ：MC =30最大遗传进化代数： NEra.max2000保留算子：Nopt3杂交率： pc0.8变异率： pm0.053 遗传算法的应用电源规划3.2.6 算例及其结果结果分析3 遗传算法的应用电源规划收敛特性局部放大进化代数目标函数值/百万元(a) 最优解的收敛曲线遗传算法的全局优化性和隐含并行性使得遗传算法具有非常高收敛速度，能够快速定位于电源规划问题的全局最优解的邻域附近。遗传算法的随机搜索过程使得遗传算法还具有局部搜索能力弱的特点混合遗传算法3 遗传算法的应用电源规划收敛特性

22、进化代数目标函数值/百万元(b) 中值解的收敛曲线4 群体智能优化方法简介专家系统(ES_Expert System) 在启发式推理中引入专家知识，将专家知识与计算机计算结合，根据某种规则进行决策和推理。是一种很好的启发式推理工具，其效率很大程度上决定于知识库的建立。模糊集理论(FS_Fuzzy Set Theory) 用隶属度函数将输入模糊化；输入和输出关系用模糊规则描述；输出的模糊变量用隶属度函数反模糊化，变为现实世界的决策。模拟退火算法(SA_Simulated Annealing) 模拟热力学中液体凝结与结晶/金属熔液冷却与退火过程的随机搜索技术，其执行过程是一系列的“产生新解判断接受

23、/舍弃”迭代过程。理论上是一个全局最优算法。4 群体智能优化方法简介禁忌搜索算法(TS_Tabu Search) 一种扩展邻域的启发式搜索技术。通过记录（Tabu表）搜索历史，从中获得知识并用来指导后续搜索方向以避开局部最优解。原理：产生一个初始解，采用一组“移动”操作从当前解的邻域中随机产生一系列试验解，选择最好的解作为当前解；重复迭代，直到满足一定的终止准则。 目前还不能从数学上证明一定能收敛于全局最优解，但大量的应用研究表明它能有效地获得非常好的次优解；它还具有局部搜索能力强的特点。神经网络(ANN_Artificial Neural Networks) 模拟生物神经网络构造的，由一些简

24、单的节点及其大规模并行连接构造的网络，它致力于按照生物神经系统同样的方式处理真实世界的客观事物，已被证明通过适当的训练，可用于模式识别、预测、分类和组合优化问题。4 群体智能优化方法简介免疫算法(IA_Immune Algorithm) 免疫系统是生物体的一个高度进化、复杂的功能系统，它可以自适应地识别和排除侵入机体的抗原性异物，并具有学习、记忆、自适应调节能力，维护体内环境的稳定。免疫系统的这一特有的进化特性被用于各类组合优化问题求解。思维进化算法(MEA_Mind Evolution Algorithm) 基于人类思维进化过程的优化算法。把整个群体划分为若干个子群体，采用趋同（Similartaxis）和异化（Dissmilat