人工智能原理及MATLAB實現(xiàn) 教案 第5章 計算智能

《人工智能算法》課程教案教學(xué)目的、要求：1.掌握進化算法、搜索算法、群智能算法、混合優(yōu)化算法的基本概念和原理2.熟悉模糊計算基礎(chǔ)知識3.理解算法的分析步驟、應(yīng)用場景和優(yōu)勢4.能夠?qū)崿F(xiàn)簡單的算法并進行實驗驗證教學(xué)重點及難點：重點：算法的原理難點：簡單算法的實現(xiàn)和應(yīng)用教學(xué)基本內(nèi)容教學(xué)過程設(shè)計§5計算智能§5.1進化算法進化算法是一種模擬自然選擇和遺傳學(xué)機制的優(yōu)化算法，用于解決復(fù)雜的搜索和優(yōu)化問題，其應(yīng)用廣泛。進化算法包括遺傳算法、遺傳規(guī)劃、進化策略和進行規(guī)劃等，在此只介紹遺傳算法和進化策略。遺傳算法（GeneticAlgorithms，GA）：基本思想是基于達爾文（Darwin）的進化論和孟德爾（Mendel）的遺傳學(xué)說；工作對象是字符串。對于整個遺傳算法影響最大的是編碼和適應(yīng)度函數(shù)的設(shè)計。編碼是應(yīng)用遺傳算法時要解決的首要關(guān)鍵問題。編碼的方法也影響到遺傳算子的計算方法。常用的編碼方法有以下4種：（1）二進制編碼。它是遺傳算法編碼中最常用的方法。（2）符號編碼。（3）浮點數(shù)編碼，也稱為真值編碼方法。適用于精度要求較高的遺傳算法，以便于在較大空間進行遺傳搜索。（4）格雷編碼。為了體現(xiàn)個體的適應(yīng)能力，引入了對問題中的每一個個體都能進行量度的函數(shù)，即適應(yīng)度函數(shù)。適應(yīng)度函數(shù)求取的是極大值，并且具有非負性。常見的幾種變換方法：（1）線性變換：f(Z)=aZ+b（2）冪變換：f(Z)=Za（3）指數(shù)變換：f(Z)=exp(－βZ)對于有約束條件的極值，其適應(yīng)度可用罰函數(shù)方法處理。遺傳算子就是遺傳算法中進化的規(guī)則。基本遺傳算法的遺傳算子主要有選擇算子、交叉算子和變異算子。遺傳算法的具體步驟：①對問題進行編碼；②定義適應(yīng)度函數(shù)后，生成初始化群體；③對于得到的群體進行選擇復(fù)制，交叉，變異操作，生成下一代種群；④判斷算法是否滿足停止準(zhǔn)則。若不滿足，則從步驟③起重復(fù)；⑤算法結(jié)束，獲得最優(yōu)解。遺傳算法中需要選擇的參數(shù)主要有串長l、群體大小n、交叉概率pc以及變異概率pm等。與其他方法相比，遺傳算法具有編碼性、多解性和全局優(yōu)化性、自適應(yīng)性、不確定性、隱含并行性、智能性的優(yōu)點。進化策略（EvolutionStrategies，ES）：20世紀(jì)60年代，德國柏林大學(xué)的因戈·雷切伯格（I.Rechenberg）和施韋費爾（H.P.Schwefel）等在進行風(fēng)洞試驗時，研究發(fā)展形成了進化策略方法。進化策略以其簡單、通用、魯棒性和適應(yīng)性而聞名，是專門為求解參數(shù)優(yōu)化問題而設(shè)計的，而且在進化策略算法中引入了自適應(yīng)機制。算法的基本流程。算法的構(gòu)成要素：染色體構(gòu)造：（X,σ）=（（x1,x2,…,xL），（σ1,σ2,…,σL））算子：①重組算子。重組是將參與重組的父代染色體上的基因進行交換，形成下一代的染色體的過程。目前常見的有離散重組、中間重組、混雜重組等；②變異算子：③選擇算子。在進化策略中，選擇過程是確定性的。在不同的進行策略中，選擇機制也有所不同。§5.2模糊計算1965年，美國控制論專家拉特飛·扎德（L.A.Zadeh）把模糊性和數(shù)學(xué)統(tǒng)一起來，提出了模糊集合理論與模糊邏輯，它采用精確的方法、公式和模型來度量和處理模糊、信息不完整或不太正確的現(xiàn)象與規(guī)律。模糊集是一種邊界不分明的集合。隸屬函數(shù)的表示方法：模糊系統(tǒng)中常用的隸屬度函數(shù)有11種，例如高斯形、鐘形等隸屬度函數(shù)。模糊集運算：交集（邏輯與）、合集（邏輯或）/邏輯非（余）、模糊集的基。設(shè)A∈F(U)，對任意λ∈[0，1]，集合稱為集合A的λ截集，λ稱為閾值或置信水平。截集的概述描述了模糊集合與普通集合之間的轉(zhuǎn)換關(guān)系。模糊度是模糊集合的度量，有以下幾種計算方式：距離模糊度。設(shè)A0.5是A的λ＝0.5截集，有熵模糊度。如果令，則熵模糊度的定義為貼近度。用距離刻畫模糊集的模糊度效果不是很理想，可以用貼近度來衡量兩個模糊集之間的相近程度，貼近度越大，則表明這兩者越接近。聚類分析就是將相似相像的事物歸為一類。模糊聚類分析是利用模糊等價關(guān)系來實現(xiàn)的?；谀：葍r關(guān)系的聚類分析可分為三步：（1）建立模糊相似矩陣第一步是求樣本集中任意兩個樣本Xi與Xj之間的相似系數(shù)rij，進而構(gòu)造模糊相似矩陣R=(rij)n×n。①數(shù)量積法②相關(guān)系數(shù)法還包括絕對值減數(shù)法、算術(shù)平均法等。（2）改造模糊相似關(guān)系為模糊等價關(guān)系（3）聚類對求得的模糊等價矩陣求λ－截集Rλ，再將Rλ中為1的元素對應(yīng)行和列的對象歸并為一類，由Rλ的分類由細變粗，形成一個動態(tài)的分類圖。§5.3搜索算法搜索過程有三大要素：搜索對象、搜索的擴展規(guī)則和搜索的目標(biāo)測試。通過搜索求解問題的基本思想：（1）將問題中的已知條件看成狀態(tài)空間中的初始狀態(tài)；將問題中要求達到的目標(biāo)看成狀態(tài)空間中的目標(biāo)狀態(tài)；將問題中其他可能發(fā)生的情況看成狀態(tài)空間中的任一狀態(tài)。（2）設(shè)法在狀態(tài)空間尋找一條路徑，由初始狀態(tài)出發(fā)，能夠沿著這條路徑達到目標(biāo)狀態(tài)。典型的搜索方法有：隨機搜索算法（例如模擬退火算法）、演化搜索算法（例如人工免疫算法）、記憶型搜索算法（例如禁忌搜索算法、和聲搜索算法）?！?.4群智能算法群智能（SwarmIntelligence，SI）的概念最早由貝尼（Beni）、哈克伍德（Hackwood）和王（Wang）等人在分子自動機系統(tǒng)中提出，指的是“無智能的主體通過合作表現(xiàn)出宏觀智能行為的特性”。1999年，埃里克·博納博（EricBonabeau）、馬爾科·多里戈（MarcoDorigo）和蓋伊·特絡(luò)拉茲（GuyTheraulaz）在《SwarmIntelligenceFromNaturetoArtificialSystems》中對群智能進行了詳細的論述和分析。群智能算法是一類基于群體行為原理的優(yōu)化算法，其靈感來源于自然界中的群體行為，如蟻群覓食、鳥群遷徙等。這類算法通過模擬群體中個體的行為和相互作用，尋找滿足某種優(yōu)化目標(biāo)的解。在構(gòu)建一個群智能算法中，應(yīng)滿足五條基本原則：鄰近原則、品質(zhì)原則、多樣性原則、穩(wěn)定性原則、適應(yīng)性原則。群體智能是用隨機分布在搜索優(yōu)化空間的點來模擬自然界中的個體，用個體的進化過程作為隨機搜索最優(yōu)解的過程，用求解問題的目標(biāo)函數(shù)來判斷個體對于環(huán)境的適應(yīng)能力，根據(jù)適應(yīng)能力而優(yōu)勝劣汰，將整個群體逐步向最優(yōu)解靠近。與傳統(tǒng)的優(yōu)化方法相比，群體智能算法具有簡單的迭代式尋優(yōu)、環(huán)境自適應(yīng)性和系統(tǒng)自調(diào)節(jié)性、有指導(dǎo)的隨機并行式全局搜索、系統(tǒng)通用性和魯棒性強、智能性、易于與其他算法相結(jié)合的特點。一些典型的群智能算法：1.蟻群算法（AntColonyOptimization，ACO）：是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。該算法受到自然界中真實蟻群通過個體間的信息傳遞、搜索從蚊穴到食物間的最短距離的集體尋優(yōu)特征的啟發(fā)，來解決一些離散系統(tǒng)中優(yōu)化的困難問題。目前，該算法已被應(yīng)用于求解旅行商問題、指派問題以及調(diào)度問題等，取得了較好的結(jié)果。作為一種隨機優(yōu)化方法，螞蟻算法不需要任何先驗知識，最初只是隨機地選擇搜索路徑，隨著對解空間的了解，搜索更加具有規(guī)律性，并逐漸得到全局最優(yōu)解。各種形式的蟻群算法中，螞蟻數(shù)量m、信息啟發(fā)式因子α、期望值啟發(fā)式因子β和信息素揮發(fā)因子ρ都是影響算法性能的重要參數(shù)。粒子群算法（ParticleSwarmOptimiztion，PSO）：是一種有效的全局尋優(yōu)算法，最初由美國學(xué)者肯尼迪（Kennedy）和埃伯哈特（Eberhart）于1951年提出。它是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。由于每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的雙重優(yōu)點，從而能在較少的迭代次數(shù)內(nèi)找到最優(yōu)解。目前該方法已廣泛應(yīng)用于函數(shù)優(yōu)化、數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)訓(xùn)練等領(lǐng)域?？夏岬系韧ㄟ^觀察鳥群覓食提出了兩種粒子群算法模式即全局模式（globalversionPSO）和局部模式（localversionPSO）。3.人工魚群算法（ArtificialFishSchoolAlgorithm，AFSA）：是由李曉磊博士于2002年首次提出。通過研究魚群的行為，李曉磊總結(jié)并提取了適用于魚群算法幾種典型行為－魚的覓食行為、聚群行為和追尾行為，并用之于尋優(yōu)過程，進而形成了魚群優(yōu)化算法。4.人工蜂群算法（ArtificialBeeColonyAlgorithm，ABC）：是由卡拉伯卡（Karaboga）于2005年提出的基于蜜蜂群體的覓食行為的一種新的啟發(fā)式仿生算法，它建立在蜜蜂群體生活習(xí)性模型基礎(chǔ)上，模擬了蜂群依各自分工不同協(xié)作采蜜、交換蜜源信息以找到最優(yōu)蜜源這一群體行為。ABC算法具有良好的優(yōu)化能力，可以用來解決數(shù)值優(yōu)化問題，在其他方面如生產(chǎn)調(diào)度、路徑規(guī)劃等方面也取得了良好的應(yīng)用效果。ABC算法將全局搜索和局部搜索的方法相結(jié)合，從而使得蜜蜂在食物源的開采和探索這兩方面取得了很好的平衡。ABC算法的尋優(yōu)過程由四個選擇過程構(gòu)成：①局部選擇過程；②全局選擇過程；③貪婪選擇過程；④隨機選擇過程?！?.5混合優(yōu)化算法如今，算法混合（組合）的思想已發(fā)展成為提高算法優(yōu)化性能的一個重要且有效的途徑，其出發(fā)點就是使各種單一算法相互取長補短，產(chǎn)生更好的優(yōu)化效率。該策略的關(guān)鍵問題是問題分解與綜合的處理、子算法和領(lǐng)域函數(shù)的選擇、進程層次上算法轉(zhuǎn)換接口的處理、優(yōu)化過程中的數(shù)據(jù)處理。目前混合算法的結(jié)構(gòu)類型主要可歸結(jié)為串行、鑲嵌、并行及混合結(jié)構(gòu)。串行結(jié)構(gòu)是一種最簡單的結(jié)構(gòu)，它的混合算法就是吸收不同算法的優(yōu)點，用一種算法的搜索結(jié)果作為另一種算法的起點依次來對問題進行優(yōu)化。設(shè)計串行結(jié)構(gòu)的混合算法需要解決的問題主要是確定各種算法的轉(zhuǎn)換時機。鑲嵌結(jié)構(gòu)表示為一種算法作為另一種算法的一個優(yōu)化操作或用操作搜索性能的評價器。設(shè)計鑲嵌結(jié)構(gòu)的混合算法需要解決的問題主要是子算法與嵌入點的選擇。并行結(jié)構(gòu)包括同步式并行，異步式并行和網(wǎng)絡(luò)結(jié)構(gòu)。問題分解與綜合以及進程間的通信問題是設(shè)計并行結(jié)構(gòu)的混合算法需解決的主要問題。§5.6計算智能的matlab實戰(zhàn)算法例題講解3min引入：通過生物界自然選擇、變異和雜交等自然進化方式實例引入。內(nèi)容設(shè)計思路：通過具體案例展示算法的應(yīng)用，進行實驗和分析，引導(dǎo)學(xué)生了解內(nèi)