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

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

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