遺傳算法及其在圖像分割中的應(yīng)用.ppt

《遺傳算法及其在圖像分割中的應(yīng)用.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、遺傳算法及其在圖像分割中的應(yīng)用目錄遺傳算法簡(jiǎn)介圖像分割簡(jiǎn)介一維最大熵閾值分割二維最大熵閾值分割9/21/20212遺傳算法簡(jiǎn)稱GA（GeneticAlgorithms）遺傳算法是20世紀(jì)60~70年代主要由美國(guó)JohnHolland教授提出。其內(nèi)涵哲理啟迪于自然界生物從低級(jí)、簡(jiǎn)單到高級(jí)、復(fù)雜，乃至人類這樣一個(gè)漫長(zhǎng)而絕妙的進(jìn)化過(guò)程。借鑒Darwin的物競(jìng)天擇、優(yōu)勝劣汰、適者生存的自然選擇和自然遺傳的機(jī)理。其本質(zhì)是一種求解問(wèn)題的高效并行全局搜索方法，它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最優(yōu)解。遺傳

2、算法9/21/20213遺傳算法基本思想從初始化的群體出發(fā)，通過(guò)隨機(jī)選擇(復(fù)制)（使群體中優(yōu)秀的個(gè)體有更多的機(jī)會(huì)傳給下一代），交叉（體現(xiàn)了自然界中群體內(nèi)個(gè)體之間的信息交換），和變異（在群體中引入新的變種確保群體中信息的多樣性）等遺傳操作，使最具有生存能力的染色體以最大可能生存,群體一代一代地進(jìn)化到搜索空間中越來(lái)越好的區(qū)域.9/21/20214基本遺傳算法的構(gòu)成要素(1)染色體編碼方法基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來(lái)表示群體中的個(gè)體，其等位基因由二值符號(hào)集{0，1}組成。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來(lái)生成。如：x

3、；100111001000101101就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是l＝18。(2)個(gè)體適應(yīng)度評(píng)價(jià)基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。9/21/20215(3)遺傳算子基本遺傳算法使用下述三種遺傳算子：?選擇運(yùn)算：使用比例選擇算子；?交叉運(yùn)算：使用單點(diǎn)交叉算子；?變異運(yùn)算：使用基本位變異算子。(4)基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：?M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20~100。?T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100~5

4、00?pc：交叉概率，一般取為0.4~0.99?pm：變異概率，一般取為0.0001~0.19/21/20216基本遺傳算法的形式化定義基本遺傳算法可定義為一個(gè)7元組：GA＝(M,F,s,c,m,pc,pm)M——群體大?。籉——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算于；c——交叉操作算子：m——變異操作算于；pc——交叉概率；pm——變異概率；9/21/20217基本遺傳算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t

5、);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend9/21/20218基本遺傳算法的實(shí)現(xiàn)根據(jù)上面對(duì)基本遺傳算法構(gòu)成要素的分析和算法描述，我們可以很方便地用計(jì)算機(jī)語(yǔ)言來(lái)實(shí)現(xiàn)這個(gè)基本遺傳算法?，F(xiàn)對(duì)具體實(shí)現(xiàn)過(guò)程中的問(wèn)題作以下說(shuō)明：一）編碼與解

6、碼(1)編碼假設(shè)某一參數(shù)的取值范圍是[umin,umax]，用長(zhǎng)度為l的二進(jìn)制編碼符號(hào)串來(lái)表示該參數(shù)，則它總共能夠產(chǎn)生2l種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：00000000…00000000＝0umin00000000…00000001＝1umin+?00000000…00000010＝2umin+2?……11111111…11111111=2l–1umax9/21/20219其中，?為二進(jìn)制編碼的編碼精度，其公式為：(2)解碼假設(shè)某一個(gè)體的編碼是：則對(duì)應(yīng)的解碼公式為：9/21/202110二）個(gè)體適應(yīng)度評(píng)價(jià)一般情況下，根據(jù)目標(biāo)

7、函數(shù)值來(lái)進(jìn)行種群中個(gè)體適應(yīng)度值的計(jì)算。(1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(X)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)(2)對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問(wèn)題，即：minf(X)＝max(-f(X))9/21/202111三）選擇算子(1)選擇算子或復(fù)制算子的作用：從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。(2)最常用和最基本的選擇算子：比例選擇算子。(3)比例選擇算子：指?jìng)€(gè)體被選

8、中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。(4)執(zhí)行比例選擇的手段是輪盤選擇。輪盤法的基本精神是：個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度：pi=fi/?fi(i=1,2,…,M)式中pi——個(gè)體i被選中的概