资源描述：
《论文十进制遗传算法的收敛性分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第21卷 第1期淮南工业学院学报Vol.21 №.12001年3月JOURNALOFHUAINANINSTITUTEOFTECHNOLOGYMAR.2001十进制遗传算法的收敛性分析黄友锐(淮南工业学院电气工程系,安徽 淮南 232001)摘 要:十进制遗传算法是一种模拟生物进化的最优化搜索方法,由于其稳定性好、不需要计算目标函数的导数和能处理多维数值问题,十进制遗传算法在科学研究和工程技术中得到了广泛运用。通过对十进制遗传算法的收敛性进行分析,为改进十进制遗传算法奠定了理论基础。关键词:十进制遗传算法;收敛性;马尔柯夫链中图分类号:TP18文献标识码:A 文章编号
2、:167120932(2001)0120028204⋯,Im为闭区间,即是各个参数的取值范围。不妨1 引言设Ik=[LBk,UBk],k=1,2,⋯,m。遗传算法是一类借鉴生物界自然选择和自然2.2 十进制遗传算法的具体过程遗传机制的随机化搜索策略算法,由美国Holland与二进制遗传算法类似,十进制遗传算法也相教授提出,其主要特点是群体搜索策略和群体中个当于对问题的解空间8进行了某种精度的编码,体之间的信息交换,搜索不依赖于梯度信息。可广其精度是与编码长度有直接关系。例如要求计算出泛用于组合优化、机器学习、自适应控制、规划设计-8的xi要精确到10,即在计算机内存储
3、一个浮点和人工生命等领域,是21世纪有关智能计算中的数,那么这个参数的编码点数为(UBk-LBk)ö关键技术之一。应该指出的是,遗传算法虽然可以10-8,即I-8k=[LBk,UBk]被宽度为10的区间划分实现均衡的搜索,并且在许多复杂问题的求解中往了,出现了(UB-8k-LBk)ö10个分割点,对应每个往能得到满意的结果,但是该算法的全局优化收敛分割点的是它在坐标轴上的浮点表示。(此处并非性的理论分析尚待解决。目前普遍认为,标准遗传遵循二进制从0编到2l,而是做了个平移,第j个算法并不保证全局最优收敛,但是,在一定的约束-8编码点经过平移后为j×10+LBk,由于这
4、个对条件下,遗传算法可以实现这一点。下面将对在科应是一一的,所以不妨使用浮点数来表示,从而免学研究和工程技术中得到广泛运用的十进制遗传去了编码和解码的过程。)算法的收敛性进行分析。同样的,对其它的参数进行类似的编码过程,→2 十进制遗传算法的基本过程这样就实现了对原问题的编码过程。x](x1,x2,2.1 问题的数学模型⋯,xm),这里xk表示具有适当精度的参数值(即一为了讨论方便,假设所要求的问题是一个多维种编码)。为以后叙述方便,将其看作xk的一种数变量的优化问题,如下面这个简化问题,其基本形据的存储形式,只不过与xk有一定的舍入误差,记式为:第k维参数的精度记为
5、Ek。下面讨论几个重要遗传→算子在十进制遗传算法的具体实现形式。maxf(x)→2.2.1 交叉 在交叉算子中摒弃了原二进制算法x∈R中的单点交叉策略,而采取在参数们的间隔中选取→m其中:f(x):8→R,8=I1×I2×⋯ImAR,I1,I2,交叉点。例如:收稿日期:2000—11—20作者简介:黄友锐(1971—),男,安徽长丰人,博士,从事电子信息方面的教学和科研工作。28©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.黄友锐: 十进制遗传算法的收敛性分析
6、 第1期(x1,x2,⋯xiûxi+1,⋯xm)2.2.2.2 非均匀突变(y1,y2,⋯yiûyi+1,⋯ym)这种策略把突变为:11Txk+$(t,UBk-xk)ifflip=02xk=11(x1,x2,⋯xiûyi+1,⋯ym)xk-$(t,xk-LBk)ifflip=1t(y1,y2,⋯yiûxi+1,⋯xm)其中:$(t,y)=y(1-r(1-T))b,r为随机数,0≤r≤也可选取多个交叉点进行交叉,仅考虑这种最简单1,T为最大代数,t为当前代数,b为系统参数,它的形式。为什么要摒弃原来在二进制中采用的交叉用来调整突变对代数的依赖
7、性,flip由突变概率来策略呢?先来考虑二进制算法中的交叉策略:在参控制,从而达到控制向哪个方向突变。可以看出随数经过编码后的代码段中任选一个空档,双方互换着t的增加,$(t,y)减小。当t小的时候这种突变空档前后的代码段。可以均匀地搜索整个空间,它比上一种更能体现一如图:种自适应的遗传性,即一定代数后子孙不会离它太173=1010û11011010û0010=162远。但是这种策略的突变是依赖于代数t的,对具]体的理论分析有一定的困难。34=0010û00100010û1101=452.2.2.3 高斯噪声突变 由上面的策略启发,在参数取值随近加一
