第7章遗传算法及其应用.ppt

《第7章遗传算法及其应用.ppt》由会员分享，可在线阅读，更多相关《第7章遗传算法及其应用.ppt（79页珍藏版）》请在三一办公上搜索。

1、第 7 章 遗传算法及其应用,裔赢显狸幢羡怨氧词簇汽炬赔桔庄整滞题迫醚娥缄奇湛典寿去荐籍泉鸽嚣第7章遗传算法及其应用第7章遗传算法及其应用,2,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,虎阅吸尊儒釉哺没轧佑踩惑撞拢咖舟垮训轨秃材慢靛迈赞吱浇舔停吭柠挠第7章遗传算法及其应用第7章遗传算法及其应用,3,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,虾道拦勃痕锣旨喂椭存丑哗包么啦为遇葛乾棉球雁绚

2、邮涵喧诣刘抓际勿帅第7章遗传算法及其应用第7章遗传算法及其应用,4,7.1 遗传算法的产生与发展,遗传算法（genetic algorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。,维杜技洞奎咕迅狡届流譬丸盏悦缕妨打猾睛酉颓甩蛹沙脾祥馒膏壳篓宽威第7章遗传算法及其应用第7章遗传算法及其应用,5,7.1 遗传算法的产生与发展,7.1.1 遗传算法的生物背景7.1.2 遗产算法的基本思想7.1.3 遗产算法的发展历史7.1.4 设计遗产算

3、法的基本原则与内容,寡歇赘濒谚矣滴底散倔鸿樱率属具萌饿畅耍鉴忌娃蔑花钝酵蝎椅呻稍劝虐第7章遗传算法及其应用第7章遗传算法及其应用,6,7.1.1 遗传算法的生物学背景,适者生存：最适合自然环境的群体往往产生了更大的后代群体。生物进化的基本过程：,染色体(chromosome)：生物的遗传物质的主要载体。基因(gene)：扩展生物性状的遗传物质的功能单元和结构单位。基因座（locus）：染色体中基因的位置。等位基因（alleles）：基因所取的值。,凰慷骏于耸祈钡泡蹲玩健扦臂卖块集灾郡隶双弯夏匹燎湖浚岭押伊烽恰各第7章遗传算法及其应用第7章遗传算法及其应用,7,7.1.2 遗传算法的基本思想,椿

4、疵至驯敏谦调揭舱罐件踞角铝伙龄卑滔瘁恃救参溉髓虏髓沿诗杖闭酉虞第7章遗传算法及其应用第7章遗传算法及其应用,8,7.1.2 遗传算法的基本思想,遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。,惨戳衷旧抽办赏乔刚捂显夸扩铆抢摸怨腾揽眨逊矛弓肺攻沪蹋阂灯阵驳谚第7章遗传算法及其应用第7章遗传算法及其应用,9,7.1.3 遗传算法的发展历史,1962年，Fraser提出了自然遗传算法。1965年，Holland首次提出了人工遗传操作的重要性。1967年，Bagley首次提出了遗传算法这一术语。1970年，Cavicchio把遗传算法应用于模式识别中。197

5、1年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。1975年，美国J.Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。20世纪80年代以后，遗传算法进入兴盛发展时期。,辞运研帆盂摆傅谬顶善炕态瞳藩吟匿鸟寒叠歧泻奠系曹掖扔卷硼穗体缉裹第7章遗传算法及其应用第7章遗传算法及其应用,10,7.1.4 设计遗传算法的基本原则与内容,设计的基本原则：,萧耕沾被曾懂苦虞倾咸惹影售望软带殊糊赤郝孜矣围烩彭绵昂颗挨伎娄拴第7章遗传算法及其应用第7章遗传算法及其应用,11,设计的基本内容：,7.1.4 设计遗

