遗传算法的分析及其改进

　　1　引言

　　遗传算法是由美国控制论专家Holland提出的一种基于生物进化论及孟代尔基因遗传理论的搜索型优化算法。遗传算法就是模仿了生物的遗传、进化原理,并引用了随机统计理论而形成的。在求解过程中,遗传算法从一个初始变量群体开始,一代一代地寻找问题的最优解,直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代式算法。

　　2　遗传算法概述

　　遗传算法求解问题的一般过程为:①确定代表最优化问题可行解决方法的遗传基因的表示方案,即编码基因串。如编码为A=a1a2…aq,表示A为一个q维实向量。②产生一个由确定长度特征串组成的初始群体。确定群体规模N后,从可能的特征串空间中随机选取N个q维向量Ai, i=1,…,N,组成初始群体H0={A01,A02,…,A0n}。③由适应度函数F(Ati)求得群体中每个串的适应度值,其中t为进化代数。F(Ati)应能够评价特征串空间中任一q维向量的最优化程度。④应用体现“适者生存”原则的选择进化方案,即具有高适应度值的串应以更大的概率被选择繁殖到下一代中。

　　复制概率可选为: Pti=F(Ati) /∑Ni=1F(Ati)。由于高适应值串更容易被选中复制到下一代中,因此适应值较高的串将在下一代中产生更多的子代串,但复制无法探测到特征串空间中新的点。⑤为了在群体中引入新的串,对被选出的串以概率Pc、Pm执行交叉互换和突变。⑥反复迭代地执行步骤③、④、⑤直到满足停止准则,指定算法的执行结果。

　　3　遗传算法的数学机理

　　从上述内容可以看出,遗传算法的执行过程中包含了大量的随机性操作,因此有必要对其数学机理进行分析。为此首先引入“模式”这一概念。

　　3.1　模式定理[1]

　　将群体中的个体即基因串中的相似样板称为“模式”,模式表示基因串中某些特征位相同的结构。在二进制编码的串(即个体)中,模式是基于三字符集{0, 1, * }的字符串,符号*表示任意字符,或“0”或“1”。一个长度为L的串包含着2L个模式。遗传算法中串的运算实际上就是模式的运算。模式中包含两个重要的参数:模式阶和定义距。定义1　模式H中确定位置的个数成为模式H的模式阶,记做O(H)。

　　定义2　模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距,记做δ(H)。

　　对于某种模式,模式定理给出了在下一代群体中将会有多少个体与这种模式匹配。模式定理:在遗传算子选择、交叉、变异的作用下,具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将呈指数增长。用公式可表示为:

　　3.2　积木块假设