遗传算法之scikit Opt库使用

一、遗传算法概念

基本思想：

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

二、算法过程

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

几个关键算子

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

选择算子：轮盘选择（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
 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)

运行遗传算法

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)

用 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)

遗传算法进行整数规划

在多维优化时，想让哪个变量限制为整数，就设定 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 就是整数了。

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