进化策略（Evolution Strategy）

咸玄天

2023-12-01

进化策略（Evolution Strategy）

建议在了解ES之前先确保对遗传算法的思路有一定的了解，在比较中学习更有效率，贴一个之前写过的遗传算法介绍

与遗传算法的相同之处：

都是利用进化理论进行优化，即利用遗传信息一代代传承变异适者生存，从而得到最优解。

与遗传算法的不同之处：

1.DNA序列采用实数编码，而非0-1二进制码

2.变异时无法进行简单的0-1互换，思考：实数值该怎么变？随机？

变异思路：为DNA序列上的每一个实数值添加变异强度。根据这个变异强度决定DNA序列上的实数值该变成多少

3.编码：

由第2点可知，进化策略在编码时，不仅要有表示解决方案的实数编码链A1，还得有一条表示每个实属值对应的变异强度值组成的链A2（也就是说，遗传给后代的信息有两种）

4.交叉：

两条链都要交叉，即A1与B1交叉形成表示子代解决方案的C1链，A2与B2交叉形成表示C1链对应位置实数值变异强度的C2链（父：A，母：B，子：C）

5.C1链上值的变异方法：

将C1链上的值看作正态分布的均值μ;
将C2链上变异强度值看作标准差σ;
用正态分布产生一个与C1链上选定位置相近的数，进行替换;

6.C2链上值的变异方法：

因为随着不断遗传迭代，种群中个体1号链的值不断逼近最优解，变异的强度也应当不断减小。所以也需要根据需求自定义2号链的变异方法。

7.选择：

将生成的孩子加入父代中，形成一个包含两代DNA的种群U;
对U种群中每个DNA序列的1号链（表示解决方案）进行fitness计算（打分），并根据分值从大到小排列（用U‘表示排列后的混合种群）;
截取U’中的分值高的前n位（n表示一代种群中的个体数目）形成新种群;

Python实现

上述的3-7点已经算是对进化策略的算法描述了，具体代码本人还没有自己敲只是看了看，这里就不粘了直接上莫烦源码

(1+1) - ES

与进化策略（ES）的相同之处：

本质算法思路都是ES

与进化策略（ES）的不同之处：

1.(1+1)-ES是ES的一种特殊形式，只考虑一个子代和一个父代，而不是种群中的所有个体。左1表示：一个父代个体，右1表示：一个子代个体，+表示：以父代和子代混合起来的形式选择，查看关于‘(1+1)’的详细解释

2.由1可知，在(1+1)-ES中，仅需对两个个体（一父一子）进行适者生存的选择，较好的那个留下，较差的淘汰

3.因为只有一个父代A所以不需要交叉，直接根据变异强度进行变异生成孩子C

4.遗传给后代的信息业包阔两部分，但不是两条链，而是用一条链A和一个数值a表示，A中所有值对应于同一个定义好的变异强度值a

4.分别利用fitness对A和C计算得分，得分高的留下，低的淘汰

5.定义了特定的变异强度的变化规则公式详见此处（我没懂）

Python实现

代码很简单我这贴一下莫烦源码：

import numpy as np
import matplotlib.pyplot as plt

DNA_SIZE = 1             # DNA (real number)
DNA_BOUND = [0, 5]       # solution upper and lower bounds
N_GENERATIONS = 200
MUT_STRENGTH = 5.        # 统一定义的变异强度


def F(x): return np.sin(10*x)*x + np.cos(2*x)*x     # to find the maximum of this function


# find non-zero fitness for selection
def get_fitness(pred): return pred.flatten()


def make_kid(parent):
    # 无交叉仅变异
    k = parent + MUT_STRENGTH * np.random.randn(DNA_SIZE)  #根据父代基因信息以及变异强度进行变异
    k = np.clip(k, *DNA_BOUND)    #控制范围
    return k


def kill_bad(parent, kid):
    global MUT_STRENGTH
    fp = get_fitness(F(parent))[0]      #计算得分
    fk = get_fitness(F(kid))[0]
    p_target = 1/5                      #变异强度的变异规则所定
    if fp < fk:     # kid better than parent
        parent = kid
        ps = 1.     # kid win -> ps = 1 (successful offspring)
    else:
        ps = 0.
    # adjust global mutation strength
    MUT_STRENGTH *= np.exp(1/np.sqrt(DNA_SIZE+1) * (ps - p_target)/(1 - p_target))    #变异强度的变异规则
    return parent


parent = 5 * np.random.rand(DNA_SIZE)   # parent DNA

plt.ion()       # something about plotting
x = np.linspace(*DNA_BOUND, 200)

for _ in range(N_GENERATIONS):
    # ES part
    kid = make_kid(parent)           #生孩子
    py, ky = F(parent), F(kid)       
    parent = kill_bad(parent, kid)   #淘汰不好的

    # something about plotting
    plt.cla()
    plt.scatter(parent, py, s=200, lw=0, c='red', alpha=0.5,)
    plt.scatter(kid, ky, s=200, lw=0, c='blue', alpha=0.5)
    plt.text(0, -7, 'Mutation strength=%.2f' % MUT_STRENGTH)
    plt.plot(x, F(x)); plt.pause(0.05)

plt.ioff(); plt.show()

参考：莫烦进化理论系列视频

进化策略（Evolution Strategy）