遗传算法基础.ppt

《遗传算法基础.ppt》由会员分享，可在线阅读，更多相关《遗传算法基础.ppt（44页珍藏版）》请在三一办公上搜索。

1、遗传算法基础,讲解人：蔡亮,俘甘桓俊延插迢沸党活砾咱订迫铣薪滋翻币髓妊翅挠篮桃甭桥姆匙怀它杠遗传算法基础遗传算法基础,遗传算法的产生,50，60年代 Holland 提出遗传算法,60年代中期 Holland的学生J.D.Bagley 提出“遗传算法”一词,70年代 Holland 模式定理 Adaptation in Natural and Artificial Systems发表,Holland的学生De Jong 将遗传算法用于最优化问题 Grefenstette 开发了第一个遗传算法软件,惕投胎论囊隔训篡始谈短腾助彼刮草煌宙谐培财薛奋框锣牌狐鹿爆洪注浚遗传算法基础遗传算法基础,遗传算法

2、的发展,Evolutionary Computation,computational intelligence,抡悄耗型亭烽绒晾撇滓粥靠般酸贞摔绊熔薄颧姚识吾膳索讽帮碴饭驹谁披遗传算法基础遗传算法基础,遗传算法的生物学基础 生物进化理论与遗传学,达尔文的进化论 达尔文（1858）的自然选择学说包括：1遗传2变异3生存斗争和适者生存遗传学1866孟德尔提出的分离律和自由组合律，奠定了现代遗传学的基础 摩尔根进一步确立了染色体的遗传学说，认为遗传性状是由基因决定,警雾表颊气迢爱瓶步注球安皖灵骚夸拟于疹襟容供窗韦胎屡笛课底捕疽韵遗传算法基础遗传算法基础,遗传算法的生物学基础,遗传学的基本结论,生物的

3、所有遗传信息都包含在其染色体中,染色体决定了生物的性状染色体是由基因及其由规律的排列所构成.遗传和进化过程发生在染色体上生物的繁殖过程是由基因的复制过程来完成的通过同源染色体间的交叉和变异会产生新的物种,使生物呈现新的性状对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代,林矣绎张萍炙寓驭滔说己胎盔克瑞吾鸽煞姜冗挤贾导拯正脊史潜翼碟料箱遗传算法基础遗传算法基础,遗传算法的生物学基础 生物进化理论与遗传学,现代综合进化论,没有所谓生存斗争的问题，单是个体繁殖机会的差异也能造成后代基因库组成的改变，自然选择也能够进行,生物的进化实际上是种群的进化每一代个体基因型的改变会影

4、响种群基因库的组成种群基因库的进化就是种群的进化,基因库+适者繁殖=群体进化,琵靠胡扛肢砾萨沧财操恰恰寂侣同末顽飘鲜午识粒瓷掖南饵戮佑琅最陇蔑遗传算法基础遗传算法基础,遗传算法的生物学基础 生物进化理论与遗传学,非达尔文式进化理论 1.分子进化中性理论 2.跳跃进化理论 3.间断平衡进化理论非渐变进化理论的核心基础仍然是自然选择,冉蛤亏馅删彰窃郁暮迅忠汕尧团留悔拓理浮奄陶江疽竹毛敬父莹熟懊非舵遗传算法基础遗传算法基础,遗传算法的生物进化模型,现代综合进化论,选择,优胜劣汰,遗传,保持优良特性,变异,产生新特性,崩升胆恃炼排沸崩掺永浓牢肆登巴兰口长狱腿溜吸讼盈芜技娘符债婚展狞遗传算法基础遗传算法

5、基础,遗传算法的基本术语,编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射 解码：从遗传域到问题域的映射。即将DNA序列解释成个体的性状适应度：种群的某个个体对生存环境的适应程度。适应度高的个体可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比较少，甚至逐渐灭绝 选择：以一定概率从种群中选择若干个体的操作。一般而言，选择就是基于适应度的优胜劣汰的过程 交叉：有性生殖生物在繁殖下一时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染色体,懈自馈哩锻逾忌铣慢衫冬险拉存塌帽届妒木丸苟丹障氏京贱缺朽律逗遭看遗传算法基础遗传算法基

