一种使用长定义距模式的遗传算法

基本遗传算法(SGA) 和模式定理都是基于二进制编码,关于选择、交叉和变异算子的,但是交叉算子对模式的破坏性很大,尤其对定义距较长的模式,而且关于交叉算子的重组功能模式定理却没有给出清晰的解释。设计了针对长定义距模式的再生算子,并提出采用再生算子代替交叉算子的长

http://doc.guandang.net

-1- 一种使用长定义距模式的遗传算法

赖志柱

重庆大学数理学院，重庆 (400045)

E-mail ：laizhizhucqu@http://doc.guandang.net

摘 要：基本遗传算法(SGA) 和模式定理都是基于二进制编码，关于选择、交叉和变异算子的，但是交叉算子对模式的破坏性很大，尤其对定义距较长的模式，而且关于交叉算子的重组功能模式定理却没有给出清晰的解释。设计了针对长定义距模式的再生算子，并提出采用再生算子代替交叉算子的长模式遗传算法，仿真结果表明了再生算子的有效性。 关键词：遗传算法，模式定理，模式

中图分类号：TP301.6 文献标志码：A

1. 引言

遗传算法(Genetic Algorithms ，GA)最早由美国Michigan 大学的Holland 教授提出，起源于20世纪60年代对自然和人工自适应系统的研究[1]，它是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。

模式定理[1,2,3,4,5,6]表明：对于低阶、短定义距和平均适应度较高的模式在遗传算子作用下将按指数规律增长；而建筑模块假设说明了有效基因之间的继承和重组，两者构成了关于GA 进化过程能够发现最优解的一个充分条件。

文献[7]指出遗传算法通过处理群体中的有限个体内在地处理了大量模式，从而能在短时间内完成大面积搜索；这种隐并行性是遗传算法的一个重要特点，也是其相对其它优化算法的优势所在。但是，对隐并行性的讨论仅指出遗传算法处理模式的能力很强，并没有特别指出这些模式的阶数高低和定义距的长短对算法处理模式能力的影响。事实上，模式的阶数高低和定义距的长短对遗传算法能否有效应用影响比较大，阶数越高，定义距越长，模式处理能力越弱。准确地说是遗传算法处理低阶、短定义距模式的能力较强，处理高阶、长定义距模式的能力则相对较弱；而不是一般地对所有模式的处理能力都强[8]。

对于那些定义距长的模式，因它们在交叉算子的作用下最容易被破坏，故而往往难以有再生存的机会。可以预料这种平均适应度高但定义距长的模式最可能接近于全局最优解，而它们往往可以保持群体中个体的多样性；如果能将它们转换为低阶、平均适应度高且定义距短的模式，则有利于GA 搜索到全局最优解，同时也有利于提高收敛速度[9]。

另一方面，模式的定义距的长短应该是概率均匀的，而交叉算子可以看作是专门为短定义距模式服务的，将长定义距模式向短定义距模式转换是一个可行办法，当然设计一种专门针对长定义距模式的遗传算子也是可行的。

2. 算法设计

基于对自然界中生物遗传进化与生理机制的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。由不同的编码方法和不同的遗传算子就构成不同的遗传算法，下面将设计一种所谓的再生算子和用再生算子代替交叉算子的遗传算法。

2.1 再生算子的设计

基本遗传算法(SGA) 和模式定理都是基于二进制编码,关于选择、交叉和变异算子的,但是交叉算子对模式的破坏性很大,尤其对定义距较长的模式,而且关于交叉算子的重组功能模式定理却没有给出清晰的解释。设计了针对长定义距模式的再生算子,并提出采用再生算子代替交叉算子的长

http://doc.guandang.net

-2- 设有两个待处理的染色体为X =121x x x x n n L ?，Y =121y y y y n n L ?，则再生后的染色体'X ，'Y 按下面的规则生成：

'i x =???≠=i i i

i i y x random y x x i )2( ???

≠==i i i i i i y x random y x y y )2(' (1≤≤i n) 其中random(2)表示随机生成0或者1，'X ='1'2'1'x x x x n n L ?，'Y ＝ '1'2'1'y y y y n n L ?。

另外，为了与交叉算子比较，同样为再生算子设定一个概率pr ，即两个被选中的染色体参加再生算子作用的概率，并使pr 与交叉概率pc 相等。

2.2 本文采用的选择策略

适应值比例选择：适应值比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应值和群体平均适应值的比例有关，本文采用轮盘赌(roulette wheel)方式实现。

2.3 算法的工作流程

迭代开始(iteration)：t=0

初始化(initialize)：P(0)={)0(,),0(),0(21n a a a L }

适应性评价(evaluate)：P(0)={))0((,)),0(()),0((21n a f a f a f L }

while(循环) T t ≤ do

轮盘赌选择(select) ：P’(t)=s(P(t))

再生：P’’(t)=r(P’(t)，pr)

变异(mutation)：P’’’(t)=m(P’’(t)，p m )

新一代群体：P(t+1)=P’’’(t)，t=t+1

适应值评价(evaluate)：P(t+1)={))1((,)),1(()),1((21+++t a f t a f t a f n L }

结束(end do)

由于上述改进的遗传算法没有使用交叉算子而是改用再生算子，而再生算子是针对长定义距模式的，因此称以上改进的算法为长模式遗传算法(Long Schema Genetic Algorithms ,LSGA)

3. 算例

为了验证本文设计的再生算子的有效性，我们选择了六峰值驼背函数(Six-hump Camel Back Function)进行测试。本实验测试程序是作者用C++编程语言开发的。

六峰值驼背函数：

22242

)44(3

1.24(),(y y xy x x x y x f +?+++?= 33≤≤?x 22≤≤?y 六峰值驼背函数有六个局部极小点[4]，其中)7126.0,0898.0(?和)7126.0,0898.0(?为全局最小点，最小值为031628.1?。

对于上述测试函数，采用基本遗传算法(Simple Genetic Algorithm, SGA)和长模式遗传算法(LSGA)进行优化计算500次。每个变量用10位长的二进制位串来表示，即个体的基因型为20位长的二进制位串。遗传算法的运行参数分别为：群体大小为80，终止进化代数为200，

基本遗传算法(SGA) 和模式定理都是基于二进制编码,关于选择、交叉和变异算子的,但是交叉算子对模式的破坏性很大,尤其对定义距较长的模式,而且关于交叉算子的重组功能模式定理却没有给出清晰的解释。设计了针对长定义距模式的再生算子,并提出采用再生算子代替交叉算子的长

http://doc.guandang.net

-3- 交叉概率和再生概率都是0.6，变异概率为0.001。另外为增强算法的收敛性，SGA 和LSGA 都采用了精英保留策略。下表为仿真结果，其中算法成功是指算法结果满足err f f best <?*，*f 表示全局最优解，best f 表示算法所得到的最优解，err=0.001。

表1 六峰值驼背函数的仿真结果

算法 成功次数成功率平均进化代数

SGA 358

71.6% 115 LSGA 394 78.8% 116

4. 讨论

从上表可以看到，LSGA 的成功率比SGA 大，而平均进化代数几乎没有相差，这表明本文提出的采用长定义距模式的再生算子用来代替传统的交叉算子有一定的效果，但本文只是初步工作，尚有很多问题有待解决，比如：再生算子的理论分析，不同的选择策略或不同的参数选择对再生算子的性能影响，再生算子和交叉算子组合运用效果如何以及算例有待丰富等等。