人工智能 課件 第四章 進(jìn)化算法和群智能算法

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

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

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

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

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