正文 字體大�。� 中
遺傳算法 Genetic Algorithm 簡(jiǎn)介 (2007-05-15 12:31:00)
一、概述
遺傳算法（Genetic Algorithm，縮寫(xiě)為GA）是一種有效的解決最優(yōu)化問(wèn)題的方法。它最先是由John Holland于1975年提出的。從那以后，它逐漸發(fā)展成為一種通過(guò)模擬自然進(jìn)化過(guò)程解決最優(yōu)化問(wèn)題的計(jì)算模型。
二、流程
遺傳算法求解問(wèn)題的過(guò)程如下: 1.首先生成一組初始的候選解群體(假設(shè)為M個(gè)候選解個(gè)體),稱(chēng)為第0代; 2.計(jì)算群體中各個(gè)候選解的適應(yīng)值; 3.如果有候選解滿足算法終止條件,算法終止,否則繼續(xù)4; 4.根據(jù)交配概率,將候選解群體中的個(gè)體隨機(jī)兩兩配對(duì),進(jìn)行交配操作以生成新的候選解; 5.根據(jù)變異概率,對(duì)4中生成的候選解群中的每個(gè)個(gè)體進(jìn)行變異操作; 6.使用選擇機(jī)制形成新一代候選解;轉(zhuǎn)2。 從上面的算法過(guò)程中,我們可以知道,用遺傳算法來(lái)求解問(wèn)題有四個(gè)基本要素:1候選解的表示方式;2適應(yīng)值的定義及度量方法;3算法的控制參數(shù)與變量;4算法終止準(zhǔn)則。 1、候選取解的表示方式,最簡(jiǎn)單的就是采用定長(zhǎng)二進(jìn)制編碼。如我們可以將十進(jìn)制的40轉(zhuǎn)換成二進(jìn)制的串,(40)10=(101000)2,反過(guò)來(lái)就可以將一個(gè)二進(jìn)制串解碼為一個(gè)十進(jìn)制整數(shù)。 2、適應(yīng)值的定義及度量方法與要解決的問(wèn)題有關(guān),通常用目標(biāo)函數(shù)來(lái)評(píng)估候選取解的優(yōu)劣。 3、算法的控制參數(shù)與變量。通常,我們把每一代中的候選解個(gè)數(shù)M稱(chēng)為群體規(guī)模,群體規(guī)模M在整個(gè)算法中一般是不變的一個(gè)常數(shù)。遺傳操作主要是雜交和變異兩個(gè)算子,并有其相應(yīng)的概率參數(shù)(Pc:雜交概率,Pm變異概率)來(lái)進(jìn)行控制。遺傳算法求解問(wèn)題時(shí),并不保證能找到滿足問(wèn)題要求的解,所以,還要設(shè)定算法的最大迭代次數(shù)(或稱(chēng)為代數(shù))。 4、算法終止準(zhǔn)則一般有:找到了滿足問(wèn)題的解;候選取群體已收斂于某一點(diǎn);算法已達(dá)到了設(shè)定的代數(shù)等。 這樣,一個(gè)簡(jiǎn)單遺傳算法的框架可非形式化地表示如下: Simple_Genetic_algorithm(){ t:=1; /*變量t表示迭代代數(shù)*/ 初始化候選解群體Population(t); 計(jì)算各個(gè)解的適應(yīng)值; do while(終止條件不滿足) { 隨機(jī)地將群中的個(gè)體兩兩配對(duì),進(jìn)行交配操作; 執(zhí)行變異操作; 利用選擇機(jī)制形成下一代候選取:Population(t+1):=Selection(Population(t)); t:=t+1; } } 三、交配、變異及選擇 我們以二進(jìn)制的表示方式來(lái)解釋遺傳算子及選擇機(jī)制。 在自然生物界,一個(gè)生物個(gè)體的特征通常被認(rèn)為是由其父輩遺傳下來(lái)的,當(dāng)然也可能有部分變異。而遺傳是由DNA來(lái)決定的。我們現(xiàn)在將一個(gè)候選解看成為生物個(gè)體中的一條DNA(假設(shè)該種生物的遺傳物質(zhì)只有一條DNA,并且不存在性別差異,即任意兩個(gè)個(gè)體都可以進(jìn)行交配),DNA鏈上的基因只有兩種類(lèi)型,可以分別將其定義為0或1。交配操作就是將兩個(gè)父輩串隨機(jī)從同一個(gè)位置分成兩段,然后進(jìn)行相應(yīng)段的交換,生成兩個(gè)相應(yīng)的子女。變異算子相對(duì)就要簡(jiǎn)單些,從個(gè)體串中隨機(jī)將某一位按變異概率進(jìn)行翻轉(zhuǎn)(0翻轉(zhuǎn)為1,1翻轉(zhuǎn)為0,即所謂的基因變)。 在實(shí)際算法中,雙親進(jìn)行交配操作是由交配概率Pc來(lái)控制,交配點(diǎn)的選擇也是隨機(jī)產(chǎn)生的。變異操作由變異概率進(jìn)行控制。 在群體規(guī)模為M的算法中,由M個(gè)個(gè)體的父輩群通過(guò)交配生成M個(gè)后代,M個(gè)后代再經(jīng)過(guò)變異操作又生成M個(gè)子代,這樣就要從M個(gè)父輩和M個(gè)子代中選擇M個(gè)個(gè)體來(lái)形成下一代解群體。簡(jiǎn)單遺傳算法就從M個(gè)子代中選擇M個(gè)個(gè)體來(lái)生成下一代。借鑒達(dá)爾文的進(jìn)化論的觀點(diǎn),適者生存,不適應(yīng)者被淘汰,那么,適應(yīng)值高的個(gè)體就應(yīng)該有更高的機(jī)會(huì)生存下來(lái),而適應(yīng)值很低的個(gè)體就被淘汰。也就是說(shuō),適應(yīng)值高的個(gè)體應(yīng)該有更多的機(jī)會(huì)來(lái)繁殖多個(gè)后代,適應(yīng)值低的個(gè)體就沒(méi)有機(jī)會(huì)繁殖后代。 在遺傳算法中,采用按比選擇的機(jī)制來(lái)形成下一代。設(shè)整個(gè)解群的平均適應(yīng)值為favg,則一個(gè)適應(yīng)值為fI的個(gè)體將被分配到fi/favg個(gè)后代。 這樣,高出平均適應(yīng)值的個(gè)體將會(huì)獲得多于一個(gè)的子女,而低于平均適應(yīng)值的個(gè)體最多只能得到一個(gè)后代。 簡(jiǎn)單遺傳算法采用一種稱(chēng)為"輪轉(zhuǎn)法"的方法來(lái)實(shí)現(xiàn)按比例選擇機(jī)制。在一個(gè)圓中,整個(gè)圓的弧度角為2л。根據(jù)適應(yīng)值,每個(gè)個(gè)體串fI在圓中分配這一個(gè)扇區(qū)(如圖1),扇區(qū)弧度的大小為(2лfi/favg)。所有扇區(qū)分配后,只要在0到2л之間產(chǎn)生一個(gè)隨機(jī)數(shù),該隨機(jī)數(shù)落在哪個(gè)扇區(qū)內(nèi),則該個(gè)體將被選中一次,有期望獲得繁殖以產(chǎn)生后代。在群體規(guī)模為M的算法中,只要重復(fù)地產(chǎn)生M個(gè)這樣的隨機(jī)數(shù),就可以從經(jīng)過(guò)遺傳操作生成的M個(gè)子代中選擇出M個(gè)體來(lái)形成下一代(當(dāng)然,有些個(gè)體一次都可能不會(huì)被選中,而有些個(gè)體被重復(fù)選中多次,下一代中就出現(xiàn)了多個(gè)同樣的父輩)。
四、總結(jié)
從以上介紹可以看出，GA算法具有下述特點(diǎn)： 1、GA是對(duì)問(wèn)題參數(shù)的編碼組進(jìn)行進(jìn)貨，而不是直接對(duì)參數(shù)本身。 2、GA的搜索是從問(wèn)題解的編碼組開(kāi)始搜索，而不是從單個(gè)解開(kāi)始。 3、GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。 4、GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則。 實(shí)踐表明，遺傳算法解最優(yōu)化問(wèn)題的計(jì)算效率比較高、適用范圍相當(dāng)廣。為了解釋這一現(xiàn)象，Holland給出了圖式定理。所謂圖式，就是某些碼位取相同值的編碼的集合。圖式定理說(shuō)明在進(jìn)化過(guò)程的各代中，屬于適應(yīng)度高、階數(shù)低且長(zhǎng)度短的圖式的編碼數(shù)量將隨代數(shù)以指數(shù)形式增長(zhǎng)。另外，Holland還發(fā)現(xiàn)遺傳算法具有隱含的并行計(jì)算特性。最近的研究則表明，上述遺傳算法經(jīng)適當(dāng)改進(jìn)后對(duì)任意優(yōu)化問(wèn)題以概率1收斂于全局最優(yōu)解。 將遺傳算法用于解決各種實(shí)際問(wèn)題后，人們發(fā)現(xiàn)遣傳算法也會(huì)由于各種原因過(guò)早向目標(biāo)函數(shù)的局部最優(yōu)解收斂，從而很難找到全局最優(yōu)解。其中有些是由于目標(biāo)函數(shù)的特性造成的，例如函數(shù)具有欺騙性，不滿足構(gòu)造模塊假說(shuō)等等；另外一些則是由于算法設(shè)計(jì)不當(dāng)。為此，不斷有人對(duì)遺傳算法提出各種各樣的改進(jìn)方案。例如：針對(duì)原先的定長(zhǎng)二進(jìn)制編碼方案；提出了動(dòng)態(tài)編碼、實(shí)數(shù)編碼等改進(jìn)方案；針對(duì)按比例的選擇機(jī)制，提出了競(jìng)爭(zhēng)選擇、按續(xù)挑選等改進(jìn)方案；針對(duì)原先的一點(diǎn)交叉算子，提出了兩點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等算子；針對(duì)原先遺傳算法各控制參數(shù)在進(jìn)化過(guò)程中不變的情況，提出了退化遺傳算法、自適應(yīng)遺傳算法等。另外，針對(duì)不同問(wèn)題還出現(xiàn)了分布式遺傳算法、并行遺傳算法等等。
分享
頂
閱讀┊ ┊ ┊┊ ┊打印┊
加載中，請(qǐng)稍候......
前一篇：《變形金剛》機(jī)器人造型曝光
后一篇：CListCtrl使用技巧[轉(zhuǎn)]
評(píng)論 重要提示：警惕虛假中獎(jiǎng)信息 在插畫(huà)中找尋曾經(jīng)的美好 關(guān)注每日最熱門(mén)博客
發(fā)評(píng)論 旅游行攝，輕品日本 是誰(shuí)改變了你的博客？ 關(guān)注每日最熱門(mén)博客
登錄名： 密碼： 找回密碼 注冊(cè)
昵 稱(chēng)：
驗(yàn)證碼： 請(qǐng)點(diǎn)擊后輸入驗(yàn)證碼
以上網(wǎng)友發(fā)言只代表其個(gè)人觀點(diǎn)，不代表新浪網(wǎng)的觀點(diǎn)或立場(chǎng)。
< 前一篇《變形金剛》機(jī)器人造型曝光
后一篇 >CListCtrl使用技巧[轉(zhuǎn)]
