人工智能 課件 第四章 進化算法和群智能算法

人工智能第四章進化算法和群智能算法本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法4.1概述概述優(yōu)化技術(shù)是指在滿足一定條件下，在眾多或參數(shù)中尋找最優(yōu)化方案或參數(shù)值，以是的某個或多個功能指標達到最優(yōu)，或使系統(tǒng)的某些性能指標達到最大值或最小值。在計算智能和人工智能交叉工程應用領(lǐng)域得到廣泛重視，鑒于實際工程問題的復雜性、約束性、非線性、多極小、建模困難等特點，需要尋求適用于大規(guī)模并行且具有智能特征的算法。智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，受人類智能、生物群體社會性或自然現(xiàn)象規(guī)律的啟發(fā)，為接近復雜問題提供了新的思路和手段。智能優(yōu)化算法大體可以分為五類：進化算法、群智能算法、模擬退火算法、禁忌搜索算法和神經(jīng)網(wǎng)絡(luò)算法。其中，進化算法通過模擬自然界群體和個人間的進化機制、合作競爭來設(shè)計搜索策略；群智能算法則受到生物群體行為研究的啟發(fā)，將模擬生物群體尋徑行為融入到求解高度復雜的優(yōu)化問題中。本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法4.2遺傳算法遺傳算法（GeneticAlgorithm，GA）是一種進化算法，其基本原理是仿效生物界中的“物競天擇、適者生存”的演化法則，它最初由美國Michigan大學的J.Holland教授于1967年提出。70年代，K.A.Dejong基于遺傳算法的思想，在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算試驗[2]；80年代，遺傳算法由D.E.Goldberg在一系列研究工作的基礎(chǔ)上歸納總結(jié)而成。90年代以后，遺傳算法作為一種高效、實用、魯棒性強的優(yōu)化技術(shù)，發(fā)展極為迅速，在機器學習、模式識別、神經(jīng)網(wǎng)絡(luò)、控制系統(tǒng)優(yōu)化及社會科學等不同領(lǐng)域得到廣泛應用。進入21世紀，以不確定性、非線性、時間不可逆為內(nèi)涵的復雜性科學成為一個研究熱點。遺傳算法因能有效地求解NP(Non-deterministicPolynomial)問題以及非線性、多峰函數(shù)優(yōu)化和多目標優(yōu)化問題，得到了眾多學科學者的高度重視，同時也極大的推動了遺傳算法理論研究和實際應用的不斷深入與發(fā)展。1.基本概念4.2遺傳算法個體（individual）：指染色體帶有特征的實體；種群（population）：個體的集合，該集合內(nèi)個體數(shù)稱為種群的大小；進化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化；適應度（fitness）：度量某個物種對于生存環(huán)境的適應程度。對生存環(huán)境適應程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應程度較低的物種，其繁殖機會就會相對較少，甚至逐漸滅絕。1.基本概念選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作；復制（reproduction）：細胞在分裂時，遺傳物質(zhì)DNA通過復制而轉(zhuǎn)移到新產(chǎn)生的細胞中，新的細胞就繼承了舊細胞的基因;交叉（crossover）：在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。又稱基因重組，俗稱“雜交”;變異（mutation）：在細胞進行復制時可能以很小的概率產(chǎn)生某些復制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。4.2遺傳算法4.2遺傳算法2.算法流程遺傳算法包括三個基本操作：選擇、交叉和變異。（1）選擇（selection），用來確定重組和交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。選擇操作首先要計算適應度值，通?？梢圆扇“幢壤倪m應度計算或基于排序的適應度計算。其次，按照計算出來的適應度值進行父代個體的選擇，通常采用的選擇方法包含：輪盤賭選擇、隨機遍歷抽樣、局部選擇、截斷選擇和錦標賽選擇。4.2遺傳算法2.算法流程（2）交叉（crossover），結(jié)合來自父代遺傳種群的信息來產(chǎn)生新的個體。依據(jù)個體編碼表示方法的不同，可以選擇不同的交叉算法，對于實值編碼，可以選擇離散重組、中間重組、線性重組、擴展線性重組。對于二進制編碼，可以選擇單點交叉、多點交叉、均勻交叉、洗牌交叉、縮小代理交叉。（3）變異（mutation），交叉之后的子代基因按一定概率產(chǎn)生變化，依據(jù)個體編碼表示方法的不同，可以采取實值變異和二進制變異兩種方法。4.2遺傳算法3.遺傳算法的參數(shù)設(shè)置在遺傳算法程序設(shè)計與調(diào)試中，有幾個重要的參數(shù)對于算法性能有著至關(guān)重要的作用。（1）種群規(guī)模（2）交叉概率（3）變異概率（4）終止條件判斷的最大進化代數(shù)4.2遺傳算法4.算法的改進算法改進的方向通常針對個體基因的操作、種群的宏觀操作、基于知識的操作和并行化遺傳算法方面進行。（1）算法結(jié)構(gòu)和參數(shù)的改進（2）有約束優(yōu)化問題的遺傳算法（3）并行遺傳算法4.2遺傳算法5.遺傳算法優(yōu)化實例

