差分进化算法（Differential Evolution)

1.算法提出及思想来源

差分进化算法（Differential Evolution，DE)于1997年由Rainer Storn和Kenneth Price在遗传算法等进化思想的基础上提出的，本质是一种多目标（连续变量）优化算法（MOEAs），用于求解多维空间中整体最优解。

差分进化思想来源即是早期提出的遗传算法（GeneticAlgorithm，GA），模拟遗传学中的杂交(crossover)、变异(mutation)、复制(reproduction)来设计遗传算子。

差分进化算法相对于遗传算法而言，相同点都是通过随机生成初始种群，以种群中每个个体的适应度值为选择标准，主要过程也都包括变异、交叉和选择三个步骤。不同之处在于遗传算法是根据适应度值来控制父代杂交，变异后产生的子代被选择的概率值，在最大化问题中适应值大的个体被选择的概率相应也会大一些。而差分进化算法变异向量是由父代差分向量生成，并与父代个体向量交叉生成新个体向量，直接与其父代个体进行选择。显然差分进化算法相对遗传算法的逼近效果更加显著。

2.算法过程：

DE的群体由突变和选择过程驱动。突变过程，包括突变和交叉操作，这两步操作被设计用于利用或探索搜索空间，而选择过程被用于确保有希望的个体的信息可以进一步利用。

(1)种群初始化：

在解空间中随机均匀产生M个个体，每个个体由n维向量组成

<script type="math/tex; mode=display" id="MathJax-Element-40">X_i(0) =(x_{i,1}(0),x_{i,2}(0),x_{i,3}(0),…,x_{i,n}(0)) \\ i=1,2,3,…,M</script>
第i个个体的第j维值取值方式如下：
<script type="math/tex; mode=display" id="MathJax-Element-41">X_ {i,j}(0)=L_{j\_min}+rand(0,1)(L_{j\_max}-L_{j\_min})\\ i=1,2,3,…,M\\ j=1,2,3,…,n</script>
对于群体规模参数M，一般介于5×n5×n<script type="math/tex" id="MathJax-Element-42">5×n</script>与10×n10×n<script type="math/tex" id="MathJax-Element-43">10×n</script>之间，但不能少于4×n4×n<script type="math/tex" id="MathJax-Element-44">4×n</script>

(2)变异:

在第g次迭代中，从种群中随机选择3个个体Xp1(g),Xp2(g),Xp3(g)Xp1(g),Xp2(g),Xp3(g)<script type="math/tex" id="MathJax-Element-73">X_{p1}(g),X_{p2}(g),X_{p3}(g)</script>,且p1≠p2≠p3≠ip1≠p2≠p3≠i<script type="math/tex" id="MathJax-Element-74">p1\neq p2\neq p3 \neq i</script>，生成的变异向量为：

<script type="math/tex; mode=display" id="MathJax-Element-75">H_i(g)=X_{p1}(g)+F·(X_{p2}(g)-X_{p3}(g))</script>
其中Δp2,p3(g)=Xp2(g)−Xp3(g)Δp2,p3(g)=Xp2(g)−Xp3(g)<script type="math/tex" id="MathJax-Element-76">\Delta_{p2,p3}(g)=X_{p2}(g)-X_{p3}(g) </script>是差分向量，FF<script type="math/tex" id="MathJax-Element-77">F</script>是缩放因子
对于缩放因子F $F$<script type="math/tex" id="MathJax-Element-78">F</script>，一般是在[0,2]之间选择，通常取0.5
参数FF<script type="math/tex" id="MathJax-Element-79">F</script>的自适应调整：
将变异算子中随机选择的三个个体进行从优到劣的排序，得到Xb,Xm,Xw $X_b,X_m,X_w$<script type="math/tex" id="MathJax-Element-80">X_b,X_m,X_w</script>,对应适应度fb,fm,fwfb,fm,fw<script type="math/tex" id="MathJax-Element-81">f_b,f_m,f_w</script>,变异算子改为：
<script type="math/tex; mode=display" id="MathJax-Element-82">V_i=X_b+F_i(X_m-X_w)</script>
同时，F的取值根据生成差分向量的两个个体自适应变化：
<script type="math/tex; mode=display" id="MathJax-Element-83">F_i=F_l+(F_u-F_l)\frac{f_m-f_b}{ f_w-f_b}\\其中，F_l=0.1,F_u=0.9</script>

变异策略：

