遗传算法及其应用实例(可用)

所需积分/C币:14 2012-03-13 22:41:03 815KB PDF
19
收藏 收藏
举报

详细介绍了遗传算法原理及其应用实例,很有用的哦
遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出 优点,适用于解决复杂、困难的全局优化问题。 个优化问题被称为是复杂的,通常指它具有下述特征之 (1)目标函数没有明确解析表达(如非数值优化问题)。 (2)日标函数虽有明确表达,但不可能恰好估值(如大部分最 优控制问题、金融优化问题)。 (3)日标函数有极多的峰值(如DMA计算、组合优化问题)。 (4)多日标优化,即目标函数是向量值。 一个优化问题被称为是困难的,则通常是指:或者目标函数∫不 连续、不可微、高度非线性,或者优化问题是困难的组合问题。 对于这些复杂、困难的优化问题,已知的优化方法或者根木不可 用,或者可用但不有效。相比之下,遗传算法不但保证可用,而且常 常显得更为有效。 但是,我们必须注意到,一个通用而又较少依赖于目标函数值与 其他辅助信息的算法不可能比专用且充分利用目标函数值与相关辅 助信息的算法更为有效,而当一个问题有某些辅助信息可供使用时, 舍弃应用本来可供应用的信息而去应用于这些信息无关的算法也不 是一个聪眀的选择。所以,遗传算法一般来说并不适宜应用于通常的 数值优化问题(例如连续可微的数学规划问题),或者说,当应用于 这样的问题时,遗传算法并不总能显示其优越性 Page 3 of 20 接下来,我们通过一个求解简单函数的最小值点的问题来初步展 示遗传算法的具体实现方法: 问题1: 求函数f(x)=11sin(6x)+7co5x)在x∈[0,2z区间上的最小值点 15 5 0 -10 15 20 6 上图为函数f(x)=1lim(6x)+7c5x)在x∈[0,2z区间上的曲线图像, 可以看出,该函数有多个极值点,如果使用其他的搜寻方法,很容易 陷入局部最小点,而不能搜寻到真正的全局最小点,但遗传算法可以 较好地弥补这个缺陷。遗传算法的具体实现如下 1问题分析。对于本问题,自变量x可以抽象为个体的基囚组, 即用二进制编码表示x;函数值f(x)可以抽象为个体的适应度,函数 值越小,适应度越高。 关于进制编码方式,在精度允许的范围下,可以将区间内的无 Page 4 of 20 穷多点用间隔足够小的有限点来代替,以降低计算量同时仸证精度损 失不大。如用16位二进制数米表示该区间的点,相邻点的间隔仅为 2z=0。9585×105,相邻点的函数值的变化幅度已经很小,由此带来 的精度损失完仝可以接受。 另一个问题是普通的二进制编码方式可能具有较大的汉明 ( Hamming)距离,例如15和16的二进制表示为0111和1000 从15到16必须改变所有位,这种缺陷将降低遗传算法的搜索效率。 采用格雷编码( Gray encoding)可以避免这一缺陷。格雷码的特点是 任意两个连续的两个整数的编码值之间只有一个位是不同的,其他位 都完全相同。格雷编码的原理如下 设有二进制串b2…b,对应的格雷串aa2…an,则从二进制编码 到格雷编码的变换为a=,=1 b1田h,i≠1 从格雷编码到二进制编码的变换为b=a)m2 例如,0-15的格雷码如下表所示: 1 2 3 7 00000001001100100110011101010100 8 10 11 14 15 1100110111111101010101110011000 2.根据遗传算法的运算过程编写程序。 i f(x)=lIsin(6x)+7cos(5x),0<-x<=2* pi =16; N=32 M=48 Page 5 of 20 T=100; Pm.=0.03; for i =1:1: N x1(1,i)=rand()*2*p 2(1,i)=uint16(×1(1,i)/ pi)*65535); grayCode(i,:)= num2gray(x2(l, i),l)i end for t =1:1: T y1=11*sin(6*x-)+7*Cs(5*x1); for i =1: 1: M/2 [a, b] nin(yl)i graycodeNew(i,: )=grayCode(b,: graycodeNew(i + M/2,: ) grayCode(b,: 1(1,b) inf end for 1:1:M/2 p= unidrnd (l)i if rand(< Pc for temp grayCcdeNew(i,3)i graycodeNew(i,j)= grayccdeNew(m 1,j); grayCodeNew(M G)=temp; end end end for I =1: 1: M for 1:1:L if≌and()<Pm graycodeNew (i,j) grayCodeNew(i, j)i en end f。yi 1:1:M 4(1, i)= gray2num(graycodeNew(i,: ))i end 3=doub1e(x4)★2 /65535 y3=11*sin(6*x3)+7*CoS(5*x3); for [a, b] =min(y3)i 1(1,i) 3(1;b); graycode(i,: ) =graycodeNew(b,: ) 3(1,b)=inf end Page 6 of 20 end y1=11*sin(6*x1)+7*cos(5 3结论分析。程序运行结果为: 最小值点为x=1.8486,f(x)=-17.8340。 下面针对上面的问题,讨论遗传算法中一些初始化参数的设定方 法及其影响 (1)编码长度L。使用二进制编码时,L通常由对问题的求解精 度决定,编码长度L越长,可期望的最优解的精度也就越髙,但应注 意过大的L会增大运算量。 (2)种群规模N。种群规模N表示每一代种群中所含个体数日。 当N取值较小时,可提高遗传算法的运算速度,但却降低种群的多样 性,容易引起遗传算法早熟,出现假收敛;而当N取值较大时,乂会 使得遗传算法效率降低。一般建议的取值范围是20~100。 (3)交叉概率P。在遗传算法中交叉算子被认为是主要搜索算 子,因而一般取较大值。一般说,较大的P容易破坏群体中已形成的 优良模式,是搜索的随机性太大,而较小的P使发现新个体(特别是 优良新个体)的速度太慢。一般建议的取值范围是0.4~0.99。另外 比较理想的的方式是非一致地使用交叉概率,例如在遗传算法的前期 使用较大的尸,后期降低P以保留优良个体。 (4)变异概率卩。较大的变异概率ρ使遗传算法在整个搜索空 间中大步跳跃,而小的变异概率使遗传算法聚焦于特别区域作局部搜 Page 7 of 20 索。一般在不使用交叉算子的情形(演化策略( Evolution Strategy) 算法,进化程序( Evolution Programming)算法),变异算子作主要搜 索算子,P取较大值(0.4~1);而在与交叉算子联合使用的情形(遗 传算法),P通常取较小值(0.00~-0.5)。 (5)终止进化代数T。遗传算法不同于传统优化算法,它很难 有明确的搜索终止准则(特别是对于非数值优化问题),于是通常需 指定一个终止进化代数来终止算法,一般设T∈[00100般来说, 事先指定T通常只能找到给定问题的在给定时限内所能寻求的相对 满意解,但不一定是问题的最优解或较髙精度的近似解。为了获得较 髙精度解,通常可依据种群适应度的稳定情况来实时调整r的设置。 总体来说,以上参数的确定并没有明确的准则可依据,需要根据 实际问题的特点以及算法的运行情况进行实时的调整,以搜索获得更 为满意的最优解 Page 8 of 20 接下来,我们用遗传算法来求解一个更为复杂的函数最值问题 问题2: 求 Schaffer两数的最大值点: f(x,x,)=05sin2x2+x2-0.5 5≤x,≤5,i=1,2 [1+0.001(x2+x2) 0.8 0.6 0.4 0.2 5 0 根据遗传算法的一般运算过程编写 MATLAB程序如下: L=32 N=60 M=80 T=100; P PI.=0.02; for i =1:1. N x10(,i)=unidrnd(2 l -1)i x10(2, i)=unidrnd(2 A l-1 1(1,i)=c∞uble(x10(-;i))/(2^L-1)*10 11(2,i)= double(x10(2,i))/(2^-1)*10-5 end for t=1:1: T Page 9 of 20 for terp1(;i)=x11(1;i)^2+x11(2;i) 1(1,i)=0.5-(sin(sqrt(temp1(,i)))^2-0.5)/(-+0.001 色 grayCodel(l i ) num2gr ay(x10(1;立);L) graycodel(2,i,:::: )=num2gray(x10(2,i),l)i fo¥i=1:1:M E max Code2(l i,: =graycodel(l b: ly Code2(2r i, )=grayCodel(2, b, inf end ori=1:1:M/2 lidrnd(L) if rando< pc f。y e rayCede2(l, i,j)i graycode2(1, i,i)=graycode2( ) graycode2(1,M-i+ 1,i)=tempi temp grayCcde2(2, i,3)i grayCode2(2, i,i)= graycode2(2, M grayCode2(2/M i)=tempi end end end for 1:1:M for 1:1:L fork=1:1:2 i£yand()<Pm graycode2(k, i, i) graycode2(k, i, i)i end end en end for 1:1:M x20(1, i)=gray2num(grayCcde2(1, i,: )i x20(,i)= gray2num(grayCode2(2 )); 21(1,i)=doub1e(x20(;i))/(2^-1) x21(2,i)=doub1e(x20(2;i))!(2^L-1)*10-5 temp2(1;i)=x21(1;i)^2+x21(2;i)^2 2(1,i)=0.5-(sin(sgrt(temp2(1,i)))^2-0.5)/(1+.001 temp2(1, i) end Page 10 of 20

...展开详情
试读 20P 遗传算法及其应用实例(可用)
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
遗传算法及其应用实例(可用) 14积分/C币 立即下载
1/20
遗传算法及其应用实例(可用)第1页
遗传算法及其应用实例(可用)第2页
遗传算法及其应用实例(可用)第3页
遗传算法及其应用实例(可用)第4页

试读结束, 可继续读2页

14积分/C币 立即下载