(精品)简明遗传算法课件.ppt

W W z zHUST_CEEE遗传算法及其应用遗传算法及其应用Genetic Algorithm&its Aplication吴耀武吴耀武华中科技大学电气与电子工程学院华中科技大学电气与电子工程学院W W z zHUST_CEEE 遗传算法的概念遗传算法的概念遗传算法的概念遗传算法的概念 遗传算法及其应用遗传算法及其应用 遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 群体智能优化方法简介群体智能优化方法简介群体智能优化方法简介群体智能优化方法简介 W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念1.1 1.1 遗传算法的起源遗传算法的起源自然进化自然进化自然进化自然进化 化石记录表明：复杂结构生命是在相对短的时间内进化而来的！化石记录表明：复杂结构生命是在相对短的时间内进化而来的！化石记录表明：复杂结构生命是在相对短的时间内进化而来的！化石记录表明：复杂结构生命是在相对短的时间内进化而来的！进化理论的一般特性进化理论的一般特性进化理论的一般特性进化理论的一般特性进化过程进化过程进化过程进化过程是发生在染色体上，而不是在它们所编码的生物体上；是发生在染色体上，而不是在它们所编码的生物体上；是发生在染色体上，而不是在它们所编码的生物体上；是发生在染色体上，而不是在它们所编码的生物体上；自自自自然然然然选选选选择择择择把把把把染染染染色色色色体体体体以以以以及及及及由由由由它它它它们们们们所所所所译译译译成成成成的的的的结结结结构构构构的的的的表表表表现现现现联联联联系系系系起起起起来来来来，那那那那些些些些适适适适应应应应性性性性好好好好的的的的个个个个体体体体的的的的染染染染色色色色体体体体经经经经常常常常比比比比差差差差的的的的个个个个体体体体的的的的染染染染色色色色体体体体有有有有更更更更多多多多的的的的繁繁繁繁殖机会；殖机会；殖机会；殖机会；繁繁繁繁殖殖殖殖过过过过程程程程是是是是进进进进化化化化发发发发生生生生的的的的那那那那一一一一刻刻刻刻。变变变变异异异异可可可可以以以以使使使使生生生生物物物物体体体体子子子子代代代代染染染染色色色色体体体体不不不不同同同同于于于于它它它它们们们们父父父父代代代代染染染染色色色色体体体体。通通通通过过过过结结结结合合合合两两两两个个个个父父父父代代代代染染染染色色色色体体体体中中中中的的的的物物物物质质质质，重重重重组组组组（杂交、交叉杂交、交叉杂交、交叉杂交、交叉）过程可以在子代中产生有很大差异的染色体；）过程可以在子代中产生有很大差异的染色体；）过程可以在子代中产生有很大差异的染色体；）过程可以在子代中产生有很大差异的染色体；生生生生物物物物进进进进化化化化没没没没有有有有记记记记忆忆忆忆。有有有有关关关关产产产产生生生生个个个个体体体体的的的的信信信信息息息息包包包包含含含含在在在在个个个个体体体体所所所所携携携携带带带带的的的的染染染染色色色色体体体体的的的的集集集集合合合合以以以以及及及及染染染染色色色色体体体体编编编编码码码码的的的的结结结结构构构构之之之之中中中中，这这这这些些些些个个个个体体体体会会会会很很很很好好好好地地地地适适适适应应应应它们的环境。它们的环境。它们的环境。它们的环境。大多数生物体是通过大多数生物体是通过大多数生物体是通过大多数生物体是通过自然选择自然选择自然选择自然选择和和和和有性繁殖有性繁殖有性繁殖有性繁殖进行演进行演进行演进行演化的。化的。化的。化的。自然选择自然选择自然选择自然选择决定群体中那些个体能够存活并繁殖；决定群体中那些个体能够存活并繁殖；决定群体中那些个体能够存活并繁殖；决定群体中那些个体能够存活并繁殖；有性繁殖有性繁殖有性繁殖有性繁殖保证了后代基因中的混合和重组。保证了后代基因中的混合和重组。保证了后代基因中的混合和重组。保证了后代基因中的混合和重组。自然选择原则自然选择原则达尔文进化论达尔文进化论达尔文进化论达尔文进化论 适者生存，优胜劣汰！适者生存，优胜劣汰！W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念遗传算法的起源遗传算法的起源遗传算法的起源遗传算法的起源 是一族通过模拟自然进化过程搜索最优解的方法。是一族通过模拟自然进化过程搜索最优解的方法。是一族通过模拟自然进化过程搜索最优解的方法。是一族通过模拟自然进化过程搜索最优解的方法。1940194019401940年代，生物模拟已成为计算科学的组成部分；年代，生物模拟已成为计算科学的组成部分；年代，生物模拟已成为计算科学的组成部分；年代，生物模拟已成为计算科学的组成部分；1960196019601960年年年年代代代代，美美美美国国国国MichiganMichiganMichiganMichigan大大大大学学学学John John John John HollandHollandHollandHolland在在在在从从从从事事事事自自自自适适适适应应应应系系系系统统统统研研研研究究究究时时时时，注注注注意意意意到到到到学学学学习习习习也也也也可可可可以以以以通通通通过过过过一一一一个个个个群群群群体体体体的的的的许许许许多多多多代进化适应发生。代进化适应发生。代进化适应发生。代进化适应发生。1960196019601960年年年年代代代代中中中中期期期期，HollandHollandHollandHolland开开开开发发发发了了了了一一一一种种种种编编编编程程程程技技技技术术术术遗遗遗遗传传传传算算算算法法法法，其其其其基基基基本本本本思思思思想想想想是是是是利利利利用用用用类类类类似似似似于于于于自自自自然然然然选选选选择择择择的的的的方方方方式式式式来来来来设设设设计计计计计算机程序计算机程序计算机程序计算机程序1975197519751975年年年年HollandHollandHollandHolland出出出出版版版版了了了了专专专专著著著著Adaptation Adaptation Adaptation Adaptation in in in in Natural Natural Natural Natural and and and and Artificial Systems,Artificial Systems,Artificial Systems,Artificial Systems,遗传算法逐渐为人所知。遗传算法逐渐为人所知。遗传算法逐渐为人所知。遗传算法逐渐为人所知。W W z zHUST_CEEE染色体染色体编码编码，生成初始种群，生成初始种群遗传代数：遗传代数：NEra0计算每个个体的计算每个个体的适应度适应度收敛收敛否否?ny 进进行行选选择择、杂杂交交pc、变变异异pm和和保保留留等等遗遗传传操操作作，生生成成新一代种群新一代种群NEraNEra1解码解码输出结果输出结果1 遗传算法的概念遗传算法的概念1.2 1.2 遗传算法描述遗传算法描述基本遗传算法框图基本遗传算法框图基本遗传算法框图基本遗传算法框图主要步骤主要步骤主要步骤主要步骤1.1.1.1.确定表示方案确定表示方案确定表示方案确定表示方案 染色体串染色体串染色体串染色体串映射映射映射映射搜索空间搜索空间搜索空间搜索空间2.2.2.2.确定适应值度量确定适应值度量确定适应值度量确定适应值度量3.3.3.3.确定控制算法的参数和变量确定控制算法的参数和变量确定控制算法的参数和变量确定控制算法的参数和变量 种种种种 群群群群 规规规规 模模模模 MMc c、最最最最 大大大大 进进进进 化化化化 代代代代 数数数数MMEraEra、pc、pm(pcpm)、保保保保留留留留个个个个体体体体数等数等数等数等4.4.4.4.确定指定结果的方法和停止确定指定结果的方法和停止确定指定结果的方法和停止确定指定结果的方法和停止运行准则运行准则运行准则运行准则 选择选择一个个体一个个体选择遗传算子选择遗传算子pmpc执行执行变异变异操作获得操作获得子代一个新个体子代一个新个体ii1 1选择选择两个个体两个个体执行执行杂交杂交操作获得操作获得子代两个新个体子代两个新个体ii1 1iMc？yn保留保留若干若干最优最优个体个体基因干预基因干预人机人机交互交互W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念染色体编码染色体编码染色体编码染色体编码 y y y yf(xf(xf(xf(x),),),),x(xx(xx(xx(x-,x+)-,x+)-,x+)-,x+)x x x x为为为为0,10,10,10,1：二进制编码：二进制编码：二进制编码：二进制编码x x x x为整数：二进制为整数：二进制为整数：二进制为整数：二进制/十进制编码十进制编码十进制编码十进制编码x x x x为实数：二进制为实数：二进制为实数：二进制为实数：二进制/十进制十进制十进制十进制/实数编码实数编码实数编码实数编码 编码原则：编码原则：完备性。完备性。问题空间中所有点（侯问题空间中所有点（侯选解）都能用遗传算法空间中的选解）都能用遗传算法空间中的点（染色体）表现；点（染色体）表现；健全性。健全性。遗传算法空间中的染色遗传算法空间中的染色体都能对应问题空间中的所有侯体都能对应问题空间中的所有侯选解；选解；非冗余性。非冗余性。染色体和侯选解一一染色体和侯选解一一对应。对应。染色体染色体编码编码，生成初始种群，生成初始种群遗传代数：遗传代数：NEra0计算每个个体的计算每个个体的适应度适应度收敛收敛否否?ny 进进行行选选择择、杂杂交交pc、变变异异pm和和保保留留等等遗遗传传操操作作，生生成成新一代种群新一代种群NEraNEra1解码解码输出结果输出结果W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念染色体染色体编码编码，生成初始种群，生成初始种群遗传代数：遗传代数：NEra0计算每个个体的计算每个个体的适应度适应度收敛收敛否否?ny 进进行行选选择择、杂杂交交pc、变变异异pm和和保保留留等等遗遗传传操操作作，生生成成新一代种群新一代种群NEraNEra1解码解码输出结果输出结果生成初始种群生成初始种群生成初始种群生成初始种群 根根根根据据据据染染染染色色色色体体体体编编编编码码码码，随随随随机机机机确确确确定定定定染染染染色色色色体体体体中中中中的的的的各各各各段段段段基基基基因因因因值值值值；也也也也可可可可根根根根据据据据研研研研究究究究问问问问题题题题空间特点指定部分基因段。空间特点指定部分基因段。空间特点指定部分基因段。空间特点指定部分基因段。适应度函数的确定适应度函数的确定适应度函数的确定适应度函数的确定作作作作用用用用：评评评评价价价价种种种种群群群群中中中中个个个个体体体体的的的的优优优优劣劣劣劣；基于适应度函数值的选择。基于适应度函数值的选择。基于适应度函数值的选择。基于适应度函数值的选择。求极小值问题：求极小值问题：求极小值问题：求极小值问题：求极大值问题：求极大值问题：求极大值问题：求极大值问题：W W z zHUST_CEEE选择选择一个个体一个个体选择遗传算子选择遗传算子pmpc执行执行变异变异操作获得操作获得子代一个新个体子代一个新个体ii1 1选择选择两个个体两个个体执行执行杂交杂交操作获得操作获得子代两个新个体子代两个新个体ii1 1iMc？yn保留保留若干若干最优最优个体个体基因干预基因干预人机人机交互交互0.6910.6360.1441.00.0个体301000个体211000个体101101个体410011赌轮选择赌轮选择1 遗传算法的概念遗传算法的概念遗传操作遗传操作遗传操作遗传操作选择选择选择选择(复制复制复制复制)选选选选择择择择算算算算子子子子根根根根据据据据是是是是每每每每个个个个个个个个体体体体对对对对应应应应的的的的优优优优化化化化问问问问题题题题目目目目标标标标函函函函数数数数转转转转换换换换成成成成的的的的适适适适应应应应度度度度函函函函数数数数值值值值的的的的大大大大小小小小进进进进行行行行复复复复制制制制，体体体体现现现现了了了了自自自自然然然然界界界界中中中中适适适适者者者者生生生生存存存存法法法法则则则则，是是是是遗遗遗遗传算法的关键。传算法的关键。传算法的关键。传算法的关键。适应度函数值比例法（赌轮法）适应度函数值比例法（赌轮法）个体被选取的概率个体被选取的概率适应值的比例变换法适应值的比例变换法 期望值法（期望值法（个体不多时个体不多时）排位次法（排位次法（个体适应度相近时个体适应度相近时）个体个体编码编码适应度适应度函数值函数值选择率选择率累积累积选择率选择率1011011690.1440.1442110005760.4920.636301000640.0550.6914100113610.3091.000W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念遗传操作遗传操作遗传操作遗传操作杂交杂交杂交杂交(交叉交叉交叉交叉)GA的根本所在。通过模拟生物界中的有性繁殖，能能能能把把把把注注注注意意意意力力力力集集集集中中中中到到到到搜搜搜搜索索索索空空空空间间间间中中中中期期期期望值最高的部分望值最高的部分望值最高的部分望值最高的部分。方方方方法法法法：一一一一点点点点杂杂杂杂交交交交、二二二二点点点点杂杂杂杂交交交交和和和和多点杂交多点杂交多点杂交多点杂交遗传操作遗传操作遗传操作遗传操作变异变异变异变异 模拟生物进化过程中偶然的基因突变现象，能能能能保保保保持持持持群群群群体体体体的的的的多多多多样样样样性性性性，避避避避免免免免陷陷陷陷于于于于局局局局部部部部最最最最优优优优，并并并并可可可可以以以以在在在在当当当当前前前前解解解解的的的的附附附附近找到更好的解近找到更好的解近找到更好的解近找到更好的解。选择选择一个个体一个个体选择遗传算子选择遗传算子pmpc执行执行变异变异操作获得操作获得子代一个新个体子代一个新个体ii1 1选择选择两个个体两个个体执行执行杂交杂交操作获得操作获得子代两个新个体子代两个新个体ii1 1iMc？yn保留保留若干若干最优最优个体个体基因干预基因干预人机人机交互交互杂交前杂交前杂交前杂交前 A1=1100000 A2=1001111杂交后杂交后杂交后杂交后 A1=1101111 A2=1000000变异前变异前变异前变异前 A1=1100 01变异后变异后变异后变异后 A1=1101 11W W z zHUST_CEEE选择选择一个个体一个个体选择遗传算子选择遗传算子pmpc执行执行变异变异操作获得操作获得子代一个新个体子代一个新个体ii1 1选择选择两个个体两个个体执行执行杂交杂交操作获得操作获得子代两个新个体子代两个新个体ii1 1iMc？yn保留保留若干若干最优最优个体个体基因干预基因干预人机人机交互交互1 遗传算法的概念遗传算法的概念遗传操作遗传操作遗传操作遗传操作保留保留保留保留 使得遗传算法能以概率1收敛到全局最优解。对对对对种种种种群群群群进进进进行行行行简简简简单单单单的的的的选选选选择择择择(复复复复制制制制)、杂杂杂杂交交交交和和和和变变变变异异异异操操操操作作作作是遗传算法的精髓！是遗传算法的精髓！是遗传算法的精髓！是遗传算法的精髓！停止运行准则停止运行准则停止运行准则停止运行准则 最大困难所在！1 1 1 1）达到最大进化代数）达到最大进化代数）达到最大进化代数）达到最大进化代数 2 2 2 2）连续多代没有改进时）连续多代没有改进时）连续多代没有改进时）连续多代没有改进时染色体染色体编码编码，生成初始种群，生成初始种群遗传代数：遗传代数：NEra0计算每个个体的计算每个个体的适应度适应度收敛收敛否否?ny 进进行行选选择择、杂杂交交pc、变变异异pm和和保保留留等等遗传操作遗传操作 生成新一代种群生成新一代种群NEraNEra1解码解码输出结果输出结果W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念1.3 遗传算法的基本定理遗传算法的基本定理模式定理模式定理模式定理模式定理 在考虑选择、交叉和变异作用下，一个特定模式H在下一代中期望产生的数目可近似表示为其其中中，(H)为为模模式式定定义义长长度度，指指模模式式H中中第第一一个个常常数数位位置置与与最最后后一一个个常常数数位位置置之之间间的的距距离离；O(H)为为模模式式的的阶阶，指指出出现在模式现在模式H中常数位置的个数。中常数位置的个数。模式定义长度短、低阶且适应值在群体平均适应值以上的模式，在遗传算法迭代过程中将按指数增长率被采样。W W z zHUST_CEEE1 遗传算法的概念遗传算法的概念1.3 遗传算法的基本定理遗传算法的基本定理隐含并行性隐含并行性隐含并行性隐含并行性 串串串串长长长长为为为为L L、规规规规模模模模为为为为N N的的的的二二二二进进进进制制制制群群群群体体体体中中中中，包包包包含含含含有有有有2 2L L到到到到N N22L L个个个个模模模模式式式式。模模模模式式式式数数数数是是是是按按按按二二二二项项项项式式式式分分分分布布布布的的的的，由由由由于于于于杂杂杂杂交交交交算算算算子子子子会会会会破破破破坏坏坏坏那那那那些些些些定定定定义义义义长长长长度度度度相相相相对对对对较较较较长长长长的的的的模模模模式式式式，因因因因此此此此，按按按按有有有有效效效效方方方方式式式式被被被被处处处处理理理理的的的的模式数目与群体规模的立方成正比，即模式数目与群体规模的立方成正比，即模式数目与群体规模的立方成正比，即模式数目与群体规模的立方成正比，即N Ns sO O(N N3 3)。此此此此即即即即：每每每每一一一一代代代代中中中中除除除除了了了了仅仅仅仅对对对对N N个个个个染染染染色色色色体体体体处处处处理理理理外外外外，遗遗遗遗传传传传算算算算法法法法实实实实际际际际上上上上处处处处理理理理大大大大约约约约O O(N N3 3)个个个个模模模模式式式式，从从从从而而而而每每每每代代代代只只只只执执执执行行行行与与与与群群群群体体体体规规规规模模模模成成成成比比比比例例例例的的的的计计计计算算算算量量量量，就就就就可可可可以以以以同同同同时时时时收收收收到到到到并并并并行行行行地地地地对对对对大大大大约约约约O O(N N3 3)个模式进行有效处理的目的，并且无须额外的存储。个模式进行有效处理的目的，并且无须额外的存储。个模式进行有效处理的目的，并且无须额外的存储。个模式进行有效处理的目的，并且无须额外的存储。Holland Holland称之为称之为称之为称之为遗传算法的遗传算法的遗传算法的遗传算法的隐含并行性隐含并行性隐含并行性隐含并行性W W z zHUST_CEEE2 遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较2.1 2.1 传统数学优化方法传统数学优化方法传统数学优化方法传统数学优化方法线性规划线性规划线性规划线性规划 (LP_LP_LinearLinear Programming Programming)在在在在满满满满足足足足一一一一组组组组线线线线性性性性约约约约束束束束条条条条件件件件下下下下，寻寻寻寻求求求求多多多多变变变变量量量量线线线线性性性性目目目目标标标标函函函函数的极大数的极大数的极大数的极大/小值。小值。小值。小值。求求求求解解解解方方方方法法法法：单单单单纯纯纯纯形形形形法法法法、线线线线性性性性混混混混合合合合整整整整数数数数规规规规划划划划法法法法（分分分分枝枝枝枝定定定定界法、割平面法、隐枚举法界法、割平面法、隐枚举法界法、割平面法、隐枚举法界法、割平面法、隐枚举法）和）和）和）和内点法内点法内点法内点法。非线性规划非线性规划非线性规划非线性规划 (NP_NonlNP_Nonlinearinear Programming Programming)目标函数或约束条件：一个或多个非线性函数。目标函数或约束条件：一个或多个非线性函数。目标函数或约束条件：一个或多个非线性函数。目标函数或约束条件：一个或多个非线性函数。求求求求解解解解方方方方法法法法：微微微微分分分分法法法法、拉拉拉拉格格格格朗朗朗朗日日日日乘乘乘乘子子子子法法法法、牛牛牛牛顿顿顿顿法法法法、梯梯梯梯度度度度法、变尺度法以及基于变分法的优化方法等。法、变尺度法以及基于变分法的优化方法等。法、变尺度法以及基于变分法的优化方法等。法、变尺度法以及基于变分法的优化方法等。要求函数要求函数要求函数要求函数连续连续连续连续、甚至、甚至、甚至、甚至可导可导可导可导W W z zHUST_CEEE2 遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较2.1 2.1 传统数学优化方法传统数学优化方法传统数学优化方法传统数学优化方法动态规划动态规划动态规划动态规划 (DP_DP_DynamicDynamic Programming Programming)运运运运 筹筹筹筹 学学学学 的的的的 重重重重 要要要要 分分分分 支支支支，由由由由 美美美美 国国国国 数数数数 学学学学 家家家家 贝贝贝贝 尔尔尔尔 曼曼曼曼（R.R.R.R.BellmanBellmanBellmanBellman）等等等等人人人人在在在在1950195019501950年年年年代代代代提提提提出出出出，是是是是研研研研究究究究多多多多阶阶阶阶段段段段决决决决策策策策过过过过程程程程最优化的一种有效方法。最优化的一种有效方法。最优化的一种有效方法。最优化的一种有效方法。动动动动态态态态规规规规划划划划将将将将整整整整个个个个优优优优化化化化问问问问题题题题转转转转化化化化为为为为一一一一个个个个多多多多阶阶阶阶段段段段优优优优化化化化序序序序列列列列来来来来处处处处理理理理，通通通通过过过过合合合合理理理理选选选选择择择择各各各各个个个个阶阶阶阶段段段段决决决决策策策策的的的的集集集集合合合合，使使使使整整整整个个个个过过过过程总体达到最优。程总体达到最优。程总体达到最优。程总体达到最优。要要要要求求求求所所所所求求求求解解解解的的的的问问问问题题题题具具具具有有有有明明明明显显显显的的的的阶阶阶阶段段段段性性性性，它它它它对对对对目目目目标标标标函函函函数数数数的的的的形形形形态态态态没没没没有有有有特特特特殊殊殊殊的的的的要要要要求求求求，理理理理论论论论上上上上可可可可以以以以真真真真正正正正获获获获得得得得全全全全局局局局最最最最优优优优解。缺点是容易出现解。缺点是容易出现解。缺点是容易出现解。缺点是容易出现“维数灾维数灾维数灾维数灾”和和和和“后效后效后效后效”问题。问题。问题。问题。W W z zHUST_CEEE2 遗传算法与传统优化方法的比较遗传算法与传统优化方法的比较2.2 2.2 遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点不不不不是是是是直直直直接接接接作作作作用用用用于于于于参参参参变变变变量量量量集集集集上上上上，而而而而是是是是利利利利用用用用参参参参变变变变量量量量的的的的某某某某种种种种编编编编码码码码，通用性强；，通用性强；，通用性强；，通用性强；采采采采用用用用群群群群体体体体搜搜搜搜索索索索策策策策略略略略，同同同同时时时时对对对对多多多多个个个个解解解解进进进进行行行行评评评评估估估估。因因因因而而而而具具具具有有有有全局优化全局优化全局优化全局优化和和和和隐含并行性隐含并行性隐含并行性隐含并行性；不不不不用用用用搜搜搜搜索索索索空空空空间间间间的的的的知知知知识识识识或或或或其其其其它它它它辅辅辅辅助助助助信信信信息息息息，仅仅仅仅用用用用适适适适应应应应度度度度函函函函数数数数值值值值来来来来评评评评价价价价个个个个体体体体。适适适适应应应应度度度度函函函函数数数数无无无无连连连连续续续续可可可可导导导导限限限限制制制制，定定定定义义义义域域域域任任任任意意意意，特别适用于求解非连续变量结构优化问题；，特别适用于求解非连续变量结构优化问题；，特别适用于求解非连续变量结构优化问题；，特别适用于求解非连续变量结构优化问题；采采采采用用用用概概概概率率率率转转转转移移移移规规规规则则则则指指指指导导导导搜搜搜搜索索索索方方方方向向向向(概概概概率率率率选选选选择择择择、概概概概率率率率交交交交叉叉叉叉、概率概率概率概率变异变异变异变异)，而非确定性规则，鲁棒性强；，而非确定性规则，鲁棒性强；，而非确定性规则，鲁棒性强；，而非确定性规则，鲁棒性强；逐代进化，易于通过逐代进化，易于通过逐代进化，易于通过逐代进化，易于通过基因干预基因干预基因干预基因干预提高收敛速度；提高收敛速度；提高收敛速度；提高收敛速度；可同时获得最优解和若干次优解，便于可同时获得最优解和若干次优解，便于可同时获得最优解和若干次优解，便于可同时获得最优解和若干次优解，便于决策分析决策分析决策分析决策分析。W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用3.1 3.1 遗传算法的应用领域遗传算法的应用领域自适应系统自适应系统自适应系统自适应系统自适应下棋程序自适应下棋程序自适应下棋程序自适应下棋程序模式识别模式识别模式识别模式识别函数优化函数优化函数优化函数优化管道优化管道优化管道优化管道优化医学图像变换医学图像变换医学图像变换医学图像变换囚犯困境游戏囚犯困境游戏囚犯困境游戏囚犯困境游戏分类系统分类系统分类系统分类系统喷气发动机涡轮设计喷气发动机涡轮设计喷气发动机涡轮设计喷气发动机涡轮设计(10010(10010(10010(10010387387387387)导航、躲避和跟踪导航、躲避和跟踪导航、躲避和跟踪导航、躲避和跟踪主要应用领域主要应用领域主要应用领域主要应用领域搜索搜索搜索搜索优化优化优化优化机器学习机器学习机器学习机器学习电力系统中：电力系统中：电力系统中：电力系统中：规划设计规划设计规划设计规划设计、建设施工建设施工建设施工建设施工和和和和运行控制运行控制运行控制运行控制 各环节各环节各环节各环节W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用3.2 GA3.2 GA在电力系统电源规划中的应用在电力系统电源规划中的应用3.2.1 3.2.1 3.2.1 3.2.1 何谓是电源规划？何谓是电源规划？何谓是电源规划？何谓是电源规划？核心：核心：核心：核心：4 4 4 4W W W W问题，即：问题，即：问题，即：问题，即：W WhenhenW WherehereW WhathatH Howow 典型的典型的典型的典型的组合排序组合排序组合排序组合排序问题问题问题问题特点特点特点特点高维数高维数高维数高维数：m m m m个待优选电站，个待优选电站，个待优选电站，个待优选电站，m!m!m!m!组合方案组合方案组合方案组合方案m m m m38383838，m!m!m!m!38!38!38!38!5.23105.23105.23105.231044 44 44 44(约约约约1.66101.66101.66101.661037373737年年年年!)!)!)!)非线性非线性非线性非线性：目标函数、约束条件是非线性的：目标函数、约束条件是非线性的：目标函数、约束条件是非线性的：目标函数、约束条件是非线性的整数性整数性整数性整数性：变量是整数型的：变量是整数型的：变量是整数型的：变量是整数型的不确定性不确定性不确定性不确定性：基础数据（负荷、燃料、设备价格、水电：基础数据（负荷、燃料、设备价格、水电：基础数据（负荷、燃料、设备价格、水电：基础数据（负荷、燃料、设备价格、水电风电出力、贴现率等）不确定风电出力、贴现率等）不确定风电出力、贴现率等）不确定风电出力、贴现率等）不确定W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划为什么要进行电源规划？为什么要进行电源规划？为什么要进行电源规划？为什么要进行电源规划？按英国按英国19971997年装机水平：年装机水平：1.18kW1.18kW13.613.6亿亿1616亿亿kWkWW W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.2 GA3.2.2 GA3.2.2 GA3.2.2 GA电源规划模型电源规划模型电源规划模型电源规划模型目标函数目标函数目标函数目标函数约束条件约束条件约束条件约束条件待建电站建设施工约束待建电站建设施工约束待建电站建设施工约束待建电站建设施工约束系统可靠性约束系统可靠性约束系统可靠性约束系统可靠性约束系统系统系统系统/分区电力电量平衡约束分区电力电量平衡约束分区电力电量平衡约束分区电力电量平衡约束电站运行约束电站运行约束电站运行约束电站运行约束W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.2 GA3.2.2 GA3.2.2 GA3.2.2 GA电源规划模型电源规划模型电源规划模型电源规划模型总体框图总体框图总体框图总体框图待选电源数据 染色体编码染色体编码，生成初始种群生成初始种群：MC遗传代数：NEra0 投资决策子模型投资决策子模型：优化各个体的投资决策 运行优化子模型运行优化子模型：优化各个体的运行成本 计算各个体的适应度适应度 收敛否收敛否?ny 进行选选择择、杂杂交交、变变异异和保保留留等遗传操作，生生成新一代种群成新一代种群NEraNEra1 解码解码，输出电源规划优化结果输出电源规划优化结果现有系统数据负荷预测数据各种约束数据染色体染色体编码编码，生成初始种群，生成初始种群遗传代数：遗传代数：NEra0计算每个个体的计算每个个体的适应度适应度收敛收敛否否?ny 进进行行选选择择、杂杂交交pc、变变异异pm和和保保留留等等遗遗传传操操作作，生生成成新一代种群新一代种群NEraNEra1解码解码输出结果输出结果W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.3 3.2.3 3.2.3 3.2.3 整数向量染色体编码与初始种群的生成整数向量染色体编码与初始种群的生成整数向量染色体编码与初始种群的生成整数向量染色体编码与初始种群的生成染色体编码（电源规划方案）染色体编码（电源规划方案）染色体编码（电源规划方案）染色体编码（电源规划方案）整数向量整数向量整数向量整数向量mm 电源规划方案可以编码为长度为N的整数向量m(m1,m2,mN)。其中，mk表示向量m的第k个元（顺序第k位投建的待优选电站序号）。电源规划初始方案集（初始种群电源规划初始方案集（初始种群电源规划初始方案集（初始种群电源规划初始方案集（初始种群MMC C）生成）生成）生成）生成动态模板整数向量染色体编码法动态模板整数向量染色体编码法动态模板整数向量染色体编码法动态模板整数向量染色体编码法k k随机数随机数j j 1,1,N Nk k11动态模动态模板板m mb b选中选中电站序号电站序号染色体染色体编码编码m mi i1 14 41231234 456564 44*4*2 24 41231235 56 65 545*45*3 32 21 12 236362 2452*452*4 43 313136 66 64526*4526*5 51 11 13 31 145261*45261*6 61 13 33 3452613452613W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.4 3.2.4 3.2.4 3.2.4 适应度函数值的计算适应度函数值的计算适应度函数值的计算适应度函数值的计算种群中方案种群中方案种群中方案种群中方案i i的适应度函数值的适应度函数值的适应度函数值的适应度函数值AFAFi i3.2.5 3.2.5 3.2.5 3.2.5 遗传操作遗传操作遗传操作遗传操作选择算子选择算子选择算子选择算子 适应度函数值比例法（赌轮法）适应度函数值比例法（赌轮法）适应度函数值比例法（赌轮法）适应度函数值比例法（赌轮法）W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.5 3.2.5 3.2.5 3.2.5 遗传操作遗传操作遗传操作遗传操作杂交算子杂交算子杂交算子杂交算子1)1)次序杂交（次序杂交（次序杂交（次序杂交（OCOCOrdering CrossoverOrdering Crossover）例：例：例：例：mF1(9 9,2,2,1313,4 4,6,12,6,12,3 3,8 8,1 1,1010,15,5,14,7,15,5,14,7,1111)mF2(4 4,6,6,9 9,1111,5,2,14,5,2,14,1 1,7,7,3 3,1313,15,15,1010,12,12,8 8)杂交位置杂交位置杂交位置杂交位置 (0,0,0,0,*,*,0,0,0,0,0,0,*,0,0,*,0,0,0,0,0,0,0,0,0,0)mS1(9 9,2,13,4,6,12,2,13,4,6,12,1111,8,8,1 1,10,15,5,14,7,10,15,5,14,7,3 3)mS2(1313,6,9,11,5,2,14,1,7,3,6,9,11,5,2,14,1,7,3,4 4,15,15,8 8,12,12,1010)2)2)位置杂交（位置杂交（位置杂交（位置杂交（LCLCLocating CrossoverLocating Crossover）例：例：例：例：mF1(9 9,2,2,13,4,13,4,6,12,6,12,3 3,8 8,1 1,1010,15,5,14,7,15,5,14,7,1111)mF2(4 4,6,6,9,119,11,5,2,14,5,2,14,1 1,7,7,3 3,1313,15,15,1010,12,12,8 8)杂交位置杂交位置杂交位置杂交位置 (0,0,0,0,*,*,0,0,0,0,0,0,*,0,0,*,0,0,0,0,0,0,0,0,0,0)mS1(2,13,2,13,9,119,11,4,6,12,4,6,12,1 1,8,8,3 3,10,15,5,14,7,10,15,5,14,7)mS2(6,9,6,9,1313,4 4,11,5,2,11,5,2,8 8,14,14,1010,1,7,3,15,12,1,7,3,15,12)W W z zHUST_CEEE3 遗传算法的应用遗传算法的应用电源规划电源规划电源规划电源规划3.2.5 3.2.5 3.2.5 3.2.5 遗传操作遗传操作遗传操作遗传操作杂交算子杂交算子杂交算子杂交算子3)3)映射杂交（映射杂交（映射杂交（映射杂交（MCMCMapping CrossoverMapping Crossover）例：例：例：例：mF1(9,2,13,4,9,2,13,4,6,12,3,86,12,3,8,1,10,15,5,14,7,11,1,10,15,5,14,7,11)mF2(4,6,9,11,4,6,9,11,5,2,14,15,2,14,1,7,3,13,15,10,12,8,7,3,13,15,10,12,8)杂交位置杂交位置杂交位置杂交位置 (0,0,0,0,0,0,0,0,*,*,*,*,*,*,*,*,0,0,0,0,0,0,0 0,0,0,0,0,0,0)mS1(9,12,13,4,9,12,13,4,5,2,14,15,2,14,1,8,10,15,6,3,7,11,8,10,15,6,3,7,11)mS2(4,5,9,11,4,5,9,11,6,12,3,86,12,3,8,7,14,13,15,10,2,1,7,14,13,15,10,2,1)4)4)循环杂交（循环杂交（循环杂交（循环杂交（CCCCCycling CrossoverCycling Crossover）例：例：例：例：mF1