睿智的智能优化算法4——进化策略（Evolution Strategy）

我不是女神ヾ 2024-04-18 13:46 29阅读 0赞

### 睿智的智能优化算法4——进化策略（Evolution Strategy） ###

*  1、算法思路
 *   *  1.1、杂交方式
     *  1.2、基因突变
     *  1.3、淘汰低适应度个体。
 *  2、与遗传算法对比
 *   *  2.1、相同点：
     *  2.2、不同点：
 *  实现代码
 *  GITHUB下载连接

遗传算法是一种基于达尔文进化论的与基因相关的优化算法，但由于其编码方式需要用到01编码，所以其存在实数处理方面的局限性；本文将介绍遗传算法的姊妹，进化策略，其可以用于实数处理。关于什么是遗传算法，及其实现方式，大家可以关注我的另一篇博文[睿智的智能优化算法2——遗传算法的python实现][2_python]  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 1、算法思路 #

进化策略的思路与遗传算法相似，二者都是利用进化理论进行优化，即利用遗传信息一代代传承变异，通过适者生存的理论，保存适应度高的个体，得到最优解。  
了解进化策略，首先要从进化策略的个体入手。  
进化策略的每个个体都具有两个特点。  
1、基因，通过基因进行运算可以得到每个个体的适应度。  
2、变异强度，变异强度则是每次基因杂交完，基因变化的一个范围。  
假设一个种群有四个个体，四个个体的参数如图所示：  
![在这里插入图片描述][20190907155912432.png_pic_center]  
进化策略的更新方式主要分为两个部分：  
1、通过现有的种群，更新后代，其中需要经过杂交、基因突变两个过程。  
2、将生成的后代与他们的父母辈合成一个种群，在其中淘汰低适应度个体。  
接下来我将详细讲述杂交、基因突变、淘汰低适应度个体的过程。

## 1.1、杂交方式 ##

与遗传算法不同，进化策略的杂交方式主要分为 步：  
1、随机选择双亲。  
2、从双亲身上分别取指定位置的基因，二者组合成为新基因。  
3、从双亲身上分别取指定位置的杂交强度，二者组合成为新的变异强度。  
其执行示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
执行代码如下所示：

# 杂交，随机选择父母
    p1, p2 = np.random.choice(self.pop_size, size=2, replace=False)
    # 选择杂交点
    cp = np.random.randint(0, 2, self.gene_size, dtype=np.bool)
    # 当前孩子基因的杂交结果
    kv[cp] = self.pop['DNA'][p1, cp]
    kv[~cp] = self.pop['DNA'][p2, ~cp]
    # 当前孩子变异强度的杂交结果
    ks[cp] = self.pop['mut_strength'][p1, cp]
    ks[~cp] = self.pop['mut_strength'][p2, ~cp]

## 1.2、基因突变 ##

在算法中，每次个体杂交完，都会进行一定的变异，变异的多少由个体的变异强度决定，其变异的代码如下。其中np.random.randn()满足正态分布。

# kv代表DNA，ks代表变异强度
    kv += ks * np.random.randn()

变异的示意图如下：  
![在这里插入图片描述][20190907162527881.png_pic_center]  
由于算法最终要收敛，所以变异强度需要不断变小，但不可以低于0，变小方式如下：

# 变异强度要大于0，并且不断缩小
    ks[:] = np.maximum(ks + (np.random.rand()-0.5), 0.)

## 1.3、淘汰低适应度个体。 ##

淘汰低适应度个体前首先需要合并父种群和子种群

# 进行vertical垂直叠加
    for key in ['DNA', 'mut_strength']:
        self.pop[key] = np.vstack((self.pop[key], self.kids[key]))

再计算整个种群的适应度：

# 计算fitness
    self.pred = F(self.pop['DNA'])
    fitness = self.get_fitness()

最后对整个适应度进行，获得适应度从大到小的索引，并选择适应度最大的POP\_SIZE个个体：

# 读出按照降序排列fitness的索引
    max_index = np.argsort(-fitness)
    # 选择适应度最大的POP_SIZE个个体
    good_idx = max_index[:POP_SIZE]   
    for key in ['DNA', 'mut_strength']:
        self.pop[key] = self.pop[key][good_idx]

其整体的执行过程如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]

# 2、与遗传算法对比 #

## 2.1、相同点： ##

进化策略的思路与遗传算法相似，二者都是利用进化理论进行优化，即利用遗传信息一代代传承变异，通过适者生存的理论，保存适应度高的个体，得到最优解。

## 2.2、不同点： ##

1、遗传算法采用二进制编码杂交；而进化策略使用实数。  
2、遗传算法采用二进制0->1，1->实现变异；而进化策略则使用变异强度实现变异。

3、遗传算法仅需要一条编码链，用于存储个体的基因；进化策略在编码时，不仅要有实数编码链，还要有变异强度编码链。

4、遗传算法在交叉繁殖的时候，仅实现基因的交叉；进化策略则要实现两条链的交叉，父母辈的实数链交叉形成子辈的实数链，变异强度编码链交叉形成子辈的变异强度编码链。