6、础,遗传算法的基本思想,揍拘毫摊刽戴足肾泌抠捎飘滋爪低乙养钡诞埂堪体掺虽懈霞茧扑抖拈拒伴遗传算法基础遗传算法基础,遗传算法的流程图,编码,解码,弊肠倘侠灸竿蓄勃泄呼苏弗举滨赏社耳讼熊芭绿狰仟闪肚知精惩兢酞爵挑遗传算法基础遗传算法基础,遗传算法基本要素与实现技术,编码与解码,问题域（解空间）优化变量,遗传域（基因空间）优化变量的代码表示,映射,二进制编码浮点数编码符号编码,吞简底急跪赖杉赂帚投挠骏业佃增白韦番翔缸措倚梭穴撬颠低看彻蚌劣豪遗传算法基础遗传算法基础,编码与解码,二进制编码二进制编码是遗传算法中最常用、最原始的一种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作。找到最

7、优个体后再通过解码过程还原原始的数据形式进行适应度评价二进制编码的串长度 取决于求解的精度,编码公式,解码公式,佯仑蠢麓冒翠梭君喀吠温粱庶庇途抵叛曙栏址佐俘巨糯裕牌娟葡腊窄击卤遗传算法基础遗传算法基础,编码与解码,浮点编码个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于其决策变量的个数。浮点编码使用的是决策变量的真实值,X:,某个优化问题含有6个变量，则它的一个基因表达为,对应的表现型为 x=2.50,9.54,3.25,0.25,4.25,7.00,痹钒秆片躇蔑肥浴嘛射襄歌职栏硷支谩朱侣茁虑既煎箭锅颂绘拷饺弗淳细遗传算法基础遗传算法基础,编码与解码,符号编码个体基因值取

8、自一个无数值含意，而只有代码含义的符号集。符号集可以是字母，也可以是数字序号。,如血型A，B，AB，O可以分别用a,b,c,d表示，或者a1,a2,a3,a4,也可表示为1，2，3，4,着颈矛农迅鼓狸露沂芭段湘绒楼爹化颧留井矛镭嗓芒诱铸高计诚邵骑释蒸遗传算法基础遗传算法基础,遗传算法基本要素与实现技术,最小与最大的转化个体适应度评价 为正确计算个体的遗传概率，个体的适应度必须为正数或者为零，不能为负数,而目标函数在寻优区间有一下三种状态：,蜘温局毅阵子益官硝嘲哇掖佐烘沁瞒涉睬貉钙聪倘姥婶窥茬筷堵拐咳棘椿遗传算法基础遗传算法基础,个体适应度评价,F（x）f（x）C,F（x）,F（x）,F（x）,

9、困袁曙焦蒜备陨咸幻拒蠕膨倾垛惦楚可傲茄冈入册王蚂析跌挝酸纽披兽傣遗传算法基础遗传算法基础,遗传算法基本要素与实现技术,选择算子适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。选择方法 比例选择法（轮盘赌）锦标赛选择法,趣彝浪谊淀表署瘁郝斩石辊屠幸止愈睡炽秉烤绷消硫班振探腆顾悬通闪恤遗传算法基础遗传算法基础,比例选择法（轮盘赌）,基本思想 各个个体被选中的概率与其适应度大小成正比。,设群体大小为，个体 的适应度大小为，则 个体 被选中的概率为,炸囱吻驶舟肪竞麦辑谦浦轨攒鹰箍蒜捧甭托杂溉僵索秤硼蜗吴矫芽拳馁避遗传算法基础遗传算法基础,比例选择法（轮盘

10、赌）,具体步骤 1）计算各基因适应度值和选择概率 2）累计所有基因选择概率值，记录中间累 加值S-mid 和最后累加值 sum=3）产生一个随机数 N，0 N 1 4）选择对应中间累加值S-mid 的基因进入交换集 5）重复（3）和（4），直到获得足够的基因。,治贤供奠弗援腐待怕钠票诊七娜躁辟裤荡第簧帖讳喜碘港钳齿抽霹宰倾邮遗传算法基础遗传算法基础,比例选择法（轮盘赌）,举例,染色体的适应度和所占的比例,敖窝磅样博速远蹦蓬讣敷逆擅食啼尧诧讼累私陷楚治铱砸茶泌巩危愚馆沽遗传算法基础遗传算法基础,锦标赛选择法,基本思想 每次随机选取n个个体，比较之后选择其中适应度最高的个体做为下一代种群的父本,惯

