文章目錄

• 簡介
• 1. 算法原理
• 2. 算法流程
• • 2.1 初始化種群
  • 2.2 變異
  • 2.3 交叉
  • 2.4 選擇
• 3. 算法代碼
• • 3.1 偽代碼
  • 3.2 matlab
• 4. 參數控制[^1]
• • 4.1 參數說明
  • 4.2 參數選擇
• 5. 改進方法[^1]
• • 5.1 自適應變異算子

簡介

????差分進化算法(Differential Evolution，DE)由Storn和Price于1995年首次提出。主要用于求解實數優化問題。該算法是一類基于群體的自適應全局優化算法，屬于演化算法的一種，由于其具有結構簡單、容易實現、收斂快速、魯棒性強等特點，因而被廣泛應用在數據挖掘、模式識別、數字濾波器設計、人工神經網絡、電磁學等各個領域。1996年在日本名古屋舉行的第一屆國際演化計算(ICEO)競賽中，差分進化算法被證明是速度最快的進化算法。

1. 算法原理

---

????DE算法通過采用浮點矢量進行編碼生成種群個體。在DE算法尋優的過程中，首先，從父代個體間選擇兩個個體進行向量做差生成差分矢量;其次，選擇另外一個個體與差分矢量求和生成實驗個體;然后，對父代個體與相應的實驗個體進行交叉操作，生成新的子代個體;最后在父代個體和子代個體之間進行選擇操作，將符合要求的個體保存到下一代群體中去。

2. 算法流程

---

假設優化模型如下：
$$\begin{array}{l}\min f\left(x_1,x_2,?,x_D\right)\\ \text{?s.t?}{x}_j^L?x_j?x_j^U,j=1,2,?,D\end{array}$$
$where$，D是解空間的維度，$x_j^L$、$x_j^U$分別表示第j個分量$x_j$取值范圍的上界和下界。

2.1 初始化種群

初始化種群為： $$\left\{x_i(0)|x_{j,i}^L?x_{j,i}(0)?x_{j,i}^v,i=1,2,?,NP;j=1,2,?,D\right\}$$
由下式隨機生成各種群個體：
$$x_{j,i}(0)=x_{j,i}^L+rand(0,1)?\left(x_{j,i}^U?x_{j,i}^L\right)$$
$where$，$x_i(0)$表示種群中第0代的第i個個體，$x_{j,i}(0)$表示第0代的第i個個體的第j個基因。NP表示種群大小，$rand(0,1)$表示在（0，1）區間均勻分布的隨機數。

---

---

2.2 變異

????差分進化算法與遺傳算法最顯著的區別在于DE的個體變異是通過差分策略實現的。

常用的差分策略如下：
$$\begin{array}{c}{\nu }_i(g+1)=x_{i_1}(g)+F?\left(x_i(g)?x_{ij}(g)\right)\\ i=r_1=r_2=r_3\end{array}$$

$where$，$F$為縮放因子，$x_i(g)$為第g代種群中第i個個體。

即通過隨機選取種群中兩個不同的個體，將其向量差縮放后與待變異個體進行向量合成。

????在進化過程中，必須保證新生成的解的有效性，因此必須判斷生成的解是否滿足邊界條件，如果不滿足，則需要重新生成（生成方案與初始種群相同）。

第g代種群：$$\left\{x_i(g)|x_{j,i}^L?x_{j,i}(g)?x_{j,i}^v,i=1,2,?,NP;j=1,2,?,D\right\}$$
變異后的中間體：第g代種群：$$\left\{x_i(g+1)|x_{j,i}^L?x_{j,i}(g+1)?x_{j,i}^v,i=1,2,?,NP;j=1,2,?,D\right\}$$

---

---

2.3 交叉

????使用第g代種群和其變異中間體進行交叉：

$$\begin{array}{r}{u}_{j,i}(g+1)=\{\begin{array}{ll}{v}_{j,i}(g+1),& \text{?if?}\mathrm{rand}(0,1)?CR\text{?or?}j=j_{\text{rand}}\\ x_{j,i}(g),& \text{?otherwise?}\end{array}\end{array}$$
$where$，CR為交叉概率，$j_{rand}$為[1,2,……,D]的隨機整數。

????上圖為6個基因位的“染色體”或稱為“個體”的交叉操作示意圖。為了確保變異中間體{$v_{j,i}(g+1)$}的每個“染色體”至少有一個“基因”遺傳給下一代，第一個交叉操作的基因是隨機選擇$v_{j,i}(g+1)$的第$j_{rand}$作為交叉后的個體$u_{j,i}(g+1)$第$j_{rand}$位的等位基因。后續的交叉操作則是通過交叉概率CR來選取$x_i(g)$還是$v_i(g+1)$的等位基因作為$u_i(g+1)$的等位基因。

---

---

2.4 選擇

????采用貪婪算法來選擇下一代種群個體：
$$x_i(g+1)=\{\begin{array}{ll}{u}_i(g+1),& \text{?if?}f\left(u_i(g+1)\right)?f\left(x_i(g)\right)\\ x_i(g),& \text{?otherwise?}\end{array}$$

3. 算法代碼

3.1 偽代碼

3.2 matlab

4. 參數控制¹

????DE算法主要的控制參數包括：種群規模(NP)、縮放因子(F)和交叉概率(CR)。

4.1 參數說明

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

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

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

4.2 參數選擇

• M：一般介于5n到10n之間，但不能少于4，否則變異算則無法進行
• F：一般在[0,2]，通常取0.5
• CR：[0,1]，通常取0.3.CR越大，收斂速度越快，但易發生早熟現象。

5. 改進方法¹

• 基本DE算法在求解的過程中，隨著進化代數的增加，會使種群的多樣性變小，過早的收斂到局部極小點，或者致使算法停滯，這對依靠種群差異來進行進化的算法來說無疑是致命的，使算法的性能在進化的過程中變差。

• 為了解決基本DE算法的上述缺陷，針對DE算法的特點，目前主要的改進方法是針對進化模式和控制參數的優化，還有一些改進方法是將DE算法與其他一些智能算法進行結合仲用。

5.1 自適應變異算子

????為了避免早熟，增加自適應變異算子。算子算法如下：
$$\begin{array}{l}\lambda =e^{1?\frac{G_m}{G_m+1?G}}\\ F=F_0?2^2\end{array}$$
$where$，$F_0$為變異算子；$G_m$為最大進化代數；$G$為當前進化代數。

????算法開始時，自適應算子$F=F_0$~$2F_0$。具有較大值時，初期保持個體多樣性，避免早熟，隨著算法進度的不斷變化，變異算子的值逐步降低，后期變異率接近$F_0$，保留優良信息，避免最優解遭到破壞，增加搜索到全局最優解的概率。

---

https://baike.baidu.com/item/%E5%B7%AE%E5%88%86%E8%BF%9B%E5%8C%96%E7%AE%97%E6%B3%95/10052475?fr=aladdin ?? ??

總結

以上是生活随笔為你收集整理的算法 - 差分进化(DE)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。