第十一章 基因演算法 (Genetic Algorithms)

Slides:



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

我国国有银行 资本构成及资本充足率变化 小组成员:金融 尹佳裕 王淼 刘钰 金融 吴昱.
行政院原住民族委員會 法規暨訴願審議委員會 102 年度原住民身分法實例演練講習: 原住民身分認定及救濟程序.
本校自民國 78 年於顏前校長世錫任內創設本系 設立鑑識科學學系大學部,專責鑑識人才之培養, 為目前國內唯一專門培育鑑識科學人才、研究鑑識 科學學術之大學學系,設系剛滿 20 年。自 85 年於姚 前校長高橋任內,設立鑑識科學研究所招收碩士生 ,民國 88 年於謝前校長瑞智任內先後獲內政部、教.
第二节 基因在亲子代间的传递. 1. 什么叫做遗传? 2. 什么叫做性状? 3. 性状是由什么决定的?
第二章:生物科學與食品 第三節:基因改造食品.
國中學生 興趣診斷測驗 九大職類興趣分析.
高一選組輔導家長說明會 報告單位:輔導室 報告分享:林珈吟.
第二章 大学生的自我认知 第二节 认识自我 主讲教师:李冰峰 单位:黑龙江外国语学院.
第三章 现代教育与人的发展.
強制認領私生子首例 第十組組員:4970T012 劉柏宇 4970T013 黃偵泰 4970T035 陳建儒 4970T100 蔡維哲
何謂人工智慧 人工智慧的定義 人工智慧的發展 人工智慧技術的介紹
如何看懂孩子的 性向測驗與興趣量表 陳郁雯.
0726·第二小组 胡文博、俞珈、李旋霞、崔文盛、焦帅
中国职教学会质量保障与评估研究会2016年学术年会
基因工程及转基因生物.
受苦節默想崇拜 2013.
清华大学出版社 北京交通大学出版社 吴柏林 编著
第21课时 生物圈中的微生物 考 点 聚 焦 专 项 突 破 1.
國民中學 自然與生活科技 第二冊 第3章 生殖 3-1 細胞分裂 3-2 無性生殖 3-3 有性生殖.
第2章 基因和染色体的关系 第1节 减数分裂和受精作用.
农业银行网上签约流程 宁夏金溢投资 内部资料 1.
第五章 思维与想象 苏州大学教育学院心理系 吴继霞
廉政會報專題報告 農地重劃工程 施工常見缺失 報告:吳東霖 製作:張昌鈴 日期:103年12月23日.
学校核心发展力 上海市建平中学 程红兵.
3.2 体外受精和早期胚胎培养.
應用學習課程簡介 運動及體適能教練.
專案製作經驗談.
必修二 生物 (人教版).
時間:102年9月18日(星期三) 地點:國立臺灣師範大學綜合大樓509國際會議廳
想一想 议一议 P74 我们常吃的蘑菇有根、茎、叶吗? 它们的生长是否需要光? 为什么说它们是真菌而不是植物呢?
三次科技革命 学习目标: 1.知道三次科技革命的时间、标志、发源地、理论基础、主要成就、主要特点及影响。 2.培养归纳历史知识的能力
用“自言自语法”提高学生 英语口头表达能力 李奉栖.
王永慶遺產分配 第三組民法報告 4970T011 劉昭妤 4970T037 吳品怡 4970T090 袁如意
台南在地美食文化介紹 台南市鳳凰城文史協會 理事長 歐財榮.
第十章 小粒子和大宇宙.
人类科学史上 三大工程 曼哈顿计划(原子弹) 阿波罗计划(登月) 人类基因组计划 了解人类自身,操纵生命 其意义比以上两个计划更为深远.
一、作者概說:    王壽來,民國三十八年生,山西省 五臺縣人,中興大學 法律系畢業,美國 喬治城大學碩士、臺灣師範大學 美術研究所碩博士。長期從事文化與外交工作,現任文建會 文化資產總管理處籌備處主任。   王壽來靈感多取自生活經驗,善用中外名言,描繪人生百態。著有《公務員快意人生》、《藝術‧收藏‧我》、《公務員DNA》、《和世界偉人面對面》等書。
牛 奔 生物启发式优化方法 及其在管理中的应用
第五章 遗传算法.
导入新课 波能绕过障碍物产生衍射。既然光也是一种波,为什么在日常生活中难以观察到光的衍射现象呢?.
高中生物学必修Ⅰ 分子与细胞 前 言.
金門縣重大空難應變機制-消防局 壹、消防搶救、滅火、緊急救護 一、派遣作為:
关注生物技术的 伦理问题.
自我介绍 ——陈丽敏.
复习专题 现代文阅读 (总论) 汕头市潮阳第四中学:陈钦发.
2015年高考历史质量分析报告 兰州市外国语高级中学 杨彩玲.
肝功能正常的小三阳注意事项.
突變 突變是指遺傳物質發生改變, 而影響到性狀的表現 例:白化症.
第Ⅱ部分 问题求解 第4章 超越经典搜索 中国科大 计算机学院.
好好國際物流股份有限公司 全球運籌物流服務建議 中 華 貨 物 通 關 自 動 化 協 會 理 事 長 劉 陽 柳 二○○二年五月十五日
司法机关.
第四章 人工智慧演算法 2018/9/19.
第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他.
資訊管理 第九章 資料採礦.
第六章 智慧型的行銷資訊系統 課程名稱 行銷資訊系統 進度 第六章 授課老師 總時數 3小時 線 行銷資訊系統 – E世代的行銷管理.
植生工程植材選用決策支援系統 指導:錢滄海 授課:林俐玲 學生:楊孟叡.
生物五界的分類方式.
南瑞学堂 学员简明操作指南 上海时代光华教育发展有限公司 2013年.
遗传算法(Genetic Algorithm) Natural Computing
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
指導老師:謝文魁 老師 組員:邱獻德 蔡雅芳 鐘筱嬿 陳姿伶 王彥婷
使用服务平台办理离校 操作指南.
人是由什么发育而来的? 一个受精卵.
资金时间价值概述 主讲人 任晓宇 去除PPT模板上的--无忧PPT整理发布的文字 首先打开PPT模板,选择视图,然后选择幻灯片母版
学年第一学期领取教材明细查询的通知 学年第一学期学生使用的教材均在网上平台公示。现将有关事项通知如下:
情境式職涯興趣測驗 曾馨霈 旗山國中輔導室.
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
非同源染色体:不是同源染色体的两条染色体
证据运用 第八章 证据的运用 第一节 证据体系的结构及运用规则.
Presentation transcript:

