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

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

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

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

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