智能優(yōu)化理論-第5章文化仿生智能算法

仿生智能算法REPORTING目錄5.1Memetic算法5.2文化算法PART015.1Memetic算法REPORTINGWENKUDESIGN5.1.1Memetic算法的提出Memetic算法是由澳大利亞學(xué)者M(jìn)oscato和Norman在1992年提出的一種仿生智能算法，結(jié)合了全局搜索和局部啟發(fā)式搜索。早在1976年，英國生態(tài)學(xué)家Dawkins在學(xué)術(shù)著作TheSelfishGene中首次提出新概念“meme”?！癿eme”（模因）與“gene”（基因）相對應(yīng)，是文化資訊傳承的單位。1989年，Moscato在撰寫的技術(shù)報告中首次提出了Memetic算法的概念，并把它作為一種基于群體優(yōu)化的混合式搜索算法。1992年，Moscato和Norman確立了Memetic算法，并成功應(yīng)用于求解TSP問題。目前Memetic算法已用于解決函數(shù)優(yōu)化、組合優(yōu)化、車間生產(chǎn)調(diào)度、物流與供應(yīng)鏈、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制、圖像處理等問題。遺傳算法基于達(dá)爾文的自然選擇、生物進(jìn)化論而創(chuàng)立，主要應(yīng)用于生物進(jìn)化層次。拉馬克挑戰(zhàn)了達(dá)爾文的理論，認(rèn)為生物體可以將其在生命過程中獲得的知識和經(jīng)驗(yàn)在進(jìn)化中傳遞到后代。生物進(jìn)化和社會發(fā)展具有某些共同特征，且相互補(bǔ)充。社會發(fā)展主要通過知識進(jìn)行傳遞，而傳遞方式包括結(jié)構(gòu)化的語言、思想和文化等。5.1.2Memetic算法的原理5.1.2Memetic算法的原理美國細(xì)胞生物學(xué)家威爾遜認(rèn)為，基因進(jìn)化主要發(fā)生在生物世界中，依賴于幾個世代的基因頻率的改變，因此是緩慢的；文化的發(fā)展以拉馬克理論為特征，依賴于獲得性狀的傳遞，相對來說傳遞速度比較快。在Memetic算法中，類似于遺傳算法中的基因庫，也有一個供模因進(jìn)行繁殖的模因庫。模因庫在復(fù)制過程中有的模因會比其他模因表現(xiàn)出更大的優(yōu)勢。Dawkins認(rèn)為模因和基因常常相互加強(qiáng)，自然選擇也有利于那些能夠?yàn)槠渥陨砝娑闷湮幕h(huán)境的模因。Dawkins的模因理論認(rèn)為，模因與基因類似，它是一代接一代往下傳遞的文化單位，如語言、觀念、信仰、行為方式等文化的傳遞過程中與基因在生物進(jìn)化過程中起到類似的作用。模因在傳播中往往會因個人的思想和理解而改變，因此父代傳遞給子代時信息可以改變，表現(xiàn)在算法上就有了局部搜索的過程。5.1.2Memetic算法的原理在模因的影響下，個體都具有自我學(xué)習(xí)的傾向，即個體進(jìn)行自我調(diào)整，提高自身競爭力，并由此影響下一代新產(chǎn)生的個體。Memetic算法也可以看成遺傳算法與局部搜索算法的結(jié)合，在遺傳算法過程中，所有通過進(jìn)化生成的新的個體在被放入種群之前均要執(zhí)行局部搜索，以實(shí)現(xiàn)個體在局部領(lǐng)域內(nèi)的學(xué)習(xí)。在Memetic算法中，基因?qū)?yīng)著問題的解，而模因?qū)?yīng)著解的局部搜索策略。因?yàn)槟Ｒ虻囊?，代與代之間的個體競爭力在不斷提高。5.1.2Memetic算法的原理進(jìn)化階段通過選擇、交叉、變異3個遺傳算子，在現(xiàn)有種群上產(chǎn)生新種群。選擇根據(jù)適應(yīng)度值函數(shù)評價每個染色體的質(zhì)量，適應(yīng)度值較好的個體以更大概率被選擇進(jìn)入下一操作。染色體編碼及初始種群產(chǎn)生根據(jù)問題類型確定染色體編碼方式，隨機(jī)生成種群大小的染色體，生成初始種群。5.1.3Memetic算法的描述

