粒子群演算法應用

A. 粒子群演算法及應用的目錄

前言
第1章緒論
1.1最優化問題
1.1.1函數優化問題與組合優化問題
1.1.2優化演算法的發展
1.2幾種常見的啟發式演算法
1.2.1遺傳演算法
1.2.2模擬退火演算法
1.2.3人工神經網路
1.3群體智能演算法
1.3.1蟻群演算法
1.3.2粒子群演算法
1.4粒子群演算法的發展與應用
1.4.1粒子群演算法的發展
1.4.2粒子群演算法的應用
參考文獻
第2章基本粒子群演算法
2.1引言
2.2基本粒子群演算法
2.3帶慣性權重的粒子群演算法
2.3.1一般的慣性因子設計
2.3.2基於模糊系統的慣性因子的動態調整
2.4帶收縮因子的粒子群演算法
2.5與其他演算法的異同
2.5.1基於梯度的優化演算法
2.5.2進化計算方法
2.5.3蟻群演算法
2.6復雜度
2.6.1復雜度的判定標准和基本概念
2.6.2時空復雜度分析
參考文獻
第3章粒子群演算法的分析
3.1一維空間軌跡
3.1.1粒子群系統的簡化
3.1.2單個粒子的軌跡
3.2多維空間軌跡
3.2.1區域特性
3.2.2步長分析
3.3代數分析
3.3.1系統簡化
3.3.2代數觀點
3.4解析分析
3.5差分方程分析
3.5.1粒子運動軌跡的穩定性分析
3.5.2粒子運動軌跡的影響因素
3.5.3粒子運動軌跡與演算法收斂的關系
參考文獻
第4章改進的粒子群演算法及分析
4.1離散粒子群優化演算法
4.1.1二進制離散粒子群優化演算法
4.1.2改進的二值離散粒子群優化演算法
4.1.3離散量子粒子群優化演算法
4.1.4模糊離散粒子群優化演算法
4.2小生境粒子群優化演算法
4.2.1小生境粒子群演算法
4.2.2基於聚類的小生境粒子群演算法
4.2.3種群小生境粒子群演算法
4.3混合粒子群優化演算法
4.3.1基於遺傳思想改進粒子群演算法
4.3.2混沌粒子群優化演算法
4.3.3基於模擬退火的粒子群優化演算法
4.4其他粒子群改進演算法
4.4.1子矢量
4.4.2子矢量的更新過程
4.4.3參數分析
參考文獻
第5章在函數優化中的應用
5.1基準測試函數
5.2優化測試函數的分類
5.2.1無約束優化測試函數
5.2.2有約束優化測試函數
5.2.3極大極小優化測試函數
5.2.4多目標優化測試函數
5.3智能單粒子演算法優化性能
參考文獻
第6章在圖像壓縮中的應用
6.1矢量量化
6.2常用的幾種矢量量化方法
6.2.1K-means演算法
6.2.2模糊K-means演算法
6.2.3模糊矢量量化演算法
6.2.4FRLVQ演算法
6.2.5FRLVQ-FVQ演算法
6.3粒子對演算法
6.3.1粒子結構
6.3.2與傳統粒子群演算法的差異
6.3.3碼書更新過程
6.4演算法比較
參考文獻
第7章在基因聚類中的應用
7.1基因晶元技術簡介
7.2基因表達數據聚類分析
7.2.1基因表達數據分析
7.2.2聚類分析
7.3基因表達數據聚類分析
7.3.1聚類演算法的分類
7.3.2K-means聚類
7.3.3層次聚類
7.3.4自組織映射
7.3.5改進型聚類演算法
7.4粒子對演算法在基因聚類中的應用
7.4.1粒子結構
7.4.2聚類分析
7.4.3聚類結果
7.5基因聚類分析結果的評價標准
參考文獻
第8章粒子群演算法應用綜述
8.1優化問題求解
8.1.1約束優化問題求解
8.1.2規劃問題求解
8.1.3離散空間組合優化問題求解
8.2工程設計與優化領域
8.2.1電路及濾波器設計
8.2.2神經網路訓練
8.2.3控制器設計與優化
8.2.4RBF網路優化訓練舉例
8.3電力系統領域
8.3.1電容器優化配置
8.3.2最優潮流計算與無功優化控制
8.3.3機組優化組合問題
8.3.4電網擴展計劃
8.3.5電力系統恢復
8.3.6負荷經濟分配及調度
8.3.7狀態估計
8.3.8參數辨識
8.3.9優化設計
8.3.10OPF問題舉例
8.4機器人控制領域
8.4.1機器人控制與協調
8.4.2移動機器人路徑規劃
8.5交通運輸領域
8.5.1車輛路徑問題
8.5.2VRP問題舉例
8.5.3交通控制
8.6通信領域
8.6.1路由選擇及移動通信基站布置優化
8.6.2天線陣列控制
8.6.3偏振模色散補償
8.7計算機領域
8.7.1任務分配問題
8.7.2數據分類
8.7.3圖像處理
8.8工業生產優化領域
8.8.1機械領域
8.8.2化工領域
8.9生物醫學領域
8.10電磁學領域
參考文獻
附錄A粒子對演算法應用於圖像矢量量化的源代碼
附錄B智能單粒子優化演算法求解函數的源代碼
附錄C23個基準測試函數
附錄D基因聚類常用軟體
……

