DE算法简介

前言

这两天看了DE算法，简单说下自己的认识

一、DE是什么？

百科定义：差分进化算法(Differential Evolution Algorithm，DE)是一种高效的全局优化算法。它也是基于群体的启发式搜索算法，群中的每个个体对应一个解向量。

差分进化算法DE（Differential Evolution）由Storn等人于1995年提出。最初用于解决切比雪夫多项式问题，现在DE广泛用于解决复杂优化问题，并且取得非常不错的效果。它通过模拟生物进化的过程，通过不断演化生成一组解，以期望找到问题的最优解。

二、DE流程

1. 初始化种群： 随机生成一定数量的个体，形成初始种群；
2. 变异（差分操作）：对每个个体执行差分操作，生成新的个体。差分操作涉及目标个体、两个随机选择的其他个体和一个缩放因子；
3. 交叉： 将变异后的个体与目标个体进行交叉操作，生成新的解；
4. 选择： 比较新生成的解和当前种群中对应位置的个体，选择其中更优秀的个体作为下一代的种群；
5. 重复迭代： 重复执行上述步骤，直到满足停止条件，例如达到最大迭代次数。

2.1 初始化种群

初始化种群先确定个体的数量NP（又称种群规模）和个体的初始基因数D；然后指定范围后随机生成结果；
如下所示，博主是生成了一个基因数D为10的种群，种群数量NP为2（放的太多会影响内容，出于演示考虑就放两个，真正运行时不能这样）。

[[-18.02048681 -14.41718301  -9.71498628 -19.59758138   2.96261434
    9.88606516 -17.80244701  10.98612544   7.85991822  -4.35000201]
 [-11.12895672   7.22395332  -8.69086121  -7.86988929  -3.97588362
    7.80052737   7.26921488   6.6008707  -10.11471569  15.70808097]]
1
2
3
4

2.2 变异（差分操作）

在第g次迭代中，从种群中随机选择3个个体Xp1(g)，Xp2(g)，Xp3(g)，且p1≠p2≠p3≠i，生成的变异向量为

Xp1(g)称为基向量，(Xp2(g)-Xp3(g))称为差分向量;
F是缩放因子，F越大，越不容易陷入局部极值点；F越小，越有利于收敛到局部极值点;
计算出来的结果Hi(g)被称为变异个体；
上面的i代表的是当前第g代种群中的第i个个体，所以其实当前种群中的每个个体都会生成一个变异个体。

2.3 交叉

以一定概率让新产生的变异个体与原种群中个体进行交叉重组，增强种群的多样性

其中cr∈[0,1]为交叉概率，得出的结果Vi,j被称为试验个体

2.4 选择

将试验个体和父代个体相比较选择损失函数较小的作为下一代个体

2.5 重复迭代

重复执行上述步骤，直到满足停止条件，例如达到最大迭代次数。

三、DE运行结果

附代码

import numpy as np
import random
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif']=['SimHei'] #设置显示中文标签
plt.rcParams['axes.unicode_minus']=False   #设置正常显示符号
import math as mt

#损失函数
def funcl(x):
    y = 0
    for i in range(len(x)):
        y = y + x[i] ** 2
    return y


#初始化参数
NP = 100  # 初始化种群数
D = 10  # 基因数目
CR = 0.1  # 交叉算子
F0 = 0.4  # 初始变异算子
G = 1000  # 最大遗传代数
Xs = 20  # 上限
Xx = -20  # 下限

jiyi = np.random.rand(NP, D)
f = jiyi * (Xs - Xx) + Xx  # 随机获得初始种群
FIT = []  # 适应度计算存储列表
trace = []
xtrace = []

for i in range(NP):
    FIT.append(funcl(f[i]))

# 差分进化循环
for i in range(G):
    print(f'第{i}代')
    vec = []  # 变异种群,没看懂但是都是2维的
    u = [[] for i in range(NP)]  # 选择种群
    lamda = mt.exp(1 - G / (G - i))  # 自适应变异算子，随着迭代次数发生变化，之后可以讨论一下
    F = F0 * (2 ** lamda)
    # 变异操作，和遗传算法的变异不同！,得到任意两个个体的差值，与变异算子相乘加第三个个体
    for m in range(NP):
        r1 = random.sample(range(0, NP), 1)[0]
        while r1 == m:
            r1 = random.sample(range(0, NP), 1)[0]
        r2 = random.sample(range(0, NP), 1)[0]
        while r2 == m or r2 == r1:
            r2 = random.sample(range(0, NP), 1)[0]
        r3 = random.sample(range(0, NP), 1)[0]
        while r3 == m or r3 == r2 or r3 == r1:
            r3 = random.sample(range(0, NP), 1)[0]
        vec.append(f[r1] + F * (f[r2] - f[r3]))

    # 交叉操作,交叉所有个体的第j维
    r = random.sample(range(0, NP), 1)[0]
    for j in range(D):
        cr = np.random.rand()
        tem = []
        if cr <= CR or j == r:
            for k in range(len(f)):
                u[k].append(vec[k][j])  # 添加所有个体的第j维
        else:
            for k in range(len(f)):
                u[k].append(f[k][j])

    # 边界条件处理
    for j in range(NP):
        for m in range(D):
            if u[j][m] < Xx or u[j][m] > Xs:
                u[j][m] = np.random.rand() * (Xs - Xx) + Xx  # 因为vec是变异得到的，所以不一定在取值范围之内
            else:
                continue
    # 选择操作
    FIT1 = []
    for m in range(NP):
        FIT1.append(funcl(u[m]))
    for m in range(NP):
        if FIT1[m] < FIT[m]:
            f[m] = u[m]
    FIT = []
    for m in range(NP):
        FIT.append(funcl(f[m]))
    trace.append(min(FIT))
    xtrace.append(f[FIT.index(min(FIT))].tolist())  # 这里呀，ndarray读进来的时候会发生浅拷贝和深拷贝的问题，转成列表形式保存就不会出问题了
xvalue = []
for i in range(len(xtrace)):
    xvalue.append(xtrace[i][2])

# 绘制结果
plt.plot(trace, color='deepskyblue', marker='o', linewidth=2, markersize=3)
plt.xlabel('迭代次数', fontsize=10)
plt.ylabel('损失函数', fontsize=10)
plt.show()
plt.close()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94