4.2遺傳算法5.遺傳算法優(yōu)化實例背包（0-1）問題。有N件物品和一個容量為V的背包。第i件物品的體積是c(i)，價值是w(i)。求解將哪些物品放入背包可使物品的體積總和不超過背包的容量，且價值總和最大。算法流程：（1）初始化種群數(shù)目為Np=50，染色體維數(shù)為L=10，最大進化代數(shù)為G=100。（2）產(chǎn)生二進制初始種群，其中1表示選擇該物品，0表示不選擇該物品。適應度值等于所有被選中物品的價值總和，計算種群中個體適應度值，當物品體積總和大于背包容量時，對適應度值添加懲罰項計算。（3）對適應度進行歸一化，采用基于輪盤賭的選擇操作、基于概率的交叉和變異操作，產(chǎn)生新的種群，并把歷代的最優(yōu)個體保留在新種群中，進行下一步遺傳操作。（4）判斷是否滿足終止條件：若滿足，則結(jié)束搜索過程，輸出優(yōu)化值；若不滿足，則繼續(xù)進行迭代優(yōu)化。本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法4.3差分進化算法差分進化算法（DifferentialEvolutionAlgorithm，DE算法）是一種簡單的進化算法，1995年，該算法由RainerStorn和KennethPrice為求解chebyshev多項式而提出。DE是一種隨機的并行直接搜索算法，它可對非線性不可微連續(xù)空間函數(shù)進行最小化，以其易用性、穩(wěn)健性和強大的全局尋優(yōu)能力在多個領(lǐng)域取得成功。應用在約束優(yōu)化問題、聚類優(yōu)化計算、非線性優(yōu)化控制、神經(jīng)網(wǎng)絡(luò)、濾波器設(shè)計、陣列天線及其他方面得到廣泛應用。差分進化算法4.3差分進化算法DE算法有兩個階段：種群初始化和進化迭代。種群初始化是在可行域內(nèi)采用均勻分布等概率的生成初始空間解向量，進化迭代過程的操作有差分變異、交叉和選擇等主要步驟。首先隨機選擇種群中兩個互異的個體，進行差分和縮放，再加上種群中第三個隨機個體來產(chǎn)生變異個體，然后父代個體和變異個體采用交叉操作獲得試驗個體，最后將試驗個體和父代個體的適應度值進行比較，選擇適應度值較優(yōu)的個體進入下一代繼續(xù)迭代，直到滿足終止準則，停止迭代。1.標準DE算法：2.差分進化算法的參數(shù)設(shè)置全局優(yōu)化算法的性能可以通過控制參數(shù)的適當選取來提升，對于差分進化算法可以參照一些經(jīng)驗規(guī)則來選取控制參數(shù)。（1）種群規(guī)模（2）變異算子（3）交叉算子（4）最大進化代數(shù)G（5）終止條件4.3差分進化算法3.改進DE算法DE算法的變形形式實際應用中根據(jù)具體問題，在差分進化算法的操作流程中的變異操作進行變形操作。4.3差分進化算法4.差分進化算法優(yōu)化實例用離散差分進化算法求函數(shù)f(x,y)=-[(x2+y-1)2+(x+y2-7)2]/200+10的最大值，其中x的取值為-100~100之間的整數(shù)，y的取值為-100~100之間的整數(shù)，其函數(shù)值圖形如圖4-12所示。4.3差分進化算法本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法4.4粒子群算法粒子群算法1995年Kennedy等人模擬鳥群覓食的過程，提出了粒子群（ParticleSwarmOptimization,PSO）算法，后來演變?yōu)橐环N很好的優(yōu)化工具?；舅枷朐从谠邙B類覓食過程中通過集體協(xié)作和競爭達到遷移和聚集，PSO算法就是從這種模擬中得到啟示并應用到求解優(yōu)化問題中，這里的“粒子”表示優(yōu)化問題解搜索空間中的一只鳥，每個粒子都對應有一個適應度值（fitnessvalue）來判定被優(yōu)化函數(shù)是否達到最優(yōu)值。4.4粒子群算法粒子群算法社會認知學的角度從另一個側(cè)面，也給出了PSO算法的理論解釋，即，群體中的每個個體都可以從過往經(jīng)驗和鄰近個體表現(xiàn)中獲得有益信息，該理論基礎(chǔ)由以下三個主要基本因素組成：外在刺激的評價、與近鄰的比較、領(lǐng)先個體的模仿。根據(jù)鄰近粒子的定義范圍，PSO算法可以分為全局模式和局部模式。兩種模式表現(xiàn)出不同的算法性能，前者收斂速度較快，但會陷入局部極值；后者算法收斂速度較慢，但極少陷入局部極值。粒子群算法是一種并行算法。4.4粒子群算法1.算法基本原理PSO算法在初始化環(huán)節(jié)，使得一群粒子處于初始狀態(tài)，包括了各個粒子的隨機位置和隨機飛行方向。粒子根據(jù)如下公式來對其位置和速度進行更新：從上式可以看出，公式(4-15)表示，第i個粒子在各維度方向上以速度vi來更新位置；速度vi的更新受到當前個體最優(yōu)值和全局最優(yōu)值信息的影響，即公式(4-14)中。4.4粒子群算法1.算法基本原理基本PSO優(yōu)化算法的流程圖如圖4-14所示，每個粒子的位置和速度都以隨機方式進行初始化，而后粒子的速度就朝著全局最優(yōu)和個體最優(yōu)的方向靠近，位置的更新由粒子的速度和移動所花費的時間決定。在運動過程中（即每一次迭代），都對每個粒子位置的適應度不斷進行評價，當如果某個粒子的適應度值優(yōu)于全局最優(yōu)位置的適應度，則該粒子所處的位置就成為種群最優(yōu)粒子位置，這樣全局最優(yōu)解將不斷更新。在整個粒子群群體的運動過程中，每個粒子也根據(jù)自身適應度來更新個體的最優(yōu)位置。由此表明，粒子在向全局最優(yōu)解轉(zhuǎn)移的同時，也向個體最優(yōu)解靠攏4.4粒子群算法2.粒子群優(yōu)化算法的參數(shù)設(shè)置（1）慣性權(quán)重在粒子速度的更新方程式(4-16)中加入慣性權(quán)重w，通過慣性權(quán)重來控制當前速度對下一速度的影響。

