最优化算法讲课ppt课件

《最优化算法讲课ppt课件》由会员分享，可在线阅读，更多相关《最优化算法讲课ppt课件（41页珍藏版）》请在装配图网上搜索。

1、第四章 遗传算法的高级实现技术主要内容n4.1 倒位算子n4.2 二倍体与显性操作算子n4.3 变长度染色体遗传算法n4.4 小生境遗传算法n4.5 混合遗传算法4.1 倒位算子n4.1.1 定义：什么是倒位操作？n 所谓倒位操作Inverse Operation是指颠倒个体编码串随机指定的二个基因座之间的基因陈列顺序，从而构成一个新的染色体。4.1 倒位算子n4.1.2 详细操作过程:n在个体编码串中随机指定二个基因座之后的位置为倒位点；n以倒位概率 颠倒这二个倒位点之间的基因陈列顺序。ip1231234.1 倒位算子n对二进制编码个体进展倒位操作的例如：nA：1 1 0 0 1 0 0 1

2、 1 0n A：1 1 0 1 0 0 1 0 1 0倒位点1倒位点2倒位操作倒位操作改动了个体编码串的部分基因陈列顺序，其目的主要是为了可以使遗传算法更有利于生成较好的方式。4.1 倒位算子012345678910 11 12 13 14 1516 17 18212327 28 29 30 3132 33 34 35 36 37 38 39SGn4.1.3 倒位算子运用实例4.1 倒位算子n用遗传算法进展机器人途径规划时，可取机器人挪动过程中所经过栅格标号的顺序陈列来作为一个个体一条行走道路的表现方式，如下所示即表示一条行走道路：nPATH：039132939虚线n假设在上述行走道路的第二个

3、途径和第三个途径点之间进展倒位操作，可得到一条新的道路：nPATH:093132939实线4.2 二倍体与显性操作算子n4.2.1 二倍体构造的生物根底n 生物学中，二倍体是指含有二个同源基因组(染色体)的个体。n二倍体是由两个同源染色体构成的，其中的每一个染色体都含有一样功能的基因信息。4.2.1 二倍体构造的生物根底n二倍体构造中各个基因有显性基因和隐性基因之分，这二类基因使个体所呈现出的表现型由下述规那么来决议显性规那么：n 在每个基因座上，当两个同源染色体其中之一的基因是显性时，那么该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。

4、A b c D e f GA b C D e f G 二倍体构造A b C D e f G个体表现型4.2.1 二倍体构造的生物根底n二倍体的二个重要特性：n1二倍体的记忆才干，它使得生物可以记忆以前阅历过的环境及变化，使得生物的遗传进化过程可以快速地顺应环境的变化。这个特点在遗传算法中的应意图义就在于，运用二倍体构造的遗传算法可以处理动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地运用于动态环境，它难于跟踪环境的动态变化过程。n2显性操作的鲁棒性，它使得即使随机选择了顺应度不高的个体，而在显性操作的作用下，可以用其另一同源染色体对其进展校正，从而防止这个有害选择所带来的不利之处。这

5、个特点运用于遗传算法中，能有利于提高遗传算法的运算效率维护好的搜索群体。4.2.2 二倍体构造在遗传算法中的实现方案nHollstien提出了二倍体与显性操作的双基因座显性映射方法：n每个二进制基因用两个基因来描画，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。n随后，Hollstien将这种映射关系简化为单基因座显性映射方法。nHolland对这种单基因座的显性映射描画方法进展了改良。描画基因的字符集为0,1,10，其中10为隐性的1，1为显性的1。4.2.2 二倍体构造在遗传算法中的实现方案0000000100110111 0

6、M 0m 1M 1m0M0m1M1m单基因座显性映射方法单基因座显性映射方法双基因座显性映射方法双基因座显性映射方法图 1图 24.2.2 二倍体构造在遗传算法中的实现方案n运用双倍体的遗传算法的算法构造与根本遗传算法的算法构造相类似，不同之处在于：n (1)显性性状也能进化，所以同源染色体之间也需进展交叉操作。n (2)变异操作需求思索隐性性状；n (3)对个体进展交叉、变异运算之后，要进展显性操作。4.2.2 二倍体构造在遗传算法中的实现方案n算法DiploidyGAn 初始化，并设置进化代数计数器初值：t=1。n 随机产生具有二倍体构造的初始群体P(0)。n 对初始群体P(0)进展显性操

