遗传算法之scikit Opt库使用
Table of Contents
一、遗传算法概念
基本思想:
-
遗传算法(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、安装
|
|
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()
3、工具参数含义与使用指导
可以使用命令查看使用帮助
|
|
遗传算法进行整数规划
在多维优化时,想让哪个变量限制为整数,就设定 precision
为 整数 即可。
例如,我想让我的自定义函数 demo_func
的某些变量限制为整数+浮点数(分别是隔2个,隔1个,浮点数),那么就设定 precision=[2, 1, 1e-7]
例子如下:
|
|
说明:
- 当
precision
为整数时,对应的自变量会启用整数规划模式。 - 在整数规划模式下,变量的取值可能个数最好是 $2^n$,这样收敛速度快,效果好。
- 如果
precision
不是整数(例如是0.5),则不会进入整数规划模式,如果还想用这个模式,那么把对应自变量乘以2,这样precision
就是整数了。
更多参考提供的文档:自定义算子、