十进制遗传算法的收敛性分析

第21卷　第1期2001年3月

淮南工业学院学报

JOURNALOFHUAINAN

INSTITUTEOFTECHNOLOGY.21　№.1Vol

MAR.2001

十进制遗传算法的收敛性分析

黄友锐

(淮南工业学院电气工程系,安徽　淮南　232001)

摘　要:十进制遗传算法是一种模拟生物进化的最优化搜索方法,由于其稳定性好、不需要计算目标函数的导数和能处理多维数值问题,十进制遗传算法在科学研究和工程技术中得到了广泛运用。通过对十进制遗传算法的收敛性进行分析,为改进十进制遗传算法奠定了理论基础。

关键词:十进制遗传算法;收敛性;马尔柯夫链

中图分类号:TP18　　文献标识码:A　　文章编号:167120932(2001)0120028204

1　引言

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索策略算法,由美国Holland教授提出,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域,是21世纪有关智能计算中的关键技术之一。应该指出的是,遗传算法虽然可以实现均衡的搜索,并且在许多复杂问题的求解中往往能得到满意的结果,但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认为,标准遗传算法并不保证全局最优收敛,但是,在一定的约束条件下,遗传算法可以实现这一点。下面将对在科学研究和工程技术中得到广泛运用的十进制遗传算法的收敛性进行分析。

…,Im为闭区间,即是各个参数的取值范围。不妨设Ik=[LBk,UBk],k=1,2,…,m。2.2　十进制遗传算法的具体过程

与二进制遗传算法类似,十进制遗传算法也相当于对问题的解空间8进行了某种精度的编码,其精度是与编码长度有直接关系。例如要求计算出的xi要精确到10-8,即在计算机内存储一个浮点数,那么这个参数的编码点数为(UBk-LBk) 10-8,即Ik=[LBk,UBk]被宽度为10-8的区间划分

了,出现了(UBk-LBk) 10-8个分割点,对应每个分割点的是它在坐标轴上的浮点表示。(此处并非遵循二进制从0编到2l,而是做了个平移,第j个编码点经过平移后为j×10-8+LBk,由于这个对应是一一的,所以不妨使用浮点数来表示,从而免

)去了编码和解码的过程。

同样的,对其它的参数进行类似的编码过程,这样就实现了对原问题的编码过程。x](x1,x2,…,xm),这里xk表示具有适当精度的参数值(即一

种编码)。为以后叙述方便,将其看作xk的一种数据的存储形式,只不过与xk有一定的舍入误差,记第k维参数的精度记为Ε下面讨论几个重要遗传k。算子在十进制遗传算法的具体实现形式。

2.2.1　交叉　在交叉算子中摒弃了原二进制算法

→

2　十进制遗传算法的基本过程

2.1　问题的数学模型

为了讨论方便,假设所要求的问题是一个多维变量的优化问题,如下面这个简化问题,其基本形式为:

maxf(x)

→

→

x∈R

→

其中:f(x):8→R,8=I1×I2×…ImΑR,I1,I2,

m

中的单点交叉策略,而采取在参数们的间隔中选取交叉点。例如:

收稿日期:2000—11—20

作者简介:黄友锐(1971—),男,安徽长丰人,博士,从事电子信息方面的教学和科研工作。

28

第1页下一页