7、作。n 评价初始群体P(0)中各个个体的顺应度。n 交叉操作：P(t)Crossoverp(t)。由每两个随机配对的二倍体个体进展交叉操作时，共可产生四个单倍体个体。n 变异操作：P(t)Mutationp(t)。在对群体中的各个个体进展变异操作时，需求思索隐性基因的作用。n 对群体P(t)进展显性操作。n 评价群体P(t)中各个个体的顺应度。n 个体选择、复制操作：P(t+1)Reproduction P(t)Ptn 终止条件判别。假设不满足终止条件，那么:tt+1，转到第步，继续进展进化操作过程；假设满足终止条件那么:输出当前最优个体，算法终了。4.3 变长度染色体遗传算法n在遗传算法的实

8、践运用中，有时为简要地描画问题的解，也需求运用不同长度的编码串。结点1和结点6之间的连通道路，可用以下二种方法来描画：4.3 变长度染色体遗传算法n(1)用二进制编码来表示各个结点能否在连通道路上，其中1表示在连通道路上，0表示不在连通道路上。此时可运用等长度的编码串来表示连通道路，如：nPATH1：1 1 0 0 1 1nPATH2：1 1 1 1 1 1n(2)用连通道路所经过结点的顺序陈列来表示该条连通道路，如：nPATH1：12 5 6nPATH2：1 2 3 4 5 64.3.1 变长度染色体遗传算法的编码与解码n编码编码n将常规遗传算法的染色体编码串中各基因将常规遗传算法的染色体编

9、码串中各基因座位置及相应基因值组成一个二元组，把这个座位置及相应基因值组成一个二元组，把这个二元组按一定顺序陈列起来，就组成了变长度二元组按一定顺序陈列起来，就组成了变长度染色体的一种通用染色体编码方式。普通它可染色体的一种通用染色体编码方式。普通它可表示为表示为:nik是所描画的基因在原常规染色体中的基是所描画的基因在原常规染色体中的基因座编号，因座编号，vk为对应的基因值。为对应的基因值。),(),(),)(,(:221nnkkimviviviviX4.3.1 变长度染色体遗传算法的编码与解码n假设常规遗传算法中一个个体的基因型是：nX：1 0 0 1 0 1n其染色体长度为L6。运用变长

10、度染色体编码，该个体就可表示为：nXm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)n 在这种变长度染色体遗传算法中，允许染色体的长度可长可短。如：n Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)nXm：(1，1)(3，0)(5，0)(6，1)n前者称为过剩指定，后者称为缺省指定。而当个体的一切基因都能在编码串中得到独一的描画时，这种描画称为正常指定。4.3.1 变长度染色体遗传算法的编码与解码n解码n 正常指定没有问题。过剩指定或缺省指定，可按下述规那么来进展解码处置：n(1)描画过剩时的解码方法。规定取最左边的二元组来进展解码。n例

11、如，对于变长度染色体遗传算法中的个体nXm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)n它在常规遗传算法中所对应的个体为：nX：1 0 0 1 0 14.3.1 变长度染色体遗传算法的编码与解码 (2)描画缺乏时的解码方法。可规定它们取某一项先设定的规范值(或缺省值)。例如，对于变长度染色体遗传算法中的个体Xm：(1，1)(3，0)(5，0)(6，1)假设取缺省值为0的话，那么它在常规遗传算法中所对应的个体为：X：1 0 0 0 0 14.3.2 切断算子与拼接算子n1切断算子(Cut operator)n切断算子以某一预先指定的概率，在变长度染色体中随机

12、选择一个基因座，在该处将个体的基因型切断，使之成为二个个体的基因型。n2拼接算子(Splice operator)n拼按算子以某一预先指定的概率，将二个个体的基因型衔接在一同，使它们合并为一个个体的基因型。4.3.3 变长度染色体遗传算法的算法构造n算法算法MessyGAn 1初始化。随机产生初始化。随机产生M个染色体，长度全个染色体，长度全部为部为k的个体，以它们作为变长度遗传算法的的个体，以它们作为变长度遗传算法的初始个体集合初始个体集合P(0)，其中，其中k为根据问题的不同为根据问题的不同而设定的一个参数，并且而设定的一个参数，并且k l。n 2顺应度评价。对变长度的染色体进展解顺应度评

