《最优化算法讲课课件》由会员分享，可在线阅读，更多相关《最优化算法讲课课件（41页珍藏版）》请在金锄头文库上搜索。
1、2018/10/17,1,第四章 遗传算法的高级实现技术,2018/10/17,2,主要内容,4.1 倒位算子 4.2 二倍体与显性操作算子 4.3 变长度染色体遗传算法 4.4 小生境遗传算法 4.5 混合遗传算法,2018/10/17,3,4.1 倒位算子,4.1.1 定义：什么是倒位操作？所谓倒位操作（Inverse Operation）是指颠倒个体编码串随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体。,2018/10/17,4,4.1 倒位算子,4.1.2 具体操作过程: 在个体编码串中随机指定二个基因座之后的位置为倒位点； 以倒位概率 颠倒这二个倒位点之间的基因排列顺
2、序。,1,2,3,1,2,3,2018/10/17,5,4.1 倒位算子,对二进制编码个体进行倒位操作的示例： A：1 1 0 0 1 0 0 1 1 0,A：1 1 0 1 0 0 1 0 1 0,倒位点1,倒位点2,倒位操作,倒位操作改变了个体编码串的部分基因排列顺序，其目的主要是为了能够使遗传算法更有利于生成较好的模式。,2018/10/17,6,4.1 倒位算子,S,G,4.1.3 倒位算子应用实例,2018/10/17,7,4.1 倒位算子,用遗传算法进行机器人路径规划时，可取机器人移动过程中所经过栅格标号的顺序排列来作为一个个体（一条行走路线）的表现形式，如下所示即表示一条行走路线
3、： PATH：039132939（虚线） 若在上述行走路线的第二个路径和第三个路径点之间进行倒位操作，可得到一条新的路线： PATH: 093132939（实线）,2018/10/17,8,4.2 二倍体与显性操作算子,4.2.1 二倍体结构的生物基础生物学中，二倍体是指含有二个同源基因组(染色体)的个体。二倍体是由两个同源染色体构成的，其中的每一个染色体都含有相同功能的基因信息。,2018/10/17,9,4.2.1 二倍体结构的生物基础,二倍体结构中各个基因有显性基因和隐性基因之分，这二类基因使个体所呈现出的表现型由下述规则来决定（显性规则）：在每个基因座上，当两个同源染色体其中之一的基因
4、是显性时，则该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。,A b c D e f G A b C D e f G二倍体结构,A b C D e f G,个体表现型,2018/10/17,10,4.2.1 二倍体结构的生物基础,二倍体的二个重要特性： 1）二倍体的记忆能力，它使得生物能够记忆以前经历过的环境及变化，使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于，使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地应用于动态环境，它难于跟踪环境的动态变化过程。 2
5、）显性操作的鲁棒性，它使得即使随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而避免这个有害选择所带来的不利之处。这个特点应用于遗传算法中，能有利于提高遗传算法的运算效率维护好的搜索群体。,2018/10/17,11,4.2.2 二倍体结构在遗传算法中的实现方案,Hollstien提出了二倍体与显性操作的双基因座显性映射方法：每个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。随后，Hollstien将这种映射关系简化为单基因座显性映射方法。 Holland对这种单
6、基因座的显性映射描述方法进行了改进。描述基因的字符集为0, 1, 10，其中10为隐性的1，1为显性的1。,2018/10/17,12,4.2.2 二倍体结构在遗传算法中的实现方案,0M 0m 1M 1m,0M 0m 1M 1m,单基因座显性映射方法,双基因座显性映射方法,图 1,图 2,2018/10/17,13,4.2.2 二倍体结构在遗传算法中的实现方案,使用双倍体的遗传算法的算法结构与基本遗传算法的算法结构相类似，不同之处在于：(1) 显性性状也能进化，所以同源染色体之间也需进行交叉操作。(2) 变异操作需要考虑隐性性状；(3) 对个体进行交叉、变异运算之后，要进行显性操作。,2018
7、/10/17,14,4.2.2 二倍体结构在遗传算法中的实现方案,算法DiploidyGA 初始化，并设置进化代数计数器初值：t=1。 随机产生具有二倍体结构的初始群体P(0)。 对初始群体P(0)进行显性操作。 评价初始群体P(0)中各个个体的适应度。 交叉操作：P(t)Crossoverp(t)。由每两个随机配对的二倍体个体进行交叉操作时，共可产生四个单倍体个体。 变异操作：P(t)Mutationp(t)。在对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用。 对群体P(t)进行显性操作。 评价群体P(t)中各个个体的适应度。 个体选择、复制操作：P(t+1)Reproductio
8、n P(t)P（t） 终止条件判断。若不满足终止条件，则: tt+1，转到第步，继续进行进化操作过程；若满足终止条件则:输出当前最优个体，算法结束。,2018/10/17,15,4.3 变长度染色体遗传算法,在遗传算法的实际应用中，有时为简要地描述问题的解，也需要使用不同长度的编码串。,结点1和结点6之间的连通路线，可用以下二种方法来描述：,2018/10/17,16,4.3 变长度染色体遗传算法,(1)用二进制编码来表示各个结点是否在连通路线上，其中1表示在连通路线上，0表示不在连通路线上。此时可使用等长度的编码串来表示连通路线，如：PATH1：1 1 0 0 1 1PATH2：1 1 1
9、1 1 1 (2)用连通路线所经过结点的顺序排列来表示该条连通路线，如：PATH1：12 5 6PATH2：1 2 3 4 5 6,2018/10/17,17,4.3.1 变长度染色体遗传算法的编码与解码,编码将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可表示为:ik是所描述的基因在原常规染色体中的基因座编号，vk为对应的基因值。,2018/10/17,18,4.3.1 变长度染色体遗传算法的编码与解码,若常规遗传算法中一个个体的基因型是：X：1 0 0 1 0 1其染色体长度为L6。
10、使用变长度染色体编码，该个体就可表示为：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)前者称为过剩指定，后者称为缺省指定。而当个体的所有基因都能在编码串中得到唯一的描述时，这种描述称为正常指定。,2018/10/17,19,4.3.1 变长度染色体遗传算法的编码与解码,解码正常指定没有问题。过剩指定或缺省指定，可按下述规则来进行解码处理： (1)描述过剩时的解码方法。规定取最左边的二
11、元组来进行解码。 例如，对于变长度染色体遗传算法中的个体 Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0) 它在常规遗传算法中所对应的个体为： X：1 0 0 1 0 1,2018/10/17,20,4.3.1 变长度染色体遗传算法的编码与解码,(2)描述不足时的解码方法。可规定它们取某一项先设定的标准值(或缺省值)。 例如，对于变长度染色体遗传算法中的个体 Xm：(1，1)(3，0)(5，0)(6，1) 若取缺省值为0的话，则它在常规遗传算法中所对应的个体为： X：1 0 0 0 0 1,2018/10/17,21,4.3.2 切断算子与拼接算子,1切断
12、算子(Cut operator)切断算子以某一预先指定的概率，在变长度染色体中随机选择一个基因座，在该处将个体的基因型切断，使之成为二个个体的基因型。 2拼接算子(Splice operator)拼按算子以某一预先指定的概率，将二个个体的基因型连接在一起，使它们合并为一个个体的基因型。,2018/10/17,22,4.3.3 变长度染色体遗传算法的算法结构,算法MessyGA（1）初始化。随机产生M个染色体，长度全部为k的个体，以它们作为变长度遗传算法的初始个体集合P(0)，其中k为根据问题的不同而设定的一个参数，并且k l。（2）适应度评价。对变长度的染色体进行解码处理后，评价或计算各个个体
13、的适应度。（3）基本处理阶段。对群体P(t)施加选择算子，以保留适应度较高的个体。（4）并列处理阶段。对群体P(t)施加变异算子、切断算子和拼接算子，以生成新的个体。（5）重复第步，直到满足终止条件为止。,2018/10/17,23,4.4 小生境遗传算法,4.4.1 小生境与遗传算法生物学上，小生境(Niche)是指特定环境下的一种生存环境。生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代；它们也都是在某一特定的地理区域中生存。在用遗传算法求解多峰值函数的优化计算问题时，经常是只能找到个别的几个最优解，甚至往往得到的是局部最优解，而有时希望优化算法能够找出问题的所有最忧解
14、，包括局部最优解和全局最优解。基本遗传算法对此无能为力。既然作为遗传算法模拟对象的生物都有其特定的生存环境，那么借鉴此概念，我们也可以让遗传算法中的个体在一个特定的生存环境中进化，即在遗传算法中可以引进小生境的概念，从而解决这类问题，以找出更多的最优解。,2018/10/17,24,4.4.2 遗传算法中小生境的实现方法,1基于预选择机制的小生境实现方法(Cavicchio ，1970年） 2基于排挤的小生境实现方法（ De Jong，1975年） 3基于共享函数(Sharing Function)的小生境实现方法（ Goldberg和Richardson， 1987年）,2018/10/17
15、,25,4.4.2 遗传算法中小生境的实现方法,1基于预选择机制的小生境实现方法1970年，Cavicchio率先在遗传算法中引入了基于预选择机制(Preselection)的小生境实现方法。只有在子代个体的适应度超过其父代个体的情况下，子代个体才能替换其父代个体，进入下一代群体。由于这种方式趋向于替换与其本身相似的个体(父与子之间的性状遗传)，因而能够较好地维持群体的多样性，并造就小生境的进化环境。,2018/10/17,26,4.4.2 遗传算法中小生境的实现方法,2基于排挤的小生境实现方法排挤的思想源与在一个有限的生存空间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争各种有限的
16、生存资源。这种实现方法的基本思想是：设置一排挤因子CF，由群体中随机选取的1CF个个体组成排挤成员然后依据新产生的个体与排挤成员的相似性来排挤掉一些与排挤成员相类似的个体。这里，个体之间的相似性可用个体编码串之间的海明距离来度量。随着排挤过程的进行群体中的个体逐渐被分类，从而形成各个小的生存环境并维持了群体的多样性。,2018/10/17,27,4.4.2 遗传算法中小生境的实现方法,3 基于共享函数(Sharing Function)的小生境实现方法这种实现方法的基本思想是：通过反映个体之间相似程度的共享函数来调整群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维护群体的多样性，创造出小生境的进化环境。,