B. 粒子群優化演算法

         粒子群演算法 的思想源於對鳥/魚群捕食行為的研究，模擬鳥集群飛行覓食的行為，鳥之間通過集體的協作使群體達到最優目的，是一種基於Swarm Intelligence的優化方法。它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作，它通過追隨當前搜索到的最優值來尋找全局最優。粒子群演算法與其他現代優化方法相比的一個明顯特色就是所 需要調整的參數很少、簡單易行 ，收斂速度快，已成為現代優化方法領域研究的熱點。

         設想這樣一個場景：一群鳥在隨機搜索食物。已知在這塊區域里只有一塊食物；所有的鳥都不知道食物在哪裡；但它們能感受到當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢？

        1. 搜尋目前離食物最近的鳥的周圍區域

        2. 根據自己飛行的經驗判斷食物的所在。

        PSO正是從這種模型中得到了啟發，PSO的基礎是 信息的社會共享

        每個尋優的問題解都被想像成一隻鳥，稱為「粒子」。所有粒子都在一個D維空間進行搜索。

        所有的粒子都由一個fitness function 確定適應值以判斷目前的位置好壞。

        每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。

        每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據它本身的飛行經驗以及同伴的飛行經驗進行動態調整。

        粒子速度更新公式包含三部分： 第一部分為「慣性部分」，即對粒子先前速度的記憶；第二部分為「自我認知」部分，可理解為粒子i當前位置與自己最好位置之間的距離；第三部分為「社會經驗」部分，表示粒子間的信息共享與合作，可理解為粒子i當前位置與群體最好位置之間的距離。

        第1步   在初始化范圍內，對粒子群進行隨機初始化，包括隨機位置和速度

        第2步   根據fitness function，計算每個粒子的適應值

        第3步   對每個粒子，將其當前適應值與其個體歷史最佳位置（pbest）對應的適應值作比較，如果當前的適應值更高，則用當前位置更新粒子個體的歷史最優位置pbest

        第4步   對每個粒子，將其當前適應值與全局最佳位置（gbest）對應的適應值作比較，如果當前的適應值更高，則用當前位置更新粒子群體的歷史最優位置gbest

        第5步   更新粒子的速度和位置

        第6步   若未達到終止條件，則轉第2步

        【通常演算法達到最大迭代次數或者最佳適應度值得增量小於某個給定的閾值時演算法停止】

粒子群演算法流程圖如下：

以Ras函數（Rastrigin's Function）為目標函數，求其在x1,x2∈[-5,5]上的最小值。這個函數對模擬退火、進化計算等演算法具有很強的欺騙性，因為它有非常多的局部最小值點和局部最大值點，很容易使演算法陷入局部最優，而不能得到全局最優解。如下圖所示，該函數只在(0,0)處存在全局最小值0。

C. 粒子群演算法的演算法介紹

