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

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