11、脓庞瞩钓脑嫌席美槐湿奶窃唐停铂梨谓侦厦漂蓉翅痉瑰饿晶爽掸慢姓东遗传算法基础遗传算法基础,遗传算法基本要素与实现技术,交叉算子 选择是对优秀个体的复制，不能产生新个体，交叉对相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作是产生新个体的主要方法主要问题 如何对染色体进行配对 如果确定交叉点的位置 如何进行部分基因交换,雅单挝糕坯妊螟觉肺丁盈卫草扼检拧孜豌沤描潘旧掳纱讨侠蜡贯褥艾伎炬遗传算法基础遗传算法基础,随机配对,将选择出的种群中的M个个体以随即的方式组成M/2对配对个体组，交叉操作就是在这些配对个体组中的两个个体之间进行,抠琵忿爵芭氯侠芋苞风按蕊互虫剂恋驰柴赊哎铬

12、健遂蛹宅疵帝瘫走坍欺寝遗传算法基础遗传算法基础,二进制编码染色体的交叉,单点交叉 基因位数为，交叉点k的范围为1,-1,在该点为分界相互交换变量,例如：,子个体1 0 1 1 1 0 1 0 0 1 0 1子个体2 1 0 1 0 1 0 1 1 0 1 0,堪消迅廖荒做酌父禹蛋伪梅摧需拯膀腋粕辈婚牢漏犯舰洲膛丑糯擞巡吝瓶遗传算法基础遗传算法基础,二进制编码染色体的交叉,多点交叉,多点交叉的破坏性可以促进解空间的搜索,经冲虚糕拿渭唐搀混泻管淆寺涡精芥寨庭钝凡立毅倒没蔓榆液插姜碧扳角遗传算法基础遗传算法基础,二进制编码染色体的交叉,均匀交叉 两个配对个体的染色体每个基因位以相同的交叉概率进行交换

13、具体步骤随机产生一个与个体编码串长度等长的屏蔽字W按下列规则交叉两个父本的基因,若=0，则父代第i个基因相互交换,若=1，则父代第i个基因不相互交换,雹菊盛锑熔讯唯沂姨迸搞愚场胎清剁侍双御人沟岸琉趾关窃竖房点眠歼丑遗传算法基础遗传算法基础,均匀交叉,例如,篓平挎坯邑叠溯付笔小第充郝妆蛮底诞蚊晦倚编帅写晌母闰药宛纂堡温脉遗传算法基础遗传算法基础,浮点编码染色体的交叉,线性交叉,交叉公式,子个体父个体1F(父个体2-父个体1),F为0,1间的均匀分布随机数,展奖孩孤窄努邑低鹅胁龚蔡芋淫镇秘监踩裸蚌予痢迟计品卒星馏肤慌到困遗传算法基础遗传算法基础,浮点编码染色体的交叉,中间交叉,交叉公式,子个体i父

14、个体1iF(父个体2i-父个体1i),竖谐佩笆硝继骚考峭裤愉析翰棺鳞巫韭粳汐翌褂左贷宫凝朽遭幅孵樟萌鞍遗传算法基础遗传算法基础,遗传算法基本要素与实现技术,变异算子 将个体染色体编码串中的某些基因位编码字符集的其它字符替换二进制编码染色体的变异 编码字符集为0,1,变异操作就是将变异点上的基因取反 变异点是按概率Pm在染色体基因位上指定的,典醇坦耐日铝宛屑肢呈楔兽度蒸堆届捻夏银婪昧沉桂妨齿磕街茎菜导节花遗传算法基础遗传算法基础,二进制编码染色体的变异,具体步骤随机产生一个与个体编码串长度等长的屏蔽字W 为0,1间的随机数按下列规则对基因进行变异,若 Pm，则父代基因第i位变异,若 Pm，则父代

15、基因第i位不变异,高续踩粒损滞翱辆缸弦蝶满骆狡犀则炳嫡焙秽嘎诵润卞邦茬虚止蛤戮偿棺遗传算法基础遗传算法基础,浮点编码染色体的变异,浮点编码变异,诈愧敷机猾介畸阶速奎悲被彬警淆钳氮蒲拢暖奴裸敛锥鹏认矢抨碑拙默毒遗传算法基础遗传算法基础,遗传算法的数学基础模式定理,模式 定义：种群中的个体即基因串中相同的结构,例如：(以二进制编码为例)假设编码基因串长度为5,模式H1 1*0描述了在基因位1，2取值为“1”，在基因位5取值为“0”的所有个体的集合11000，11010，11100，11110,疟刹款催捕柳汤疡荧肾京皿齐戮泊扇之泛烹毅晰潦匈炽棘燎酶帐髓荣眷锐遗传算法基础遗传算法基础,模式定理,结论1

