人工智能原理及MATLAB實(shí)現(xiàn) 課件 第5章 計(jì)算智能

第五章計(jì)算智能第五章計(jì)算智能5.1進(jìn)化算法定義進(jìn)化計(jì)算（EvolutionaryAlgorithm，EA）是通過(guò)模仿自然界生物基因遺傳與種群進(jìn)化的過(guò)程和機(jī)制，而產(chǎn)生的一種群體導(dǎo)向隨機(jī)搜索技術(shù)和方法。進(jìn)化算法是一種模擬自然選擇和遺傳學(xué)機(jī)制的優(yōu)化算法，包括遺傳算法、遺傳規(guī)劃、進(jìn)化策略和進(jìn)行規(guī)劃等。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法遺傳算法（GeneticAlgorithms，GA）的基本思想是基于達(dá)爾文（Darwin）的進(jìn)化論和孟德?tīng)枺∕endel）的遺傳學(xué)說(shuō)。20世紀(jì)70年代初，美國(guó)Michigen大學(xué)的約翰·霍蘭德（JohnHolland）教授受到達(dá)爾文進(jìn)化論的啟發(fā)，用數(shù)碼串來(lái)類比生物中的染色個(gè)體，通過(guò)選擇、交叉、變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色體所蘊(yùn)涵問(wèn)題解的質(zhì)量的優(yōu)劣，通過(guò)種群的不斷“更新?lián)Q代”，從而提高種群的平均適應(yīng)度，通過(guò)適應(yīng)度函數(shù)引導(dǎo)種群的進(jìn)化方向，并在此基礎(chǔ)上，使得最優(yōu)個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.1

遺傳算法的基本原理1．編碼與解碼將問(wèn)題變換為位串形式編碼表示的過(guò)程稱為編碼；相反地，將位串形式編碼表示變換為原問(wèn)題結(jié)構(gòu)的過(guò)程稱為解碼或碼。把位串形式編碼表示稱為染色體或個(gè)體。編碼的方法影響到遺傳算子的計(jì)算方法。常用的編碼方法有以下4種：（1）二進(jìn)制編碼。它是遺傳算法編碼中最常用的方法。（2）符號(hào)編碼。（3）浮點(diǎn)數(shù)編碼，也稱為真值編碼方法。（4）格雷編碼。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.1

遺傳算法的基本原理2.適應(yīng)度函數(shù)為了體現(xiàn)個(gè)體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)個(gè)體都能進(jìn)行量度的函數(shù)，即適應(yīng)度函數(shù)。適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性。常見(jiàn)的幾種適應(yīng)度函數(shù)變換方法：（1）線性變換：f(Z)=aZ+b（2）冪變換：f(Z)=Za（3）指數(shù)變換：f(Z)=exp(－βZ)對(duì)于有約束條件的極值，其適應(yīng)度可用罰函數(shù)方法處理。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.1

遺傳算法的基本原理3.遺傳算子遺傳算子就是遺傳算法中進(jìn)化的規(guī)則。基本遺傳算法的遺傳算子主要有選擇算子、交叉算子和變異算子。（1）選擇算子。也稱復(fù)制算子，是GA的關(guān)鍵。常用選擇算子的操作方法有賭輪選擇方法、排序選擇法、最優(yōu)保存策略。（2）交叉算子。交叉算子體現(xiàn)了自然界信息交換的思想，其作用是將原有群體的優(yōu)良基因遺傳給下一代，并生成包含更復(fù)雜結(jié)構(gòu)的新個(gè)體。交叉算子有一點(diǎn)交叉、二點(diǎn)交叉、多點(diǎn)交叉和一致交叉等。（3）變異算子。變異算子是遺傳算法中保持物種多樣性的一個(gè)重要途徑，它模擬了生物進(jìn)化過(guò)程中的偶然基因突變現(xiàn)象。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.2遺傳算法的求解步驟1.對(duì)問(wèn)題進(jìn)行編碼；2.定義適應(yīng)度函數(shù)后，生成初始化群體；3.對(duì)于得到的群體進(jìn)行選擇復(fù)制，交叉，變異操作，生成下一代種群；4.判斷算法是否滿足停止準(zhǔn)則。若不滿足，則從步驟③起重復(fù)；5.算法結(jié)束，獲得最優(yōu)解。流程圖第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.3算法控制參數(shù)的選擇1.對(duì)問(wèn)題進(jìn)行編碼；2.定義適應(yīng)度函數(shù)后，生成初始化群體；3.對(duì)于得到的群體進(jìn)行選擇復(fù)制，交叉，變異操作，生成下一代種群；4.判斷算法是否滿足停止準(zhǔn)則。若不滿足，則從步驟③起重復(fù)；5.算法結(jié)束，獲得最優(yōu)解。第五章計(jì)算智能5.1進(jìn)化算法5.1.1遺傳算法

