第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势.

Slides:



Advertisements
Similar presentations
简单迭代法的概念与结论 简单迭代法又称逐次迭代法,基本思想是构造不动点 方程,以求得近似根。即由方程 f(x)=0 变换为 x=  (x), 然后建立迭代格式, 返回下一页 则称迭代格式 收敛, 否则称为发散 上一页.
Advertisements

课前寄语 1 、保持纪律 2 、相互配合. 第三节 公民的投资 —— 公民的存款储蓄 课堂导入.
版 画 制 作版 画 制 作 版 画 种 类版 画 种 类 版 画 作 品版 画 作 品 刘承川.
2.5 微分及其应用. 三、可微的条件 一、问题的提出 二、微分的定义 六、微分的形式不变性 四、微分的几何意义 五、微分的求法 八、小结 七、微分在近似计算中的应用.
夯实教师教育 办好非师范教育 ---- 以外语专业为例 河北师范大学 李正栓. 1. 坚定不移地实施教师教育 A. 关键词:师范院校 师范院校是以培育师资为目的的教育机构,多属于高等教育 层级。 含 “ 师范大学 ” 或 “ 师范学院 ” 。另外,由师专升为本科的院校 多数更名为 “XX 学院 ”
旅遊實務Ⅰ 授課教師:李健民 上課班級: 320. 課程大綱 旅遊業之設立程序 旅行業組織結構 旅行業之分類 旅行業之管理.
中医内科 陈良金. 目的要求: 熟悉虚劳的证候特征。 了解虚劳的发病与气血阴阳及五脏的关系。 掌握虚劳和肺痨及一般虚证的区别与联系。 掌握虚劳的治疗要点。 熟悉虚劳各个证型的辨证论治。 了解虚劳的预后及调摄护理。
写作中的几点小技巧 金乡县羊山中学 张秀玲. 一、写外貌不用 “ 有 ” 作文如何来写外貌?同学们的作文里总会出现类 似这样的句子: “ XX 可漂亮了,她有一头卷卷的黄头 发,有一双乌黑的葡萄般的大眼睛,有高高的鼻子, 还有一张樱桃小嘴。 ” 如果试着去掉文中的 “ 有 ” ,把文字重新修改一遍,
十大写作技巧. 一、写外貌不用 “ 有 ” 作文如何写外貌?孩子的作文里总会看到类似这样的名 子: “XX 可漂亮了,她有一头卷卷的黄头发,有一双乌黑的 葡萄般的大眼睛,有一个高高的鼻子,还有一张樱桃小嘴。 ” 如果你试着让他们去掉文中的 “ 有 ” ,把文字重新串联一遍, 会发现作文顺了很多。 写上段文字的同学经蒋老师指导后修改如下:
親 ( 四 ) 親近神的路. 一、親的三字訣、七字訣: 親近神,親愛人; 與主交通親近神,同情關心親愛人。 甚麼是親? 1. 親有親近、親愛,更有關心、同情、親切的 意思。 2. 親的人與人沒有間隔,拉近人與人之間的距 離,並且樂意幫助人,與人相調建造在一起。
招商谈判技巧 芝麻官营销. 技巧原则 孙子兵法云: “ 兵无常势,水无常形,能 因敌之变化而取胜者,谓之神。 ” “ 内功心法 ” 只有在真正实践中才能体会、 掌握。 谈判有没有具体的套路?有没有 “ 一招制 敌 ” 的擒拿手?
商管群科科主任 盧錦春 年 3 月份初階建置、 4 月份進階建置、 5 月份試賣與對外營業。
“ 十二五 ” 广东省科技计划项目 经费监管培训 广东省科技厅 一、专项经费管理法规 一、专项经费管理法规 二、经费监督检查 二、经费监督检查 三、项目预算调整管理 三、项目预算调整管理 四、课题经费预算执行管理 四、课题经费预算执行管理 五、项目(课题)财务验收 五、项目(课题)财务验收 2.
教育研究课题的实施 北京教育科学研究院 陶文中 第一节 如何制定课题研究计划 (开题论证报告) 一般结构(框架) 1 、课题名称 2 、研究目的和意义 3 、研究的基本内容 ( 1 )理论研究(细分为若干子项目) ( 2 )实践研究( 细分为若干子项目)
第二班群教師團隊 105 張心平 107 鐘于寧 106 黃意評 108 鄭婉茹. 第二班群之班親會說明 學校規定事項說明 教學活動說明 班群活動介紹.
1 語音下單代表號 請輸入分公司代碼 2 位結束請按#字鍵 統一證券您好 ﹗ 請輸入分公司代碼結束請按#字鍵,如不知分公司代碼請按*號。 請輸入您的帳號後 7 位 結束請按#字鍵 請在聽到干擾音時輸入您的密碼結束請按#字鍵 主選單一覽表 委託下單請按 1 ; 取消下單請按 2 成交回報請按.
人權教育融入教學與 法治教育 彭巧綾 蔡永棠 閱讀理解 六頂思考帽 以概念圖整理閱讀理解 指導學生運用關鍵詞,繪製概 念圖,並分享修正。
差勤.
申論題要拿高分並不容易,因為他是 有一定的技巧的,如果你遵照下列技 巧來作答申論題,相信高分並不難拿, 其技巧如下:
重建精细管理意识 不能粗线条管理 不简单敷衍人民 不轻易指责媒体 不与媒体对立冲突 粗心 粗糙 粗略 粗鲁 粗暴 不消极等待自生自灭
义务教育课程标准实验教材 四年级下册 语文园地六 词语盘点 习作 口语交际 我的发现 日积月累 展示台.
102大學甄選入學 個人申請、繁星推薦說明 主講人:簡慧嫻.
被 江 泽 民 残 酷 迫 害 致 死 的 法 轮 功 学 员 李竟春,女,1954年3月16日出生,江西省九江市人。于2000年12月18日到北京证实大法,关押在北京市门头沟看守所遭受非人的迫害。在狱中李竟春绝食抗争被管教骗喝一瓶“可疑的豆浆”后一直咳嗽不断,发烧呕吐,吐出白色有强烈异味液体,于2000年1月4日死亡。
目录 如何职位分析调查表 职位分析的目的与意义 职位调查表内容与要点说明 职位分析注意事项 职位分析调查工作计划.
1 修辞手法 2 表现手法 3 表达方式 4 结构技巧 表达技巧.
32个团体游戏 增加团队凝聚力.
高等数学 A (一) 总复习(2).
专利技术交底书的撰写方法 ——公司知识产权讲座
新進教師研習 教務處報告 報告人:教務處 林永仁 2011 年 8 月31日.
「明清時期台灣古典散文」 教師:田啟文.
大洋洲.
新頒解釋函令 ● 所得稅扣(免)繳相關法令、 ● 所得稅扣(免)繳申報實務 ● 扣繳常見稅務違章類型 財政部南區國稅局屏東分局
当代 国 际 关 系(案例6) 冷战时期美苏关系的演变.
鼻炎 症狀: 鼻(眼睛)內發癢或不舒服、 打噴嚏、 流鼻涕(水)、 鼻塞………等 。 鼻子內的任何發炎。
清华大学出版社 北京交通大学出版社 吴柏林 编著
模块七 房地产营销渠道策略 主要内容 房地产营销渠道类型 房地产营销渠道选择方法 开发商与代理商的合作模式.
遣詞造句知多少? 中文系 王偉勇教授 兼通識教育中心中心主任.
(4)理论体系与实训模块 必须衔接、融合 本课程把理论教学体系与实训模块结构连接成一个完整的高职课程体系。
最有利標及評選優勝廠商 講師 劉金龍 經歷:臺中市政府發包科科長.
三、市场营销学研究的基本方法 (1)产品研究法。是以物为中心的研究方法,即在产品分类的基础上,对各类产品市场分别进行研究。 (2)机构研究法。是以研究市场营销制度为出发点,体现以人为中心的研究方法,即集中对整个市场营销系统中的各特定机构的性质和功能进行研究。 (3)职能研究法。是以研究产品从生产者到消费者手中所进行的各种营销活动过程中,市场营销组织所发挥的功能的方法。
青春期 要長大囉! 男女有別 生命的誕生~兩性結合才有下一代的新生命 為什麼會有月經? 經痛怎麼辦 ? 渡過快樂青春喜歡自己
胚胎学总论 (I) 制作:皖南医学院组胚教研室.
“深入推进依法行政加快建设法治政府” -《法治政府建设实施纲要》解读
親愛的吉姆舅舅:   今天吃完晚餐後,奶奶說,在家裡情況變好以前,您要我搬到城裡跟您住。奶奶有沒有跟您說,爸爸已經好久沒有工作,也好久沒有人請媽媽做衣服了?   我們聽完都哭了,連爸爸也哭了,但是媽媽說了一個故事讓我們又笑了。她說:您們小的時候,她曾經被您追得爬到樹上去,真的嗎?   雖然我個子小,但是我很強壯,只要我會做的我都可以幫忙,但是,奶奶說,做其他事情以前,要先把功課做完。
网络的利与弊 2017/3/19 该课件由【语文公社】
战 后 国 际 关 系 专题五:冷战时期美苏关系的演变 政治学与行政管理系.
第六节 可降阶的二阶微分方程 一、 型的微分方程 二、 型的微分方程 三、 型的微分方程.
四种命题 班级:C274 指导教师:钟志勤 任课教师:颜小娟.
最有利標及評選優勝廠商 講師 劉金龍 經歷:臺中市政府發包科科長.
當 家 新 鮮 事.
第五章 定积分及其应用.
兒童及少年福利服務 講師:張智昇.
中國美術史報告-我最喜歡的一幅畫 班級:2年2班 姓名:郭馥甄 座號:23.
第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他.
高鐵炫風 製作人林淑蘭老師.
行政院勞工委員會勞工保險局 勞退舊制與新制分析說明 高雄市政府人事處 99年2月1日.
2007/5/23初訪螢光蕈 (等了兩年).
开始 结束.
3.1.3几种常见函数的导数 高二数学 选修1-1.
遗传算法(Genetic Algorithm) Natural Computing
导数的应用 ——函数的单调性与极值.
幂函数 大连市第十六中学李秀敏.
因式定理.
四川省天全中学说课竞赛 多媒体演示课件 ★ ☆ 函数的单调性 天全中学数学组 熊 亮.
九年级数学(下) §26.1 二次函数的图像与性质(3) 烟塘中学 :冯 闻
第十一章 基因演算法 (Genetic Algorithms)
高雄區12年國教入學方式 報告人:高雄市政府教育局 局長 鄭新輝.
§3 函数的单调性.
幂函数.
第二章 一元一次不等式和一元一次不等式组 回顾与复习(一).
Presentation transcript:

