现代智能优化算法：遗传算法（1）综述

jquave

由于遗传算法框架简单，便于实现，而其全部精髓都在于”问题形式化 编码设计算子调整（俗称调参）结果展示“整条工作流程的工程实现上，而无代码不知乎，因此本文将以简短之口舌快速回顾一下遗传算法的基本知识。
遗传算法

遗传算法充分利用了“物竞天择，适者生存”的原理，是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。算法的思想是，对于某一类优化问题，也许我们无法给出最优解的性质，但是我们可以找到一种适值函数来对解进行评估，迭代优化适应度函数，适应度函数的优化与解的优化单方向对应。
对于一个已经形式化的最优化问题，适应度函数可以是目标函数本身，也可以是标定的目标函数，见“选择压力”章节。
遗传算法的基本原理

根据问题的目标函数构造一个适值函数，对于一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传运算、选择，多代繁殖，获得适应值最好的个体作为问题的最优解，这是遗传算法的基本思想和算法流程。遗传算法的基本流程概括如下：

• 产生一个初始种群
  
• 根据问题的目标函数构造适值函数
  

适值函数：目标函数，产生适值函数的过程称为标定，即转化为如下的优化问题：

或者

• 根据适应值的好坏不断选择和繁殖：适应值大的个体，基因容易被遗传到下一代
  
• 若干代后得到适应值最好的个体即为最优解
  

构成要素

• 种群和种群大小：每个个体是一个染色体，每个染色体对应着一个问题的一个解，一般来说，群体规模越大，遗传算法效果越好
  
• 编码方法：基因表达方法
  
  
  
  • 二进制编码：
    染色体
    染色体每一位是一个基因，n称为染色体的长度
    二进制编码是适用于以下三种情况：
    
    
    
    • 背包问题
      
    • 实优化问题
      
    • 指派问题
      
    
    
  • 实数编码
    
  • 整数编码：
    整数编码适合离散优化问题，常用的一类编码有顺序编码
    
  
  
• 遗传算子
  
  
  
  • 交叉（Crossover）
    
    
    
    • 交叉率（）：提高交叉率会达到更大的解空间，减小停在非最优解上的机会，但是交叉率太高会因为过多搜索不必要的解空间而耗费时间
      
    • 变异率（）：变异率控制新基因导入种群的比例，变异率过高会使得后代有可能失去
      
    • 交叉方法：
      
      
      
      • 单切点交叉：随机选择一个切点，切点两侧分别看为两个子串，交换之
        
      • 双切点交叉：随机选择两个切点，交换两个切点之间的子串
        
      
      
    
    
  • 变异（Mutation）
    变异方法：单点突变，随机选择编码中某个位点，改变该位点的值
    
  
  
• 选择策略：从种群中选择适应值高的个体以生成交配池的过程
  

正比选择策略，即每个个体被选中遗传运算的概率为该个体的适应值和种群中个体适应值总和的比例，种群规模为，得到选择概率 后，按照旋轮法（Roulette Wheel，轮盘赌）实现选择操作：

   
共转轮次，每次转轮时，随机产生，当时，选择个体.


其他额外的一些选择操作，具体问题具体分析：

• 随机遍历抽样
  
• 局部选择
  
• 截断选择
  
• 锦标赛选择
  

选择操作的作用提高了群体适应度，降低了群体多样性

• 停止准则
  
  
  
  • 最大迭代步数准则
    
  • 收敛准则
    
  
  

算法流程



一图胜千言。
解空间与编码空间转换



遗传算法的前处理将初始解进行编码，算法本质是在编码空间进行遗传运算（调用遗传算子），而进行解码并在解空间调用适应度函数为编码池的编码进行评估，运行选择策略，最终开启下一轮循环，直到达成停止准则。
遗传算法收敛性理论解释：模版理论

定义：

• 模版是若干位取确定值，其他位不确定的一类个体的总称，记为S
  
• 模版长度定义为模版中从左到右第一个确定的位与最后一个确定的位之间的长度（算头不算尾）
  
• 模版的阶数定义为模版中所含有的确定基因位的个数
  
• 阶数为的模版的个体总数为
  

模版理论：
引入了模版理论后，遗传算法的群体进化过程可以看作通过选择、交叉、变异等遗传算子的运算来不断寻找好的模版的过程。
引理1：
在正比选择（轮盘赌选择）下，模版S在代的期望个体数为 ，其中是代模版中所有个体的适应值的均值与种群中所有个体的适应值均值的比。
引理2：（单点交叉）
第代以概率做交叉，对长度为 的模版中的个体，则在第代中该个体仍然为中个体的概率的下界为：

，其中为第t代个体为模版S的概率
引理3:（变异）
若代以概率做变异，对于一个阶数为的模版S重点额个体，则在t+1代仍为S的概率的下界为：


主定理（模版定理）：
第t代以概率和发生交叉和变异的时候，长度为，阶数为，适应值均值为的模版S在第t+1代的期望的个体数的下界为：


如果：


则随着代数t增加而增加。
改进与变形

编码方法

• 顺序编码（1到n的自然数编码）
  
• 实数编码，适合于实优化问题
  
• 整数编码，适合于新产品投入、时间优化和伙伴挑选问题
  

遗传运算中的问题

• 顺序编码的合法性修复
  

• 交叉修复策略
  
  
  
  • 部分映射交叉（PMX）
    
  • 顺序交叉（OX）
    
  • 循环交叉（CX）
    
  
  
• 变异修复策略
  
  
  
  • 换位变异
    
  • 移位变异
    
  
  

2. 实数编码合法性修复

• 凸组合交叉
  

适值函数的标定

通过标定使得目标函数映射为适值函数
定义：选择压力
选择压力指种群中好、坏个体被选中的概率差，如果差较大则选择压力大，通过调节选择压力的大小可以实现遗传算法中局部搜索和广域搜索的调节
局部搜索、广域搜索与选择压力的关系
局部搜索是针对一个较小的区域进行搜索，致力于找到更好、更精确的解，而广域搜索是进行大面积的搜索，希望找到较好的解存在的区域，显然，局部搜索和广域搜索是遗传算法的一对矛盾
适值函数的标定方法

• 线性标定：
  
• 动态线性标定：在迭代的过程中，参数随着迭代次数的增加而变化就得到了动态线性标定。
  
• 幂律标定：，其中参数可以用来调节选择压力，选择压力小，时，将成为随机搜索，缺点是计算耗费时间
  
• 对数标定：
  
• 指数标定：
  
• 窗口技术：，其中是窗口大小，是前代中的最小目标值
  
• 正规化技术：
  

最大化标定：
最小化标定：
其中
选择策略

• 截断选择：排序后选择最优的前T个个体，让每个有的选择概率，即平均每个得到的概率被选择
  
• 顺序选择：对个个体进行排序，定义最好的个体的选择概率为，则个体的选择概率为
  

概率归一化：当NP有限的时候，，令，其中

• 正比选择（轮盘赌选择）
  

停止准则

• 最大代数
  
• 收敛准则：
  

高级基因操作

• 倒位操作
  

在染色体中随机指定两个基因的位置为倒位点，以倒位概率顺序翻转两个倒位点之间的基因

• 显性操作
  

下一篇讲一讲如何构造一个优化问题的维度适应遗传算法框架，要上python辣。
Reference：
智能优化方法，汪定伟等，高等教育出版社，2007.