通过阅读本文，你将了解遗传算法（Sciopt-kit GA）的具体实现。
一、外部库学习任务表
按需要学习，在学习完成后，在下方打勾：
- [x] import numpy as np
- [ ] from .base impot SkoBase
- [x] from sko.tools import func_transformer
- [ ] from abc import ABCMeta, abstractmethod
- [x] from .operators import crossover, mutation, ranking, selection
1.1 def func_transformer(func)
使用指定模式 mode， 对 func 进行优化，返回一个优化后的函数。
预备知识备注：
- getattr(object, name[, default]) 返回一个对象的属性值，default 为默认值
- @lru_cache（@cache 3.9）装饰器，缓存某个函数的运行结果，以避免重复执行
- multiprocessing.Pool 对象，通过使用子进程而非子线程执行并发操作
- multiprocessing.dummy.Pool 对象，通过使用子线程执行并发操作
- 确定 mode 值，mode 可能值为 ：
('common', 'multithreading', 'multiprocessing', 'vectorization', 'cached', 'others')
- 根据 mode 值对函数进行优化：
二、类库的主体函数
2.1 GeneticAlgorithmBase 类解读
2.1.1 GABase 类包含的属性（字段）
为了在大纲里显示更多文字，将 GeneticAlgorithmBase 简写成 GABase
| 字段名 | 注释 |
|---|---|
| func | 经过优化后的目标函数 |
| size_pop | 种群的数量，assert 其为偶数，默认 50 |
| max_iter | 最大迭代次数，默认 200 |
| prob_mut | 编译的概率，默认 0.001 |
| n_dim | 变量的个数（问题的维度） |
| early_stop | 提取终止的标志，整数，最优值出现了 early_stop 次 |
| has_constraint | 是否有约束条件 |
| constraint_eq | 等式约束，默认空 |
| constraint_ueq | 不等式约束，默认空 |
| Chrom | 种群，GA 中实现为由基因的个体 |
| X | 运算过程变量，由 chrom2x 得到 |
| Y_raw | 运算过程变量，由 func(X) 计算得到，迭代个体的真实目标函数值 |
| Y | 运算过程变量，由 x2y 得到 |
| FitV | 运算过程变量，变量（种群）的适应度 |
| generation_best_X | 过程记录变量，记录着每一代种群适应度最大个体的 X |
| generation_best_Y | 过程记录变量，记录着每一代种群适应度最大个体的 Y |
| all_history_Y | 过程记录变量，记录着每一代种群所有个体的 Y 值 |
| all_history_FitV | 过程记录变量，记录着每一代种群所有个体的适应度 |
| best_x | 迭代结束的结果，为 generation_best_X 的最小值 |
| best_y | 迭代结束的结果，为 generation_best_X 的最小值 |
2.1.2 GABase 类包含的方法
@ 指的是 abstractmethod，即抽象方法
| 方法名 | 注释 |
|---|---|
| chrom2x(Chrom)@a | 基因转换成实数 |
| x2y | 由 X 计算得到 Y，应用了罚函数，将约束转换成无约束 |
| ranking@a | 排序 |
| selection@a | 选择 |
| crossover@a | 交叉 |
| mutation@a | 变异 |
| run(max_iter) | 执行迭代过程 |
2.1.3 GABase 类 run 方法解读
- 赋值最大迭代数 self.max_iter，赋值用于判断提前结束标志的临时变量 best
进入种群的迭代循环：
- 计算 X、Y（初始化种群？）
- 排序、选择、交叉、变异
- 记录 generation_best_X、generation_best_Y、all_history_Y、all_history_FitV
- 如果指定可以提前结束迭代，当最优值出现 early_stop 次，则跳出迭代循环
- 返回 generation_best_Y 中记录着的最小个体
2.1.4 GABase 类 x2y 方法解读
存在约束条件，则对每个个体应用罚函数（看下表），罚因子是 1e5：
| 约束条件类型 | 个体罚函数的计算方法 |
|---|---|
| 等式约束 | $\sum{\vert constranint \vert}$ （constranint 为等式约束求得的结果，为 0 说明满足等式约束） |
| 不等式约束 | $\sum{\max(0, constraint)}$ （constranint 为不等式约束求得的结果，大于0，说明不满足不等式约束） |
援引作者对罚函数缺点的说明：
- 非常依赖初始值的选择，如果初始值“不小心”全随机到了可行域外，那么算法会在可行域外迭代
- 约束不能太多，否则目标函数非常“不平滑”，最后的优化结果什么也不是
- 最拖累效果的是等式约束，超过两个基本就完蛋了。
2.2 GA 类解读
GA 类继承自 GeneticAlgorithmBase 基类，该类实现了 chrom2x、排序、选择、交叉、变异等过程，接下来将这些过程进行解读。
2.2.1 GA 类额外包含的属性（字段）
预备知识备注：
- np.where(_condition, x, y_) 矢量化 + 广播，相当于 x if condition else y
| 额外字段名 | 注释 |
|---|---|
| lb | ndarray，变量的下界 |
| ub | ndarray，变量的上界 |
| precision | ndarray，变量的精确度 |
| Lind | ndarray，变量基因占用的位数，用于确定 X 的位置： $Lind_i=⌈\log_2{(\frac{ub_i-lb_i}{precision_i}+1)}⌉$ |
| int_mode_ | ndarray of boolean，变量是否为整数 |
| int_mode | 布尔值，进入整数模式的标识 |
| un_extend if int_mode | 进入整数模式，染色体最大的取值： $un\_extend_i = \begin{cases} lb_i + 2^{Lind_i}-1) \cdot precision_i & \text{if } int\_mode\__i \\ ub_i & \text{otherwise} \end{cases}$ |
| len_chrom | 基因的总个数 |
2.2.2 GA 类包含的方法
预备知识备注：
- np.random.randint(_low, high: int, size: tuple of ints_) 根据上下界和形状创建随机数组。
- 格雷码（Gray Code）是用 0-1 编码数字的一种方法。？
- _ndarray_.cumsum() 按照顺序累加元素，得到新列表，例如输入 array([0, 1, 2, 3, 4]) 则输出 array([ 0, 1, 3, 6, 10])。该方法用于确定基因的位置。
- _ndarray_.cumsum(_axis=x_) 在某轴上按照顺序累加元素，得到新列表。
- 位操作？
| 方法名 | 注释 |
|---|---|
| crtbp | 初始化种群，Chrom is ndarray of ndarray of byte |
| gray2rv(_gray_code_) | 将（用格雷码表示的）染色体片段转换为实数 |
| chrom2x(_Chrom_) | 将格雷码数组（染色体数组）转换为变量数组 X |
| ranking | 计算种群的适应度，这里 $FitV=-Y$ |
| selection | 从种群中随机抽取 3 个个体进行比赛，获胜者进入下一代，下一代种群满则停止比赛 |
| crossover | 分两半按顺序配对，选取一个随机区间，交换区间内父代的基因，得到两个子代 |
| mutation | 按照概率选择某些基因发生变异 |
2.2.3 GA 类 chrom2x 方法解读
chrom2x 可以看作是基因表达成性状的过程，这里指由格雷码编码的基因表达为实数种群。方法的大致逻辑如下：
- 获取基因的位置信息
- 初始化 X，根据位置信息，切片转换成实数并放入 X
- 基因是按照精细度划分成段得到，并不包含起始信息，于是进一步转化 $x_i:=lb_i+(ub\_extend_i-lb_i)\cdot x_i$。
如果进入整数模式，转换出来的整数可能越界，如是则转换为最大值。
2.2.4 位运算在基因交叉、变异中的运用
位运算包括：与、或、异或、取反、左移、右移。为了方便复习，总结一下与、或和异或的运算规则：
| 位运算 | 符号 | 运算规则 |
|---|---|---|
| 与 | & | $1\&1=1;1\&0=0;0\&0=0$ |
| 或 | | | $1 \vert 1=1;1 \vert 0=1;0 \vert 0=0$ |
| 异或 | ^ | $1∧1=0;1∧0=1;0∧0=1$ |
| 取反 | 未知 | 1 变成 0；0 变成 1 |
GA 类将基因表示成 0-1 构成的数组，应用位运算可以有效的完成交叉和编译操作，非常巧妙。下面我将分别进行说明：
一、基于源码解读位操作在基因「交叉」中的运用
列举某个位置的基因交叉前后的状态：
| 父代 1 交叉前 | 父代 2 交叉前 | 父代 1 交叉后 | 父代 2 交叉后 |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
思路巧妙，我也不过多解释了，看总结的整个过程：
| 父代 1 交叉前（Chrom1） | 父代 2 交叉前（Chrom2） | mask2 = Chrom1 ^ Chrom2 | Chrom1 ^ mask2（父代 1 交叉后） | Chrom2 ^ mask2（父代 2 交叉后） |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
二、基于源码解读位操作在基因「变异」中的运用
思路巧妙，不过多解释，看下面这个过程：
| 原始基因（Chrom） | 变异（mask） | 变异后的基因（Chrom ^ mask） |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
三、心得体会
- 使用 numpy 进行矢量化运算，确实可以大幅提升程序的运行效率。
- 位运算用于 0 1 基因交叉和变异非常巧妙。
- 遗传算法的实现并不能，阅读源码的过程很有启发性，是精修编程语言的有效方法。
- 遗传算法模拟了生物进化的过程，貌似有一定的科学依据。
- 现有一个疑惑：如何才能更加有效的处理约束条件。
- 对二进制编码与实数的映射还需要进一步学习。