引言
優化問題是工業設計中經常遇到的問題,許多問題最後都可以歸結為優化問題. 為了解決各種各樣的優化問題,人們提出了許多優化算法,比較著名的有爬山法、遺傳算法、神經網絡算法等。
優化問題
一是要求尋找全局最優點
二是要求有較高的收斂速度
約束優化問題
近年來，一些學者将PSO算法推廣到約束優化問題，其關鍵在于如何處理好約束，即解的可行性。如果約束處理的不好，其優化的結果往往會出現不能夠收斂和結果是空集的狀況。基于PSO算法的約束優化工作主要分為兩類：
（1）罰函數法。罰函數的目的是将約束優化問題轉化成無約束優化問題。
（2）将粒子群的搜索範圍都限制在條件約束簇内，即在可行解範圍内尋優。
根據文獻介紹，Parsopoulos等采用罰函數法，利用非固定多段映射函數對約束優化問題進行轉化，再利用PSO算法求解轉化後問題，仿真結果顯示PSO算法相對遺傳算法更具有優越性，但其罰函數的設計過于複雜，不利于求解；Hu等采用可行解保留政策處理約束，即一方面更新存儲中所有粒子時僅保留可行解，另一方面在初始化階段所有粒子均從可行解空間取值，然而初始可行解空間對于許多問題是很難确定的；Ray等提出了具有多層信息共享策略的粒子群原理來處理約束，根據約束矩陣采用多層Pareto排序機制來産生優良粒子，進而用一些優良的粒子來決定其餘個體的搜索方向。
但是，目前有關運用PSO算法方便實用地處理多約束目标優化問題的理論成果還不多。處理多約束優化問題的方法有很多，但用PSO算法處理此類問題目前技術并不成熟，這裡就不介紹了。
遺傳算法
屬于進化算法( Evolutionary Algorithms) 的一種,它通過模仿自然界的選擇與遺傳的機理來尋找最優解. 遺傳算法有三個基本算子:選擇、交叉和變異. 但是遺傳算法的編程實現比較複雜,首先需要對問題進行編碼,找到最優解之後還需要對問題進行解碼,另外三個算子的實現也有許多參數,如交叉率和變異率,并且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗。
PSO算法
粒子群優化算法(PSO)是一種進化計算技術(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源于對鳥群捕食的行為研究 。該算法最初是受到飛鳥集群活動的規律性啟發，進而利用群體智能建立的一個簡化模型。粒子群算法在對動物集群活動行為觀察基礎上，利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中産生從無序到有序的演化過程，從而獲得最優解。
PSO同遺傳算法類似，是一種基于叠代的優化算法。系統初始化為一組随機解，通過叠代搜尋最優值。但是它沒有遺傳算法用的交叉(crossover)以及變異(mutation)，而是粒子在解空間追随最優的粒子進行搜索。同遺傳算法比較，PSO的優勢在于簡單容易實現并且沒有許多參數需要調整。目前已廣泛應用于函數優化，神經網絡訓練，模糊系統控制以及其他遺傳算法的應用領域。
人工生命
"人工生命"是來研究具有某些生命基本特征的人工系統。
兩方面内容
1. 研究如何利用計算技術研究生物現象
2. 研究如何利用生物技術研究計算問題
我們現在關注的是第二部分的内容. 現在已經有很多源于生物現象的計算技巧. 例如,人工神經網絡是簡化的大腦模型. 遺傳算法是模拟基因進化過程的。
社會系統
現在我們讨論另一種生物系統- 社會系統. 更确切的是, 在由簡單個體組成的群落與環境以及個體之間的互動行為. 也可稱做"群智能"(swarm intelligence). 這些模拟系統利用局部信息從而可能産生不可預測的群體行為。
例如floys 和birds 他們都用來模拟魚群和鳥群的運動規律, 主要用于計算機視覺和計算機輔助設計。
在計算智能(computational intelligence)領域有兩種基于群智能的算法.蟻群算法(ant colony optimization)和PSO粒子群算法(particle swarm optimization). 前者是對螞蟻群落食物采集過程的模拟. 已經成功運用在很多離散優化問題上。
粒子群優化算法(PSO) 也是起源對簡單社會系統的模拟. 最初設想是模拟鳥群覓食的過程. 但後來發現PSO是一種很好的優化工具。
算法介紹
簡介
如前所述，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
比較
演化計算技術
大多數演化計算技術都是用同樣的過程 ：
1.種群随機初始化
2. 對種群内的每一個個體計算适應值(fitness value).适應值與最優解的距離直接有關
3. 種群根據适應值進行複制
4. 如果終止條件滿足的話，就停止，否則轉步驟2
從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都随機初始化種群，而且都使用适應值來評價系統，而且都根據适應值來進行一定的随機搜索。兩個系統都不是保證一定找到最優解 。
記憶
但是，PSO 沒有遺傳操作如交叉(crossover)和變異(mutation). 而是根據自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶。
與遺傳算法比較, PSO 的信息共享機制是很不同的. 在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個種群的移動是比較均勻的向最優區域移動. 在PSO中, 隻有gBest (or pBest) 給出信息給其他的粒子，這是單向的信息流動. 整個搜索更新過程是跟随當前最優解的過程. 與遺傳算法比較, 在大多數的情況下，所有的粒子可能更快的收斂于最優解。
和PSO
人工神經網絡
人工神經網絡(ANN)是模拟大腦分析過程的簡單數學模型，誤差反向傳播算法是最流行的神經網絡訓練算法。近來也有很多研究開始利用演化計算(evolutionary computation)技術來研究人工神經網絡的各個方面。
演化計算可以用來研究神經網絡的三個方面：網絡連接權重，網絡結構(網絡拓撲結構，傳遞函數)，網絡學習算法。
不過大多數這方面的工作都集中在網絡連接權重，和網絡拓撲結構上。在GA中，網絡權重和/或拓撲結構一般編碼為染色體(Chromosome)，适應函數(fitness function)的選擇一般根據研究目的确定。例如在分類問題中，錯誤分類的比率可以用來作為适應值。
演化計算的優勢在于可以處理一些傳統方法不能處理的例子例如不可導的節點傳遞函數或者沒有梯度信息存在。但是缺點在于：在某些問題上性能并不是特别好。2. 網絡權重的編碼而且遺傳算子的選擇有時比較麻煩。
最近已經有一些利用PSO來代替反向傳播算法來訓練神經網絡的論文。研究表明PSO 是一種很有潛力的神經網絡算法。PSO速度比較快而且可以得到比較好的結果。而且還沒有遺傳算法碰到的問題。
PSO訓練過程
這裡用一個簡單的例子說明PSO訓練神經網絡的過程。這個例子使用分類問題的基準函數(Benchmark function)IRIS數據集。(Iris 是一種鸢尾屬植物) 在數據記錄中，每組數據包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數據. 這樣總共有150組數據或模式。
我們用3層的神經網絡來做分類。現在有四個輸入和三個輸出。所以神經網絡的輸入層有4個節點，輸出層有3個節點我們也可以動态調節隐含層節點的數目，不過這裡我們假定隐含層有6個節點。我們也可以訓練神經網絡中其他的參數。不過這裡我們隻是來确定網絡權重。粒子就表示神經網絡的一組權重，應該是4*6+6*3=42個參數。權重的範圍設定為[-100，100] (這隻是一個例子，在實際情況中可能需要試驗調整).在完成編碼以後，我們需要确定适應函數。對于分類問題，我們把所有的數據送入神經網絡，網絡的權重有粒子的參數決定。然後記錄所有的錯誤分類的數目作為那個粒子的适應值。現在我們就利用PSO來訓練神經網絡來獲得盡可能低的錯誤分類數目。PSO本身并沒有很多的參數需要調整。所以在實驗中隻需要調整隐含層的節點數目和權重的範圍以取得較好的分類效果。
參數設置
從上面的例子我們可以看到應用PSO解決優化問題的過程中有兩個重要的步驟: 問題解的編碼和适應度函數。
采用實數編碼
不需要像遺傳算法一樣是二進制編碼(或者采用針對實數的遺傳操作.例如對于問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而适應度函數就是f(x). 接着我們就可以利用前面的過程去尋優.這個尋優過程是一個疊代過程, 中止條件一般為設置為達到最大循環數或者最小錯誤。
PSO中并沒有許多需要調節的參數,下面列出了這些參數以及經驗設置。
粒子數: 一般取 20 – 40. 其實對于大部分的問題10個粒子已經足夠可以取得好的結果, 不過對于比較難的問題或者特定類别的問題, 粒子數可以取到100 或 200。
粒子的長度: 這是由優化問題決定, 就是問題解的長度。
粒子的範圍: 由優化問題決定,每一維可以設定不同的範圍。
Vmax: 最大速度,決定粒子在一個循環中最大的移動距離,通常設定為粒子的範圍寬度,例如上面的例子裡,粒子 (x1, x2, x3) x1 屬于 [-10, 10], 那麼 Vmax 的大小就是 20。
學習因子: c1 和 c2 通常等于 2. 不過在文獻中也有其他的取值. 但是一般 c1 等于 c2 并且範圍在0和4之間。
中止條件: 最大循環數以及最小錯誤要求. 例如, 在上面的神經網絡訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環設定為2000, 這個中止條件由具體的問題确定。
全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優化算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優. 後者收斂速度慢一點不過很難陷入局部最優. 在實際應用中, 可以先用全局PSO找到大緻的結果,再用局部PSO進行搜索。
慣性權重
另外的一個參數是慣性權重, Shi 和Eberhart指出(A modified particle swarm optimizer,1998)：當Vmax很小時（對schaffer的f6函數，Vmax<=2),使用接近于1的慣性權重;當Vmax不是很小時（對schaffer的f6函數，Vmax>=3),使用權重w=0.8較好.如果沒有Vmax的信息,使用0.8作為權重也是一種很好的選擇.慣性權重w很小時偏重于發揮粒子群算法的局部搜索能力；慣性權重很大時将會偏重于發揮粒子群算法的全局搜索能力。
