智能计算——遗传算法

基本概念

  • 种群:种群是指用遗传算法求解问题时,初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。
  • 个体:个体是指种群中的单个元素,它通常由一个用于描述其基本遗传结构的数据结构来表示。例如,可以用0、1组成的长度为l的串来表示个体。
  • 染色体:染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因,染色体上由若干个基因构成的一个有效信息段称为基因组
  • 适应度函数:适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据
  • 遗传操作:遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下三种基本形式:
    • 选择(Selection)
    • 交叉(Crossover)
    • 变异(Mutation) :对选中个体的染色体中的某些基因进行变动,以形成新的个体,它可增强种群的多样性

算法流程

遗传编码

  • 二进制编码:二进制编码是将原问题的结构变换为染色体的位串结构

    对应范围[𝒖_𝒎𝒊𝒏, 𝒖_𝒎𝒂𝒙],精度为𝝈,确定需要多少位的二进制编码串能够覆盖范围内的所有数

  • 格雷编码:对二进制编码进行变换后所得到的一种编码方法

  • 实数编码:(高位或复杂优化问题)若干个实数表示一个个体,然后在实数空间进行遗传操作

种群设定

初始种群的产生:随机产生一定数目的个体,从中挑选最好的个体加到初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规模。

种群规模的确定

  • 群体规模太小,遗传算法的优化性能不太好,易陷入局部最优解。
  • 群体规模太大,计算复杂。
  • 一般取 20-100

适应度函数

将目标函数映射成适应度函数:最大化问题取目标函数值,最小化问题取倒数。

欺骗问题:将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作。

  • 超级个体:适应度远远大于其它 => 过早收敛
  • 平均适应度接近最优适应值 => 停滞现象

适应度函数的尺度变换(fitness scaling)或者定标:对适应度函数值域的某种映射变换。

选择

  • 适者生存:适应度越高,被选择的概率越大
  • 为了避免过快收敛到局部最优解,还需要维持种群的多样性
  1. 排序方法:计算每个个体的适应度后,根据适应度大小顺序对群体中个体进行排序,然后把事先设计好的概率按排序分配给个体,作为各自的选择概率。
  2. 轮盘赌选择
    • 按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例。
    • 产生一个随机数,它落入转盘的哪个区域就选择相应的个体交叉。
  3. 锦标赛选择方法:从群体中随机选择k个个体,将其中适应度最高的个体保存到下一代。这一过程反复执行,直到保存到下一代的个体数达到预先设定的数量为止。
  4. 随机竞争方法:每次按赌轮选择方法选取一对个体,然后让这两个个体进行竞争,适应度高者获胜。如此反复,直到选满为止。
  5. 最佳个体保存方法:把群体中适应度最高的个体不进行交叉而直接复制到下一代中,保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。

交叉

  • 二进制交叉:二进制编码情况下所采用的交叉操作
    • 单点交叉:在两个父代个体的编码串中随机设定一个交叉点,然后对这两个父代个体交叉点前面或后面部分的基因进行交换
    • 两点交叉:先在两个父代个体的编码串中随机设定两个交叉点,然后再按这两个交叉点进行部分基因交换,生成子代中的两个新的个体
    • 多点交叉
    • 均匀交叉:随机生成一个与父串具有相同长度,并被称为交叉模版(或交叉掩码)的二进制串,然后再利用该模版对两个父串进行交叉,即将模版中1对应的位进行交换,而0对应的位不交换,依此生成子代中的两个新的个体。
  • 实值交叉:在实数编码情况下所采用的交叉操作
    • 离散交叉:随机选择对第k个分量以后的所有分量进行交叉
    • 算术交叉:两个个体的线性组合而产生出两个新的个体

交叉概率:0.25-1.00

  • 过高:高性能模式遭遇破坏的可能性大
  • 过低:开辟新的搜索区域能力变低

变异

  • 二进制变异:先随机地产生一个变异位,然后将该变异位置上的基因值由“0”变为“1”,或由“1”变为“0”,产生一个新的个体。
  • 实值变异:用另外一个在规定范围内的随机实数去替换原变异位置上的基因值,产生一个新的个体。
    • 基于位置的变异方法:先随机地产生两个变异位置,然后将第二个变异位置上的基因移动到第一个变异位置的前面。
    • 基于次序的变异:先随机地产生两个变异位置,然后交换这两个变异位置上的基因。

变异概率:0.001左右

变异是辅助性的搜索,变异的概率不能太大,以防止一些重要的基因丢失,而且变异太大会导致算法趋于随机搜索

机器学习