6、传算法的基本原则与内容,留除葛烂渝霍阵脉题营夺沂秘漆诗沈徘崩戒炮谓耀婚鼎宅殉庆描拜密绘剃第7章遗传算法及其应用第7章遗传算法及其应用,12,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,夷夕出僳乘档必糊播蘸快公戮乙啸隅疯阉癸久虏仪榷移侠惧匀帅滇顷悲肖第7章遗传算法及其应用第7章遗传算法及其应用,13,7.2 遗传算法的基本算法,遗传算法的五个基本要素：参数编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定,站烘魏缄圾稚窥杭姬肺讨扒评剃拜总愁井敬梅寥搂俯淮揪烘嘶哪获度乓无第7章遗传算法及

7、其应用第7章遗传算法及其应用,14,7.2 遗传算法的基本算法,7.2.1 编码7.2.2 群体设定7.2.3 适应度函数7.2.4 选择7.2.5 交叉7.2.6 变异7.2.7 遗传算法的一般步骤,慈居旬掐祷今需靛佬鸵荷哄院坚棍剑迁绑儡胳起本萝崭蔫搁妆泥盾戎恤味第7章遗传算法及其应用第7章遗传算法及其应用,15,7.2.1 编码,位串编码,一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。,二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B=0，1上，然后在位串空间上进行遗传操作。,（1）二进制编码,蟹骡吏砌率茅爬雷饯岭际云剪抓绝喻验桃茸卉贺缸霞燕涉

8、浊婶夏姬垦韵乓第7章遗传算法及其应用第7章遗传算法及其应用,16,7.2.1 编码,(1)二进制编码（续）,优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。,缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：01111 16：10000 要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。,驱家锗仰纲粟径浴贞官眷惩拧经鹤侮仪佛辑太闯注奇宙巫蚀劳茧灶柞笺邵第7章遗传算法及其应用第7章遗传算法及其应用,17,7.2.1 编码,位串编码（2）Gray 编码,Gray编码:将二进

9、制编码通过一个变换进行转换得到的编码。,战秸黔斋曲奔锄吠毖楞扛蛛件研抱索暑钓湾榷慨舵沟焕殊浚处衡皆棺蝗惭第7章遗传算法及其应用第7章遗传算法及其应用,18,7.2.1 编码,2.实数编码,采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。,含珊鸦途硬挤扯农萄蚜宿胸粕遣氓拯齿铆恰哪枝调廷泉隘议清汹激唐陶佯第7章遗传算法及其应用第7章遗传算法及其应用,19,7.2.1 编码,3.有序串编码,有序问题：

10、目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。,4结构式编码,Goldberg等提出MessyGA(mGA)的遗传算法编码方法。,仰望宝隧箔茂效噪臂踞栽九称障甸星坡掇座蒜玉导庄诛源葬晋碳坡逸闯嘶第7章遗传算法及其应用第7章遗传算法及其应用,20,初始种群的产生,7.2.2 群体设定,（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。,沽渡稳你疤寇聂言形房繁柯羊性极似辜势驯截十潍讲橙矾频啃失猪

11、若躯吏第7章遗传算法及其应用第7章遗传算法及其应用,21,2.种群规模的确定,7.2.2 群体设定,模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。,群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。,涧翘庸膝锗夕困厉莲气耀弛鼠耻郸轻夫主菩辙礼芜掇游助羹社赖座孝栋则第7章遗传算法及其应用第7章遗传算法及其应用,22,将目标函数映射成适应度函数的方法,7.2.3 适应度函数,若目标函数为最大化问题，则 若目标函数为最小化问题，则,将目标函数转换为求最大值的形式,且保证函数值非负！,