第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势

4.1 基本概念 1. 个体与种群 ● 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼,一个个 体也就是搜索空间中的一个点。 ● 种群 (population) 就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。

2. 适应度与适应度函数 ● 适应度 (fitness) 就是借鉴生物个体对环境的 适应程度, 而对问题中的个体对象所设计的 表征其优劣的一种测度。 ● 适应度函数 (fitness function) 就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。

3. 染色体与基因 染色体( chromosome )就是问题中个体的 某种字符串形式的编码表示。字符串中的字符 也就称为基因( gene )。 例如: 个体 染色体 ( 2 , 5 , 6 )

4. 遗传操作 亦称遗传算子 (genetic operator) ,就是关 于染色体的运算。遗传算法中有三种遗传操作 : ● 选择 - 复制 (selection-reproduction) ● 交叉 (crossover ,亦称交换、交配或杂交 ) ● 变异 (mutation ,亦称突变 )

选择 - 复制 通常做法是:对于一个规模为 N 的种群 S, 按每个染色体 x i ∈ S 的选择概率 P(x i ) 所决定 的选中机会, 分 N 次从 S 中随机选定 N 个染色体, 并 进行复制。 这里的选择概率 P(x i ) 的计算公式为

交叉 就是互换两个染色体某些位上的基因。 s 1 ′= , s 2 ′= 可以看做是原染色体 s 1 和 s 2 的子代染色体。 例如, 设染色体 s 1 = , s 2 = , 交换其后 4 位基因, 即

