智能优化方法资料课件

第第9章章 智能优化方法智能优化方法Contents遗传算法遗传算法 1 1蚁群优化算法蚁群优化算法 2 2粒子群优化算法粒子群优化算法 3 3 4 4遗传算法遗传算法Genetic Algorithm(GA)Contents算法简介算法简介 1 1基本流程基本流程 2 2改进研究改进研究 3 3相关应用相关应用 4 44.1 遗传算法简介遗传算法简介遗传算法是什么？遗传算法是什么？遗传算法遗传算法（Genetic Algorithm，GA）是进化计算的一个分支，是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。是一种模拟自然界生物进化过程的随机搜索算法。遗传算法的思想来源是怎样的？遗传算法的思想来源是怎样的？它由谁提出的？它由谁提出的？GA思想源于思想源于自然界自然界“自然选择自然选择”和和“优胜劣汰优胜劣汰”的进化规律，的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授它最早由美国密歇根大学教授John H.Holland提出，提出，现在已经广泛应用于各种工程领域的优化问题之中。现在已经广泛应用于各种工程领域的优化问题之中。4.1.1 基本原理基本原理遗传算法遗传算法遗传算法遗传算法 达尔文进化论达尔文进化论现代遗传学现代遗传学生物模拟技术生物模拟技术4.1.1 基本基本原理原理生物遗传进化生物遗传进化群体群体种群种群染色体染色体基因基因适应能力适应能力交配交配变异变异进化结束进化结束遗传算法遗传算法搜索空间的一组有效搜索空间的一组有效解解选择得到的新群体选择得到的新群体可行解的编码串可行解的编码串染色体的一个编码单染色体的一个编码单元元染色体的适应值染色体的适应值染色体交换部分基因得到新染色体交换部分基因得到新染色体染色体染色体某些基因的数值改变染色体某些基因的数值改变算法结束算法结束生物遗传进化过程生物遗传进化过程遗传算法遗传算法类比关系类比关系4.1.1 基本基本原理原理生物进化过程生物进化过程遗传基因重组过程遗传基因重组过程4.1.1 基本基本原理原理模式定理模式定理模式模式模式模式指群体中编码的某些位置具有相似结构的染色体集合指群体中编码的某些位置具有相似结构的染色体集合 模式的定义长度模式的定义长度模式的定义长度模式的定义长度指模式中第一个具有确定取值的基因到最后一个具有指模式中第一个具有确定取值的基因到最后一个具有确定取值的基因的距离确定取值的基因的距离 模式的阶模式的阶模式的阶模式的阶指模式中具有确定取值的基因个数指模式中具有确定取值的基因个数 HollandHolland的模式定理提出，遗传算法的实质是通过选择、交的模式定理提出，遗传算法的实质是通过选择、交配和变异算子对模式进行搜索，低阶、定义长度较小且平配和变异算子对模式进行搜索，低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长。即随着进化的不断进行，较优染色体的个数指数级增长。即随着进化的不断进行，较优染色体的个数将快速增加。将快速增加。4.1.1 基本基本原理原理积木块假设积木块假设积木块积木块积木块积木块指低阶、定义长度较小且平均适应值高于群体平均适应值的指低阶、定义长度较小且平均适应值高于群体平均适应值的模式模式 积木块假设认为在遗传算法运行过程中，积木块在遗传算积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能够相互结合，产生新的更加优秀的积木块，子的影响下能够相互结合，产生新的更加优秀的积木块，最终接近全局最优解最终接近全局最优解 。4.1.2 研究进展研究进展GA 研究内容与方向研究内容与方向 算法性能算法性能算法性能算法性能研究研究研究研究混合算法混合算法混合算法混合算法研究研究研究研究并行算法并行算法并行算法并行算法研究研究研究研究算法应用算法应用算法应用算法应用研究研究研究研究与与GA相关的重要学术期刊与国际会议相关的重要学术期刊与国际会议重要学术期刊重要学术期刊lEvolutionary ComputationlIEEE Transactions on Evolutionary Computationl重要国际会议重要国际会议lInternational Conference on Genetic AlgorithmlACM Genetic and Evolutionary Computation ConferencelWorkshop on Foundations of Genetic Algorithms and Classifier SystemslGenetic Programming ConferencelInternational Workshop on Artificial Lifel 4.2 遗传算法的流程遗传算法的流程流程结构流程结构l染色体编码染色体编码l群体初始化群体初始化l适应值评价适应值评价l选择算子选择算子l交配算子交配算子l变异算子变异算子l算法流程图和伪代码算法流程图和伪代码应用举例应用举例l函数优化问题函数优化问题l算法的执行步骤示意图算法的执行步骤示意图染色体编码染色体编码二进制编码方法（二进制编码方法（Binary Representation）浮点数编码方法（浮点数编码方法（Float Point Representation）0000000011111111一般情况下，遗传算法在群体初始化阶段采用的是随机数初始化随机数初始化方法。采用生成随机数的方法，对染色体的每一维变量进行初始化赋值。初始化染色体时必须注意染色体是否满足优化问题对有效解的定义。如果在进化开始时保证初始群体已经是一定程度上的优良群体的话，将能够有效提高算法找到全局最优解的能力。群体初始化群体初始化评估函数用于评估各个染色体的适应值，进而区分优劣。评估函数常常根据问题的优化目标来确定，比如在求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。在遗传算法中，规定适应值越大的染色体越优。因此对于一些求解最大值的数值优化问题，我们可以直接套用问题定义的函数表达式。但是对于其他优化问题，问题定义的目标函数表达式必须经过一定的变换。适应值评价适应值评价选择选择算子算子轮盘赌选择算法轮盘赌选择算法交配算子交配算子在染色体交配阶段，每个染色体能否进行交配由交配概率Pc（一般取值为0.4到0.99之间）决定，其具体过程为：对于每个染色体，如果Random(0,1)小于Pc则表示该染色体可进行交配操作（其中Random(0,1)为0,1间均匀分布的随机数），否则染色体不参与交配直接复制到新种群中。每两个按照Pc交配概率选择出来的染色体进行交配，经过交换各自的部分基因，产生两个新的子代染色体。具体操作是随机产生一个有效的交配位置，染色体交换位于该交配位置后的所有基因。交配算子交配算子染色体的变异作用于基因之上，对于交配后新种群中染色体的每一位基因，根据变异概率Pm判断该基因是否进行变异。如果Random(0,1)小于Pm，则改变该基因的取值（其中Random(0,1)为0,1间均匀分布的随机数）。否则该基因不发生变异，保持不变。变异算子变异算子遗传算法流程图和伪代码遗传算法流程图和伪代码4.2.2 应用举例应用举例例4.1已知函数 ，其中 ，用遗传算法求解y的 最大值。运行步骤运行步骤算子选择参数设置混合遗传算法并行遗传算法4.3 遗传算法的改进遗传算法的改进 确定性采样确定性采样排挤模型排挤模型最佳个体保存模型最佳个体保存模型4.3.1 算子选择算子选择适应值比例模型适应值比例模型排序模型排序模型随机锦标赛模型随机锦标赛模型无回放余数随机采样无回放余数随机采样期望值模型期望值模型选择算子选择算子选择算子选择算子交配算子交配算子交配算子交配算子单性孢子交配算子单性孢子交配算子边重组交配算子边重组交配算子循环交配算子循环交配算子顺序交配算子顺序交配算子部分匹配交配算子部分匹配交配算子多点交配算子多点交配算子算术交配算子算术交配算子均匀交配算子均匀交配算子两点交配算子两点交配算子边集合交配算子边集合交配算子变异算子变异算子变异算子变异算子非均匀变异算子非均匀变异算子高斯变异算子高斯变异算子边界变异算子边界变异算子群体规模群体规模N 染色体长度染色体长度L 影响算法的搜索能力和运行效率。若N设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜索能力，但是由于群体中染色体的个数较多，势必增加算法的计算量，降低了算法的运行效率。若N设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的能力。N的设置一般为20100。影响算法的计算量和交配变异操作的效果。L的设置跟优化问题密切相关，一般由问题定义的解的形式和选择的编码方法决定。对于二进制编码方法，染色体的长度L根据解的取值范围和规定精度要求选择大小。对于浮点数编码方法，染色体的长度L 跟问题定义的解的维数D相同。除了染色体长度一定的编码方法，Goldberg等人还提出了一种变长度染色体遗传算法Messy GA，其染色体的长度并不是固定的。4.3.2 参数设置参数设置交配概率交配概率Pc 变异概率变异概率Pm 决定了进化过程种群参加交配的染色体平均数目。取值一般为0.4至0.99。也可采用自适应方法调整算法运行过程中的交配概率。增加群体进化的多样性，决定了进化过程中群体发生变异的基因平均个数。Pm的值不宜过大。因为变异对已找到的较优解具有一定的破坏作用，如果Pm的值太大，可能会导致算法目前处于的较好的搜索状态倒退回原来较差的情况。Pm的取值一般为0.001至0.1之间。也可采用自适应方法调整算法运行过程中的Pm值。R视采用的染色体编码方案而定。对于二进制编码方法，R=0,1，而对于浮点数编码方法，R与优化问题定义的解每一维变量的取值范围相同。基因取值基因取值范围范围R 4.3.2 参数设置参数设置终止条件终止条件决定算法何时停止运行，输出找到的最优解，采用何种终止条件，跟具体问题的应用有关。可以使算法在达到最大进化代数时停止，最大进化代数一般可设置为1001000，根据具体问题可对该建议值作相应的修改。也可以通过考察找到的当前最优解是否达到误差要求来控制算法的停止。或者是算法在持续很长的一段进化时间内所找到的最优解没有得到改善时，算法可以停止。适应值评价适应值评价影响算法对种群的选择，恰当的评估函数应该能够对染色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化能力。评估函数的设置同优化问题的求解目标有关。评估函数应满足较优染色体的适应值较大的规定。为了更好地提高选择的效能，可以对评估函数做出一定的修正。目前主要的评估函数修正方法有：线性变换；乘幂变换；指数变换等。4.3.2 参数设置参数设置4.3.3 混合遗传算法混合遗传算法爬山法爬山法模拟退火算法模拟退火算法最速下降法最速下降法其它其它局部搜索算法局部搜索算法遗传算法遗传算法4.3.3 混合遗传算法混合遗传算法并行组合模拟退火算法并行模拟退火遗传算法贪婪遗传算法遗传比率切割算法遗传爬山法引入局部改善操作的混合遗传算法免疫遗传算法并行计算并行计算单指令流多数据流计算机单指令流多数据流计算机多指令流多数据流计算机多指令流多数据流计算机并行计算网络并行计算网络串行计算串行计算单指令流单数据流处理器单指令流单数据流处理器4.3.4 并行遗传算法并行遗传算法并行遗传算法并行遗传算法标准型并行方法标准型并行方法分解型并行方法分解型并行方法标准型并行方法标准型并行方法分解型并行方法分解型并行方法子群体进化信息交换问题子群体进化信息交换问题分解型并行方法分解型并行方法u交换的时间交换的时间 u交换的方式交换的方式 u交换的内容交换的内容 群体模型群体模型u岛屿模型岛屿模型 u踏脚石模型踏脚石模型 u邻居模型邻居模型 图像处理和模式识别图像处理和模式识别优化与调度优化与调度机器学习机器学习智能控制智能控制其它其它人工生命人工生命自动程序设计自动程序设计应用应用4.4 遗传算法的应用遗传算法的应用