如前所述，PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。
PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。
PSO 初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。 在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和新的位置：
v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = present[] + v[] (b)
v[] 是粒子的速度, w是慣性權重,present[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於（0， 1）之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2.
程序的偽代碼如下
For each particle
____Initialize particle
END
Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End
____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained
在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用戶設定的Vmax，那麼這一維的速度就被限定為Vmax

D. 粒子群演算法（一）：粒子群演算法概述

  本系列文章主要針對粒子群演算法進行介紹和運用，並給出粒子群演算法的經典案例，從而進一步加深對粒子群演算法的了解與運用（預計在一周內完成本系列文章）。主要包括四個部分：

  粒子群演算法也稱粒子群優化演算法（Particle Swarm Optimization, PSO），屬於群體智能優化演算法，是近年來發展起來的一種新的進化演算法（Evolutionary Algorithm, EA）。 群體智能優化演算法主要模擬了昆蟲、獸群、鳥群和魚群的群集行為，這些群體按照一種合作的方式尋找食物，群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷地改變搜索的方向。 群體智能優化演算法的突出特點就是利用了種群的群體智慧進行協同搜索，從而在解空間內找到最優解。
  PSO 演算法和模擬退火演算法相比，也是 從隨機解出發，通過迭代尋找最優解 。它是通過適應度來評價解的品質，但比遺傳演算法規則更為簡單，沒有遺傳演算法的「交叉」和「變異」，它通過追隨當前搜索到的最大適應度來尋找全局最優。這種演算法以其 容易實現、精度高、收斂快 等優點引起了學術界的重視，並在解決實際問題中展示了其優越性。

  在粒子群演算法中，每個優化問題的解被看作搜索空間的一隻鳥，即「粒子」。演算法開始時首先生成初始解，即在可行解空間中隨機初始化 粒子組成的種群 ，其中每個粒子所處的位置 ，都表示問題的一個解，並依據目標函數計算搜索新解。在每次迭代時，粒子將跟蹤兩個「極值」來更新自己， 一個是粒子本身搜索到的最好解 ，另一個是整個種群目前搜索到的最優解 。 此外每個粒子都有一個速度 ，當兩個最優解都找到後，每個粒子根據如下迭代式更新：

  其中參數 稱為是 PSO 的 慣性權重(inertia weight) ，它的取值介於[0,1]區間；參數 和 稱為是 學習因子(learn factor) ；而 和 為介於[0,1]之間的隨機概率值。
  實踐證明沒有絕對最優的參數，針對不同的問題選取合適的參數才能獲得更好的收斂速度和魯棒性，一般情況下 , 取 1.4961 ，而 採用 自適應的取值方法 ，即一開始令 ， 使得 PSO 全局優化能力較強 ；隨著迭代的深入，遞減至 ， 從而使得PSO具有較強的局部優化能力 。

  參數 之所以被稱之為慣性權重，是因為 實際 反映了粒子過去的運動狀態對當前行為的影響，就像是我們物理中提到的慣性。 如果 ，從前的運動狀態很少能影響當前的行為，粒子的速度會很快的改變；相反， 較大，雖然會有很大的搜索空間，但是粒子很難改變其運動方向，很難向較優位置收斂，由於演算法速度的因素，在實際運用中很少這樣設置。也就是說， 較高的 設置促進全局搜索，較低的 設置促進快速的局部搜索。

E. 粒子群演算法

粒子群演算法（particle swarm optimization，PSO）是計算智能領域中的一種生物啟發式方法，屬於群體智能優化演算法的一種，常見的群體智能優化演算法主要有如下幾類：

除了上述幾種常見的群體智能演算法以外，還有一些並不是廣泛應用的群體智能演算法，比如螢火蟲演算法、布穀鳥演算法、蝙蝠演算法以及磷蝦群演算法等等。

而其中的粒子群優化演算法（PSO）源於對鳥類捕食行為的研究，鳥類捕食時，找到食物最簡單有限的策略就是搜尋當前距離食物最近的鳥的周圍。

設想這樣一個場景：一群鳥在隨機的搜索食物。在這個區域里只有一塊食物，所有的鳥都不知道食物在哪。但是它們知道自己當前的位置距離食物還有多遠。那麼找到食物的最優策略是什麼？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

Step1:確定一個粒子的運動狀態是利用位置和速度兩個參數描述的，因此初始化的也是這兩個參數；
Step2:每次搜尋的結果（函數值）即為粒子適應度，然後記錄每個粒子的個體歷史最優位置和群體的歷史最優位置；
Step3:個體歷史最優位置和群體的歷史最優位置相當於產生了兩個力，結合粒子本身的慣性共同影響粒子的運動狀態，由此來更新粒子的位置和速度。

位置和速度的初始化即在位置和速度限制內隨機生成一個N x d 的矩陣，而對於速度則不用考慮約束，一般直接在0~1內隨機生成一個50x1的數據矩陣。

此處的位置約束也可以理解為位置限制，而速度限制是保證粒子步長不超限制的，一般設置速度限制為[-1,1]。

粒子群的另一個特點就是記錄每個個體的歷史最優和種群的歷史最優，因此而二者對應的最優位置和最優值也需要初始化。其中每個個體的歷史最優位置可以先初始化為當前位置,而種群的歷史最優位置則可初始化為原點。對於最優值，如果求最大值則初始化為負無窮，相反地初始化為正無窮。

每次搜尋都需要將當前的適應度和最優解同歷史的記錄值進行對比，如果超過歷史最優值，則更新個體和種群的歷史最優位置和最優解。

速度和位置更新是粒子群演算法的核心，其原理表達式和更新方式：

每次更新完速度和位置都需要考慮速度和位置的限制，需要將其限制在規定范圍內，此處僅舉出一個常規方法，即將超約束的數據約束到邊界（當位置或者速度超出初始化限制時，將其拉回靠近的邊界處）。當然，你不用擔心他會停住不動，因為每個粒子還有慣性和其他兩個參數的影響。

粒子群演算法求平方和函數最小值，由於沒有特意指定函數自變數量綱，不進行數據歸一化。