变异 就是改变染色体某个 ( 些 ) 位上的基因。 例如, 设染色体 s= 将其第三位上的 0 变为 1, 即 s= → = s′ 。 s′ 也可以看做是原染色体 s 的子代染色体。

4.2 基本遗传算法 遗传算法基本流程框图 生成初始种群 计算适应度 选择 - 复制 交叉 变异 生成新一代种群 终止 ? 结束

算法中的一些控制参数: ■ 种群规模 ■ 最大换代数 ■ 交叉率 (crossover rate) 就是参加交叉运算的染 色体个数占全体染色体总数的比例,记为 P c, 取 值范围一般为 0.4 ~ 0.99 。 ■ 变异率 (mutation rate) 是指发生变异的基因位 数所占全体染色体的基因总位数的比例,记为 P m ,取值范围一般为 ~ 0.1 。

基本遗传算法 步 1 在搜索空间 U 上定义一个适应度函数 f(x) ,给定种群规模 N ,交叉率 P c 和变异率 P m , 代数 T ; 步 2 随机产生 U 中的 N 个个体 s 1, s 2, …, s N , 组成初始种群 S={s 1, s 2, …, s N } ,置代数计数 器 t=1 ; 步 3 计算 S 中每个个体的适应度 f() ; 步 4 若终止条件满足,则取 S 中适应度最 大的个体作为所求结果,算法结束。

