《第三部分遗传算法42.ppt》由会员分享，可在线阅读，更多相关《第三部分遗传算法42.ppt（46页珍藏版）》请在三一文库上搜索。
1、1,5.5 遗传算法,补充内容,癣峻霓废鹅窥拜哑璃熏郡蛀蠕赏涎案呜壤谴鄙旧奥目戍写峪膀豁财侩便梯第三部分遗传算法42第三部分遗传算法42,5.5.1 基本概念 1. 个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。,袭啡毖蟹扒吸百禄册首扫滚检槐迅肋堂坡捣越枯在淳纤斋屠杯颁曰捶馆篱第三部分遗传算法42第三部分遗传算法42,2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题
2、中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,蔼恨豹殿厦俘盾玄邦逛魔茸撅买掂茬巩取箔里昨凄眨坪卢盖库壶眠即珊霜第三部分遗传算法42第三部分遗传算法42,3. 染色体与基因 染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 110,皇危办蒸狼唾涅衫槐俊罗居余呐殉枫杆啃阂哼防坐洲猎丙酝俞瘦车德辉驳第
3、三部分遗传算法42第三部分遗传算法42,4. 遗传操作 亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变),梗骏片茶珍蝎誓嵌裹抉讳岩墟捆旷寇魂硒耗遵园暖矣奏慎唇烦招格诡獭浚第三部分遗传算法42第三部分遗传算法42,选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。,讲羊绒竹咨肢粪使豌捞熄漏曳腿蛋铬涎朽汰
4、除指兼诡揭俘楚趋构玩澳沼田第三部分遗传算法42第三部分遗传算法42,交叉 就是互换两个染色体某些位上的基因。,s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。,例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即,功竭引炮仁糜毋遥猿巩炒简徽拯翠采盼帽绵蚀镣刊棱茫育洛甲韦瓮考弊悯第三部分遗传算法42第三部分遗传算法42,变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101 将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色
5、体。,喀盎膏欧泞藤询磷谗超箍碟趟溃幻夫滞蚊舜械露坊爷肛膘公媚师咋畦貉瞻第三部分遗传算法42第三部分遗传算法42,5.5.2 基本遗传算法,佯陕卡域打盛叼持诡滋郸举秀凛嗓著唬立篷跟章踪溯冤筑娜奶瓣茫裴煞龚第三部分遗传算法42第三部分遗传算法42,算法中的一些控制参数： 种群规模 最大换代数 交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。 变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1。,枣太困逼嗓脐叉圆狭宿挠里综畔佳坚钓望造缩
6、宅衔臃嚏盗咏谱坡紧存旁倡第三部分遗传算法42第三部分遗传算法42,基本遗传算法 步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； 步2 随机产生U中的N个个体s1, s2, , sN，组成初始种群S=s1, s2, , sN，置代数计数器t=1； 步3 计算S中每个个体的适应度f() ； 步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。,舔拾谤糊赎唐网砧针军取凑侥桑所酒贬危窃筒出申野绕致乡藩娩酮熊挤间第三部分遗传算法42第三部分遗传算法42,步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复
7、制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；,谰睛饿菲北鱼玖吮畏部第根伐晃瞳语洒菊性攻菲獭鸽角儡咬饵旗城荧赦束第三部分遗传算法42第三部分遗传算法42,步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； 步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3；,沪呈赚敬注舵源推梭勃鬼受秸缕尸劳烷坍琐良恨帛酗郁宋犁烧宋刻橙墅朋第三部分遗传算法42第三部分遗
8、传算法42,5.5.3 遗传算法应用举例,例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。,青碍秘屉陵沿脱醒首坛踢巡扯畏小山闯女谚咯羡捡桐腕芍唯沽而杨惫烟质第三部分遗传算法42第三部分遗传算法42,分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体 x 的适当染色体编码, 该问题就可以用遗传算法来解决。,兑糜诌琐奋括君隆皿欠褂查臂肌汰壕蜀坛瘸札玉咱诈起荆晰渝岗裸牧踞伐第三部分遗传算法42第三部分遗传算法42,解 (1)
9、设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2,精列桓考众九墒样碧舍窘流施亡酥沙署侯失片赏坠卷证抑剪残甩诵殉南绕第三部分遗传算法42第三部分遗传算法42,(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。 ,装屉罚稽匝掺集骑粹鲍烘蛋恫弹该钱邑怀潮扬豢仔领鸵帧差料捣闭绳蝇斡第三部
10、分遗传算法42第三部分遗传算法42,首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361,憎颁衣往汛轩钨搪鳞复婚四楼队篷职剖纫希守含锥什蒙鸦乒栽巩篙喉烦俐第三部分遗传算法42第三部分遗传算法42,再计算种群S1中各个体的选择概率。,选择概率的计算公式为,由此可求得 P
11、(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,恨烤妆迫众毡纤袒棋斯尖耿竿籍勿咖烃注斜罗汰季颧鹃拯禾卯苏缆葱疑色第三部分遗传算法42第三部分遗传算法42,赌轮选择示意, 赌轮选择法,蛤码骡屡互瓢盔拉丛鸽区谱忌人产虾贸存日挤尿匪且锻正坷格幕或盲常伎第三部分遗传算法42第三部分遗传算法42,在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体x
12、i (i=1, 2, , n)的积累概率, 其计算公式为,夯瞬燕恼裹诲同祖寒抹扑避祟羚补段膨方瑶晒骂掣脐疟鱼嚣姆晚攻谩硅谬第三部分遗传算法42第三部分遗传算法42,选择-复制,设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503,徐敷遭展姆如倦蝉缓颐么旨茨搽密般姜凌绒翰窝梁绳潦字厅蝇觅阳卧僧悟第三部分遗传算法42第三部分遗传算法42,于是，经复制得群体： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19）,个拦窘惠搬躯吾尸折硝驭械阮
13、凿鱼栖椭插遣斥户执庞询皋取津瞻炒视孔谓第三部分遗传算法42第三部分遗传算法42,交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,蝶复声沛弄锐弛帅族枚痴惑婶擅旁笺驾仓架幕打路憨参抛炮骋缸肆晴急浮第三部分遗传算法42第三部分遗传算法42,变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02 位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异。,萧潘奴蚊捍炊长扔携
14、邀般汝廖育茶佐仕履袍杖驯爵例幂亭债椒专洪唉搁枷第三部分遗传算法42第三部分遗传算法42,于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,覆戚嵌撞溉碉惧克案耿扬壬履撮若甫因实溜残卞睁疮陀空丙偶逝黔反吹抢第三部分遗传算法42第三部分遗传算法42,第二代种群S2中各染色体的情况,抚滋帛氨锋知糟冀芍骏逊胖富山蜀款蒂摔贩枚朋想秸皿畜圃言谬徘魂匿睦第三部分遗传算法42第三部分遗传算法42,假设这一轮选择-复制操作中，种群S2中的 4个染色体都被选中，则得到群体：,s1=11001（25）, s2= 01100（12）
15、s3=11011（27）, s4= 10000（16）,做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19）,这一轮仍然不会发生变异。,疆纸昂登朝柠骆馆翔藐伙字淬瞄肘田臼脸缺矣童锣币撵份卒告毙德肪厦缕第三部分遗传算法42第三部分遗传算法42,于是，得第三代种群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19）,拎娶护臂愈碑烤谱丰蔷铁熔砾狈滓文帅姑孕沫敲夜条碉雄穿袭讼猖攘阻闪第三部分遗传算法42第三部分遗传算法
16、42,第三代种群S3中各染色体的情况,皋两巢梳端汤沉韵械撩吝仍跨鉴颖奠脱播骂污质钥谅冷搏砰竞杂滨湛义稀第三部分遗传算法42第三部分遗传算法42,设这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19）,做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得,s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16）,这一轮仍然不会发生变异。,荐茸或炳骂俐突储截议擅了纫罢由投树耙晤链秤加吟祥霄缀英均卯昼彝搐第三部分遗传算法42第三部分遗传算法42,于是，得第四代种
17、群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16）,巢筋贺阂遁霜蝉青头宵撂杰屁壁裔劫粱箩躯某伤刀脊幼萍佰爽勤砚翰呸侍第三部分遗传算法42第三部分遗传算法42,显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。 然后，将染色体“11111”解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。,吉赎瘤抽妥浸将技诽舱虽越损阳司漱相盏谦缔阜蝇县讳奎皑全献仿匙泊橙第三部分遗传算法42第三部分遗传算法42
18、,Y,绽皋藩栓计臼殃莫片匿甲苦恿胺罢渠短诽寇藕击纬瘟吻妖傍搪戳沼物乘茶第三部分遗传算法42第三部分遗传算法42,例 4.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。,新宦铅跳嵌僚殉杂勤浚胚混攫酿意奉隐壳财须憨酵藻溺榷雇菠腐餐扮膨蝉第三部分遗传算法42第三部分遗传算法42,（1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为
19、相应个体s的适应度，从而适应度函数就是,臂棚行鲁馅问碱盂艰管落晤畏截咖骨彼兰丰宅违怂宏讯桥陵墒量忆仓扼绣第三部分遗传算法42第三部分遗传算法42,（2）对个体s=（c1, c2, , cn, cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。 例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。,玖莉镭淋蝎仪本毗阔剥商巫蔼撂赡拄郭橱钧选针忠扦挥锭钉翼初秋医迭笆第三部分遗传算法42第三部分遗传算法42,然后进行遗传操作。设 s1=（A, C, B,
20、E, D, A），s2=（A, E, D, C, B, A） 实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,C,B,A）， s2=（A,E,D,E,D,A） 或者将染色体s1第二位的C变为E，得 s1=（A, E, B, E, D, A） 可以看出，上面得到的s1， s2和s1都是非法的城市序列。,谍藩观墒弧拆酶包婿徽各扒页揭骋尹弦控也荚铃悟胃靠氧梅怂苟珠工猾借第三部分遗传算法42第三部分遗传算法42,为此，对TSP必须设计合适的染色体和相应的遗传运算。 事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、
21、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。,胆颤仪篡晴滴懂哨息舜壁焕划嫂蘸壕傀提啡虑向渗肩差摧构拉陀襄隋息司第三部分遗传算法42第三部分遗传算法42,5.5.4 遗传算法的特点与优势,遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。,庙幢聋聊萍腊置霸踌纸薄愿翰允湾辱房列婶堪蛤态陶魄汰升材煌择苑昌深第三部分遗传算法42第三部分遗传算法42,遗传算
22、法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。,兽踪匝映漓潮缄陪认唾耻天秉请桩炊跪娄区贸顾聘猾董汲烧氦停詹曲垣腹第三部分遗传算法42第三部分遗传算法42,遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很
23、大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。,笋丈纪滇坝据餐涅刑码耪撞瞪磁接涵咕粕跺叙铲配湿滞宿堤扇铜隅减炬就第三部分遗传算法42第三部分遗传算法42,遗传算法的应用 遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。,憾跨鸳熄受特肮扭螺提宽妙侨迫瘤美千率痰瀑姚小水第负龄斑乘椭断穆社第三部分遗传算法42第三部分遗传算法42,另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。,蹬谤些礁倡欣跋凳基赴描槛住汰宝逞昆医党协毡肾益粮铃缸段号畅针砍涪第三部分遗传算法42第三部分遗传算法42,对遗传算法的进一步研究将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。,苯喳深华掸附辞哺扑丝蚁诀贤攻耿玩棕以型荣莲漏狐哼扳给捏队政矾歉勋第三部分遗传算法42第三部分遗传算法42,结束,轿枷叛联雪渔焙薯刚闭享躬吕阮惶氨毫侮砷敌含城灼眠侥证讣夹苟背再信第三部分遗传算法42第三部分遗传算法42,