收稿日期:2004-10-29 通讯联系人 E-mail:zhongshounan@ yahoo. com .cn
基金项目:国家自然科学基金资助项目(70171016)
作者简介:游雪肖(1980-),女 ,硕士生,现从事遗传算法方面的研究 . E-mail:xuexiao80 @ sina . com
文章编号:1671-8836(2005)05-0542-05
十进制编码遗传算法的模式理论分析
游雪肖,钟守楠
(武汉大学 数学与统计学院,湖北 武汉 430072)
摘 要:基于单点交叉采用串表示,n(≥2)点交叉与均匀交叉采用环表示的方式,推导出十进制编码遗传算法
的模式理论,避免了二进制遗传算法模式理论中把交叉点的选取看作是相互独立的和忽视交叉对染色体生成作用
的两点不足,得出了对于任意进制的遗传算法,如果进化层次一致,那么运行机理相似的结论 .
关 键 词:遗传算法;模式定理;十进制编码
中图分类号:TP 301. 6 文献标识码:
A
遗传算法(Genetic Alg o rithm,GA)自上个世纪
60 年代由美国的 Holland 教授提出后,众多学者专
家在其机理研究方面做了大量的工作
[1 ~ 4]
. 其中
Holland 的模式理论定性地分析了遗传算法的运行
机理,奠定了遗传算法的理论基础 . 但二进制编码的
遗传算法模式理论中至少存在着两点不足:其一,把
交叉点位置的选取看作是独立的
[1 ,3 ,4]
,而事实上,
对多点交叉来说,在交叉算子的作用过程中,随机生
成的多个不同的交叉点,其位置的选取并不相互独
立;其二,仅考虑了交叉算子对染色体的破坏作用,
而忽略了对染色体的生成作用
[2 ,4]
. 目前,为解决二
进制遗传算法所不能避免的精度与效率的冲突,十
进制编码越来越多地被使用,但其相应的模式理论
却一直未能完善给出,难以对其进化机制和性能进
行精确分析 .本文借鉴了文献[2,3]的思想,在文献
[5]的基础上推导出了基于单点交叉、多点交叉和均
匀交叉
[6]
3 种不同交叉方式的十进制模式定理,该
模式定理避免了二进制编码遗传算法理论中的上述
不足,并且得出了对于任意进制的遗传算法,如果进
化层次一致,那么运行机理相似的结论 .
1
基本概念与定义
1 . 1 十进制编码遗传算法的基本概念与定义
对于十进制编码的遗传算法,文献[5]采用 2 元
符号基因表 S ={+ ,-}和 10 元数值基因表 V =
{0,1,2,3,4,5,6,7 ,8 ,9}以及小数点基因{·}对染色
体进行编码,每个染色体串可用带下标的字母表示,
其中下标表示位置顺序,例如,一个 10 位染色体串
A =+52 . 31 - 36 .55 可以表示为
A = a
1
a
2
a
3
· a
4
a
5
a
6
a
7
a
8
· a
9
a
10
其中 a
i
表示基因,a
i
∈ S∪ V ,·表示小数点基因 .
定义 1 模式就是一个相同的构型,它描述的
是一个染色体串的子集 . 这个集合中所有的染色体
串之间在某些位上相同 .考虑由 3 元符号基因表 S
+
={#}∪{+ ,-}={+ ,-,#}和 11 元数值基因表
V
+
= {}∪ V ={,0,1 ,2,3,4,5,6 ,7,8,9}表示
的模式,其中 # 和 代表不确定位基因,即 # 与 S
中的某一基因相对应,而 与 V 中的某一基因相对
应 .例如长 L 为 10 的模式 A =#5· # ·
55,上例 A =+52 . 31 - 36 .55 即为该模式的一个具
体表示 .
定义 2 模式的不变位是指模式中的小数点基
因,而模式的不变数则指模式中不变位的个数,记为
η(H).
定义 3 模式的确定位是指模式中出现的符号
基因表 S 和数值基因表 V 中的元素 .
注意模式的不变位与模式的确定位不同 .
定义 4 模式的阶是指模式中所含有的确定基
因位的个数,
记作 o(H).
定义 5 模式的定义距是指模式中从左到右除
小数点基因外第一个确定位到最后一个确定位之间