步 5 按选择概率 P(x i ) 所决定的选中机会, 每次从 S 中随机选定 1 个个体并将其染色体复制, 共做 N 次,然后将复制所得的 N 个染色体组成 群体 S 1 ; 步 6 按交叉率 P c 所决定的参加交叉的染色 体数 c ,从 S 1 中随机确定 c 个染色体,配对进行 交叉操作,并用产生的新染色体代替原染色体, 得群体 S 2 ;

步 7 按变异率 P m 所决定的变异次数 m ,从 S 2 中随机确定 m 个染色体,分别进行变异操作,并 用产生的新染色体代替原染色体,得群体 S 3 ; 步 8 将群体 S 3 作为新一代种群,即用 S 3 代替 S , t = t+1 ,转步 3 ;

4.3 遗传算法应用举例 例 4.1 利用遗传算法求解区间[ 0,31 ]上的 二次函数 y=x 2 的最大值。 y=x2y=x2 31 X Y

分析 原问题可转化为在区间[ 0, 31 ]中搜索能 使 y 取最大值的点 a 的问题。那么,[ 0, 31 ] 中 的点 x 就是个体, 函数值 f(x) 恰好就可以作为 x 的 适应度,区间[ 0, 31 ]就是一个 ( 解 ) 空间 。这 样, 只要能给出个体 x 的适当染色体编码, 该问 题就可以用遗传算法来解决。

解 (1) 设定种群规模, 编码染色体,产生初始种 群。 将种群规模设定为 4 ;用 5 位二进制数编码染 色体;取下列个体组成初始种群 S 1 : s 1 = 13 (01101), s 2 = 24 (11000) s 3 = 8 (01000), s 4 = 19 (10011) (2) 定义适应度函数, 取适应度函数: f (x)=x 2

(3) 计算各代种群中的各个体的适应度, 并 对其染色体进行遗传操作, 直到适应度最高的个 体 ( 即 31 ( ) ) 出现为止。

首先计算种群 S 1 中各个体 s 1 = 13(01101), s 2 = 24(11000) s 3 = 8(01000), s 4 = 19(10011) 的适应度 f (s i ) 。 容易求得 f (s 1 ) = f(13) = 13 2 = 169 f (s 2 ) = f(24) = 24 2 = 576 f (s 3 ) = f(8) = 8 2 = 64 f (s 4 ) = f(19) = 19 2 = 361

再计算种群 S 1 中各个体的选择概率。 选择概率的计算公式为 由此可求得 P(s 1 ) = P(13) = 0.14 P(s 2 ) = P(24) = 0.49 P(s 3 ) = P(8) = 0.06 P(s 4 ) = P(19) = 0.31