第十一章 基因演算法 (Genetic Algorithms)

基因演算法 基因演算法(Genetic Algorithms)也和記憶基礎理解及類神經網路相同,是建立在類比生物思考過程之上。數百萬年來物競天擇使生物不斷進化,也更適應環境,生存下來的適者會藉由繁衍,將自身的基因傳遞給下一代。增加個體對環境的適應性來解決問題。

基因演算法 基因演算法常被應用在三個領域: 訓練類神經網路 生成記憶基礎理解的評分函數 排程的最適化功能等。 其中最普遍的,就是用來訓練類神經網路。目前許多類神經網路都將基因演算法列為訓練的選項之一。

基因演算法 密西根大學的約翰.賀藍(John Holland)首創用了『基因演算法』,發展出這項技術有力的理論基礎。他在理論中描述了基因演算法是如何運作,以及基因如何巧妙地創造了適應生存的物種。

基因演算法 資料採礦著重是分類,預測,而不是最適化,儘管許多資料採礦的問題可以視作最適化問題。一個典型的資料採礦問題,是根據某項產品前一週的銷售量及其特性等等,預測其存貨量。換成最適化的方式,問題就變:『哪一種函數與存貨曲線是最吻合,可用來預測。』使用統計迴歸是一種方式,類神經網路是另一方式,基因演算法則提供了另一種可能性。

基因演算法 遺傳學概述: 在比較高等的動物中,這些傳遞下來的DNA 藉由雜交融合了其它適者的DNA,這種技術 稱之為雜交(Cross over)。 有時候傳遞基因給下一代的過程也會有出 錯,稱之突變(mutation)。 這所有的過程加起來,一代一代傳遞,使得 生物高度適應其環境:這就是演化過程。

電腦上的遺傳學 一個簡單的例子來解釋基因演算法如何運作:在一個只有一個參數『p』簡單函數,p值為在0 至31之間,該函數31p – p2 見下圖。這個例子可視為一個基因組(genome),只含有一個5位元基因參數p。(需要5位元來表達0到31)這個函數的最大值出現在p為15與16時,分別以01111與10000代表。這個例子也顯示即使有數個最適狀態,基因演算法依然適用。

電腦上的遺傳學

電腦上的遺傳學 我們必須選擇所謂的適配函數(fitness function)來解決這個問題。在這個例子裡,適配函數就是31p – p2,然後進行以下一些步驟: 定義基因組以及適配函數,創造第一代的基 因組。 2.藉由選擇,雜交,以及突變,來修訂起始群 體。 3.重複步驟2,直到這個群體不再進步為止。

電腦上的遺傳學 運用基因演算的第一個步驟就是設定問題。該基因組含有一個5位元基因參數p。如下表顯示,第一代有四個隨產生的基因組。平均適配值是117.75,已經相當不錯,不過基因演算法可以使其更為改善。

電腦上的遺傳學 基因 p 適配值 10110 22 176 00011 3 87 00010 2 58 11001 25 150

電腦上的遺傳學 如下圖所示,基本演算過程利用三個運算元來修訂起始群體 - 選擇(selection),雜交(crossover),及突變(mutation)。

電腦上的遺傳學