12、若目标函数为最大化问题，则 若目标函数为最小化问题，则,晓慷甘梯地胜阑败锨疆潘板少陇铺邹腕搅向风馒酬眼枢宵床裙娇诌勤总侧第7章遗传算法及其应用第7章遗传算法及其应用,23,将目标函数映射成适应度函数的方法(续）,7.2.3 适应度函数,存在界限值预选估计困难或者不能精确估计的问题！,若目标函数为最大化问题，则 若目标函数为最小化问题，则：目标函数界限的保守估计值。,唱佑赐进扶蘑厩痢字吮邑采骆兆索酶蒸钎瘟课群袖蛊易彭罢面跋笔趁盆垢第7章遗传算法及其应用第7章遗传算法及其应用,24,适应度函数的尺度变换,在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（d

13、eceptive problem）。,7.2.3 适应度函数,过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。,停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。,适应度函数的尺度变换（fitness scaling）或者定标：对适应度函数值域的某种映射变换。,拍摩疑舷的滔菊御啼卵捌轨勘奏您痒段薯荣继藕朗瘪履燥溶蛔苇垛殊哩植第7章遗传算法及其应用第7章遗传算法及其应用,25,适应度函数的尺度变换(续）,（1）线性变换：,7.2.3 适应度函数,满足,烹襟驭极俐皱诅卧疼嗅酱芍萄树折碧级愿馁灭男够龋堵宅阻夯牙惰的颗逢第7章遗传算法及其应用第7章遗传算法及其应用,26,适应度函

14、数的尺度变换(续）,（2）幂函数变换法：,7.2.3 适应度函数,（3）指数变换法：,中黎友豹蝶讹置肘窘组啥罚恐宠俩连剿吉绕律臭示础倦纤蔼缆跺计究篮师第7章遗传算法及其应用第7章遗传算法及其应用,27,7.2.4 选择,个体选择概率分配方法 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。,普洪若卒碗配噶娶苯鳞账机卓赣烽惕扁胺抱辩蔚孙睛饵履泌谗谦壕匣耸泣第7章遗传算法及其应用第7章遗传算法及其应用,28,7.2.4 选择,个体选择概率

15、分配方法（1）适应度比例方法（fitness proportional model）或蒙特卡罗法（Monte Carlo）,各个个体被选择的概率和其适应度值成比例。,个体 被选择的概率为：,磨难彬滁颜体启阅妇筑沉帖回洗悲邦官惜灭网茎厚扇度谬椽歼庄接杆搀锗第7章遗传算法及其应用第7章遗传算法及其应用,29,7.2.4 选择,1.个体选择概率分配方法（2）排序方法（rank-based model）,线性排序：J.E.Baker,群体成员按适应值大小从好到坏依次排列：个体 按转盘式选择的方式选择父体,樊韵抛斩抱栈糠培苹秃函即蔗傀洋挪昂歹白攒离施置弓窟宇诽埃袖岂跟刊第7章遗传算法及其应用第7章遗传算

16、法及其应用,30,7.2.4 选择,1.个体选择概率分配方法（2）排序方法（rank-based model）,非线性排序：Z.Michalewicz,将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：,溺韩弟数精彝枚棺练遣揍罢酣辰宝了佬拼喘族蚌搂怯咆命利境峨豌薛屏站第7章遗传算法及其应用第7章遗传算法及其应用,31,7.2.4 选择,1.个体选择概率分配方法（2）排序方法（rank-based model）,可用其他非线性函数来分配选择概率，只要满足以下条件：,噬昌胜戮癸定基皱盼薛赏炒疥缕圾高之堪抡帐莫桃暴撵同魔聂顺今沈僻熬第7章遗传算法及其应用第7章遗传算法及其应用,32,7.2.

17、4 选择,2.选择个体方法（1）转盘赌选择（roulette wheel selection）,按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。,第1轮产生一个随机数：0.81,第2轮产生一个随机数：0.32,鹏命仇勇疲桑瞅襟撩踏摈闹绍望燃椅簇肩猿捷磋呕柄程噶便鄂邵绝剿橱秃第7章遗传算法及其应用第7章遗传算法及其应用,33,7.2.4 选择,2.选择个体方法（2）锦标赛选择方法（tournament selection model）,锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过

18、程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。,随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。,妊喘澎糊排朴沃犯哼拾喇掸鲁眼鸳疑称匝帜葫矣沫疆灵逝泅礼晕茎柿州餐第7章遗传算法及其应用第7章遗传算法及其应用,34,7.2.4 选择,2.选择个体方法（3）和 选择,从规模为 的群体中随机选取个体通过重组和变异生成 个后代，再选取 个最优的后代作为新一代种群。,从 个后代与其父体共 中选取 个最优的后代。,沫聊蔬霍冷简取涂桅找蔓岸萌跌迢值氓却衰础淬拟牛颐悸泅擞籽吹臃牧废第7章

19、遗传算法及其应用第7章遗传算法及其应用,35,7.2.4 选择,2.选择个体方法（4）Boltzmann锦标赛选择,最佳个体（elitist model）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。,（5）最佳个体保存方法,随机选取两个个体，若 则选择适应值好的作为胜者，否则计算概率，若，选择差解，否则选择好解。,惟恐恳射著黎戮颂崎嚷鸡涅波惩恶瞄摹账山诅舔砧捣畴湃绥惋垛扑慕怜弄第7章遗传算法及其应用第7章遗传算法及其应用,36,7.2.5 交叉,1.基本的交叉算子（1）一点交叉（single-point

20、crossover）,一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。,二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。,（2）二点交叉（two-point crossover）,查室济作亨义翁区范愁猾爽傣揍昏簿抒呜寇狮肯九柴届甜此炬他吃狼抗讼第7章遗传算法及其应用第7章遗传算法及其应用,37,7.2.5 交叉,基本的交叉算子（续）,均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。,（3）均匀交叉（uniform crossover）或一致交叉

21、,娄倒驴衙虞剁汐矛嫂譬慷疽在由盎助振庐评浇银赫缺韵残霉撑潭粟金疗举第7章遗传算法及其应用第7章遗传算法及其应用,38,7.2.5 交叉,2.修正的交叉方法（1）部分匹配交叉PMX：Goldberg D.E.和R.Lingle(1985),凛顾慷压项商磋许谆砧舵贬逊硬厢局拣嘉棕澜侨主镐庆赦辑鸽浙日僧捷锚第7章遗传算法及其应用第7章遗传算法及其应用,39,7.2.5 交叉,2.修正的交叉方法(续）（2）顺序交叉OX：Davis L.(1985),（3）循环交叉CX：Smith D.(1985),舜续世啪透杆阻早伺鞠厢艺捣满淄彝妻仪君彦直娘豆刽特鼎斌小椒先迂挤第7章遗传算法及其应用第7章遗传算法及其

22、应用,40,7.2.5 交叉,3.实数编码的交叉方法（1）离散交叉（discrete crossover）,部分离散交叉：在父解向量中选择一部分分量，然后交换这些分量。二进制的点式交叉,整体离散交叉：以0.5的概率交换父体 的所有分量。二进制编码的均匀性交叉,跨泳障俱栖袍钉眶自蛊届玲因箔溉颐鸦寥绝盏杆钠讲丫氧两诀迂即搂婪铆第7章遗传算法及其应用第7章遗传算法及其应用,41,7.2.5 交叉,3.实数编码的交叉方法（续）（2）算术交叉（arithmetical crossover）,部分算术：先在父解向量中选择一部分分量，如第 个分量以后的所有分量，然后生成 个0，1区间的随机数，并将两个后代定

23、义为：,伟误驱摩散孵激竭辫痪滓镑狂疮卖旋置杀历婉磕世威还异边詹档娥缅衣擎第7章遗传算法及其应用第7章遗传算法及其应用,42,7.2.5 交叉,3.实数编码的交叉方法（续）（2）算术交叉（arithmetical crossover）,整体算术交叉：先生成 n 个区间的随机数，则后代分别定义为：,赋狰腊龚鄙遮余非起晦噎辫溉敝隆注哮丛绷毅弃裳阂酵狮叮缠莹恫烃掂龋第7章遗传算法及其应用第7章遗传算法及其应用,43,7.2.6 变异,1.整数编码的变异方法（1）位点变异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。,（2）逆转变异：在个体码串中随机选择两点（逆转

24、点），然后将两点之间的基因值以逆向排序插入到原位置中。,（3）插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。,仍拨恕耪掐岭谓埠票八授主办娘阜谁旭闲匣淬辉用剪戈卯训苟选钳滨勉娇第7章遗传算法及其应用第7章遗传算法及其应用,44,7.2.6 变异,1.整数编码的变异方法（续）（4）互换变异：随机选取染色体的两个基因进行简单互换。（5）移动变异：随机选取一个基因，向左或者向右移动一个随机位数。（6）自适应变异：类似于位点变异，但变异概率随群体中个体的多样性程度而自适应调整。,流漾欺镜渍初囊尼吃云邀震保狂神启劫怖嗣豫跳蔽瑶芹耍宰未肺筑杂剐黔第7章遗传算法及其应用第7章遗传算

25、法及其应用,45,7.2.6 变异,2.实数编码的变异方法（1）均匀性变异,均匀性变异：在父解向量中随机地选择一个分量（第 个），然后在 中以均匀概率随机选择 代替 以得到，即,按捧卤奏神索仗哎灵汾铸串雷锯旅谐锦萝拎缎辈睁墓菩最程近钉城皿屑夯第7章遗传算法及其应用第7章遗传算法及其应用,46,7.2.6 变异,2.实数编码的变异方法（续）（2）正态性变异（normal distributed mutation）,蔽牵懊乳揉情贝券别特郝颐蜕扭坊隋辙遥艘嫩嚎疫壳罪峡尹青扳鹊恢兄瓶第7章遗传算法及其应用第7章遗传算法及其应用,47,7.2.6 变异,2.实数编码的变异方法（续）（3）非一致性变异,Z

26、.Michalewicz首先提出将变异算子的结果与演化代数联系起来。在演化初期，变异范围相对较大，而随着演化的推进，变异范围越来越小，起着一种对演化系统的微调作用。,舶醉鲁淑磁痹痊筐鬼价胳畅稍陵蚤菏讣沸芯仆派衬证碑掏益氯殴初各误芽第7章遗传算法及其应用第7章遗传算法及其应用,48,7.2.6 变异,2.实数编码的变异方法（续）（3）非一致性变异,瓷耳陵噪撤包崩漫骏断购汛竭捅洞究臭碰琴正粟咀克萍舱汕致撅躯乳卞婶第7章遗传算法及其应用第7章遗传算法及其应用,49,7.2.6 变异,2.实数编码的变异方法（续）（4）自适应变异,自适应变异方式与非一致性变异算子相同，只是将其中的演化代数 改为，函数表

27、达式变为：,促娇蒸兵诡抽题第慕彩砸阻硒流齿剔氰郝啼割柳幂借拍钨浪信镭纫啤芦奄第7章遗传算法及其应用第7章遗传算法及其应用,50,7.2.7 遗传算法的一般步骤,技尊恼没步东拓黔清鲸客迂遍攒捍肛刚玻越瑚手碟层弧契艰礁疹琅溢绅彬第7章遗传算法及其应用第7章遗传算法及其应用,51,7.2.7 遗传算法的一般步骤,（1）使用随机方法或者其它方法，产生一个有N个染色 体的初始群体 pop(1)，；,（3）若满足停止条件，则算法停止；否则，以概率 从pop(t)中随机选择一些染色体构成一个新种群,嘴哑截孪僵靳么挚吝后龄陡杀劳郭厢斡嗽曝挪衣晌建啡裹疮尖庸素伟服浩第7章遗传算法及其应用第7章遗传算法及其应用,

28、52,7.2.7 遗传算法的一般步骤,（4）以概率 进行交叉产生一些新的染色体，得到一个新的群体,（5）以一个较小的概率 使染色体的一个基因发生变异，形成；，成为一个新的群体 返回（2）。,卉符湃务揣皑尺哉座腹休晶扇引信醉扯枫佣语腹备熟钉舜烦牺禽韩极崎辨第7章遗传算法及其应用第7章遗传算法及其应用,53,7.2.8 遗传算法的特点,可直接对结构对象进行操作。利用随机技术指导对一个被编码的参数空间进行高效率搜索。采用群体搜索策略，易于并行化。仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。,持园抛辜蒙李靳目闽陈运果确妊列活藕倚蝎命盛祸血锰以哄梧州靳偶帚腰第7章

29、遗传算法及其应用第7章遗传算法及其应用,54,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,破被晚投酥胁诊枚峦吞石宴抽颊怪浇撅训分牲钱绷认到访颊缆厩萍更貌撰第7章遗传算法及其应用第7章遗传算法及其应用,55,7.3 遗传算法的改进算法,7.3.1 双倍体遗传算法7.3.2 双种群遗传算法7.3.3 自适应遗传算法,篮惩哑馆赋谱瘟乏勇斌曾纬药翱孩诊爸见寄彤悄交妒蹄工虏棠疚捏如旷看第7章遗传算法及其应用第7章遗传算法及其应用,56,7.3.1 双倍体遗传算法,1.基本思想 双倍体遗传算法采用显性和

30、隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。双倍体遗传算法采用显性遗传。,双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。,顿户尝呐莲唆犊笛童甚拐柴嫉厄撇胞毒畏猩狂斌惠专隆校烹产藤派悟演懈第7章遗传算法及其应用第7章遗传算法及其应用,57,7.3.1 双倍体遗传算法,2.双倍体遗传算法的设计,（1）编码/解码：两个染色体（显性、隐性）（2）复制算子：计算显性染色体的适应度，按照显性染色体 的复制概率将个体复制到下一代群体中。（3）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。（4）变异算子：个体的显性染色体按

31、正常的变异概率变异；隐性染色体按较大的变异概率变异。（5）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。,告委邻憎廊寡矫给呀诲沟砂省哺捣轧姜秆剩惰阉豌资趋邻首庞浸促娜呸习第7章遗传算法及其应用第7章遗传算法及其应用,58,双种群遗传算法程序流程图,母陡碘豁涤屿明凡廉幸评马蔚捆喷覆手哥焕湘金隆稍谋辆啄迅潜下明坏慌第7章遗传算法及其应用第7章遗传算法及其应用,59,7.3.2 双种群遗传算法,基本思想 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。多种群

32、遗传算法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。,炽恬启炭详夷喝叶童灿啥缘前膛恃芭播萍聚流蕉昂沉浆朴粹腔锐行浩肪使第7章遗传算法及其应用第7章遗传算法及其应用,60,7.3.2 双种群遗传算法,2.双种群遗传算法的设计（1）编码/解码设计（2）交叉算子、变异算子（3）杂交算子,设种群A与种群B，当A与B种群都完成了选择、交叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。,解傣躺萤鲸峰铀兜潭傻雾缴祝柱疡莲僻竖蕾漫栗

33、辫豺涣泛甫千裳解这铭貉第7章遗传算法及其应用第7章遗传算法及其应用,61,7.3.3 自适应遗传算法,1.基本思想,Srinvivas M.，Patnaik L.M.等在1994年提出一种自适应遗传算法(adaptive genetic algorithms，AGA)：能随适应度自动改变。,AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使 增加，以跳出局部最优；而当群体适应度比较分散时，使 减少，以利于优良个体的生存。,同时，对于适应度高于群体平均适应值的个体，选择较低的，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的 值，使该解被淘汰。,衔嫉抑椰汰溉杠捣沿鞋谰翔菱灭茎

34、汀歧觅艾湖漱咨巢杀荆琴靡宜苏委常芜第7章遗传算法及其应用第7章遗传算法及其应用,62,7.3.3 自适应遗传算法,2.自适应遗传算法的步骤（1）编码/解码设计。（2）初始种群产生：N（N 是偶数）个候选解，组成初始解集。（3）定义适应度函数为，计算适应度。（4）按轮盘赌规则选择N 个个体，计算。（5）将群体中的各个个体随机搭配成对，共组成N/2对，对每一对个体，按照自适应公式计算自适应交叉概率，随机产生R(0,1)，如果 则对该对染色体进行交叉操作。,砍烟涤搞碱虑搅斯簿吕颅膜婴蕴精暂咕搀讲憋序秽菜蠢已抽湃饭隧譬如镜第7章遗传算法及其应用第7章遗传算法及其应用,63,2.自适应遗传算法的步骤（续

35、）（6）对于群体中的所有个体，共N个，按照自适应变异公式计算自适应变异概率，随机产生 R(0,1)，如果 则对该染色体进行交叉操作。（7）计算由交叉和变异生成新个体的适应度，新个体与父代一起构成新群体。（8）判断是否达到预定的迭代次数，是则结束；否则转（4）。,7.3.3 自适应遗传算法,扫俄系溪诬橡献揩唾沃善南怜儒疏耐裳迭涛泣毛畸魂丸碱煮丰佣凄扣颧痢第7章遗传算法及其应用第7章遗传算法及其应用,64,3.适应的交叉概率与变异概率,7.3.3 自适应遗传算法,普通自适应算法中，当个体适应度值越接近最大适应度值时，交叉概率与变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。,改进的思

36、想：当前代的最优个体不被破坏，仍然保留（最优保存策略）；但较优个体要对应于更高的交叉概率与变异概率。,皂叮混则惠刨绎稚宰丘碍踌挫芬腮甫摩喂华钵嵌啮淤狂循钉堆戈堂酝绕估第7章遗传算法及其应用第7章遗传算法及其应用,65,F自适应方法：,7.3.3 自适应遗传算法,3.自适应的交叉概率与变异概率（续）,纯腹疗栏标骋凑皋鲤里陷畸甚溃殆厩屎漾峭槛冷亚嚷逮洛搁寿竿狈仍茁旦第7章遗传算法及其应用第7章遗传算法及其应用,66,7.3.3 自适应遗传算法,S自适应方法：,自适应的交叉概率与变异概率（续）,劳畴测额囊宏刹匝懒宋尾浴引器纷虏装萌馁袭卓能荷兑屡埠惕品僻诈捣声第7章遗传算法及其应用第7章遗传算法及其应

37、用,67,7.3.3 自适应遗传算法,自适应的交叉概率与变异概率（续）,C 自适应方法：,类绎坦产盼括序炯仙颇拓艇材岳验栅奇左眉怀矢共翻什永卧虚筋贞卫惧宠第7章遗传算法及其应用第7章遗传算法及其应用,68,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,诡噬骗结仲铃首冯巍煤睦诀鹅可信幻猜佩诚巍奎散蓉规诸蕉佳瘤面虹熙又第7章遗传算法及其应用第7章遗传算法及其应用,69,7.4 基于遗传算法的生产调度方法,7.4.1 基于遗传算法的流水车间调度方法,哄拼倍托弱灰俏吧窘扯盆崔疙率牺吾碍笆友盛畸祁筹英冶

38、卡挟氏撒状谓挖第7章遗传算法及其应用第7章遗传算法及其应用,70,1.流水车间调度问题,问题描述：n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为,问题的目标：确定 n 个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。,7.4.1 基于遗传算法的流水车间调度方法,厂咸滔阻埔蒙屎紊眩马谋碌雀烟殊扮讨瞥舍喧亢滩涵平夹含晤栗侵阉捎雕第7章遗传算法及其应用第7章遗传算法及其应用,71,1.流水车间调度问题,假设：(1)每个工件在机器上的加工顺序是给定的。(2)每台机器同时只能

39、加工一个工件。(3)一个工件不能同时在不同的机器上加工。(4)工序不能预定。(5)工序的准备时间与顺序无关，且包含在加工时间中。(6)工件在每台机器上的加工顺序相同，且是确定的。,7.4.1 基于遗传算法的流水车间调度方法,第耐伦岂搔兆芳颇账琴揉荫乱腰氖湖国送记苹裳凌辅伎桔痪汰姿梧佐妥酱第7章遗传算法及其应用第7章遗传算法及其应用,72,1.流水车间调度问题,7.4.1 基于遗传算法的流水车间调度方法,问题的数学模型：,个工件、台机器的流水车间调度问题的完工时间：,工件,续椒泉惭蛹知躬膳感甚爹华执誊累钮范只艇谭砰寥遏罐辟谭账豺矢浩可垂第7章遗传算法及其应用第7章遗传算法及其应用,73,2.求解

40、流水车间调度问题的遗传算法设计,（1）FSP的编码方法 对于FSP，最自然的编码方式是用染色体表示工件的顺序。,7.4.1 基于遗传算法的流水车间调度方法,对于有四个工件的FSP，第 个染色体，表示工件的加工顺序为：。,喷酞陶挟感栏禄治嗽蛋馏尊掇铅涯捡雕恃捞晴太怨辣辆让为奎垒晤乍宙伙第7章遗传算法及其应用第7章遗传算法及其应用,74,2.求解流水车间调度问题的遗传算法设计,（2）FSP的适应度函数,:个染色体 的最大流程时间，FSP的适应度函数：,7.4.1 基于遗传算法的流水车间调度方法,西轧德十掀灸鸟乍支软越冲订认暇耀拾史址泥罩猎翅眷汲辆鸭舅谐薛桶轿第7章遗传算法及其应用第7章遗传算法及其

41、应用,75,求解FSP的遗传算法实例,例1 Ho 和 Chang(1991)给出的5个工件、4台机器问题。,7.4.1 基于遗传算法的流水车间调度方法,分蹿仁驳峙吕咒命够镣却掳立拓难消些诧岔吮挥怠抹甩近燕碱庚代顿涛烫第7章遗传算法及其应用第7章遗传算法及其应用,76,用遗传算法求解。选择交叉概率，变异概,种群规模为20，迭代次数。,表7.3 遗传算法运行的结果,7.4.1 基于遗传算法的流水车间调度方法,用穷举法求得最优解：4-2-5-1-3，加工时间：213；最劣解：1-4-2-3-5，加工时间：294；平均解的加工时间：265。,遗传算法运行的结果,厦谷策嫌涸梅佰句珐蓄咽七喻钉像细授购晕擒

42、卞吾嗽碌芳款佐柿现怒蔫吻第7章遗传算法及其应用第7章遗传算法及其应用,77,表7.3 遗传算法运行的结果,最优解收敛图,7.4.1 基于遗传算法的流水车间调度方法,欧塘封村器依以晌皖坟釉荒写篱浪贞耕榜住熔炽析立呛评仅卒驱挚琵豪极第7章遗传算法及其应用第7章遗传算法及其应用,78,平均值收敛图,7.4.1 基于遗传算法的流水车间调度方法,隙魄卡秀牟溪唆拙馒蚁铭哄拄吕账春卓允驻雪眠茧翟树浅首庸疹诛滦韧桅第7章遗传算法及其应用第7章遗传算法及其应用,79,机器甘特图,7.4.1 基于遗传算法的流水车间调度方法,吱歹砰腻刚帽厦蛛犬辅搐贤荆舆论借垒樟俞碗奄松荷焚炬经刀左惠判羽贺第7章遗传算法及其应用第7章遗传算法及其应用,