赌轮选择示意 s s s s ● 赌轮选择法

在算法中赌轮选择法可用下面的子过程来模拟 : ① 在[ 0, 1 ]区间内产生一个均匀分布的随机 数 r 。 ② 若 r≤q 1, 则染色体 x 1 被选中。 ③ 若 q k-1 <r≤q k (2≤k≤N), 则染色体 x k 被选中。 其 中的 q i 称为染色体 x i (i=1, 2, …, n) 的积累概率, 其 计算公式为

选择 - 复制 设从区间[ 0, 1 ]中产生 4 个随机数如下 : r 1 = , r 2 = r 3 = , r 4 = 染色体 适应度选择概率积累概率选中次数 s 1 = s 2 = s 3 = s 4 =

于是,经复制得群体: s 1 ’ =11000 ( 24 ), s 2 ’ =01101 ( 13 ) s 3 ’ =11000 ( 24 ), s 4 ’ =10011 ( 19 )

交叉 设交叉率 p c =100% ,即 S 1 中的全体染色体都 参加交叉运算。 设 s 1 ’ 与 s 2 ’ 配对, s 3 ’ 与 s 4 ’ 配对。分别交换后 两位基因,得新染色体: s 1 ’’ =11001 ( 25 ), s 2 ’’ =01100 ( 12 ) s 3 ’’ =11011 ( 27 ), s 4 ’’ =10000 ( 16 )

变异 设变异率 p m =0.001 。 这样,群体 S 1 中共有 5 × 4 × 0.001=0.02 位基因可以变异。 0.02 位显然不足 1 位,所以本轮遗传操作不 做变异。

于是,得到第二代种群 S 2 : s 1 =11001 ( 25 ), s 2 =01100 ( 12 ) s 3 =11011 ( 27 ), s 4 =10000 ( 16 )

第二代种群 S 2 中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s 1 = s 2 = s 3 = s 4 =

假设这一轮选择 - 复制操作中,种群 S 2 中的 4 个染色体都被选中,则得到群体: s 1 ’ =11001 ( 25 ), s 2 ’ = ( 12 ) s 3 ’ =11011 ( 27 ), s 4 ’ = ( 16 ) 做交叉运算,让 s 1 ’ 与 s 2 ’ , s 3 ’ 与 s 4 ’ 分别交换后 三位基因,得 s 1 ’’ =11100 ( 28 ), s 2 ’’ = ( 9 ) s 3 ’’ =11000 ( 24 ), s 4 ’’ = ( 19 ) 这一轮仍然不会发生变异。

于是,得第三代种群 S3 : s 1 =11100 ( 28 ), s 2 =01001 ( 9 ) s 3 =11000 ( 24 ), s 4 =10011 ( 19 )

第三代种群 S 3 中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s 1 = s 2 = s 3 = s 4 =

设这一轮的选择 - 复制结果为: s 1 ’ =11100 ( 28 ), s 2 ’ =11100 ( 28 ) s 3 ’ =11000 ( 24 ), s 4 ’ =10011 ( 19 ) 做交叉运算,让 s 1 ’ 与 s 4 ’ , s 2 ’ 与 s 3 ’ 分别交换后 两位基因,得 s 1 ’’ =11111 ( 31 ), s 2 ’’ =11100 ( 28 ) s 3 ’’ =11000 ( 24 ), s 4 ’’ =10000 ( 16 ) 这一轮仍然不会发生变异。

于是,得第四代种群 S 4 : s 1 =11111 ( 31 ), s 2 =11100 ( 28 ) s 3 =11000 ( 24 ), s 4 =10000 ( 16 )

显然,在这一代种群中已经出现了适应度最 高的染色体 s 1 =11111 。于是,遗传操作终止,将 染色体 “ ” 作为最终结果输出。 然后,将染色体 “11111” 解码为表现型,即 得所求的最优解: 31 。 将 31 代入函数 y=x 2 中,即得原问题的解,即函 数 y=x 2 的最大值为 961 。

Y Y y=x2y=x X 第一代种群及其适应度 y=x2y=x X Y 第二代种群及其适应度 y=x2y=x X Y 第三代种群及其适应度 y=x2y=x X 第四代种群及其适应度

