智能优化算法之遗传算法

ajlm

1、遗传算法概述

        遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方式。它是由美国的J.Holland传授1975年首先提出，其主要特点是直接对布局对象进行操作，不存在求导和函数持续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方式，能自动获取和指导优化的搜索空间，自适应地调整搜索标的目的，不需要确定的法则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号措置、自适应控制和人工生命等范围。它是现代有关智能计算中的关键技术之一。
2、遗传算法的基本操作

        遗传算法有三个基本操作： 选择（ Selection） 、 交叉（ Crossover） 和变异（ Mutation）
• 选择。 从当前种群中选出优良的个体， 使它们有机会作为父代种群为下一代种群进行更新迭代。 按照各个个体的适应度值， 按照必然的法则或方式从上一代群体中选择出一些优良的个体遗传到下一代种群中。 选择的依据是适应性强的个体为下一代贡献一个或多个儿女的概率大。
• 交叉。 通过交叉操作可以得到新一代个体， 新个体组合了父辈个体的特性。 将群体中的各个个体随机搭配成对， 对每一个个体， 以交叉概率交换它们之间的部门染色体。
• 变异。 对种群中的每一个个体， 以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。 同生物界中一样，变异发生的概率很低， 变异为新个体的发生提供了机会。
3、遗传算法的基本法式

        遗传算法的基本法式包含了编码、解码、初始种群生成、适应度计算、选择、交叉、变异
1)编码： GA在进行搜索之前先将解空间的解数据暗示成遗传空间的基因型串布局数据，
这些串布局数据的分歧组合便构成了分歧的点。
       遗传算法的搜索核心是编码方式（遗传算子）的选择，因此对于遗传算法的研究，此中最常见的内容与标的目的是遗传算子，遗传算子的选择多样性也导致了算法表示的多样性。
       常见的编码方式有：二进制编码、自然数编码、实数编码和树形编码等，常见的编码有二进制编码与自然数编码，很多实际问题如VRP调剂问题更多采用自然数编码。（编码方式不赘述，按照模型需要自行选择即可）
2）初始群体的生成：随机发生N个初始串布局数据， 每个串布局数据称为一个个体， N个个体构成了一个群体。
3)适应度评估：适应度表白个体或解的优劣性。 分歧的问题， 适应性函数的定义分歧。
4)选择：选择的目的是为了从当前群体中选出优良的个体。  选择浮现了达尔文的适者保留原则。
常见的选择方式有：
轮盘赌法Roulette-wheel selection：
       轮盘赌选择法是依据个体的适应度值计算每个个体在子代中呈现的概率，并按照此概率随机选择个体构成子代种群。轮盘赌选择策略的出发点是适应度值越好的个体被选择的概率越大。



轮盘赌选择

为了计算选择概率 P_{i} ，需要用到每个个体i的适应度值 f_{i} --->P_{i}=f_{i}/\sum_{j=1}^{N}{f_{i}}
从给定种群中选出M个个体就等价于旋转M次轮盘，在选择个体前实际上不必对种群中的个体进行排序。
        锦标赛选择（Tournament selection）
        在锦标赛选择中，从种群中随机采样s个个体（注意：采样是有放回的），然后选择最优的个体进入下一代，只有个体的适应度值优于其他s-1个竞争者时才能博得锦标赛。注意最差的个体永远不会幸存，而最优的个体在其参与的所有锦标赛中都能获胜。



锦标赛选则

     可以通过改变锦标赛的大小s来改变，对于较大的s值，弱者被选中的机会较小，常见的有二元锦标赛和三元锦标赛等。与适应度值比例选择对比，锦标赛选择由于缺乏随机噪声，同时锦标赛选择也和遗传算法适应度函数的尺度无关.
        随机遍历选择（Stochastic-universal selection）
        随机遍历选择（SUS）是一种按照给定概率以最小化波动概率的方式选择个体的方式。可以将其认为是一种轮盘赌游戏，在轮盘上有p个等间距的点进行旋转。SUS使用一个随机值在等间隔的空间间隔内选择来选择个体。对比力于适应度比例选择法，该方式中较劣个体也有很好的机会被选择，从而奖励了不公平性。该选择方式是由James Baker提出的，展示了其道理，此中n为要选择的个体数量。随机遍历采样保证了选出的子代，比轮盘赌法更加接近但愿得到的成果。



随机遍历选择

    精英选择（Elite selection）
        精英选择将一小部门最优的候选解，原封不动的复制到下一代中，这会对性能发生巨大的影响，因为这保证了GA不会浪费时间从头发现以前拒绝的部门解。通过精英主义被保留下来的个体仍然有资格被选为下一代的父代。精英主义也与记忆有关：记住目前找到的最优解。不外精英主义的问题在于会导致GA收敛到局部最优，所以纯粹的精英主义是一场通向比来局部最优的竞争。
5)交叉：交叉操作是遗传算法中最主要的遗传操作。 通过交叉操作可以得到新一代个体，
新个体组合了其父辈个体的特性。
常见的交叉方式有：
       单点交叉（Single-point crossover）
        单点交叉通过拔取两条染色体，在随机选择的位置点长进行分割并交换右侧的部门，从而得到两个分歧的子染色体。



单点交叉

        两点交叉（Two-points crossover）
        两点交叉是指在个体染色体中随机设置了两个交叉点，然后再进行部门基因交换。两点交叉的具体操作过程是：

• 在彼此配对的两个个体编码串中随机设置两个交叉点；
  
• 交换两个个体在所设定的两个交叉点之间的部门染色体。
  

部门匹配交叉（Partially-matched crossover，PMX）        部门匹配交叉（Partially-matched crossover，PMX）
        部门匹配交叉保证了每个染色体中的基因仅呈现一次，通过该交叉策略在一个染色体中不会呈现反复的基因，所以PMX经常用于旅行商（TSP）或其他排序问题编码。
        PMX类似于两点交叉，通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体，个别基因会呈现反复的情况，为了修复染色体，可以在交叉区域内成立每个染色体的匹配关系，然后在交叉区域外对反复基因应用此匹配关系就可以消除冲突。
Step1：随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置不异）。


Step2：交换这两组基因的位置。


Step3：做冲突检测，按照交换的两组基因成立一个映射关系，如图所示，以7-5-2这一映射关系为例，可以看到第二步成果中子代1存在两个基因7，这时将其通过映射关系改变为基因2，以此类推至没有冲突为止。最后所有冲突的基因城市颠末映射，保证形成的新一对子代基因无冲突。


最终成果为：


6)变异：变异首先在群体中随机选择一个个体， 对于选中的个体以必然的概率随机地改变
串布局数据中某个串的值。
整体的流程如下：


4、案例分析

        案例后续讲述
TSP优化
        遗传算法优化神经网络
5、遗传算法特点

相对于传统算法而言，遗传算法有以下突出特点：
长处：
        1）. 可适用于灰箱甚至黑箱问题；
        2）. 搜索从群体出发，具有潜在的并行性；
        3）. 搜索使用评价函数（适应度函数）启发，过程简单；
        4）. 收敛性较强。
        5）. 具有可扩展性，容易与其他算法（粒子群、模拟退火等）结合。
不足:
        1）. 算法参数的选择严重影响解的品质,参数的选择大部门是依靠经验；
        2）. 遗传算法的本质是随机性搜索，不能保证所得解为全局最优解；
        3）.在措置具有多个最优解的多峰问题时容易陷入局部最小值而遏制搜索，造成早熟问题，无法达到全局最优。