5、遗传算法在变异时，随机选择基因段变异；进化策略则是将实数链上的实数值看作正态分布的均值μ，将变异强度编码链上变异强度值看作正态分布的标准差σ。

6、遗传算法在自然选择时，通过轮盘赌实现自然选择；进化策略则将子种群加入到父种群中，按照适应度排序，直接选出适应度最大的pop\_size个个体。

# 实现代码 #

本次实现代码源自[莫烦python][python]，但我将其改成了class的形式。

import numpy as np
    import matplotlib.pyplot as plt
    
    # 每个个体的长度
    GENE_SIZE = 1
    # 每个基因的范围
    GENE_BOUND = [0, 5]    
    # 200代   
    N_GENERATIONS = 200
    # 种群的大小
    POP_SIZE = 100          
    # 每一代生成50个孩子
    N_KID = 50  
    
    # 寻找函数的最大值
    def F(x): 
        return np.sin(10*x)*x + np.cos(2*x)*x    
    
    class ES():
        def __init__(self,gene_size,pop_size,n_kid):
            # 基因长度代表字符串的长度
            self.gene_size = gene_size
            # 种群的大小代表种群中有几个个体
            self.pop_size = pop_size
            self.n_kid = n_kid
            self.init_pop()
            print(self.pop)
        # 降到一维
        def get_fitness(self): 
            return self.pred.flatten()
    
        # 初始化种群
        def init_pop(self):
            self.pop = dict(DNA=5 * np.random.rand(1, self.gene_size).repeat(POP_SIZE, axis=0),
               mut_strength=np.random.rand(POP_SIZE, self.gene_size))
    
        # 更新后代
        def make_kid(self):
            # DNA指的是当前孩子的基因
            # mut_strength指的是变异强度
            self.kids = {
        'DNA': np.empty((self.n_kid, self.gene_size)),
                    'mut_strength': np.empty((self.n_kid, self.gene_size))}
    
            for kv, ks in zip(self.kids['DNA'], self.kids['mut_strength']):
                # 杂交，随机选择父母
                p1, p2 = np.random.choice(self.pop_size, size=2, replace=False)
                # 选择杂交点
                cp = np.random.randint(0, 2, self.gene_size, dtype=np.bool)
                # 当前孩子基因的杂交结果
                kv[cp] = self.pop['DNA'][p1, cp]
                kv[~cp] = self.pop['DNA'][p2, ~cp]
                # 当前孩子变异强度的杂交结果
                ks[cp] = self.pop['mut_strength'][p1, cp]
                ks[~cp] = self.pop['mut_strength'][p2, ~cp]
    
                # 变异强度要大于0，并且不断缩小
                ks[:] = np.maximum(ks + (np.random.rand()-0.5), 0.)    
                kv += ks * np.random.randn()
                # 截断
                kv[:] = np.clip(kv,GENE_BOUND[0],GENE_BOUND[1])   
    
        # 淘汰低适应度后代
        def kill_bad(self):
            # 进行vertical垂直叠加
            for key in ['DNA', 'mut_strength']:
                self.pop[key] = np.vstack((self.pop[key], self.kids[key]))
    
            # 计算fitness
            self.pred = F(self.pop['DNA'])
            fitness = self.get_fitness()
            
            # 读出按照降序排列fitness的索引
            max_index = np.argsort(-fitness)
            # 选择适应度最大的50个个体
            good_idx = max_index[:POP_SIZE]   
            for key in ['DNA', 'mut_strength']:
                self.pop[key] = self.pop[key][good_idx]
    
    
    test1 = ES(gene_size = GENE_SIZE,pop_size = POP_SIZE,n_kid = N_KID)
    
    plt.ion()     
    x = np.linspace(*GENE_BOUND, 200)
    plt.plot(x, F(x))
    
    for _ in range(N_GENERATIONS):
        # 画图部分
        if 'sca' in globals(): sca.remove()
        sca = plt.scatter(test1.pop['DNA'], F(test1.pop['DNA']), s=200, lw=0, c='red', alpha=0.5)
        plt.pause(0.05)
    
        # ES更新
        kids = test1.make_kid()
        pop = test1.kill_bad()
    
    plt.ioff(); plt.show()

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Optimization\_Algorithm][https_github.com_bubbliiiing_Optimization_Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[2_python]: https://blog.csdn.net/weixin_44791964/article/details/99826470
[20190723170158884.jpg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/53b6b9bb79c64ec380cb8f1364769f36.jpg
[20190907155912432.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4e1718e0a4374ac8a2feb0465d9575d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/32e215b602b34b25b9f3aa21a7fc2393.png
[20190907162527881.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/987fd13ea5894a7190fbbad1bf45ebaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a83225cebd454083bacdd40aeb4a2849.png
[python]: https://morvanzhou.github.io/tutorials/machine-learning/evolutionary-algorithm/2-02-genetic-algorithm-match-phrase/
[https_github.com_bubbliiiing_Optimization_Algorithm]: https://github.com/bubbliiiing/Optimization_Algorithm