例 4.2 用遗传算法求解 TSP 。 分析 由于其任一可能解 —— 一个合法的城市序 列,即 n 个城市的一个排列,都可以事先构造出 来。于是,我们就可以直接在解空间(所有合 法的城市序列)中搜索最佳解。这正适合用遗 传算法求解。

( 1 )定义适应度函数 我们将一个合法的城市序列 s= ( c 1, c 2, …, c n, c n+1 ) (c n+1 就是 c 1 ) 作为一个个体。这个序列中相邻两城之间 的距离之和的倒数就可作为相应个体 s 的适应度,从 而适应度函数就是

( 2 )对个体 s= ( c 1, c 2, …, c n, c n+1 )进行编码。 但对于这样的个体如何编码却不是一件直截了 当的事情。因为如果编码不当,就会在实施交 叉或变异操作时出现非法城市序列即无效解。 例如,对于 5 个城市的 TSP ,我们用符号 A 、 B 、 C 、 D 、 E 代表相应的城市,用这 5 个符号的序列 表示可能解即染色体。

然后进行遗传操作。设 s 1 = ( A, C, B, E, D, A ), s 2 = ( A, E, D, C, B, A ) 实施常规的交叉或变异操作,如交换后三位,得 s 1 ’ = ( A,C,B,C,B,A ), s 2 ’ = ( A,E,D,E,D,A ) 或者将染色体 s1 第二位的 C 变为 E ,得 s 1 ’’ = ( A, E, B, E, D, A ) 可以看出,上面得到的 s 1 ’ , s 2 ’ 和 s 1 ’’ 都是 非法的城市序列。

为此,对 TSP 必须设计合适的染色体和 相应的遗传运算。 事实上,人们针对 TSP 提出了许多编码 方法和相应的特殊化了的交叉、变异操作, 如顺序编码或整数编码、随机键编码、部分 映射交叉、顺序交叉、循环交叉、位置交叉、 反转变异、移位变异、互换变异等等。从而 巧妙地用遗传算法解决了 TSP 。

4.4 遗传算法的特点与优势 ◆遗传算法的主要特点 —— 遗传算法一般是直接在解空间搜索, 而 不像图搜索那样一般是在问题空间搜索, 最后 才找到解。 —— 遗传算法的搜索随机地始于搜索空间 的一个点集, 而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点, 所以遗传算法 是一种随机搜索算法。

—— 遗传算法总是在寻找优解, 而不像图搜 索那样并非总是要求优解, 而一般是设法尽快找 到解, 所以遗传算法又是一种优化搜索算法。 —— 遗传算法的搜索过程是从空间的一个点集 ( 种群 ) 到另一个点集 ( 种群 ) 的搜索, 而不像图搜 索那样一般是从空间的一个点到另一个点地搜 索。 因而它实际是一种并行搜索, 适合大规模 并行计算, 而且这种种群到种群的搜索有能力跳 出局部最优解。

—— 遗传算法的适应性强, 除需知适应度函 数外, 几乎不需要其他的先验知识。 —— 遗传算法长于全局搜索, 它不受搜索 空间的限制性假设的约束, 不要求连续性, 能以 很大的概率从离散的、多极值的、 含有噪声的 高维问题中找到全局最优解。

◆遗传算法的应用  遗传算法在人工智能的众多领域便得到了广泛 应用。例如,机器学习、聚类、控制(如煤气 管道控制)、规划(如生产任务规划)、设计 (如通信网络设计、布局设计)、调度(如作 业车间调度、机器调度、运输问题)、配置 (机器配置、分配问题)、组合优化(如 TSP 、 背包问题)、函数的最大值以及图像处理和信 号处理等等。

 另一方面,人们又将遗传算法与其他智能 算法和技术相结合,使其问题求解能力得 到进一步扩展和提高。例如,将遗传算法 与模糊技术、神经网络相结合,已取得了 不少成果。

对遗传算法的进一步研究将涉及 到模式定理和隐性、并行性等内容。 有兴趣的同学可参阅有关专著。