13、价。对变长度的染色体进展解码处置后，评价或计算各个个体的顺应度。码处置后，评价或计算各个个体的顺应度。n 3根本处置阶段。对群体根本处置阶段。对群体P(t)施加选择算施加选择算子，以保管顺应度较高的个体。子，以保管顺应度较高的个体。n 4并列处置阶段。对群体并列处置阶段。对群体P(t)施加变异算施加变异算子、切断算子和拼接算子，以生成新的个体。子、切断算子和拼接算子，以生成新的个体。n 5反复第反复第步，直到满足终止条件为步，直到满足终止条件为止。止。4.4 小生境遗传算法4.4.1 小生境与遗传算法小生境与遗传算法 生物学上，小生境生物学上，小生境(Niche)是指特定环境下的一种生存环境。

14、生物在其进化过程中，普通总是与本人一样的物种生活在一同，共同繁衍后代；它们也都是在某一特是指特定环境下的一种生存环境。生物在其进化过程中，普通总是与本人一样的物种生活在一同，共同繁衍后代；它们也都是在某一特定的地理区域中生存。定的地理区域中生存。在用遗传算法求解多峰值函数的优化计算问题时，经常是只能找到个别的几个最优解，甚至往往得到的是部分最优解，而有时希望优化算法可以找出问题的一切最在用遗传算法求解多峰值函数的优化计算问题时，经常是只能找到个别的几个最优解，甚至往往得到的是部分最优解，而有时希望优化算法可以找出问题的一切最忧解，包括部分最优解和全局最优解。根本遗传算法对此无能为力。既然作为遗

