遗传算法讲义3slides.docx
《遗传算法讲义3slides.docx》由会员分享，可在线阅读，更多相关《遗传算法讲义3slides.docx（16页珍藏版）》请在冰点文库上搜索。
遗传算法讲义3slides
第三章遗传算法的高级实现技术
二倍体与显性操作算子
二倍体结构的生物基础
生物学中，二倍体是指含有二个同源基因组（染色体）的个体。
二倍体是由两个同源染色体组成的，其中的每一个染色体都含有相同功能的基因信息。
二倍体结构中各个基因有显性基因和隐性基因之分，这二类基因使个体所呈现出的表现型由下述规那么来决定（显性规那么）：
在每一个基因座上，当两个同源染色体其中之一的基因是显性时，那么该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。
显性基因在纯合子（AA）或杂合子（A或a）情形下均能被表现出，而隐性基因只能在纯合子（aa）的情形下才能被表现出。
二倍体的二个重要特性：
1）二倍体的经历能力，它使得生物能够经历以前经历过的环境及转变，使得生物的遗传进化进程能够快速地适应环境的转变。
那个特点在遗传算法中的应用意义就在于，利用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能专门好地应用于动态环境，它难于跟踪环境的动态转变进程。
2）显性操作的鲁律性，它使得即便随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而幸免那个有害选择所带来的不利的地方。
那个特点应用于遗传算法中，能有利于提高遗传算法的运算效率．保护好的搜索群体。
二倍体结构在遗传算法中的实现方案
Hollstien提出了二倍体与显性操作的双基因座显性映射方式：
每一个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1值；另一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。
随后，Hollstien将这种映射关系简化为单基因座显性映射方式。
Holland对这种单基因座的显性映射描述方式进行了改良。
在那个单基因座显性映射方式中，描述基因的字符集为{0,1,10}，其中10为隐性的1，1为显性的1。
双基因座显性映射方式单基因座显性映射方式
利用双倍体的遗传算法的算法结构与大体遗传算法的算法结构相类似，但也有些不同，其不同的地方在于：
（1）显性性状也能进化，因此同源染色体之间也需进行交叉操作。
（2）变异操作需要考虑隐性性状；
（3）对个体进行交叉、变异运算以后，要进行显性操作。
利用双倍体的遗传算法可描述如下：
算法DiploidyGA
①初始化，并设置进化代数计数器初值：
t=1。
②随机产生具有二倍体结构的初始群体P（0）。
③对初始群体P（0）进行显性操作。
④评判初始群体P（0）中各个个体的适应度。
⑤交叉操作：
P’（t）←crossover[p（t）]。
由每两个随机配对的二倍体个体进行交又操作时，共可产生四个单倍体个体。
⑥变异操作：
P’’（t）←mutation[p’（t）]。
在对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用。
⑦对群体P’’（t）进行显性操作。
⑧评判群体P’’（t）中各个个体的适应度。
⑨个体选择、复制操作：
⑩终止条件判定。
假设不知足终止条件，那么:
t←t+1，转到第⑤步，继续进行进化操作进程；假设知足终止条件．那么．输出当前最优个体，算法终止。
变长度染色体遗传算法
在生物的进化进程中，其染色体的长度并非是固定不变的，而是随着进化进程也在慢慢地转变着。
在遗传算法的实际应用中．有时为简腹地描述问题的解，也需要利用不同长度的编码串。
结点1和结点6之间的连通线路，可用以下二种方式来描述：
（1）用二进制编码来表示各个结点是不是在连通线路上，其中l表示在连通线路上，0表示不在连通线路上。
现在可利用等长度的编码串来表示连通线路，如：
PATH1：
110011
PATH2：
111111
（2）用连通线路所通过结点的顺序排列来表示该条连通线路，如：
PATH1：
1—2—5—6
PATH2：
1—2—3—4—5—6
该方式利用的确实是变长度的染色体编码方式。
Goldberg等提出的MessyGA（简称MGA）是一种典型的变长度染色体遗传算法。
变长度染色体遗传算法的编码与解码（MessyGA）
编码
将常规遗传算法的染色体编码串中各基因座位置及相应基因值组成一个二元组，把那个二元组按必然顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。
一样它可表示为:
ik是所描述约基因在原常规染色体中的基因座编号，vk为对应的基因值。
关于所需求解的问题，假设利用常规遗传算法时的染色体长度固定为l，各基因值取自集合V，那么有
例如，假设常规遗传算法中一个个体的基因型是：
X：
10010l
其染色体长度为l＝6。
利用变长度染色体编码，该个体就可表示为：
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）
前者称为多余指定，后者称为缺省指定。
而当个体的所有基因都能在编码串中取得唯一的描述时，这种描述称为正常指定。
解码
对变长度染色体进行解码处置时，在正常指定情形下，将变长度染色体遗传算法中的个体基因型转换为常规遗传算法中的个体基因型时可不能有什么问题，而在多余指定或缺省指按时，就会产生描述多余或描述不足的问题，现在可按下述规那么来进行解码处置：
（1）描述多余时的解码方式。
现在，常规遗传算法中的一个基因座可能在变长度染色体中同时有几个对应的二元组，规定取最左侧的二元组来进行解码。
例如，关于变长度染色体遗传算法中的个体
Xm：
（1，1）（2，0）（3，0）（4，1）（5，0）（6，1）（3，1）（1，0）
它在常规遗传算法中所对应的个体为：
X：
100101
（2）描述不足时的解码方式。
现在，常规遗传算法中有些基因座上的基因值未被在变长度染色体中明确地指定，这时可规定它们取某一项先设定的标准值（或缺省值）。
例如，关于变长度染色体遗传算法中的个体
Xm：
（1，1）（3，0）（5，0）（6，1）
假设取缺省值为0的话，那么它在常规遗传算法中所对应的个体为：
X：
100001
切断算子与拼接算子
变长度染色体遗传算法除利用常规遗传算法中的选择算子和变异算子之外，再也不利用通用的交叉算子。
而代之以利用下述的切断算子和拼接算子，以它们作为产生新个体的要紧遗传算子。
1．切断算子（Cutoperator）
切断算子以某一预先指定的概率，在变长度染色体中随机选择一个基因座，在该处将个体的基因型切断，使之成为二个个体的基因型。
2．拼接算子（Spliceoperator）
拼按算子以某一预先指定的概率，将二个个体的基因型连接在一路，使它们归并为一个个体的基因型。
变长度染色体遗传算法的算法结构
变长度染色体遗传算法的算法结构可描述如下：
算法MessyGA
①初始化。
随机产生M个染色体，长度全数为k的个体，以它们作为变长度遗传算法的初始个体集合P（0），其中k为依照问题的不同而设定的一个参数，而且k≤l。
②适应废评判。
对变长度的染色体进行解码处置后，评判或计算各个个体的适应度。
③大体处置时期。
对群体P（t）施加选择算子，以保留适应度较高的个体。
④并列处置时期。
对群体P（t）施加变异算子、切断算子和拼接算子，以生成新的个体。
③重复第②~④步，直到知足终止条件为止。
小生境遗传算法
在自然界，“人以群分，物以类聚”是一个习以为常的现象。
生物老是偏向于与自己特点、性状相类似的生物（同类）生活在一路，一样老是与同类交配繁衍后代。
这种正选型交配方式在生物遗传进化进程中是有其踊跃的作用的。
生物学上，小生境（niche）是指特定环境中一种组织（organism）的功能，而把有一起特性的组织称作物种（species）。
为了明白得分类及小生境技术在遗传优化中的作用，咱们先考察一下大体遗传算法在单变量多峰函数优化方面的搜索特性。
等峰的单变量多极值点函数变峰的单变量多极值点函数
咱们以均匀散布的随机方式产生初始群体，那么在算法的开始时期，各个体散布在一个相对较宽的函数概念域中；
关于等峰的单变量多极值点函数，随着遗传优化进程的进行，群体开始登山，并慢慢集中到一个山峰上。
而关于变峰的单变量多极值点函数，大体遗传算法的优化结果将使群体集中到最高的一个山峰上。
而在实际应用中，咱们有时需要了解问题空间内其它山峰的情形，显然，大体遗传算法不能知足这一性能要求。
另外，大体遗传算法采取的是一种随机交配方式；而在生物界，交配那么不完满是随机的，至少有性别、区域和物种类别等方面因素的制约。
从遗传算法角度来看，尽管随机交配方式增强了开劈新的、可能是有效的搜索空间的能力，但由于缺乏对可能的交配成效（子代的质量）方面的考虑，也会带来交配的有效性和优化效率不太理想等方面的问题。
为了解决这些问题，在遗传算法中引入小生境技术已被一些实验研究证明是种有效的尝试。
1．基于预选择机制的小生境技术
1970年，Cavicchio率先在遗传算法中引入了基于预选择机制的小生境技术。
只有在子串的适应度超过其父串的情形下，子串才能替换其父串，进入下一代群体。
由于这种方式趋向于替换与其本身相似的个体（父与子之间的性状遗传），因此能够较好地维持群体的散布特性。
Cavicchio宣称利用这种方式能够在群体规模相对较小的情形下维持较高的群体散布特性。
2．基于排斥机制的小生境技术
1975年，DeJong一样化了Cavicchio的预选择机制，提出了一种称作排斥（crowding）机制的小生境技术。
利用了群体的代间覆盖方式，依据相似性替换群体中的个体。
具体算法实现步骤如下：
（1）初始化;（成立初始群体，确信遗传参数，设定排斥因子CF）
（2）计算个体的适应度；
（3）遗传操作（选择、交叉和变异）；
（4）从当前群体中随机选取群体规模的1／CF个个体组成排斥因子成员；
（5）比较新产生的个体与排斥因子成员之间的相似性；
（6）用新产生的个体去替换排斥因子成员中最相似的个体，形成新的当前群体；
（7）如未知足算法终止条件那么返回第
（2）步，不然算法终止。
在优化的初始时期，由于群体中个体间的相似性相差不大，个体的更新替换呈随机选择特性；随着遗传优化的进展，群体中的个体慢慢被分类，形成假设干个小生境，现在，基于个体相似性的替换技术可在必然程度上维持群体的散布持性，并为更进一步的分类和小生境的形成腾出空间。
DeJong曾将这一技术应用到多峰函数的遗传优化上，取得了比较中意的成效。
3．基于共享（sharing）机制的小生境技术
1987年，Goldberg和Richardson提出了一种基于共享（sharing）机制的小生境技术。
概念了共享函数（sharingfunction），用来确信每一个个体在群体中的共享度。
一个个体的共享度等于该个体与群体内的各个其它个体之间的共享函数值的总和。
共享函数是关于两个体之间的关系紧密程度（基因型的相似性或表现型的相似性）的函数，当个体间关系比较紧密时，共享函数值较大，反之，那么共享函数值较小。
设dij表示个体i和个体j之间的关系紧密程度，S为共享函数，Si表示个体i在群体中的共享度，那么有：
在计算了各个体的共享度后，个体的适应度f（i）依据下式调整为fs（i）：
显然，这种机制限制了群体内某一特殊“物种”的无操纵的增加。
图~图显示了引入基于共享机制的小生境技术的遗传算法（GA）与大体遗传（sGA）算法在多峰函数优化方面的搜索特性不同。
SGA优化等峰单变量多极基于小生境GA优化等峰单变量
值点函数的解群散布趋势多极值点函数的解群分布趋势
SGA优化变峰单变量多极基于小生境GA优化变峰单变量
值点函数的解群散布趋势多极值点函数的解群分布趋势
混合遗传算法
混合遗传算法的思想
应用实践说明，在遗传算法的应用中也会显现一些不尽人意的问题，这些问题中最要紧的是它容易产生早熟现象、局部寻优能力较差等。
另外，遗传算法也无法幸免多次搜索同一个可行解，这也是阻碍遗传算法运行效率的一个因素。
另一方面，梯度法、登山法、模拟退火算法、列表寻优法等一些优化算法却具有很强的局部搜索能力，而另一些含有与问题相关知识的启发式算法的运行效率也比较高。
在遗传算法的搜索进程中融合这些优化方式的思想、组成一种混合遗传算法（HybridGeneticAlgorithm）是提高遗传算法运行效率和求解质量的一个有效手腕。
一种大体的混合遗传算法组成框架。
由能够看出．这种混合遗传算法是在标准遗传算法中融合了局部搜索算法的思想，其特点要紧体此刻以下二个方面：
（1）引入了局部搜索进程。
基于群体中各个个体所对应的表现型，进行局部搜索，从而找出各个个体在目前的环境下所对应的局部最优解，以便达到改善群体整体性能的目的。
（2）增加了编码变换操作进程。
对局部搜索进程所取得的局部最优解，再通过编码进程将它们变换为新的个体，以便能够以一个性能较优的新群体为基础来进行下一代的遗传进化操作。
混合遗传算法的大体组成原那么
在组成混合遗传算法时，DeJong提出了下面的三条大体原那么：
（1）尽可能采纳原有算法的编码。
如此就便于利用原有算法的相关知识，也便于实现混合遗传算法。
（2）利用原有算法的优势。
如此就可保证由混合遗传算法所求到的解的质量可不能低于由原有算法所求到的解的质量。
（3）改良遗传算子。
设计能适应新的编码方式的遗传算子，并在遗传算子中溶入与问题相关的启发式知识，如此就可使得混合遗传算法既能够维持遗传算法的全局寻优特点，又能够提高其运行效率。
模拟退火算法
在金属热加工工艺中，退火是指将金属材料加热到某一高温状态，然后让其慢慢冷却下来如此一个金属热处置进程。
从统计热力学的观点来讲，随着温度的降低，物质的能量将慢慢趋近于一个较低的状态，并最终达到某种平稳。
模拟退火算法（SimulatedAnnealing）确实是基于金属退火的机理而成立起的一种全局最优化方式，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。
模拟退火算法的组成要素如下：
1．搜索空间
搜索空间也称为状态空间，它由可行解的集合所组成，其中一个状态x就代表一个可行解。
2．能量函数E（x）
能量函数也确实是需要进行优化计算的目标函数所求的最优解。
3．状态转移规那么P
状态转移规那么是指从一个状态xold（一个可行解）向另一个状态xnew（另一个可行解）的转移概率，它与当前的温度参数T有关。
4．冷却进度表T（t）
冷却进度表是指从某一高温状态To向低温状态冷却时的降温治理表。
假设时刻t的温度用T（t）来表示，那么经典模拟退火算法的降温方式为：
而快速模拟退火算法的降温方式为：
这两种方式都能够使得模拟退火算法收敛于全局最小点。
另外，在实际应用中，为计算简便起见，也可用下式来进行温度治理：
式中，k为略小于的系数。
假设图所示为某一能量函数的描述图形。
若是搜索进程陷入局部最优势A，假设要使搜索进程离开那个局部员优势而抵达C点，那么必需使系统至少要具有B点所对应的能量。
亦即，那个地址必需许诺能量函数值能够一时增大。
假设在状态xold时，系统受到某种扰动而可能会使其状态变成xnew。
与此相对应，系统的能量也可能会从E（xold）变成E（xnew），系统由状态xold变成状态xnew的同意概率可由下面的Meteopolis规那么来确信：
上式的含义是：
当新状态使系统的能量函数值减少时，系统必然同意那个新的状态；而当新状态使系统的能量函数值增加时，系统也以某一概率同意那个新的状态。
固定温度参数T，反复进行状态转移进程，接收概率p（x）将服从Gibbs散布：
式中，Z是使概率值正规化的系数。
由上式可见，随着温度参数T的减小，接收概率也慢慢减小，即能量函数增大的可能性也慢慢减小，最后系统会收敛于某一能量最小的状态，该状态就可作为目标函数的全局最小值。
模拟退火算法可描述如下：
算法SimulatedAnnealing
①随机产生一个初始最优势，以它作为当前最优势，并计算目标函数值。
②设置初始温度：
T=To。
③设置循环计数器初值：
t=1。
④对当前最优势作一随机变更,产生一新的最优势。
计算新的目标函数值，并计算目标函数值的增量D。
⑤若是D＜0，那么同意该新产生的最优势为当前员优势；
若是D＞0，那么以概率p=exp（-D/T）同意该新产生的愚优势为当前最优势。
⑥若是t＜终止步效，那么：
t=t+1，转向第④步。
⑦若是未抵达冷却状态，那么：
T=T（t）转向第③步；
若是已抵达冷却状态，那么：
输出当前最优势，计算终止。
遗传模拟退火算法
遗传模拟退火算法是将遗传算法与模拟退火算法相结合而组成的一种优化算法。
遗传算法的局部搜索能力较差、但把握搜索进程整体的能力较强；
而模拟退火算法具有较强的局部搜索能力，并能使搜索进程幸免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索进程进入最有希望的搜索区域。
若是将遗传算法与模拟退火算法相结合，相互扬长避短，那么有可能开发出性能优良的新的全局搜索算法，这确实是遗传模拟退火算法的大体思想。
与大体遗传算法的整体运行进程相类似，遗传模拟退火算法也是从一组随机产生的初始解（初始群体）开始全局最优解的搜索进程，它先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的各个个体进行模拟退火进程，以其结果作为下一代群体中的个体。
那个运行进程反复迭代地进行，直到知足某个终止条件为止。
遗传模拟退火算法可描述如下：
算法GeneticSimulatedAnnealing
①进化代数计数器初始化：
t=0;
②随机产生初始群体P（t）。
③评判群体P（t）的适应度。
④个体交叉操作：
P’（t）=Crossover[P（t）]
⑤个体变异操作：
P’’（t）=Mutation[P（t）]
⑥个体模拟退火操作：
P’’’（t）=SimulatedAnnealing[P’’（t）]
⑦评判群体P’’’（t）的适应度。
⑧个体选择、复制操作：
P（t+1）=Reproduction[P（t）∪P’’’（t）]
⑨终止条件判定。
假设不知足终止条件，那么:
t=t+1，转到第④步，继续进化进程；假设知足终止条件．那么:
输出当前最优个体，算法终止。
上面那个算法是在遗传算法的运行进程中溶入了模拟退火算法的思想。
另一种构造混合遗传算法的方式是在模拟退火算法中引入遗传算法的思想。
例如，Mathefoud所开发出的一种称为并行组合模拟退火的算法PRSA（ParallelRecombinationSimulatedAnnealing）就用于这种类型，其大体思想是在模拟退火算法的运行进程中溶入遗传算法中群体和交叉操作的概念。
该算法可描述如下：
算法PRSA
①随机生成含有M个个体的初始群体P（0）。
②设置初始温度参数：
T=Tmax
③对P（t）中的各个个体进行随机配对，对其中的每一对个体做下述处置：
进行交叉和变异运算，由两个父代个体P1、P2生成两个子代个体c1和c2。
对由父代个体和子代个体所组成的两个个体组P1和c1，P2和c2，以概率p同意父代个体为下一代群体中的个体，以概率（1-p）同意子代个体为下一代群体中的个体。
其中，
式中，fp和fc别离为父代个体和子代个体所对应的目标函数值。
④终止条件判定。
假设不知足终止条件，那么：
按降温表更新温度参效T，t=t+1，转向第③步；假设知足终止条件，那么：
输出当前最优势，算法终止。
升级会员 