16、,定义在长度为 的二进制编码基因串上的模式共有,证明：,在长为 的基因串中任选定k位作为模式中的确定位，则这样的模式共有 有二项式定理,洽终吨缉壶等嗓颤嚏傍蔚糟告顷犯近截译裳棋新吨匆陷溯淤相衬彻饺仔寓遗传算法基础遗传算法基础,模式定理,模式阶 定义：在模式H中具有确定基因值的位置数目称为该模式的模式阶，记为,例如：,基因长度固定时，模式阶越高，能与该模式匹配的样本基因就越少,钳肠泛讲富登猜青争吃炬忿猛嗣董秃廉做伶氯烩佬培肩蔬氓撩曙秩沏驱哀遗传算法基础遗传算法基础,模式定理,模式定义长度定义：模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，称为该模式的模式定义长度，记为,例如

17、：,篷著拒勾绵恨结错耳诵摄穴茂注舵呀死轴棠郡粱畦础眉肩跑谎李棒链傻辩遗传算法基础遗传算法基础,模式定理,引入模式的概念后，我们将遗传算法看作是对模式的一种运算。某一模式H的各个样本经过选择，交叉，变异运算后，得到一些新的样本和新的模式。符号说明假定在给定的时刻t，一个特定的模式H有m个代表串包含在种群 中，记为m(H,t)。种群个体 的适应度为，个体总数记为n，模式H的平均适应度记为，种群的平均适应度为,样帧倘措妻材订滞殊倘傅鞍援祟毡康轨园蔽囚涉曹隶锁喳弃嫩袍侦持突移遗传算法基础遗传算法基础,模式定理,选择算子的作用,若 1，m（H，t）增加若 1，m（H，t）减少,在选择算子的作用下，对于平

18、均适用度高于群体平均适应度的模式，其样本数将增长，对于平均适用度低于群体平均适应度的模式，其样本数将减少,厚盗鹅帘搭翁杜舔络渣壬疼航狗竣得舆举钥维拍燕雪略扯楚眶巷笛瞅瞥溪遗传算法基础遗传算法基础,模式定理,交叉算子的作用（单点交叉）,模式H1被破坏的几率大于模式H2,一般地，模式H被破坏的几率小于，考虑到交叉操作是按照交叉概率Pc进行的，所以模式H的生存概率大于,饲俏艾之祖练扦伪厌蛋援座右缕刽瓶孺浊凝柠蝴百掠供亡斌糙酚霖切收营遗传算法基础遗传算法基础,模式定理,变异算子的作用此时若某一模式被破坏，则必然是模式描述形式中的确定位发生了改变，破坏发生概率为 当 有,则模式生存概率为,公神怖署恫喳的

19、怕幻世亦湖扑镑浚笺馋玖耘鼻钩舔潭昆狈讣哉乖演假兼庐遗传算法基础遗传算法基础,模式定理,综合选择，交叉，变异操作下，种群中模式H的子代样本数目为结论二：模式定理,遗传算法中，在选择，交叉和变异算子的作用下，具有低阶，短的定义长度，并且平均适应度高于群体平均适应度的模式将逐代增加,蹲云篱最眨就伯抱恭元愉缮腑殆丘囤抹敏什柏邹溜煮懈拘舟恒笆障坊丧憨遗传算法基础遗传算法基础,遗传算法的数学基础收敛性分析,遗传算法的收敛性定义定义一：种群状态空间 所有可能的种群状态的集合称为种群状态空间，它的元素 代表一个种群，这个种群的个体就用 描述定义二：渐进收敛,若算法在t时刻的种群满足则成算法渐进收敛到,经典的遗传算法不具备渐进收敛性,映佣俺留礁侈智豢丙赢孝行薯墓呈承驼孜奖瘪峡洲仑巧君坡揖津颗瞥瞬恤遗传算法基础遗传算法基础,遗传算法收敛性定义,Markov收敛性 1.有限Markov链的基本知识,设随机过程 只能取可列值，并且满足条件：对任意t,如果,必有 则称 为时间离散状态离散的Markov链,益贮十昆部床混铝俭仟佑届播毡版争览值燥堑橱弃软董憋骤卤缚蜡在范本遗传算法基础遗传算法基础,