15、传算法模拟对象的生物都有其特定的生存环境，那么自创此概念，我们也可以让忧解，包括部分最优解和全局最优解。根本遗传算法对此无能为力。既然作为遗传算法模拟对象的生物都有其特定的生存环境，那么自创此概念，我们也可以让遗传算法中的个体在一个特定的生存环境中进化，即在遗传算法中可以引进小生境的概念，从而处理这类问题，以找出更多的最优解。遗传算法中的个体在一个特定的生存环境中进化，即在遗传算法中可以引进小生境的概念，从而处理这类问题，以找出更多的最优解。4.4.2 遗传算法中小生境的实现方法n1基于预选择机制的小生境实现方法(Cavicchio，1970年n2基于排斥的小生境实现方法 De Jong，19

16、75年n3基于共享函数(Sharing Function)的小生境实现方法 Goldberg和Richardson，1987年4.4.2 遗传算法中小生境的实现方法n1基于预选择机制的小生境实现方法基于预选择机制的小生境实现方法n 1970年，年，Cavicchio率先在遗传算法率先在遗传算法中引入了基于预选择机制中引入了基于预选择机制(Preselection)的小生境实现方法。的小生境实现方法。n 只需在子代个体的顺应度超越其父代只需在子代个体的顺应度超越其父代个体的情况下，子代个体才干交换其父代个体的情况下，子代个体才干交换其父代个体，进入下一代群体。个体，进入下一代群体。n 由于这种方

17、式趋向于交换与其本身类似由于这种方式趋向于交换与其本身类似的个体的个体(父与子之间的性状遗传父与子之间的性状遗传)，因此可，因此可以较好地维持群体的多样性，并培育小生以较好地维持群体的多样性，并培育小生境的进化环境。境的进化环境。4.4.2 遗传算法中小生境的实现方法n2基于排斥的小生境实现方法基于排斥的小生境实现方法n 排斥的思想源与在一个有限的生存空间中，排斥的思想源与在一个有限的生存空间中，各种不同的生物为了可以延续生存，它们之间各种不同的生物为了可以延续生存，它们之间必需相互竞争各种有限的生存资源。必需相互竞争各种有限的生存资源。n 这种实现方法的根本思想是：设置一排斥这种实现方法的根

18、本思想是：设置一排斥因子因子CF，由群体中随机选取的，由群体中随机选取的1CF个个体组个个体组成排斥成员然后根据新产生的个体与排斥成成排斥成员然后根据新产生的个体与排斥成员的类似性来排斥掉一些与排斥成员相类似的员的类似性来排斥掉一些与排斥成员相类似的个体。这里，个体之间的类似性可用个体编码个体。这里，个体之间的类似性可用个体编码串之间的海明间隔来度量。随着排斥过程的进串之间的海明间隔来度量。随着排斥过程的进展群体中的个体逐渐被分类，从而构成各个展群体中的个体逐渐被分类，从而构成各个小的生存环境并维持了群体的多样性。小的生存环境并维持了群体的多样性。4.4.2 遗传算法中小生境的实现方法n3 基

19、于共享函数基于共享函数(Sharing Function)的小生的小生境实现方法境实现方法n 这种实现方法的根本思想是：经过反映个这种实现方法的根本思想是：经过反映个体之间类似程度的共享函数来调整群体中各个体之间类似程度的共享函数来调整群体中各个个体的顺应度，从而在这以后的群体进化过程个体的顺应度，从而在这以后的群体进化过程中，算法可以根据这个调整后的新顺应度来进中，算法可以根据这个调整后的新顺应度来进展选择运算，以维护群体的多样性，发明出小展选择运算，以维护群体的多样性，发明出小生境的进化环境。生境的进化环境。4.4.3 小生境遗传算法在多峰值函数全局最优化中的运用nNicheGANiche

20、GA算法：算法：n 初始化初始化t=1t=1根据个体的顺应度降序陈列根据个体的顺应度降序陈列选择运算：选择运算：P Pt tPPt t交叉运算：交叉运算：PPt tP“P“t t变异运算：变异运算：P Pt tP“P“t t小生境淘汰运算小生境淘汰运算根据新的顺应度降序陈列根据新的顺应度降序陈列终止条件？终止条件？t=t+1否算法终了算法终了新序列中的前新序列中的前M个个做下一代群体做下一代群体P(t)是是4.5 混合遗传算法4.5.14.5.1混合遗传算法的根本思想混合遗传算法的根本思想4.5.1混合遗传算法的根本思想n混合遗传算法的特点：混合遗传算法的特点：n 1引入部分搜索过程。引入部分

21、搜索过程。n 基于群体中的各个个体所对应的表现基于群体中的各个个体所对应的表现型，进展部分搜索，从而找到各个个体型，进展部分搜索，从而找到各个个体在目前的环境下所对应的部分最优解，在目前的环境下所对应的部分最优解，以便到达改善群体总体性能的目的。以便到达改善群体总体性能的目的。n 2添加了编码变换操作过程。添加了编码变换操作过程。n 对于部分搜索过程所得到的部分最优对于部分搜索过程所得到的部分最优解，在经过编码过程将它们变换为新的解，在经过编码过程将它们变换为新的个体，以便可以以一个性能较优的新群个体，以便可以以一个性能较优的新群体为根底来进展下一代的遗传进化操作。体为根底来进展下一代的遗传进

22、化操作。4.5.2 混合遗传算法的根本构成原那么n在构成混合遗传算法时，De Jong提出了下面的三条根本原那么：n(1)尽量采用原有算法的编码。这样就便于利用原有算法的相关知识，也便于实现混合遗传算法。n(2)利用原有算法的优点。这样就可保证由混合遗传算法所求到的解的质量不会低于由原有算法所求到的解的质量。n(3)改良遗传算子。设计能顺应新的编码方式的遗传算子，并在遗传算子中溶入与问题相关的启发式知识，这样就可使得混合遗传算法既可以坚持遗传算法的全局寻优特点，又可以提高其运转效率。4.5.3 模拟退火算法 n从统计热力学的观念来说，随着温度的降低，物质的能量将逐渐趋近于一个较低的形状，并最终

23、到达某种平衡。n模拟退火算法(Simulated Annealing)就是基于金属退火的机理而建立起的一种全局最优化方法，它可以以随机搜索技术从概率的意义上找出目的函数的全局最小点。4.5.3 模拟退火算法n模拟退火算法的构成要素如下：n1搜索空间n搜索空间也称为形状空间，它由可行解的集合所组成。n2能量函数E(x)n能量函数也就是需求进展优化计算的目的函数。n3形状转移规那么Pn形状转移规那么是指从一个形状xold(一个可行解)向另一个形状xnew(另一个可行解)的转移概率，它与当前的温度参数T有关。4.5.3 模拟退火算法n4 4冷却进度表冷却进度表T(t)T(t)n 冷却进度表是指从某一

24、高温形状冷却进度表是指从某一高温形状ToTo向低温形状冷却时的降温管向低温形状冷却时的降温管理表。理表。n 假设时辰假设时辰t t的温度用的温度用T(t)T(t)来表示，那么经典模拟退火算法的降温来表示，那么经典模拟退火算法的降温方式为：方式为：nn 而快速模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：n这两种方式都可以使得模拟退火算法收敛于全局最小点。这两种方式都可以使得模拟退火算法收敛于全局最小点。0()lg(1)TT tt0()1TT tt4.5.3 模拟退火算法n假设搜索过程堕入部分最优点A，假设要使搜索过程脱离这个部分员优点而到达C点，那么必需使系统至少要具有B点所对应的

25、能量。亦即，这里必需允许能量函数值可以一时增大。图图3能量函数能量函数4.5.3 模拟退火算法n假设在形状xold时，系统遭到某种扰动而能够会使其形状变为xnew。与此相对应，系统的能量也能够会从E(xold)变成E(xnew)，系统由形状xold变为形状xnew的接受概率可由下面的Metropolis规那么来确定：n if E(xnew)E(xold)n n if E(xnew)E(xold)n 当新形状使系统的能量函数值减少时，系一致定接受这个新的形状；而当新形状使系统的能量函数值添加时，系统也以某一概率接受这个新的形状。1()()expnewoldpE xE xT4.5.3 模拟退火算法

26、n算法算法Simulated Annealingn 随机产生一个初始解，以它作为当前最优解，并计算目的随机产生一个初始解，以它作为当前最优解，并计算目的函数值。函数值。n 设置初始温度：设置初始温度：To。n 设置循环计数器初值：设置循环计数器初值：t=1。n 对当前最优解作一随机变动对当前最优解作一随机变动,产生一新的解。计算新的目产生一新的解。计算新的目的函数值，并计算目的函数值的增量的函数值，并计算目的函数值的增量。n 假设假设 0，那么接受该新产生的解为当前最优解；，那么接受该新产生的解为当前最优解；n 假设假设 0，那么以概率，那么以概率p=exp(-/)接受该新产生的接受该新产生的

27、解为当前最优解。解为当前最优解。n 假设假设t终止步效，那么：终止步效，那么：t=t+1，转向第，转向第步。步。n 假设未到达冷却形状，那么：假设未到达冷却形状，那么：T(t)转向第转向第步；步；n 假设已到达冷却形状，那么：输出当前最优点，计算终了。假设已到达冷却形状，那么：输出当前最优点，计算终了。4.5.4 遗传模拟退火算法n遗传模拟退火算法是将遗传算法与模拟退火算法相遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法。结合而构成的一种优化算法。n遗传算法的部分搜索才干较差、但把握搜索过遗传算法的部分搜索才干较差、但把握搜索过程总体的才干较强；程总体的才干较强；n而模拟

28、退火算法具有较强的部分搜索才干，并而模拟退火算法具有较强的部分搜索才干，并能使搜索过程防止堕入部分最优解，但模拟退火算能使搜索过程防止堕入部分最优解，但模拟退火算法却对整个搜索空间的情况了解不多，不便于使搜法却对整个搜索空间的情况了解不多，不便于使搜索过程进入最有希望的搜索区域。索过程进入最有希望的搜索区域。4.5.4 遗传模拟退火算法n算法算法Genetic Simulated Annealingn 进化代数计数器初始化：进化代数计数器初始化：t0;n 随机产生初始群体随机产生初始群体P(t)。n 评价群体评价群体P(t)的顺应度。的顺应度。n 个体交叉操作：个体交叉操作：P(t)Cross

29、overP(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，转到，转到第第步，继续进化过程；假设满足终止条件那么步，继续进化过程；假设满足终止条件那么:输出当前最输出当前最优个体，算法终了。优个体，算法终了。4.5.4 遗传模拟退火算法n在模拟退火算

30、法算法中溶入遗传算法：n 如并行组合模拟退火算法PRSAParallel Recombination Simulated Annealingn 随机生成含有M个个体的初始群体P(0)。n 设置初始温度参数：T Tmaxn 对P(t)中的各个个体进展随机配对，对其中的每一对个体做下述处置：n (a)进展交叉和变异运算，由两个父代个体P1、P2生成两个子代个体c1和c2。n (b)对由父代个体和子代个体所组成的两个个体组P1和c1，P2和c2，以概率p接受父代个体为下一代群体中的个体，以概率(1-p)接受子代个体为下一代群体中的个体。其中，n 式中，fp和fc分别为父代个体和子代个体所对应的目的函数值。n 终止条件判别。假设不满足终止条件，那么：按降温表更新温度参效T，t=t+1，转向第步；假设满足终止条件，那么：输出当前最优点，算法终了。11e x ppcpffT