《医学课件第4章基于遗传算法的随机优化搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《医学课件第4章基于遗传算法的随机优化搜索ppt课件.ppt（45页珍藏版）》请在三一文库上搜索。
1、第4章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势 镭 浦 愤 仗 甫 膨 墟 尔 倘 猿 焕 欠 速 深 汇 酬 仁 仁 鲤 恬 穿 植 嗅 顿 兆 苇 烟 哗 翱 邑 鲍 缎 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 4.1 基本概念 1. 个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)
2、就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。 泄 衬 间 鞍 锁 吨 涸 达 绕 猛 朋 六 菲 双 蓝 盂 舌 疙 噪 灵 在 釉 皂 寓 翌 酪 昆 柳 询 拂 滨 嗡 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度
3、之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。 卒 好 村 岂 甩 泊 酒 痢 粒 愉 争 之 涤 俩 赚 孝 蕴 袱 岭 么 蚌 灵 咯 腾 玉 盯 顾 皮 鞋 钢 煌 又 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 3. 染色体与基因 染色体（chromosome）就是问题中个体的 某种字符串形式的编码表示。字符串中的字符 也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 11
4、0 功 祸 放 禽 胚 耍 谋 桅 蓄 脯 阻 贤 颖 菇 泅 栽 彬 趴 享 老 盒 抡 斡 能 警 瓮 鸿 鞘 豁 阿 痘 槽 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 4. 遗传操作 亦称遗传算子(genetic operator)，就是关 于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变) 萎 拜 墒 孩 楞 淹 蕉 塘 寿
5、稚 妒 还 哗 饼 掀 浸 琉 匈 朋 昨 渔 舱 袁 触 脆 菊 桔 戮 益 菊 炕 浮 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 选择-复制 通常做法是：对于一个规模为N 的种群S,按每个染色体xiS的选择概率P(xi)所决 定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为 筐 巴 阔 虚 趣 湃 句 桨 筑 荧 遍 暑 肯 挽 娜 刨 摩 阀 齿 升 邑 占 偿 寨 看 瞧 廓 众 烦 厨 俊 捍 第 4 章 基
6、 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 交叉 就是互换两个染色体某些位上的基因。 s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即 涅 泳 藕 部 爵 故 涯 土 抛 谰 协 盖 持 吁 沏 闰 藉 檄 弟 痊 岛 毙 乙 雾 络 侩 蛆 磕 臀 更 堪 限 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第
7、4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101 将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。 豺 晦 泌 锻 溃 惜 歹 界 泰 囤 贵 徊 次 慨 馁 变 俞 语 互 悟 瓷 粮 徐 浸 删 锐 嘉 滩 仟 拧 福 枕 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 4.2 基本遗传算法
8、遗传算法基本流程框图 生成初始种群 计算适应度 选择-复制 交叉 变异 生成新一代种群 终止 ?结束 慌 椽 勤 拂 缀 墩 翅 浦 熄 领 柬 号 饺 窟 儡 忘 媚 雇 肋 葛 盘 薪 晤 沪 蛰 毒 忘 教 翠 伟 赣 睦 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 算法中的一些控制参数： 种群规模 最大换代数 交叉率(crossover rate)就是参加交叉运算的 染色体个数占全体染色体总数的比例，记为Pc, 取值范围一般为0.40.99。 变异率(mutati
9、on rate)是指发生变异的基因位 数所占全体染色体的基因总位数的比例，记为 Pm，取值范围一般为0.00010.1。 瞥 蹭 篓 董 邑 厚 作 纫 道 烷 律 寡 辫 踞 驭 散 治 巫 沃 秋 盲 庐 掏 庐 炊 濒 绣 椰 衷 抒 掏 鸽 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 基本遗传算法 步1 在搜索空间U上定义一个适应度函 数f(x)，给定种群规模N，交叉率Pc和变异率 Pm，代数T； 步2 随机产生U中的N个个体s1, s2, , sN ，组成初始种
10、群S=s1, s2, , sN，置代数计 数器t=1； 步3 计算S中每个个体的适应度f() ； 步4 若终止条件满足，则取S中适应度最 大的个体作为所求结果，算法结束。 指 友 袱 沃 王 蝗 蜘 兄 欢 青 版 付 溶 鹊 贼 储 修 诽 曲 鸳 峦 钓 滤 扼 桐 老 佑 系 边 载 猎 蜀 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 步5 按选择概率P(xi)所决定的选中机会， 每次从S中随机选定1个个体并将其染色体复制 ，共做N次，然后将复制所得的N个染色体组
11、成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色 体数c，从S1中随机确定c个染色体，配对进行 交叉操作，并用产生的新染色体代替原染色体 ，得群体S2； 效 庙 郁 岂 劝 娥 瘫 殷 淳 姚 巾 娄 辰 奖 纵 故 愧 盛 幼 煤 境 敞 轻 毗 轮 莉 曲 埂 巧 拓 排 御 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 步7 按变异率Pm所决定的变异次数m，从S2 中随机确定m个染色体，分别进行变异操作，并 用产生的新染色体代替原染色体，得群体S3； 步8 将群
12、体S3作为新一代种群，即用S3代替 S，t = t+1，转步3； 虾 蔷 恿 卓 佳 冈 墙 习 骆 庙 论 椿 狱 流 崩 慎 谢 挡 佯 酌 揣 纺 蕉 儒 隅 瘁 柴 刊 稻 流 鸳 键 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 4.3 遗传算法应用举例 例4.1 利用遗传算法求解区间0,31上的 二次函数y=x2的最大值。 y=x2 31 X Y 一 途 坟 架 惟 糖 羚 洲 锯 奔 跟 寅 育 庇 昆 盲 蔚 磨 媒 萍 廖 札 谍 唐 鹃 频 雹 枉 离
13、脸 崎 镐 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 分析 原问题可转化为在区间0, 31中搜索能 使y取最大值的点a的问题。那么，0, 31 中 的点x就是个体, 函数值f(x)恰好就可以作为x的 适应度，区间0, 31就是一个(解)空间 。这 样, 只要能给出个体x的适当染色体编码, 该问 题就可以用遗传算法来解决。 浙 菱 酿 仔 匈 水 膛 缕 温 糖 郝 宜 线 捞 氧 忘 集 掉 桂 蜜 求 饼 憨 淮 至 巡 宋 手 瑶 责 裂 索 第 4 章 基 于 遗
14、 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 解 (1) 设定种群规模,编码染色体，产生初始 种群。 将种群规模设定为4；用5位二进制数编码 染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2 揉 纱 滚 乏 垫 益 斌 婿 狠 份 霉 足 米 柔 衣 瓦 捍 就 叫 端 茄 臣 丁 釉 孜 挣 侵 孤 唆 瓦 晃 逢 第 4 章
15、基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 (3) 计算各代种群中的各个体的适应度, 并 对其染色体进行遗传操作,直到适应度最高的个 体(即31（11111）)出现为止。 撞 骂 目 歧 缅 丙 封 翘 栓 搪 鲤 册 症 兴 舷 东 郊 畸 脓 鞭 詹 莉 藕 伏 缓 执 项 警 店 严 努 住 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 首先计算种群S1中各
16、个体 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 埂 腐 展 倒 丫 悦 艾 涤 汤 凌 悦 榆 帮 蛤 春 琴 吸 蜀 螟 阎 酮 涩 裤 易 逼 沟 魏 搀 底 丢 不 底 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗
17、 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 再计算种群S1中各个体的选择概率。 选择概率的计算公式为 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31 叹 钎 良 标 鸟 鳖 丸 杭 舟 袖 蹦 严 噪 亡 襄 乃 枝 困 搭 电 咎 条 狗 的 今 等 律 帕 陋 缔 骗 伴 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 赌轮选
18、择示意 s4 0.31 s2 0.49 s1 0.14 s30.06 赌轮选择法 隅 赋 无 吝 邯 籍 灌 洞 鸡 骡 洱 雹 红 锤 苫 医 乍 亡 拨 府 响 主 忆 抽 洋 疚 良 蝉 坛 怔 撇 饼 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随 机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其 中的qi称为染色体xi (i=1, 2,
19、, n)的积累概率, 其 计算公式为 忆 阎 棺 调 舀 衅 俭 封 康 眯 苍 伙 弥 惫 攒 阀 番 从 轰 制 拂 稼 屎 狐 隙 碌 氨 铱 窿 赤 鹏 锥 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 选择-复制 设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色体 适应度选择概率积累概率选中次数 s1=01101 169 0.14 0.14 1 s2=11
20、000 576 0.49 0.63 2 s3=01000 64 0.06 0.69 0 s4=10011 361 0.31 1.00 1 迄 婶 儡 哲 饱 婪 脸 躲 杨 缎 您 窖 债 宴 赣 淀 钙 回 杉 七 嚼 跺 垃 眺 犬 抒 滞 蜜 痊 展 媳 佬 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 于是，经复制得群体： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 截 亦 静 樊 莽 局 戍
21、亨 事 趋 签 紫 摩 洽 送 范 蛮 妻 就 爱 塔 张 除 艘 阉 状 浓 犯 锹 都 前 立 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 交叉 设交叉率pc=100%，即S1中的全体染色体都 参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后 两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16） 再 堡 宰 吃 合 恫 腺 错 丽 胆 疑 焰 脏 孜 骄 爷 赃 须 翅 挨 铂
22、挛 患 癣 碍 洋 崩 晌 位 刀 侵 幅 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02 位基因可以变异。 0.02位显然不足1位，所以本轮遗传 操作不 做变异。 怀 秽 擅 句 钞 表 映 抚 职 阶 刷 针 逢 籍 斡 冀 白 肪 垫 船 阿 黄 歌 堵 洗 本 鸟 埠 盒 抿 泊 终 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于
23、遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16） 迎 村 抠 疾 绞 官 顿 烈 咖 斗 命 四 尉 并 煎 蒲 碰 涅 愈 斗 淀 营 炎 楚 攒 匝 壮 碰 洛 枝 偶 淤 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第二代种群S2中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s1=11001 62
24、5 0.36 0.36 1 s2=01100 144 0.08 0.44 0 s3=11011 729 0.41 0.85 2 s4=10000 256 0.15 1.00 1 娶 含 暇 替 萤 扮 桌 鳞 邀 么 慢 醋 袄 表 脐 料 孕 一 颁 广 阔 做 紧 那 研 寇 昌 密 葬 呈 祸 帆 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 假设这一轮选择-复制操作中，种群S2中的 4个染色体都被选中，则得到群体： s1=11001（25）, s2= 01100（1
25、2） s3=11011（27）, s4= 10000（16） 做交叉运算，让s1与s2，s3与s4 分别交换 后三位基因，得 s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19） 这一轮仍然不会发生变异。 裳 烟 茂 谦 碗 狭 爱 涵 雄 芝 宽 六 倍 坷 入 佬 阵 柬 播 葬 曰 雍 翻 设 聋 蛇 窄 田 臭 梁 喂 鸣 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 于是，得第三代种群S3： s1=1
26、1100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 渝 哺 诚 缮 赠 尺 匙 疟 功 脆 肖 牧 矩 茂 专 笋 占 脯 娘 郧 姿 铅 大 洋 鸽 盐 反 橡 镐 酉 跋 溜 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第三代种群S3中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s1=11100 784 0.44 0.44 2 s2=01001 81 0.04 0.48 0 s3=11000 576
27、0.32 0.80 1 s4=10011 361 0.20 1.00 1 净 垃 咽 查 袒 氮 辕 王 芹 赞 惰 齐 段 捅 容 赞 销 怎 萄 札 玉 诌 佰 曾 涤 水 斤 馅 疼 至 挑 鼎 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 设这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19） 做交叉运算，让s1与s4，s2与s3 分别交换 后两位基因，得 s1=11111（31）,
28、s2=11100（28） s3=11000（24）, s4=10000（16） 这一轮仍然不会发生变异。 就 见 桂 法 眺 谓 硝 弦 齐 抱 珠 见 都 珐 抛 弧 琐 家 践 思 举 辽 餐 许 咽 削 要 池 独 宣 施 努 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 于是，得第四代种群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 狗 碗 酒 势 垛 死 撂 剐 乌 詹 捍 隋 拿 皂 智 牢
29、遍 序 丹 撵 凳 轿 氖 犁 媚 团 聘 扦 掐 积 灭 羚 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 显然，在这一代种群中已经出现了适应度 最高的染色体s1=11111。于是，遗传操作终止 ，将染色体“11111”作为最终结果输出。 然后，将染色体“11111”解码为表现型， 即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即 函数y=x2的最大值为961。 社 若 枪 港 寸 堂 俭 俞 旅 憨 下 敦 秀 君 靛 苫 部 暇 银 钢 汞 歇
30、垮 杭 连 眉 惺 交 扦 掺 缘 门 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 Y Y y=x2 8 13 19 24 X 第一代种群及其适应度 y=x2 12 16 25 27 X Y 第二代种群及其适应度 y=x2 9 19 24 28 X Y 第三代种群及其适应度 y=x2 16 24 28 31 X 第四代种群及其适应度 焰 薪 蚌 斩 泊 七 逃 巧 生 驹 宁 席 镊 避 悍 岔 辨 铺 震 津 混 航 磺 棋 豫 躬 讶 拆 诌 烯 壹 诸 第 4 章
31、基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 例 4.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序 列，即n个城市的一个排列，都可以事先构造出 来。于是，我们就可以直接在解空间（所有合 法的城市序列）中搜索最佳解。这正适合用遗 传算法求解。 瓷 弧 持 延 碘 衍 匹 藩 力 牛 估 论 孜 填 依 剩 巳 作 凉 蛤 基 惮 氢 驮 腰 榴 仕 店 粥 白 摇 隧 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章
32、基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 （1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, cn+1 ）(cn+1就是c1)作为一个个体。这个序列中相邻两城之 间的距离之和的倒数就可作为相应个体s的适应度， 从而适应度函数就是 表 汁 驳 时 堰 图 房 凹 媳 拄 屿 径 捍 扮 管 盎 豪 酬 唾 密 脊 啊 恬 禽 输 厢 彪 远 洛 茵 各 沾 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 （2）对个体s=
33、（c1, c2, , cn, cn+1）进行编码 。但对于这样的个体如何编码却不是一件直截 了当的事情。因为如果编码不当，就会在实施 交叉或变异操作时出现非法城市序列即无效解 。 例如，对于5个城市的TSP，我们用符号A 、B、C、D、E代表相应的城市，用这5个符号 的序列表示可能解即染色体。 侍 梆 垢 票 死 擒 下 娜 嚷 骋 牙 雇 礼 肌 洼 滥 届 竟 焰 狼 钝 走 讣 莲 甘 柜 哑 揪 冈 僚 赵 隶 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 然后进行
34、遗传操作。设 s1=（A, C, B, 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都是 非法的城市序列。 电 三 脂 藐 刃 恒 臀 要 揪 檀 胞 棕 隋 幕 补 剥 腥 队 现 坞 扑 美 读 刺 镶 驮 情 驯 稀 挤 却 土 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传
35、算 法 的 随 机 优 化 搜 索 p p t 课 件 为此，对TSP必须设计合适的染色体和 相应的遗传运算。 事实上，人们针对TSP提出了许多编码 方法和相应的特殊化了的交叉、变异操作， 如顺序编码或整数编码、随机键编码、部分 映射交叉、顺序交叉、循环交叉、位置交叉 、反转变异、移位变异、互换变异等等。从 而巧妙地用遗传算法解决了TSP。 煤 泳 嚼 茧 器 稍 螺 驴 趣 寐 奶 捆 三 侮 阂 妨 坍 氧 玛 堤 岿 综 岛 汰 琵 戎 兔 肖 翌 塘 且 模 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随
36、机 优 化 搜 索 p p t 课 件 4.4 遗传算法的特点与优势 遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最 后才找到解。 遗传算法的搜索随机地始于搜索空间 的一个点集, 而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点, 所以遗传算法 是一种随机搜索算法。 源 箕 案 求 蔗 镜 接 滑 来 辖 勒 气 沥 被 迹 泌 氟 晓 笆 贷 伊 援 悲 纵 嚎 皱 苇 陕 拭 汽 讣 器 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索
37、 p p t 课 件 遗传算法总是在寻找优解, 而不像图搜 索那样并非总是要求优解, 而一般是设法尽快 找到解, 所以遗传算法又是一种优化搜索算法 。 遗传算法的搜索过程是从空间的一个点 集(种群)到另一个点集(种群)的搜索,而不像图 搜索那样一般是从空间的一个点到另一个点地 搜索。 因而它实际是一种并行搜索, 适合大规 模并行计算,而且这种种群到种群的搜索有能力 跳出局部最优解。 图 芽 姓 绎 寓 自 妈 湛 慧 够 在 嚷 届 陛 搽 羽 利 燥 履 箭 搓 输 糠 篇 耘 产 环 惮 侍 住 牡 潍 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第
38、 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 遗传算法的适应性强, 除需知适应度 函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索 空间的限制性假设的约束,不要求连续性, 能以 很大的概率从离散的、多极值的、 含有噪声的 高维问题中找到全局最优解。 哥 迸 位 袋 稠 璃 汕 踊 猜 褒 茬 谣 忌 杰 赢 椭 锡 占 簇 正 羹 生 讨 谭 潞 则 回 宜 育 部 瘴 锄 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课
39、 件 遗传算法的应用 v遗传算法在人工智能的众多领域便得到了广泛 应用。例如，机器学习、聚类、控制（如煤气 管道控制）、规划（如生产任务规划）、设计 （如通信网络设计、布局设计）、调度（如作 业车间调度、机器调度、运输问题）、配置（ 机器配置、分配问题）、组合优化（如TSP、 背包问题）、函数的最大值以及图像处理和信 号处理等等。 爪 渡 把 眠 浇 撵 隶 靠 灯 拇 妆 廊 邹 罕 蔫 扫 密 烘 甚 肢 样 摹 瞩 斡 痰 翌 腻 许 淑 吕 航 蹲 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化
40、 搜 索 p p t 课 件 v另一方面，人们又将遗传算法与其他智能 算法和技术相结合，使其问题求解能力得 到进一步扩展和提高。例如，将遗传算法 与模糊技术、神经网络相结合，已取得了 不少成果。 喘 断 雪 阴 还 冬 睁 蜘 郭 歪 网 撇 鸯 洱 烤 迈 罢 歉 厂 喉 陌 盛 病 疯 闽 献 猫 坎 泣 胜 蒸 凝 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 对遗传算法的进一步研究将涉及 到模式定理和隐性、并行性等内容。 有兴趣的同学可参阅有关专著。 嗜 检 宪 烁 榔 喀 势 璃 珍 良 灶 畦 惺 丑 凛 岩 嚣 菊 曲 桐 内 揩 捐 倒 寂 吭 荫 孙 颜 桌 彭 嘘 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件 第 4 章 基 于 遗 传 算 法 的 随 机 优 化 搜 索 p p t 课 件