電腦上的遺傳學 在我們的計算過程中,母群體的數量是保持恆定的,也就是說該群體不致滅種。基因組存活並繁衍的機率,與其適配值(fitness value)成正比:值越高者,在下一代基因組中所佔比例就越高。按比例計算後,遺傳給下一代的數量通常是個分數,但是群體中基因組的數量卻絕對是整數。生存是建立在依照比例再任意選擇基因組的基準上。

電腦上的遺傳學 基因 適配值 適配值百分比 期望子代數 10110 176 37.4% 1.50 00011 87 18.5% 0.74 基因 適配值 適配值百分比 期望子代數 10110 176 37.4% 1.50 00011 87 18.5% 0.74 00010 58 12.3% 0.49 11001 150 31.8% 1.27

電腦上的遺傳學 這種選擇的過程,如下表所示,使得4 個基因組出現生存的勝利者。值得注意的是,傳遞下來的基因組,適者較多,不適者較少。例如00011就沒有在這一次的選擇過程中生存下來,而10110這個最適者則佔了2個名額。母群體的平均適配值從117. 75提高140。

電腦上的遺傳學 基因 適配值 10110 176 11001 150 00010 58 10110 176

電腦上的遺傳學 下一個運算元的因素則是雜交。雜交也發生在自然界中,將2組基因組原有的某一部分與另一組雜交,產生了新的2組基因組。如前圖所示,雜交發生在2組基因組之間,且發生的節點位置乃隨機決定。舉例來說:10110與00010這2組基因組在2與3之間的位置做雜交。過程如下: 10∣110 00∣010 ─────

電腦上的遺傳學 經過雜交後(加底線者為原本第2個基因組) 10 ∣ 010 00 ∣ 010 10 ∣ 010 00 ∣ 010 新產生的基因組,稱為子嗣 (children),皆繼承了來自雙親的某部份。雜交進行的過程就是選擇某一對基因後,再如擲銅板般隨機決定是否雜交基因。這個機率稱之為雜交機率 (crossover probability),通常以pc表示。0 . 5的雜交機率(與擲銅板擲到人頭那一面的機率相同)通常會帶來好結果。

電腦上的遺傳學 在這個例子中,10110與00010這2個基因組被選擇在2與3位元之間的位進行雜交,如下表。經過選擇與雜交,母群體的平均適配值由117 . 75提高到178 . 5。這對僅僅經過一代是相當了不起的進步。

電腦上的遺傳學 基因 p 適配值 10010 18 234 11001 25 150 00110 6 150 10110 22 176

電腦上的遺傳學 最後一種運算元的因素是突變。突變在自然界中極少發生,是因為親代在繁衍後代時,基因編碼產生了錯誤所致。在提高適應性上,選擇和雜交相當有助益,但與其原先的狀況有密切相關,隨機的特性也可能阻礙一些基因產生更好的組合。突變提供了另一種可能。自然界中,突變極少發生,在基因演算法裡其比例也很低,每一代的發生機率小於1為合理。

電腦上的遺傳學 假設接下來這一代第2個基因組第3個位元的位置發生了突變。下表顯示了經過突變後的基因組。如同多數突變一般,這個突變造成毀滅性的結果:該突變基因組也不可能存活至下一代。

電腦上的遺傳學 基因 p 適配值 10010 18 234 11101 29 58 00110 6 150 10110 22 176

電腦上的遺傳學 基因演算法就是基因在一代一代傳遞的過程中,藉由選擇,雜交,以及突變來不斷改善自身的適應力。它不一定會導向最適境界(optimal solution),但卻可以很快地接這個最適境界。

應用在類神經網路上 下圖顯示一個有3個輸入節點 ( input nodes)的簡單類神經網路,一個有2個輸入節點的隱藏層,以及一個輸出節點 (output nodes) 。使得這個網路運作順利的關鍵在於調整其中的加權值,如此最適的輸入才能得到正確的答案。第一個面對的問題是這個基因組的組成。基因組包含了許多組合在一起的加權數。每個加權值都介於0與1之間。

應用在類神經網路上

應用在類神經網路上 適配函數是什麼?將訓練系統內預測的輸出值與實際的輸出值相比較,是適配函數的基礎,也就是評估網路所犯的錯誤大小,這可以藉著取網路實際的輸出值與正確的輸出值的絕對值總和來衡量。 基因演算法就是求函數的最小值。

應用在類神經網路上 現在類神經網路內這個64位元的基因組包含了許多加權值。適配函數必須決定這些加權值的在訓練系統內的比重。要用基因演算法進行訓練需要起始母群體,然後進行選擇,雜交,以及突變。 關鍵是要將問題正確編碼成為基因組,然後尋找其正確的適配函數。

基因演算法的優點 基因演算法的優點有: ●產生可解釋的結果 ●結果易於應用 ●可以處理的資料型範圍極大 ●可以用在最適化(optimization)問題上 ●和類神經網路結合容易

基因演算法的缺點 基因演算法的缺點有: ●許多問題有編碼(encoding)上的困難 ●不保証最適化 ●運算成本極高 ●可以運用的商業套裝軟體不多