AI算法之遗传算法

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出，该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
 
遗传算法的起源可追溯到20世纪60年代初期。1967年，美国密歇根大学J． Holland教授的学生 Bagley在他的博士论文中首次提出了遗传算法这一术语，并讨论了遗传算法在博弈中的应用，但早期研究缺乏带有指导性的理论和计算工具的开拓。1975年， J． Holland等提出了对遗传算法理论研究极为重要的模式理论，出版了专著《自然系统和人工系统的适配》，在书中系统阐述了遗传算法的基本理论和方法，推动了遗传算法的发展。20世纪80年代后，遗传算法进入兴盛发展时期，被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。
 
编码

由于遗传算法不能直接处理问题空间的参数，因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码，也可以称作（问题的）表示（representation）。
 
评估编码策略常采用以下3个规范：
a）完备性（completeness）：问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）表现。
b）健全性（soundness）： GA空间中的染色体能对应所有问题空间中的候选解。
c）非冗余性（nonredundancy）：染色体和候选解一一对应。
 
适应度函数

进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。
 
遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。
 
适应度函数的设计主要满足以下条件：

a）单值、连续、非负、最大化
b） 合理、一致性
c）计算量小
d）通用性强。
 
在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。
 
初始群体选取
遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略：
a）根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。
b）先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。
 
运算过程

遗传算法的基本运算过程如下：

（1）初始化：设置进化代数计数器t＝0，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。
（2）个体评价：计算群体P（t）中各个个体的适应度。
（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t＋1）。
（6）终止条件判断：若t＝T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
遗传操作包括以下三个基本遗传算子（genetic operator）：选择（selection）；交叉（crossover）；变异（mutation）。
 
选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproduction operator）。选择的目的是把优化的个体（或解）直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。
 
交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组（加上变异）。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
 
变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：
a）实值变异。
b）二进制变异。
 
一般来说，变异算子操作的基本步骤如下：

a）对群中所有个体以事先设定的变异概率判断是否进行变异
b）对进行变异的个体随机选择变异位进行变异。
 
遗传算法引入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。
 
终止条件

当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100－500代。