4.4粒子群算法2.粒子群優(yōu)化算法的參數(shù)設(shè)置（2）學習因子c1=0代表無私型粒子群算法，"只有社會，沒有自我"，迅速喪失群體多樣性，易陷入局部最優(yōu)而無法跳出；c2=0代表自我認知型粒子群算法，"只有自我，沒有社會"，完全沒有信息的社會共享，導致算法收斂速度緩慢；當c1=c2=0時，粒子將一直以當前速度飛行，直至到達邊界。c1和c2都不為0代表完全型粒子群算法，更容易保持收斂速度和搜索效果的均衡，是較好的選擇。學習因子值太小使粒子在目標區(qū)域外徘徊，值太大導致粒子越過目標區(qū)域。一般在[0,4]上取值。4.4粒子群算法2.粒子群優(yōu)化算法的參數(shù)設(shè)置（4）種群規(guī)模一般來說粒子群的規(guī)模在20~40個，可以視所要解決的具體問題來調(diào)整種群規(guī)模。（3）收縮因子在速度更新公式中引入收縮因子，令當前速度調(diào)整結(jié)束后整體收縮后再更新。4.4粒子群算法2.粒子群優(yōu)化算法的參數(shù)設(shè)置（5）拓撲結(jié)構(gòu)拓撲結(jié)構(gòu)采用一些參數(shù)來表示其結(jié)構(gòu)信息及節(jié)點間的信息流動速度，其中有三個重要的參數(shù)：平均距離：兩個節(jié)點間的平均邊數(shù)；直徑：兩個節(jié)點間的最大距離；分配序列<d1,d2,…,dn>，其中di表示從一個節(jié)點出發(fā)經(jīng)過i條邊（不循環(huán)）可以到達的節(jié)點個數(shù)的平均值。4.4粒子群算法3.改進粒子群優(yōu)化算法(1)離散PSO算法(2)基于雁群啟示的PSO算法(3)遺傳PSO算法4.4粒子群算法4.粒子群優(yōu)化算例

