最优化算法讲课教学课件

第四章 遗传算法的高级实现技术6/29/20241主要内容n4.1 倒位算子n4.2 二倍体与显性操作算子n4.3 变长度染色体遗传算法n4.4 小生境遗传算法n4.5 混合遗传算法6/29/202424.1 倒位算子n4.1.1 定义：什么是倒位操作？所谓倒位操作（所谓倒位操作（Inverse Operation）是指颠倒个体编码串随机指定的二个基是指颠倒个体编码串随机指定的二个基因座之间的基因排列顺序，从而形成一因座之间的基因排列顺序，从而形成一个新的染色体。个新的染色体。6/29/202434.1 倒位算子n4.1.2 具体操作过程:在个体编码串中随机指定二个基因座之后的位在个体编码串中随机指定二个基因座之后的位置为倒位点；置为倒位点；以倒位概率以倒位概率 颠倒这二个倒位点之间的基因排颠倒这二个倒位点之间的基因排列顺序。列顺序。1231236/29/202444.1 倒位算子n对二进制编码个体进行倒位操作的示例：A：1 1 0 0 1 0 0 1 1 0 A：1 1 0 1 0 0 1 0 1 0倒位点1倒位点2倒位操作倒位操作改变了个体编码串的部分基因排列顺序，其目的主要是为了能够使遗传算法更有利于生成较好的模式。6/29/202454.1 倒位算子012345678910 11 12 13 14 1516 17 18212327 28 29 30 3132 33 34 35 36 37 38 39SGn4.1.3 倒位算子应用实例6/29/202464.1 倒位算子n用遗传算法进行机器人路径规划时，可取机器人移动过程中所经过栅格标号的顺序排列来作为一个个体（一条行走路线）的表现形式，如下所示即表示一条行走路线：nPATH：039132939（虚线）若在上述行走路线的第二个路径和第三个路径点之间进行倒位操作，可得到一条新的路线：nPATH:093132939（实线）6/29/202474.2 二倍体与显性操作算子二倍体与显性操作算子n4.2.1 二倍体结构的生物基础二倍体结构的生物基础 生物学中，二二倍倍体体是指含有二个同源基因组(染色体)的个体。二倍体是由两个同同源源染染色色体体构成的，其中的每一个染色体都含有相同功能的基因信息。6/29/202484.2.1 二倍体结构的生物基础二倍体结构的生物基础n二倍体结构中各个基因有显性基因显性基因和隐性基因隐性基因之分，这二类基因使个体所呈现出的表现型由下述规则来决定（显性规则）：在每个基因座上，当两个同源染色体其中之一的基因是显性时，则该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。A b c D e f GA b C D e f G 二倍体结构A b C D e f G个体表现型6/29/202494.2.1 二倍体结构的生物基础二倍体结构的生物基础n二倍体的二个重要特性：n1）二倍体的记忆能力，它使得生物能够记忆以前经历过的环境及变化，使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于，使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地应用于动态环境，它难于跟踪环境的动态变化过程。n2）显性操作的鲁棒性，它使得即使随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而避免这个有害选择所带来的不利之处。这个特点应用于遗传算法中，能有利于提高遗传算法的运算效率维护好的搜索群体。6/29/2024104.2.2 二倍体结构在遗传算法中的实现方案nHollstien提出了二倍体与显性操作的双基因座显性映射方法：每个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。随后，Hollstien将这种映射关系简化为单基因座显性映射方法。Holland对这种单基因座的显性映射描述方法进行了改进。描述基因的字符集为0,1,10，其中10为隐性的1，1为显性的1。6/29/2024114.2.2 二倍体结构在遗传算法中的实现方案0000000100110111 0M 0m 1M 1m0M0m1M1m单基因座显性映射方法单基因座显性映射方法双基因座显性映射方法双基因座显性映射方法图 1图 26/29/2024124.2.2 二倍体结构在遗传算法中的实现方案n使用双倍体的遗传算法的算法结构与基本遗传算法的算法结构相类似，不同之处在于：(1)显性性状也能进化，所以同源染色体之间也需进行交叉操作。(2)变异操作需要考虑隐性性状；(3)对个体进行交叉、变异运算之后，要进行显性操作。6/29/2024134.2.2 二倍体结构在遗传算法中的实现方案n算法DiploidyGAn 初始化，并设置进化代数计数器初值：初始化，并设置进化代数计数器初值：t=1t=1。n 随机产生具有二倍体结构的初始群体随机产生具有二倍体结构的初始群体P(0)P(0)。n 对初始群体对初始群体P(0)P(0)进行显性操作。进行显性操作。n 评价初始群体评价初始群体P(0)P(0)中各个个体的适应度。中各个个体的适应度。n 交交叉叉操操作作：P(t)Crossoverp(t)P(t)Crossoverp(t)。由由每每两两个个随随机机配配对对的的二二倍倍体体个个体进行交叉操作时，共可产生四个单倍体个体。体进行交叉操作时，共可产生四个单倍体个体。n 变变异异操操作作：P(t)Mutationp(t)P(t)Mutationp(t)。在在对对群群体体中中的的各各个个个个体体进进行变异操作时，需要考虑隐性基因的作用。行变异操作时，需要考虑隐性基因的作用。n 对群体对群体P(t)P(t)进行显性操作。进行显性操作。n 评价群体评价群体P(t)P(t)中各个个体的适应度。中各个个体的适应度。n 个体选择、复制操作：个体选择、复制操作：P(t+1)P(t+1)Reproduction P(t)PReproduction P(t)P（t t）n 终终止止条条件件判判断断。若若不不满满足足终终止止条条件件，则则:tt+1tt+1，转转到到第第步步，继继续续进行进化操作过程；若满足终止条件则进行进化操作过程；若满足终止条件则:输出当前最优个体，算法结束。输出当前最优个体，算法结束。6/29/2024144.3 变长度染色体遗传算法n在遗传算法的实际应用中，有时为简要地描述问题的解，也需要使用不同长度的编码串。结点1和结点6之间的连通路线，可用以下二种方法来描述：6/29/2024154.3 变长度染色体遗传算法n(1)用二进制编码来表示各个结点是否在连通路线上，其中1表示在连通路线上，0表示不在连通路线上。此时可使用等长度的编码串来表示连通路线，如：PATH1：1 1 0 0 1 1PATH2：1 1 1 1 1 1n(2)用连通路线所经过结点的顺序排列来表示该条连通路线，如：PATH1：12 5 6PATH2：1 2 3 4 5 66/29/2024164.3.1 变长度染色体遗传算法的编码与解码n编码编码n将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可表示为:ik是所描述的基因在原常规染色体中的基因座编号，vk为对应的基因值。6/29/2024174.3.1 变长度染色体遗传算法的编码与解码n若常规遗传算法中一个个体的基因型是：X：1 0 0 1 0 1其染色体长度为L6。使用变长度染色体编码，该个体就可表示为：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)在这种变长度染色体遗传算法中，允许染色体的长度可长可短。如：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)Xm：(1，1)(3，0)(5，0)(6，1)前者称为过剩指定，后者称为缺省指定。而当个体的所有基因都能在编码串中得到唯一的描述时，这种描述称为正常指定。6/29/2024184.3.1 变长度染色体遗传算法的编码与解码n解码 正常指定没有问题。过剩指定或缺省指定，可按下述规则来进行解码处理：(1)描描述述过过剩剩时时的的解解码码方方法法。规定取最左边的二元组来进行解码。例如，对于变长度染色体遗传算法中的个体X Xm m：(1(1，1)(21)(2，0)(30)(3，0)(40)(4，1)(51)(5，0)(60)(6，1)1)(3(3，1)(11)(1，0)0)它在常规遗传算法中所对应的个体为：X X：1 0 0 1 0 11 0 0 1 0 16/29/2024194.3.1 变长度染色体遗传算法的编码与解码 (2)描描述述不不足足时时的的解解码码方方法法。可规定它们取某一项先设定的标准值(或缺省值)。例如，对于变长度染色体遗传算法中的个体Xm：(1，1)(3，0)(5，0)(6，1)若取缺省值为0的话，则它在常规遗传算法中所对应的个体为：X：1 0 0 0 0 16/29/2024204.3.2 切断算子与拼接算子n1切断算子切断算子(Cut operator)切断算子以某一预先指定的概率，在变长度染色体中随机选择一个基因座，在该处将个体的基因型切断，使之成为二个个体的基因型。n2拼接算子拼接算子(Splice operator)拼按算子以某一预先指定的概率，将二个个体的基因型连接在一起，使它们合并为一个个体的基因型。6/29/2024214.3.3 变长度染色体遗传算法的算法结构n算法算法MessyGA （1）初初始始化化。随机产生M个染色体，长度全部为k的个体，以它们作为变长度遗传算法的初始个体集合P(0)，其中k为根据问题的不同而设定的一个参数，并且k l。（2）适适应应度度评评价价。对变长度的染色体进行解码处理后，评价或计算各个个体的适应度。（3）基基本本处处理理阶阶段段。对群体P(t)施加选择算子，以保留适应度较高的个体。（4）并并列列处处理理阶阶段段。对群体P(t)施加变异算子、切断算子和拼接算子，以生成新的个体。（5）重复第步，直到满足终止条件为止。6/29/2024224.4 小生境遗传算法4.4.1 4.4.1 小生境与遗传算法小生境与遗传算法 生物学上，小生境小生境(Niche)(Niche)是指特定环境下的一种生存环境。生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代；它们也都是在某一特定的地理区域中生存。在用遗传算法求解多峰值函数的优化计算问题时，经常是只能找到个别的几个最优解，甚至往往得到的是局部最优解，而有时希望优化算法能够找出问题的所有最忧解，包括局部最优解和全局最优解。基本遗传算法对此无能为力。既然作为遗传算法模拟对象的生物都有其特定的生存环境，那么借鉴此概念，我们也可以让遗传算法中的个体在一个特定的生存环境中进化，即在遗传算法中可以引进小生境的概念，从而解决这类问题，以找出更多的最优解。6/29/2024234.4.2 遗传算法中小生境的实现方法n1基于预选择机制的小生境实现方法(Cavicchio，1970年）n2基于排挤的小生境实现方法（De Jong，1975年）n3基于共享函数(Sharing Function)的小生境实现方法（Goldberg和Richardson，1987年）6/29/2024244.4.2 遗传算法中小生境的实现方法n1基于预选择机制的小生境实现方法基于预选择机制的小生境实现方法 1970年，Cavicchio率先在遗传算法中引入了基于预选择机制(Preselection)的小生境实现方法。只有在子代个体的适应度超过其父代个体的情况下，子代个体才能替换其父代个体，进入下一代群体。由于这种方式趋向于替换与其本身相似的个体(父与子之间的性状遗传)，因而能够较好地维持群体的多样性，并造就小生境的进化环境。6/29/2024254.4.2 遗传算法中小生境的实现方法n2基于排挤的小生境实现方法基于排挤的小生境实现方法 排挤的思想源与在一个有限的生存空间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争各种有限的生存资源。这种实现方法的基本思想是：设置一排挤因子排挤因子CF，由群体中随机选取的1CF个个体组成排挤成员然后依据新产生的个体与排挤成员的相似性排挤成员的相似性来排挤掉一些与排挤成员相类似的个体。这里，个体之间的相似性可用个体编码串之间的海明距离来度量。随着排挤过程的进行群体中的个体逐渐被分类，从而形成各个小的生存环境并维持了群体的多样性。6/29/2024264.4.2 遗传算法中小生境的实现方法n3 基于共享函数基于共享函数(Sharing Function)的小生境的小生境实现方法实现方法 这种实现方法的基本思想是：通过反映个体之间相似程度的共享函数共享函数来调整群体中各个个体的适应度适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维护群体的多样性，创造出小生境的进化环境。6/29/2024274.4.3 小生境遗传算法在多峰值函数全局最优化中的应用nNicheGANicheGA算法：算法：初始化初始化t=1t=1根据个体的适应度降序排列根据个体的适应度降序排列选择运算：选择运算：P P（t t）PP（t t）交叉运算：交叉运算：PP（t t）P“P“（t t）变异运算：变异运算：P”P”（t t）P“P“（t t）小生境淘汰运算小生境淘汰运算根据新的适应度降序排列根据新的适应度降序排列终止条件？终止条件？t=t+1否算法结束算法结束新序列中的前新序列中的前M个个做下一代群体做下一代群体P(t)是是6/29/2024284.5 混合遗传算法4.5.14.5.1混合遗传算法的基本思想混合遗传算法的基本思想6/29/2024294.5.1混合遗传算法的基本思想n混合遗传算法的特点：混合遗传算法的特点：（1 1）引入局部搜索过程。）引入局部搜索过程。基于群体中的各个个体所对应的表现型，进行局部搜索，从而找到各个个体在目前的环境下所对应的局部最优解，以便达到改善群体总体性能的目的。（2 2）增加了编码变换操作过程。）增加了编码变换操作过程。对于局部搜索过程所得到的局部最优解，在通过编码过程将它们变换为新的个体，以便能够以一个性能较优的新群体为基础来进行下一代的遗传进化操作。6/29/2024304.5.2 混合遗传算法的基本构成原则n在构成混合遗传算法时，De Jong提出了下面的三条基本原则：n(1)尽尽量量采采用用原原有有算算法法的的编编码码。这样就便于利用原有算法的相关知识，也便于实现混合遗传算法。n(2)利利用用原原有有算算法法的的优优点点。这样就可保证由混合遗传算法所求到的解的质量不会低于由原有算法所求到的解的质量。n(3)改改进进遗遗传传算算子子。设计能适应新的编码方式的遗传算子，并在遗传算子中溶入与问题相关的启发式知识，这样就可使得混合遗传算法既能够保持遗传算法的全局寻优特点，又能够提高其运行效率。6/29/2024314.5.3 模拟退火算法 n从统计热力学的观点来说，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。n模拟退火算法模拟退火算法(Simulated Annealing)(Simulated Annealing)就是基于金属退火的机理而建立起的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。6/29/2024324.5.3 模拟退火算法n模拟退火算法的构成要素如下：n1 1搜索空间搜索空间搜索空间也称为状态空间，它由可行解的集合所组成。n2 2能量函数能量函数E(x)E(x)能量函数也就是需要进行优化计算的目标函数。n3 3状态转移规则状态转移规则P P状态转移规则是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率，它与当前的温度参数T有关。6/29/2024334.5.3 模拟退火算法n4 4冷却进度表冷却进度表T(t)T(t)冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)T(t)来表示，则经典模拟退火算法的降温方式经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。6/29/2024344.5.3 模拟退火算法n如果搜索过程陷入局部最优点A，若要使搜索过程脱离这个局部员优点而到达C点，则必须使系统至少要具有B点所对应的能量。亦即，这里必须允许能量函数值可以一时增大。图图3能量函数能量函数6/29/2024354.5.3 模拟退火算法n假设在状态xold时，系统受到某种扰动而可能会使其状态变为xnew。与此相对应，系统的能量也可能会从E(xold)变成E(xnew)，系统由状态xold变为状态xnew的接受概率可由下面的Metropolis规则来确定：n if E(xnew)E(xold)if E(xnew)E(xold)当新状态使系统的能量函数值减少时，系统一定接受这个新的状态；而当新状态使系统的能量函数值增加时，系统也以某一概率接受这个新的状态。6/29/2024364.5.3 模拟退火算法n算法算法Simulated Annealingn 随机产生一个初始解，以它作为当前最优解，并计算目标随机产生一个初始解，以它作为当前最优解，并计算目标函数值。函数值。n 设置初始温度：设置初始温度：To。n 设置循环计数器初值：设置循环计数器初值：t=1。n 对当前最优解作一随机变动对当前最优解作一随机变动,产生一新的解。计算新的目产生一新的解。计算新的目标函数值，并计算目标函数值的增量标函数值，并计算目标函数值的增量。n 如果如果 0，则接受该新产生的解为当前最优解；，则接受该新产生的解为当前最优解；如果如果 0，则以概率，则以概率p=exp(-/)接受该新产生的解为接受该新产生的解为当前最优解。当前最优解。n 如果如果t终止步效，则：终止步效，则：t=t+1，转向第，转向第步。步。n 如果未到达冷却状态，则：如果未到达冷却状态，则：T(t)转向第转向第步；步；如果已到达冷却状态，则：输出当前最优点，计算结束。如果已到达冷却状态，则：输出当前最优点，计算结束。6/29/2024374.5.4 遗传模拟退火算法n遗遗传传模模拟拟退退火火算算法法是将遗遗传传算算法法与模模拟拟退退火火算算法法相结合而构成的一种优化算法。n遗遗传传算算法法的局部搜索能力较差、但把握搜索过程总体的能力较强；n而模模拟拟退退火火算算法法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域。6/29/2024384.5.4 遗传模拟退火算法n算法算法Genetic Simulated Annealingn 进化代数计数器初始化：进化代数计数器初始化：t0;n 随机产生初始群体随机产生初始群体P(t)。n 评价群体评价群体P(t)的适应度。的适应度。n 个体交叉操作：个体交叉操作：P(t)CrossoverP(t)n 个体变异操作：个体变异操作：P(t)MutationP(t)n 个体模拟退火操作：个体模拟退火操作：P(t)SimulatedAnnealingP(t)n 评价群体评价群体P(t)的适应度。的适应度。n 个体选择、复制操作：个体选择、复制操作：P(t+1)ReproductionP(t)P(t)n 终止条件判断。若不满足终止条件，则终止条件判断。若不满足终止条件，则:t t+1，转到第，转到第步，继续进化过程；若满足终止条件则步，继续进化过程；若满足终止条件则:输出当前最优个体，输出当前最优个体，算法结束。算法结束。6/29/2024394.5.4 遗传模拟退火算法n在模拟退火算法算法中溶入遗传算法：如并行组合模拟退火算法PRSA（Parallel Recombination Simulated Annealing）n 随机生成含有随机生成含有M个个体的初始群体个个体的初始群体P(0)。n 设置初始温度参数：设置初始温度参数：T Tmaxn 对对P(t)中的各个个体进行随机配对，对其中的每一对个体做下述处理：中的各个个体进行随机配对，对其中的每一对个体做下述处理：(a)进行交叉和变异运算，由两个父代个体进行交叉和变异运算，由两个父代个体P1、P2生成两个子代个体生成两个子代个体c1和和c2。(b)对由父代个体和子代个体所组成的两个个体组对由父代个体和子代个体所组成的两个个体组P1和和c1，P2和和c2，以概，以概率率p接受父代个体为下一代群体中的个体，以概率接受父代个体为下一代群体中的个体，以概率(1-p)接受子代个体为下接受子代个体为下一代群体中的个体。一代群体中的个体。其中，其中，式中，式中，fp和和fc分别为父代个体和子代个体所对应的目标函数值。分别为父代个体和子代个体所对应的目标函数值。n 终止条件判断。若不满足终止条件，则：按降温表更新温度参效终止条件判断。若不满足终止条件，则：按降温表更新温度参效T，t=t+1，转向第，转向第步；若满足终止条件，则：输出当前最优点，算法结束。步；若满足终止条件，则：输出当前最优点，算法结束。6/29/2024406/29/202441