遗传算法¶
背景¶
模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法
基本原理¶
编码¶
将问题的可行解，抽象编码为适用于遗传算法的形式
- 二进制编码，将数值转化为二进制串，用于求解问题
- 若为连续区间可以给定精度过后进行编码
- TSP问题，比如10个城市，某个解可以表示为\([3,2,1,4,5,7,8,9,0]\)
- 根据不同问题进行不同的抽象实现
若要实现每个数值都能分配独一无二的串，那么串所能表示的数值个数就要大于数值解的个数，一个长度为n的串能表示\(2^n\)个数
解码¶
一个区间范围为\([a,b]\)， 区间长度为L，串长为\(n\)，当前串对应十进制T，则该串对应实值解为
\[X=a+T\cdot \frac{b-a}{2^n -1}\]
可以简单理解为：当前值=区间最小值+该二进制串对应十进制*精度
复制¶
个体进行复制，进行概率\(p_c\)进行基因的交叉
- 将个体适应度大小映射为概率进行复制：适应度高的个体有更大概率复制，且复制的份数越多——轮盘赌法
- 对适应度高的前N/4的个体进行复制，然后把后N/4的个体替换掉——"精英产生精英"
- 也可以随机将下一个个体替换掉
- 也可以随机将适应度高的解替换掉
交叉¶
- 个体按顺序两两按概率交叉，如1和2,2和3
- 也可以多个同时进行交叉
- 也可以对适应度高的前N/2个体进行相互交叉
- 也可以不按顺序交叉，对每个个体随机从前N/2个中选一个进行个体交叉
- 也可以进行多段交叉
变异¶
- 每个个体都进行变异
- 只对适应度低的后N/4或N/2进行变异
- 可以按适应度大小映射为概率变异
- 也可以是多个位点变异
算法实现¶
- 复制：按适应度大小映射为概率，进行轮盘赌复制
- 交叉：1和2,3和4，以一定概率决定是否交叉，若交叉，则二者随机选择一段进行交叉
- 变异，按照一定概率决定该个体是否变异，若变异，随机选择一个位点进行变异，按位取反
对于个体\(x_i\)，计算对应适应度\(f(x_i)\to p_i=f(x_i)/\sum f(x_i)\)
轮盘赌基本思想：适应度越高的解，按道理越应该高概率的进行复制，且复制份数应该越多，我们生成随机数，判断该随机数所在区间，则该区间对应的个体发生复制
将上图的概率序列进行累加获得一个累加和序列，仅需要判断大于生成的随机数的最小索引即可，从而在进行随机复制片段选取时避免了
if-else类型的区间判断
算法分析¶
- 优点
- 参数少，具有理论优势
- 变异机制赋予了群体跳出局部极值的能力
- 缺点
- 容易陷入局部最优，算法实现较为繁琐
启发式算法本质¶
可以用一个公式来概括启发式算法
\[启发式算法=优化策略+保底机制\]
启发式算法的基本思想是择优进化，好的根据一定策略变得更好，差的更具一定策略向更好的方向发展，哪怕下一次的解不好，大不了就不更新，也就是所谓的保底机制
若没有任何策略，则随机生成一个初始解，每次循环再随机生成一个解，如果新的解比旧解好，就更新（择优进化），否则不更新
称之为随机大法(Stochastic Big)，
简称SB大法
案例实操¶
求解\(f(x)=abs(x\sin (x)\cos(2x)-2x\sin(3x)+3x\sin (4x))\)在[0,50]的最大值