4.4粒子群算法4.粒子群優(yōu)化算例配電網(wǎng)無功優(yōu)化問題。對于第三章例題所示的無功優(yōu)化問題，利用粒子群算法進行求解。利用罰函數(shù)法，將電壓和功率約束與目標函數(shù)結(jié)合，建立適應度函數(shù)f，4.4粒子群算法4.粒子群優(yōu)化算例

本章提綱4.1概述4.2遺傳算法4.3差分進化算法4.5蟻群算法4.4粒子群算法4.5蟻群算法螞蟻能夠借助自身分泌化學物質(zhì)來給同伴傳遞信息，這種化學物質(zhì)被稱為信息素（pheromone），遇到危險時，信息素可以刺激蟻群來傳遞警示信息，依靠這種特殊的通信，螞蟻可以在運動過程中通過感知信息素來指導自己的運動方向，按計劃執(zhí)行一項任務(wù)，而這種控制自身環(huán)境的能力是在其社會行為不斷發(fā)展的過程中獲取的。大量的螞蟻聚集成群的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象，比如某一條路徑走的螞蟻越多，則后來者選擇該路徑的概率越大?；谶@種覓食行為的模擬，Dorigon等提出了蟻群優(yōu)化（AntColonyOptimization,ACO）算法來解決復雜優(yōu)化問題，算法表現(xiàn)較強的魯棒性并支持靈活的分布式計算機制。蟻群算法4.5蟻群算法如圖4-24（a）所示，食物源在D點，螞蟻以相同的速度從A點出發(fā)，可隨機選擇路線a-ABD或路線b-ACD，假設(shè)初始時每條路線分配一只螞蟻，每個時間單位走一步，從圖中可以看出，經(jīng)過9個時間單位，走路線a的螞蟻已到達食物源D，而走路線b的螞蟻才走到路程的中間C點處。如圖4-24（b）所示，經(jīng)過18個時間單位，走路線a的螞蟻到達食物源D后拿著食物又返回了起點A，而走路線b的螞蟻剛好走到D點。久而久之，在信息素指導下