Table of Contents

一、遗传算法概念

基本思想:

  1. 遗传算法(GA)是一种全局寻优搜索算法,它依据的是大自然生物进化过程中“适者生存”的规律。它首先对问题的可行解进行编码,组成染色体,然后通过模拟自然界的进化过程,对初始种群中的染色体进行选择、交叉和变异,通过一代代进化来找出最优适应值的染色体来解决问题。

  2. 遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。因此,第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择个体,幵借助于自然遗传学的遗传算子(genetic operators)进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样,后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。

二、算法过程

img

采用遗传算法解决任何一种问题,第一步要做的工作是确定正确的编码方式。

几个关键算子

可参考遗传算法中常见遗传算子

选择算子:轮盘选择(roulette wheel selection)、排序选择(rank-based selection)、锦标赛选择(Tournament selection);

交叉算子:单点交叉(Single-point crossover)、k点交叉(K-point crossover)、均匀交叉(Uniform crossover)等;

变异算子:位翻转突变(Flip bit mutation)、交换突变、反转突变(Swap mutation)等。

实数编码染色体的遗传算子:用于处理解空间连续问,也即个体由实数(浮点数)组成。混合交叉、模拟二进制交叉、实数突变。选择操作不受影响

三、遗传算法工具箱

scikit-opt 是一个封装了7种启发式算法的 Python 代码库

(差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法)

中文文档

1、安装

1
pip install scikit-opt

2、快速开始

  1. 定义你的问题

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    
    import numpy as np
    
    
    def schaffer(p):
        '''
        This function has plenty of local minimum, with strong shocks
        global minimum at (0,0) with value 0
        '''
        x1, x2 = p
        x = np.square(x1) + np.square(x2)
        return 0.5 + (np.square(np.sin(x)) - 0.5) / np.square(1 + 0.001 * x)
    
  2. 运行遗传算法

    1
    2
    3
    4
    5
    
    from sko.GA import GA
    
    ga = GA(func=schaffer, n_dim=2, size_pop=50, max_iter=800, prob_mut=0.001, lb=[-1, -1], ub=[1, 1], precision=1e-7)
    best_x, best_y = ga.run()
    print('best_x:', best_x, '\n', 'best_y:', best_y)
    
  3. 用 matplotlib 画出结果

    1
    2
    3
    4
    5
    6
    7
    8
    
    import pandas as pd
    import matplotlib.pyplot as plt
    
    Y_history = pd.DataFrame(ga.all_history_Y)
    fig, ax = plt.subplots(2, 1)
    ax[0].plot(Y_history.index, Y_history.values, '.', color='red')
    Y_history.min(axis=1).cummin().plot(kind='line')
    plt.show()
    

    Figure_1-1

3、工具参数含义与使用指导

可以使用命令查看使用帮助

1
2
import sko
help(sko.GA.GA)

image-20211008163845342

遗传算法进行整数规划

在多维优化时,想让哪个变量限制为整数,就设定 precision整数 即可。 例如,我想让我的自定义函数 demo_func 的某些变量限制为整数+浮点数(分别是隔2个,隔1个,浮点数),那么就设定 precision=[2, 1, 1e-7] 例子如下:

1
2
3
4
5
6
from sko.GA import GA

demo_func = lambda x: (x[0] - 1) ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2
ga = GA(func=demo_func, n_dim=3, max_iter=500, lb=[-1, -1, -1], ub=[5, 1, 1], precision=[2, 1, 1e-7])
best_x, best_y = ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

说明:

  • precision 为整数时,对应的自变量会启用整数规划模式。
  • 在整数规划模式下,变量的取值可能个数最好是 $2^n$,这样收敛速度快,效果好。
  • 如果 precision 不是整数(例如是0.5),则不会进入整数规划模式,如果还想用这个模式,那么把对应自变量乘以2,这样 precision 就是整数了。

更多参考提供的文档:自定义算子、