遺傳算法和粒子群算法的現狀及發展策略研究

魯欣欣，王淮冬

（1.吉林工商學院基礎教研部，吉林 長春 130507；2.長春工業大學 電氣與電子工程學院，吉林 長春 130012）

0 引言

近幾年，智能算法已經廣泛應用于電力、醫療、農業、汽車等領域，部分替代了傳統的人工控制，并已研究出較為成熟的智能算法和基于智能算法智能化的解決方案。本文主要介紹智能算法中具有代表性的兩種智能算法—遺傳算法和粒子群算法。

1 智能算法的發展

智能算法又被稱為“軟計算”，是人們通過對已發現的自然規律和一些自然現象進行總結，根據其原理，模仿求解實際需要的問題的計算方法。簡單來說，智能算法是仿生學的一個方面，通過仿生原理進行設計，例如遺傳算法、粒子群算法、神經網絡算法等，都是利用仿生原理設計的智能算法。

2 遺傳算法的發展歷程

遺傳算法（GA）最早于20世紀70年代提出，該算法是根據自然規律中生物的優勝劣汰進化演變來的[1]，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法主要是用數學中概率論的知識解決問題。通過計算機模擬運算，將求最優解問題轉換成染色體基因的交叉、變異的過程[2]；利用優勝劣汰的規則篩選所需的適應值，將不合格的數據返還，再次經歷交叉、變異的過程。在求解較為復雜的組合優化問題時，相對一些常規的優化算法，通常能夠較快地獲得較好的優化結果。遺傳算法已廣泛地應用于車間調度、機器仿真、信號處理等領域。

2.1 遺傳算法特點

在解決優化和搜索問題上，遺傳算法和傳統算法最大的不同就是利用概率理論對數據進行處理。所以遺傳算法在結果上具有猜測性，并不是確定的值。該算法利用遺傳學中的交叉變異原則對解決問題的算子重新編碼，篩選合適的算子迭代出最優解。遺傳算法能在眾多的智能算法中脫穎而出是因為該算法搜索解的方式。遺傳算法是以集合的方式將數據迭進行代求解的，解決多解最優的問題效率極高[3]，降低了陷入局部最優解的風險，并且算法更容易被編碼運行。

2.2 遺傳算法的不足

編碼的不規范會對其準確性造成極大影響。單一的遺傳算法編碼不能全面地將優化問題的約束表示出來。若增加約束條件，必然需要對編碼重新進行篩選，這樣一來，大大增加了計算時間。雖然遺傳算法更容易得出全局最優解，但是其算法的運算效率特別低，運算過程相對復雜。在計算過程中時常發生收斂過早的情況影響計算結果。目前針對遺傳算法的計算精度，收斂速度還沒有成熟可靠的設計方案。

2.3 遺傳算法的改進與應用

遺傳算法的缺點主要是運算效率低和收斂精度差。所以遺傳算法的改進方向很明顯，一是改進算法結構，提高運算效率，二是改進遺傳操作，提高算法的收斂精度。

以應用在調度規劃上的改進方式為例。標準的遺傳算法是按選擇、交叉、變異的順序結構進行運算，所以執行操作的效率很低。改進的遺傳算法在結構上將變異操作從交叉操作環節分離出來，與交叉操作并列運行，大大提高了算法的尋優速度。在操作上首先對交叉操作進行改進，以“門當戶對”的原則對個體進行配對，以單點交叉的方式代替原有的交叉方式，這樣可以削弱遺傳算法在尋優過程中出現抖動的概率。其次對變異操作進行改進，在變異的操作中利用調度規劃中出現的混沌序列進行適當次數的迭代，得到變異的新染色體。變異操作的改進是彌補對交叉改進出現的收斂早熟的漏洞，降低算法陷入局部最優解的風險。從遺傳算法的改進方式可以看出，改進的方式還是較為單一，并且僅限應用于對調度規劃中遺傳算法的改進。

3 粒子群算法的發展歷程