DE/rand/1:Vi(g)=Xp1(g)+F⋅(Xp2(g)−Xp3(g))DE/rand/1:Vi(g)=Xp1(g)+F·(Xp2(g)−Xp3(g))<script type="math/tex" id="MathJax-Element-94">DE/rand/1: V_i(g)=X_{p1}(g)+F·(X_{p2}(g)-X_{p3}(g))</script>
DE/best/1:Vi(g)=Xbest(g)+F⋅(Xp1(g)−Xp2(g))DE/best/1:Vi(g)=Xbest(g)+F·(Xp1(g)−Xp2(g))<script type="math/tex" id="MathJax-Element-95">DE/best/1: V_i(g)=X_{best}(g)+F·(X_{p1}(g)-X_{p2}(g))</script>
DE/current to best/1:Vi(g)=Xi(g)+F⋅(Xbest(g)−Xi(g))+F⋅(Xp1(g)−Xp2(g))DE/current to best/1:Vi(g)=Xi(g)+F·(Xbest(g)−Xi(g))+F·(Xp1(g)−Xp2(g))<script type="math/tex" id="MathJax-Element-96">DE/current\ to\ best/1: V_i(g)=X_{i}(g)+F·(X_{best}(g)-X_{i}(g))+F·(X_{p1}(g)-X_{p2}(g))</script>
DE/best/2:Vi(g)=Xbest(g)+F⋅(Xp1(g)−Xp2(g))+F⋅(Xp3(g)−Xp4(g))DE/best/2:Vi(g)=Xbest(g)+F·(Xp1(g)−Xp2(g))+F·(Xp3(g)−Xp4(g))<script type="math/tex" id="MathJax-Element-97">DE/best/2: V_i(g)=X_{best}(g)+F·(X_{p1}(g)-X_{p2}(g))+F·(X_{p3}(g)-X_{p4}(g))</script>
DE/rand/2:Vi(g)=Xp1(g)+F⋅(Xp2(g)−Xp3(g))+F⋅(Xp4(g)−Xp5(g))DE/rand/2:Vi(g)=Xp1(g)+F·(Xp2(g)−Xp3(g))+F·(Xp4(g)−Xp5(g))<script type="math/tex" id="MathJax-Element-98">DE/rand/2: V_i(g)=X_{p1}(g)+F·(X_{p2}(g)-X_{p3}(g))+F·(X_{p4}(g)-X_{p5}(g))</script>

(3)交叉:

<script type="math/tex; mode=display" id="MathJax-Element-104">v_{i,j}=\left\{ \begin{aligned} h_{i,j}(g) & ,rand(0,1)\leq cr\\ x_{i,j}(g) & ,else \end{aligned} \right.</script>

其中cr∈[0,1]为交叉概率cr∈[0,1]为交叉概率<script type="math/tex" id="MathJax-Element-105">cr\in[0,1]为交叉概率</script>
参数crcr<script type="math/tex" id="MathJax-Element-106">cr</script>的自适应调整：

其中fifi<script type="math/tex" id="MathJax-Element-107">f_i</script>是个体XiXi<script type="math/tex" id="MathJax-Element-108">X_i</script>的适应度，fminfmin<script type="math/tex" id="MathJax-Element-109">f_{min}</script>与fmaxfmax<script type="math/tex" id="MathJax-Element-110">f_{max}</script>分别是当前种群中最差和最优个体的适应度，f¯f¯<script type="math/tex" id="MathJax-Element-111">\bar f</script>是当前种群适应度平均值,crlcrl<script type="math/tex" id="MathJax-Element-112">cr_l</script>和crucru<script type="math/tex" id="MathJax-Element-113">cr_u</script>分别是crcr<script type="math/tex" id="MathJax-Element-114">cr</script>的下限与上限，一般crl=0.1,cru=0.6crl=0.1,cru=0.6<script type="math/tex" id="MathJax-Element-115">cr_l=0.1,cr_u=0.6</script>

(4)选择:

<script type="math/tex; mode=display" id="MathJax-Element-119">X_i(g+1)=\left\{ \begin{aligned} V_i(g) & ,f(V_i(g)) 对于每个个体，Xi(g+1)Xi(g+1)<script type="math/tex" id="MathJax-Element-120">X_i(g+1)</script>要好于或持平于Xi(g)Xi(g)<script type="math/tex" id="MathJax-Element-121">X_i(g)</script>,通过变异，交叉，选择达到全部最优。
伪代码：