1.1.5 差分進化算法

1997年，為了求解切比雪夫多項式的擬合問題，R. M. Storn等人[23]提出了主要用于求解實數優化問題的差分進化算法（DEA）。DEA作為一種基于群體導向的自適應啟發式全局隨機搜索技術，包括初始化、變異、交叉及選擇等操作；與其他優化算法的不同在于，DEA的進化個體擾動是通過多個個體的差分信息來體現的。

DEA的基本思想：首先，采用浮點向量進行編碼隨機產生初始種群；其次，把種群中任意兩個個體的向量求差生成差分向量，乘以縮放因子與第三個個體求和來產生實驗個體；再次，對父代個體與相應的實驗個體進行交叉操作，生成新的子代個體；最后，在父代個體和子代個體之間進行選擇操作，將符合要求的個體保存到下一代群體中去；通過不斷地進化，保留優良個體，淘汰劣質個體，引導搜索向最優解逼近。

DEA主要的控制參數包括種群規模、交叉概率和縮放因子。

種群規模主要反映算法中種群信息量的大小，種群規模值越大，種群信息越豐富，但是帶來的后果就是計算量變大，不利于求解。反之，使種群多樣性受到限制，不利于算法求得全局最優解，甚至會導致搜索停滯。

交叉概率主要反映的是在交叉的過程中，子代與父代、中間變異體之間交換信息量的大小程度。交叉概率的值越大，信息量交換的程度越大。反之，如果交叉概率的值偏小，將會使種群的多樣性快速減小，不利于全局尋優。

相對于交叉概率，縮放因子對算法性能的影響更大，縮放因子主要影響算法的全局尋優能力。縮放因子越小，算法對局部的搜索能力更好，縮放因子越大，算法越能跳出局部極小點，但是收斂速度會變慢。此外，縮放因子還影響種群的多樣性。

差分進化的核心和關鍵是變異操作指導算法向全局最優處靠攏。變異向量由種群中的個體與其他不同個體的向量縮放差共同構成，主要分為基向量和差分向量兩部分，根據生成變異向量的不同方法能夠得到多種變異策略。DE/x/y是一種簡易的表達變異策略的方式，其中x表示指定基向量的方式，rand表示基向量為種群中隨機選取的一個向量，best表示基向量為種群適應度值最低的向量；y代表變異策略中差分向量的數目，一般為1個或2個。在種群規模n足夠大的情況下，使用兩個差分向量可以增加種群的多樣性。

最常用的變異策略如下：

（1）DE/rand/1

（2）DE/rand/2

（3）DE/best/1

（4）DE/best/2

（5）DE/rand-to-best/1

（6）DE/rand-to-best/2

（7）DE/current-to-rand/1

其中，是隨機整數，彼此互不相同并且不同于i，范圍為[1，n]。縮放因子F是控制種群發展速度的一個正實數，F沒有上限，但是其最大值很少大于1。Xbest,g為第g代種群中適應度值最小的個體。K為（0，1）之間的隨機數。

為了增加變異向量的多樣性，實施交叉策略，將變異向量與目標向量進行交叉混合，得到試驗向量。交叉概率參數用于控制試驗向量由變異向量的元素組成的概率，這個值由用戶自己定義，范圍一般為[0，1]。交叉方式主要有兩種，分別是二項交叉和指數交叉。

差分進化算法具有如下優點。

（1）結構簡單：DEA采用浮點編碼，控制參數少，主要的進化操作是差分變異策略，這使得向量間只存在簡單的加減運算，讓算法更加易于使用。

（2）性能優越：DEA具有較高的穩定性、較強的穩健性和較快的工作效率，在解決復雜的優化問題時也有不錯的表現。

（3）自適應性：DEA對問題的特征信息不敏感，差分變異算子擁有搜索方向自適應的能力，能夠動態地調整參數以適應不同的目標函數。

（4）“貪婪”選擇策略：DEA在進化的最后一步執行選擇策略，采用“貪婪”選擇的方式選取進入下一代的個體，該方法大大提高了算法的搜索效率。

（5）時間復雜度低：基本的DEA的時間復雜度為O(n·m·Gmax)，其中，m表示個體維數，Gmax表示最大進化代數。較低的時間復雜度使得DE算法具有求解大規模全局優化問題的優勢。

雖然DE算法具有許多算法沒有的優勢，但也無法完全避免智能進化算法普遍存在的不足。

（1）停滯：以種群為基礎的算法，迭代很少的次數就收斂到了一個次優解，而種群的多樣性仍然很高，這是由于種群在一定的時間內沒有改善，使算法無法尋找到新的搜索空間以確定最優解。誘發停滯的因素有很多，其中最主要的因素是控制參數和決策空間維數的錯誤選擇。

（2）早熟收斂：一些高等級的個體特性占種群的主導地位，種群無法產生比父代更好的子代，從而導致種群收斂到了局部最優。

（3）對控制參數敏感：算法的有效性和穩健性依賴于參數值的選擇，最佳的參數值確定還與目標函數及收斂精度有關。

（4）缺乏處理約束問題的機制：在實際的優化過程中經常遇到DEA無法很好地解決約束優化問題的情況。

為了解決基本DEA的上述缺陷，目前主要的改進方法是針對種群結構、進化模式和控制參數的優化，還有一些改進方法是將DE算法與其他一些智能算法結合使用[24,25]。