![](https://csdnimg.cn/release/download_crawler_static/18895698/bg1.jpg)
ISSN
1000-0054
清华大学学报(自然科学版)
2000
年第
40
卷第
10
期
33/33
125-128
。、
I
11-2223/N
JTsinghuaUniv(Sci&Tech)
,
2000
,
Vo
1.
40
,
No.l0
基于二叉树结构编码的遗传算法*
葛志远,王永县,
南兰,刘请
(1育华大学经济管理学院,北京
100084)
文
摘·为对树形结构编码的遗传算法进行更深入的研究,
提出了基于二叉树结构编码的遗传算法的一般形式,并以函
数模型的波兰表达式为例详细描述了二叉树结构编码的遗
传算法的算子。重点分析了二叉树结构编码的遗传算法的收
敛性。在实际的研究中,对二叉树结构进行空间深度限制后,
其遗传算法可以用一个有限状态空间的
M
arkov
链来描述。
在此基础上,证明了二叉树结构编码的遗传算法在对选择算
子进行改进后依概率收敛到最优解。
关键词遗传算法,二叉树结构
M
arkov
链
中图分类号
F
224
文献标识码
A
文章编号
1000-0054(2000)10-0125-04
遗传算法是近年来迅速发展起来的一种高效的
优化算法,在科研与实际问题中的应用越来越广泛。
当前在采用二进制编码的简单遗传算法方面的研究
相对比较成熟,然而由此得出的一些用来解释遗传
算法的有效性的基本定理(如模式定理)对其他一些
编码不一定适用
[1]
。实数编码主要适用于求解高维
或复杂的优化问题,采用实数编码的遗传算法己被
证明了其收敛性。还有许多问题的自然表示是树或
者图的形式,尤其是二叉树,这类问题的表示,采用
二叉树编码比较方便[川。在采用结构编码的遗传算
法中,由于其编码形式的不同,二进制编码和实数编
码的遗传算法分析结果并不能直接推广到这类问
题。本文主要利用
M
arkov
链讨论解决这类问题的
二叉树结构编码遗传算法的收敛性。
1
问题描述
设二叉树的结点元素集为
{xl
x
ξ
剖,其中
x=
收稿日期
2000-0
卜
10
作者简介·葛志远
(1974
寸,男(汉),湖南,博士研
究生。
*基金项目·国家"九五"重点科技攻关项目(
96-920-35-
02)
{X1
,
X2
,...,
Xwl
让町,
x
中的元素可以是符号或者
变量,也可以是确定的数值。由此组成的所有树的集
合构成一个树的集合
L
又若
s
是实有限空间的子
集
,
P
是从
r
到
s
上的一个映射。
问题1:寻找一个确定的二叉树「
ξr
,使得
对任意
TE
r
有
P(
T'
) <
P(
T)
成立.
在这类问题中,用二叉树结构未定义问题,这是
因为二叉树的每个结点最多只能有两个子树,处理
起来很方便。实际上每棵树都可以通过下述转换方
法将其转换成二叉树
1
)在兄弟问加一条连线
2)
对每个结点,除了其最左的孩子之外,抹掉该结点与
其余孩子之间的连线
3)
以树的根为轴线,将整棵
树顺时针转
45
0
,由于每棵树均可通过简单的变换
变成二叉树,因此,本文仅对二叉树结构下的遗传算
法进行分析。
2
二义树结构编码的遗传算法
与二进制不同,二叉树结构编码的遗传算法是
在结构空间内进行编码。应用遗传规划解决大型的
复杂问题的时候,如果不对二叉树结构的深度进行
限制,编码的结构空间将是无限的,这会使得搜索最
优解变得相当困难,也增加对算法分析的难度。因
此,在实际应用中可以限定二叉树结构的深度,使其
结构空间被限定在一个有限的范围内,下面的分析
都是基于这一点进行的。
2. 1
交叉算子
在交叉算于中采用结点交叉的策略,将二叉树
的子树作为一个整体进行交叉,即在两个父代个体
中独立随机设定各自的交叉点,实行交叉时,两个个
体以其交叉点作为根节点的部分子树进行交叉互
换,生成两个新个体,例如图
I
中所示的两个父代通
过交叉算子获得两个子代。