粒子群優化算法（PSO）是通過模擬鳥群覓食行為而發展起來的一種基于群體協作的隨機搜索算法。PSO可以和其他優化算法進行結合且連通性特別好。PSO中，每一只鳥都代表一個需要搜索解決的問題[4]。一般將這樣的鳥稱之為搜索空間中的“粒子”。所有的粒子都有一個由被優化的函數決定的適應值，每個粒子還有一個速度決定他們飛翔的方向和距離，粒子們追隨當前的最優粒子在解空間中搜索。

3.1 粒子群算法特點

粒子群算法和遺傳算法有很多共同之處，但粒子算法運算結構十分簡單且運算效率高。因為PSO不需要對數據進行交叉和變異操作，所以PSO算法的運算效率特別高，能更快速地收斂到適應值。PSO是通過更新迭代每個粒子在空間中的位置和速度來搜索最優解的，所以粒子群算法的精確度迭代次數和粒子的位置以及速度有關。粒子群算法能得到廣泛應用也和算法特有的信息共享以及單項信息流動的屬性有關。在全局中，所有粒子共享自己的位置，跟隨整個搜索范圍內最佳位置求取最優解，大大縮短了運算時間，提高了運算效率。

3.2 粒子群算法的不足

粒子群算法處理多解問題的表現不是很好，特別是處理多樣性最優解的問題上所得到的優解值略顯單一。對于復雜函數的算子的選擇比較麻煩。對于以上問題，目前通過改進多目標粒子群算法和改進權重PSO算法等實用性更強地改進PSO算法[5]。很多改進后的PSO算法針對不同優化問題表現的更有針對性，收斂速度更快，優解精度更高，還解決了遺傳算法處理不了的問題。

3.3 粒子群算法的改進與應用

粒子群算法的優化比起其他智能算法的改進升級更容易。主要是因為其實現起來非常簡單，而且需要設置的參數較少；待優化問題的維數對算法本身的影響不大，所以更容易被改進升級，實現多目標問題的優化。

以多目標優化的粒子群算法的改進方式為例。正常所提到的粒子群算法是單目標算法，由于其收斂快速，也容易陷入局部最優解的險境；同樣地，多目標的尋優也有這樣的問題，因此采用二者相結合的改進方式解決算法容易陷入局部最優解的問題。主要從以下4個方面對算法進行改進。

（1）在優化過程中，將原有的從整個空間中對局部搜索的方式改變為從多個相鄰的小集合的方式加強對局部的搜索，保持解的多樣性，使解在空間中分布得更加均勻，提高對領導粒子選擇的質量，從而提高收斂速度。

（2）在保持解的多樣性的過程中，改進的方式就比較多。可以將空間分解成多個子空間，有利于保持粒子的多樣性；也可以和量子理論結合，輔助粒子迭代到全局最優位置，在保持種群多樣的同時，加快收斂到全局最優解的時間；還可以基于博弈機制，篩選出優質的粒子，有利于保持種群的多樣性。

（3）從收斂性上提高精確度及速度。在進行單目標優化時收斂速度很快，但由于目標數和空間維度的增加，收斂速度也會隨之降低。可通過改進慣性權重系數和學習因子加快多目標的收斂速度；也可以引入新的策略和其他智能算法結合提高算法在整個空間的搜索速度，減少種群多樣性的流失；還可以利用粒子群算法信息共享的特點對種群進行劃分，通過各個子種群的信息共享保持多樣性的同時提高收斂速度。

（4）對迭代公式和運算結構進行改進。這一方面的改進主要針對優化問題的需要，制定一套有針對性的迭代公式、參數、擴展運算結構。

4 結語

本文介紹了智能算法的由來，重點介紹了遺傳算法和粒子群算法的優缺點。針對粒子群算法存在的不足總結出了幾種優化改進的PSO算法。

目前的智能算法研究水平還很難使機器設備達到真正的人工智能，只是對各種行為進行模仿，但智能計算將在未來處于一個快速發展的階段。算法不僅限于對自然規律的仿生，還需要與人的思維邏輯結合來實現真正的人工智能。智能算法將會逐步改變人們的生活和生產方式。