5.1.3Memetic算法的描述交叉模仿生物體的繁殖過程，通過對完成選擇操作后的種群中的個體進(jìn)行兩兩交叉，將會生成同等數(shù)量的新的個體。單點(diǎn)交叉在個體編碼串中隨機(jī)設(shè)置一個交叉點(diǎn)，然后在該點(diǎn)相互交換兩個配對個體的部分基因。多點(diǎn)交叉具體操作過程首先在相互配對的兩個個體編碼串中隨機(jī)設(shè)置幾個交叉點(diǎn)，然后交換每個交叉點(diǎn)之間的部分基因。03變異將個體編碼串中的某些基因值用其他基因值來替換，從而形成一個新的個體。01均勻交叉兩個配對個體的每一位基因都以相同的概率進(jìn)行交換，從而形成兩個新的個體。02算術(shù)交叉由兩個個體的線性組合而產(chǎn)生出新的個體。5.1.3Memetic算法的描述Memetic算法的實(shí)現(xiàn)首先需要初始化種群，通過隨機(jī)生成一組空間分布的染色體（解）作為初始解。通過迭代搜索最優(yōu)解，在每一次迭代中，染色體通過交叉、變異和局部搜索進(jìn)行更新。該算法與遺傳算法有相似之處，但又不局限于簡單遺傳算法，它充分吸收了遺傳算法和局部搜索算法的優(yōu)點(diǎn)。它不僅具有很強(qiáng)的全局尋優(yōu)能力，同時每次交叉和變異后均進(jìn)行局部搜索，通過優(yōu)化種群分布，及早剔除不良種群，進(jìn)而減少迭代次數(shù)，加快算法的求解速度，保證了算法解的質(zhì)量。在Memetic算法中，局部搜索策略非常關(guān)鍵，它直接影響到算法的效率。01020304055.1.4Memetic算法的流程5.1.5Memetic算法的特點(diǎn)及其意義01Memetic算法具有并行性，表現(xiàn)在內(nèi)在并行性和內(nèi)含并行性兩方面。02內(nèi)在并行性適合于大規(guī)模運(yùn)算，讓多臺機(jī)器各自獨(dú)立運(yùn)行種群進(jìn)化運(yùn)算。內(nèi)含并行性可以同時搜索種群的不同方向，提高了搜索最優(yōu)解的概率。03適應(yīng)度函數(shù)評估個體，不受約束條件限制，不需要目標(biāo)函數(shù)導(dǎo)數(shù)，適合復(fù)雜優(yōu)化問題。群體搜索策略擴(kuò)大了解的搜索空間，提高算法的全局搜索能為與求解質(zhì)量。局部搜索策略改善了種群結(jié)構(gòu)，提高算法局部搜索能力。5.1.5Memetic算法的特點(diǎn)及其意義5.1.5Memetic算法的特點(diǎn)及其意義容錯能力很強(qiáng)，初始種群可能包含與最優(yōu)解相差很遠(yuǎn)的個體，但算法能通過遺傳操作與局部搜索等策略過濾掉適應(yīng)度很差的個體。Memetic算法提供了一種解決優(yōu)化問題的新方法，對于不同領(lǐng)域的優(yōu)化問題，可以通過改變交叉、變異和局部搜索策略來求解，擴(kuò)大了算法的應(yīng)用領(lǐng)域。PART025.2文化算法REPORTINGWENKUDESIGN文化算法是由美國學(xué)者Reynolds在1994年提出的，是一種通過文化系統(tǒng)演化模型求解進(jìn)化計算問題的算法。文化算法被定義為“一個通過符號編碼表示眾多概念的系統(tǒng)，而這些概念是在群體內(nèi)部及不同群體之間被廣泛和相對長久傳播的”。文化算法已用于解決約束單目標(biāo)優(yōu)化、多目標(biāo)優(yōu)化、作業(yè)調(diào)度、圖像分割、語義網(wǎng)絡(luò)、數(shù)據(jù)挖掘、航跡規(guī)劃等問題。5.2.1文化算法的提出5.2.2文化算法的基本結(jié)構(gòu)與原理信念空間和種群空間。文化算法是一種基于知識的雙層進(jìn)化系統(tǒng)，包含兩個進(jìn)化空間種群空間、信念空間和接口函數(shù)。接口函數(shù)包括接收、更新、影響函數(shù)。文化算法基本結(jié)構(gòu)包括三大部分種群空間模擬個體根據(jù)一定行為準(zhǔn)則進(jìn)化，信念空間模擬文化形成、傳遞、比較和更新等進(jìn)化過程。兩個空間相互獨(dú)立演化，定期貢獻(xiàn)精英個體給上層空間，上層空間不斷進(jìn)化精英群體影響或控制下層空間群體。通過特定協(xié)議進(jìn)行信息交流，形成“雙演化、雙促進(jìn)”的進(jìn)化機(jī)制。0102035.2.2文化算法的基本結(jié)構(gòu)與原理信念空間將得到的個體經(jīng)驗(yàn)按一定規(guī)則比較優(yōu)化，形成群體經(jīng)驗(yàn)，并根據(jù)新獲取的個體經(jīng)驗(yàn)通過更新函數(shù)更新現(xiàn)有的信念空間。信念空間用更新后的群體經(jīng)驗(yàn)通過影響函數(shù)來修改種群空間中個體的行為規(guī)則，進(jìn)而高效地指引種群空間的進(jìn)化。文化算法的基本原理：通過性能函數(shù)評價種群空間的個體適應(yīng)度，將種群空間個體在進(jìn)化過程中所形成的個體經(jīng)驗(yàn)傳遞給信念空間。5.2.2文化算法的基本結(jié)構(gòu)與原理5.2.2文化算法的基本結(jié)構(gòu)與原理選擇函數(shù)從現(xiàn)有種群中選擇一部分個體作為下一代個體的父輩，進(jìn)行下一輪的迭代，直至滿足終止條件。文化算法提供了一種多進(jìn)化過程的計算模型，任何符合文化算法要求的進(jìn)化算法都可以嵌入框架中作為種群空間的一個進(jìn)化過程。5.2.3文化算法求解約束優(yōu)化問題的描述寫設(shè)計01文化算法的設(shè)計過程包括：種群空間和信念空間設(shè)計；接收函數(shù)、更新函數(shù)和影響函數(shù)設(shè)計。02文化算法中存在著多種類型的知識，即約束知識、規(guī)范知識、地形知識、環(huán)境知識等。03種群空間設(shè)計是指對個體進(jìn)行編碼，以浮點(diǎn)數(shù)編碼為例，編碼長度等于問題定義的解的變量個數(shù)。5.2.3文化算法求解約束優(yōu)化問題的描述寫設(shè)計每個基因等于解的每一維變量，若待求解問題中的一個有效解為D為解的變量維數(shù)，則即為解對應(yīng)的編碼。02約束知識用于表達(dá)和處理約束條件（邊界），將搜索空間劃分為可行域和非可行域，并劃分為較小的子空間，稱為“元”。03每個信念元都包含若干屬性，如Classi表示約束性質(zhì)，Cntli、Cnt2i是內(nèi)置于信念元的計數(shù)器，分別表示該區(qū)域中可行和非可行候選解的個數(shù)。01d[]用來記錄第i信念元在哪些維度上進(jìn)行劃分，生成子樹。lNode[]、uNode[]均為1×n的向量，分別表示第i信念元各維度上的最小值和最大值。lNode[]與uNode[]結(jié)合起來，定義了信念元i的邊界范圍；Parenti表示信念樹中該信念元的父節(jié)點(diǎn)：Childreni表示信念樹中該信念元的子節(jié)點(diǎn)列表。Cntli與Cnt2i結(jié)合起來還可提供該區(qū)域內(nèi)可行候選解與非可行候選解的相對比例；Deepi用來表示第i信念元所處的信念樹（在“地形知識”部分介紹）的深度。5.2.3文化算法求解約束優(yōu)化問題的描述寫設(shè)計03算法初始化主要實(shí)現(xiàn)對種群空間和信念空間的初始化，并評估初始種群的適應(yīng)度。01實(shí)現(xiàn)基本文化算法的程序流程包括參數(shù)初始化、算法初始化、搜索求解和輸出結(jié)果四個步驟。02參數(shù)初始化是對手動輸入的設(shè)置，包括輸入種群艦?zāi)?、種群最大