5.1.1.4遺傳算法的特點(diǎn)編碼性4.多解性和全局優(yōu)性自適應(yīng)性5.不確定性隱含并行性6.智能性第五章計(jì)算智能5.1進(jìn)化算法5.1.2進(jìn)化策略

20世紀(jì)60年代，德國(guó)柏林大學(xué)的因戈·雷切伯格（I.Rechenberg）和施韋費(fèi)爾（H.P.Schwefel）等在進(jìn)行風(fēng)洞試驗(yàn)時(shí)，研究發(fā)展形成了進(jìn)化策略方法。進(jìn)化策略以其簡(jiǎn)單、通用、魯棒性和適應(yīng)性而聞名，在確定了編碼方案、適應(yīng)度函數(shù)及遺傳算法以后，算法將根據(jù)“適者生存，不適者淘汰”的策略，利用進(jìn)化中獲得的信息自行組織搜索，從而不斷地向最佳方向逼近。第五章計(jì)算智能5.1進(jìn)化算法5.1.2進(jìn)化策略算法基本流程第五章計(jì)算智能5.2模糊計(jì)算1965年，美國(guó)控制論專家拉特飛·扎德（L.A.Zadeh）把模糊性和數(shù)學(xué)統(tǒng)一起來(lái)，提出了模糊集合理論與模糊邏輯，它采用精確的方法、公式和模型來(lái)度量和處理模糊、信息不完整或不太正確的現(xiàn)象與規(guī)律。第五章計(jì)算智能5.2模糊計(jì)算5.2.1模糊系統(tǒng)理論基礎(chǔ)模糊系統(tǒng)是建立在自然語(yǔ)言基礎(chǔ)上的。在自然語(yǔ)言中常采用一些模糊概念如“大約”、“左右”、“溫度偏高”等來(lái)表示一些量化指標(biāo)，如何對(duì)這些模糊概念進(jìn)行分析、推理，是模糊集合與模糊邏輯所要解決的問(wèn)題。第五章計(jì)算智能5.2模糊計(jì)算5.2.2模糊規(guī)則和推理在模糊邏輯中，模糊規(guī)則實(shí)質(zhì)上指的是模糊蘊(yùn)含關(guān)系，即在“如果x是A，則y是B條件下，若x是，則y是”。其中A、、B、均代表模糊語(yǔ)言，并用A→B表示該提出條件，即A與B之間的模糊關(guān)系。第五章計(jì)算智能5.2模糊計(jì)算5.2.3模糊聚類分析物以類聚，將相似相像的事物歸為一類，這就是聚類分析。模糊聚類分析是利用模糊等價(jià)關(guān)系來(lái)實(shí)現(xiàn)的?；谀：葍r(jià)關(guān)系的聚類分析可分為如下三步：第1步：建立模糊相似矩陣第2步：改造模糊相似關(guān)系為模糊等價(jià)關(guān)系第3步：聚類第五章計(jì)算智能5.3搜索算法1.搜索對(duì)象2.搜索的擴(kuò)展規(guī)則3.搜索的目標(biāo)測(cè)試5.3.1搜索過(guò)程的三大要素第五章計(jì)算智能5.3搜索算法（1）根據(jù)問(wèn)題定義相應(yīng)的狀態(tài)空間，確定狀態(tài)的一般表示，它含有相關(guān)對(duì)象各種可能的排列。（2）規(guī)定一組操作（算子），能夠作用于一個(gè)狀態(tài)后過(guò)渡到另一個(gè)狀態(tài)。（3）決定一種搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿某個(gè)路徑達(dá)到目標(biāo)狀態(tài)。5.3.2搜索算法的基本步驟第五章計(jì)算智能5.3搜索算法隨機(jī)搜索算法－模擬退火算法演化搜索算法－人工免疫算法記憶型搜索算法－禁忌搜索算法、和聲搜索算法5.3.3典型的搜索算法第五章計(jì)算智能5.4群智能算法群智能算法是一類基于群體行為原理的優(yōu)化算法，其靈感來(lái)源于自然界中的群體行為，如蟻群覓食、鳥(niǎo)群遷徙等。這類算法通過(guò)模擬群體中個(gè)體的行為和相互作用，尋找滿足某種優(yōu)化目標(biāo)的解。一些典型的群智能算法：1.蟻群算法2.粒子群算法3.人工魚(yú)群算法4.人工蜂群算法第五章計(jì)算智能5.4群智能算法5.4.1群智能概述最優(yōu)化問(wèn)題是個(gè)古老的課題，早在17世紀(jì)歐洲就有人提出了求解最大值最小值的問(wèn)題，給出了一些求解法則，并隨著科學(xué)的發(fā)展，逐漸提出了許多優(yōu)化算法，由此形成了系統(tǒng)的優(yōu)化理論和算法，如無(wú)約束優(yōu)化和約束優(yōu)化、線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃等。受算法原理的限制，這些傳統(tǒng)的優(yōu)化算法一般只適用于求解小規(guī)模問(wèn)題，在計(jì)算速度、收斂性、初值敏感性等方面遠(yuǎn)遠(yuǎn)達(dá)不到實(shí)際問(wèn)題的優(yōu)化要求，不適合求解復(fù)雜的優(yōu)化問(wèn)題，弱化了其在實(shí)際工程中的應(yīng)用。第五章計(jì)算智能5.4群智能算法5.4.2群智能的一般框架在構(gòu)建一個(gè)群智能算法中，應(yīng)滿足以下五條基本的原則：（1）ProximityPrinciple（2）QualityPrinciple（3）PrincipleofDiverseResponse（4）Stabilityprinciple（5）AdaptabilityPrinciple第五章計(jì)算智能5.4群智能算法5.4.3群智能的共性要素不同個(gè)體的群智能種群的表現(xiàn)形式是多種多樣的，其中一些共性要素及其在群智能中發(fā)揮的作用是在構(gòu)建群智能需要完成的工作。1.確定時(shí)空環(huán)境2.確定組織結(jié)構(gòu)3.確定通信與語(yǔ)言形式4.確定競(jìng)爭(zhēng)與合作等個(gè)體關(guān)系5.確定記憶信息與學(xué)習(xí)內(nèi)容方式6.確定綜合決策第五章計(jì)算智能5.4群智能算法5.4.4構(gòu)建有效的群智能優(yōu)化算法群智能優(yōu)化算法是通過(guò)模擬群智能群體中個(gè)體與群體的行為而抽象出來(lái)的一種數(shù)學(xué)求解過(guò)程。群體智能是用隨機(jī)分布在搜索優(yōu)化空間的點(diǎn)來(lái)模擬自然界中的個(gè)體，用個(gè)體的進(jìn)化過(guò)程作為隨機(jī)搜索最優(yōu)解的過(guò)程，用求解問(wèn)題的目標(biāo)函數(shù)來(lái)判斷個(gè)體對(duì)于環(huán)境的適應(yīng)能力，根據(jù)適應(yīng)能力而優(yōu)勝劣汰，將整個(gè)群體逐步向最優(yōu)解靠近。第五章計(jì)算智能5.4群智能算法5.4.5群體智能算法的特點(diǎn)與傳統(tǒng)的優(yōu)化方法相比，群體智能算法具有以下的特點(diǎn)。1.簡(jiǎn)單的迭代式尋優(yōu)2.環(huán)境自適應(yīng)性和系統(tǒng)自調(diào)節(jié)性3.有指導(dǎo)的隨機(jī)并行式全局搜索4.系統(tǒng)通用性和魯棒性強(qiáng)5.智能性6.易于與其他算法相結(jié)合第五章計(jì)算智能5.4群智能算法5.4.6群智能優(yōu)化算法蟻群算法粒子群算法人工魚(yú)群算法人工蜂群算法第五章計(jì)算智能5.5混合優(yōu)化算法混合優(yōu)化算法策略的關(guān)鍵問(wèn)題是問(wèn)題分解與綜合的處理、子算法和領(lǐng)域函數(shù)的選擇、進(jìn)程層次上算法轉(zhuǎn)換接口的處理、優(yōu)化過(guò)程中的數(shù)據(jù)處理。目前混合算法的結(jié)構(gòu)類型主要可歸結(jié)為串行、鑲嵌、并行及混合結(jié)構(gòu)。第五章計(jì)算智能5.5混合優(yōu)化算法5.5.1混合優(yōu)化策略的關(guān)鍵問(wèn)題1.問(wèn)題分解與綜合的處理2.