马尔可夫模型在遗传算法中的应用

于景茹 李保华 赵澄东

摘 要：本文介绍遗传算法的基本思想，提出了遗传算法的两个重要的参数交叉率和变异率，并利用马尔科夫模型对其进行了分析。

关键词：遗传算法；交叉率；变异率；马尔可夫模型

DOI：10.16640/j.cnki.37-1222/t.2016.07.241

1 引言

遗传算法满足有限马尔可夫链的基本特征，具有齐次性，存在极限概率分布。将马尔可夫模型用于遗算法，已有相关的研究。例如，在1987年，Goldberg和Segrest[1]运用有限马尔可夫链理论对遗传算法进行了收敛性分析，Rudolph用齐次有限马尔可夫链证明了带有选择、交叉和变异操作的标准遗传算法收敛不到全局最优解，但是如果让每一代群体中的最佳个体不参加交叉与变异操作而直接保留到子代，那么遗传算法是收敛的。

本文主要是在学习了随机数学和遗传算法的基础上，在查阅大量相关资料的前提下，对马尔可夫模型在遗传算法中的应用做了一个阐述，通过这样一个学习与总结的过程，促使本人对遗传算法和马尔可夫模型有一个更为深刻的认识。

2 遗传算法的基本思想

遗传算法是基于达尔文的自然选择和进化原理。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有某种特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因性）是某种基因组合，它决定了个体的形状的外部表现。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行交叉和变异，产生新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应域环境。经过若干代的遗传后， 就能够进行适应度最大的个体的搜索， 从而完成最优化问题的最优解的求解。

基本的遗传操作是由选择、交叉、变异三个遗传算子来进行的。选择是指根据预先定义的适应度函数来随机的选择合适的个体进行复制， 并将其拷贝到下一代；交叉是指在繁殖下一代时两个同源染色体之间通过交叉重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串交叉组合形成两个新的染色体。这个过程成为基因重组，俗称杂交。变异是指在细胞进行复制时，可能易很小的概率产生某些辅助差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体产生新的性状。代中选择两个个体并在它们之间进行遗传物质的交换；变异是随便的改变包含在种群个体中的信息，从而增强种群的多样性。

我们可以认为进化是探求更好的串（染色体）的过程。交叉和变异在探求的过程中承担着一个导向的任务。其中交叉率х就是一个重要的因素，两个串以一定的概率χ进行交叉。每对交叉的串是根据它们的适应度进行随意选择的。一般来讲，交叉算子结合了两个串的优势从寻求更优的结果。

变异算子采用变异率μ扮演多样性的角色。在均衡的变异中，变异在串的每一位上都进行操作，而每一位以概率μ进行变异。变异率通常设为很低，例如0.1%。如果某一位发生了变异，那么该位就发生了改变，从0变为1或者从1变为0。变异操作的目的是为了增加新的串。

3 遗传算法的马尔可夫模型

遗传算法是不断重复杂交、变异和选择的过程。每一种遗传机制都与当前种群状态有关，而与以前的种群状态无关。因此遗传算法是一个马尔可夫链。Vose于1990年第一次准确的提出了简单遗传算法的模型。1999年Vose[5]再次对其做了一定的扩展。