论文研究-一类非线性极小极大问题的粒子群-邻近点算法.pdf

所需积分/C币:5 2019-09-08 01:38:02 521KB .PDF

针对每个分量函数都是凸函数的离散型非线性极小极大问题,提出一种全局收敛的粒子群-邻近点混合算法。该算法利用极大熵函数将极小极大问题转化为一个光滑函数的无约束凸优化问题;利用邻近点算法为外层算法,内层算法采用粒子群算法来优化此问题;数值结果表明,该算法数值稳定性好﹑收敛快,是求解此类非线性极小极大问题的一种有效算法。
周畅,张建科:一类非线性极小极大问题的粒子群邻近点算法 2012,48(36) 21 (4)f(x)都是凸函数,根据性质1可知熵函数F(x)也是 其中,i-[1,mj-1,n;参数c1和c2是正数;和r2凸函数。因此,用邻近点算法为外层算法可以保证 为相互独立的随机数,服从0.1上的均匀分布。迭代序列收敛到全局最优。 v2∈[- vma], vmax为常数,由用户设定。 Shi和 Erhart给出了惯性权重PSO° 4粒」群邻近点混合算法 Ov +C,"(P-x)+C,r2(p (5) 以下结合邻近点算法给出此类非线性极小极大 在式(5)中ω为正数,控制前一速度对当前速度的影 问题的混合算法 响,ω较大时,前一速度影响较大,算法的全局搜索 (1)粒子群-邻近点混合算法步骤 能力较强;ω较小时,前一速度影响较小,局部搜索 步骤1给定初始点x。,参数p>0,正数>0 能力较强。通过调整ω大小来跳岀局部极小值。 置k:=1。 算法的终止条件可取最大迭代次数或最小适应 步骤2调用PSO算法求解邻近点迭代问题,得 值的确定阈值。 步骤3检验是否达到精度要求,若是,算法停 3邻近点算法 止;否则,k:=k+1,转步骤2 (2)内层粒子群算法 邻近点算法是由 Martine在1970年提出的 步骤1初始化一个规模为N的粒子群,设定每 种求解凸优化的全局收敛算法, Rockafellar等人研个粒子的初始位置和速度。 究和发展了该算法。 步骤2计算每个粒子的适应值,对问题(1),其 考虑以下凸优化问题: min f(, y) (6)适应值函数为:F(x)+x-x,此处的距离函数 也可以使用其他距离。 4这里fRm→(,+x1是个闭正则凸函数。约束 步骤3对每个粒子将其适应值利其经历过的最 凸优化问题包含于式(6)中,因为可以利用示性函数 好位置P的适应值进行比较,若较好,则将其作为 δ()将约束优化转化为无约束优化问题。若6(x,y R”+m→R为约束优化的目标函数,其约束集合C 当前的最好位置。 步骤4对每个粒子将其适应值和全局经历过的 (,y)g(x,y)s0}为R=m中的闭凸集,约束函数 最好位置Pρ的适应值进行比较,若较妤,则将其作 g(x,y)是闭凸函数,则: 为当前的全局最好位置。 f(x,y)=f0(x,y)+6(x,y) (7) 步骤5根据式(5)、(4)分别对粒子的速度和位 因此,式(7)包含于式(6)中 置进行进化 采用邻近点算法( Proximal point algorithm,PPA) 步骤6如果满足终止条件,则输出解;否则返回 求解式(6),其迭代序列{(xk,y)由如下式子产生:步骤2 (xnyo)∈R (3)必要的说明 (xk+I, Vk+)=argmin/(x,)+h D(x,D) (xr.y ))y ①由于p要求充分得大,在计算中很容易使 其中D(,)是一个距离函数,早期的邻近点算法采用expp(x)发生数据溢出,很多文献已经提出了解决 DX,)=2(x,y(x,。近年来很多满足凸性办法N。 ②本文有外层算法——邻近点算法保证全局 的类似距离函数被提出来,例如 Bregman函数类似收敛性。因此,内层粒子群算法不必取太大的迭代 熵函数等。 代数。 邻近点算法本身是一个比较经典的确定性算 法,若优化问题是凸优化问题则由该算法产生的迭5数值结果 代序列{(x4,yx)收敛于全局最优点,该结论可参见文 为验证本文算法的性能,取文献[2-4]屮四个非 献[17]等文献,本文不再赘述 线性极小极大问题做测试,并和文献[24]结果比较 本文中,假设极小极大问题(1)中的各个分量 例1(文献[2参数:n=2,m=3,X=(1,0.1); 22 2012,48(36) Computer Engineering and Applications计算机工程与应用 表1PSO-PPA算法计算结果 外循环迭代次数 初始点 内层PSO算法10次计算中最差解 最优值 (1.2134664271,0.8386920419)2.2628906256 (12134664271,0.8386920419)(1.1739102805,0.8717076867)1.9600341720 (1.1739102805,0.8717076867)(1.1597895166,08831247142)19547201593 (1.1597895166,0.8831247142)(1.1623483998,0.8810686325)1.9544307998 (1.1623483998,0.8810686325)(1.1541953865,08875937779)1.9528869988 表2文献[2-4,8结果和本文结果比较 算法 搜到的最优值 搜到的最差值 最大误差搜索成功率/%) 本文算法(1.1482042171,0.8923492673) (1.1541953865,0.8875937779) 5.5379E-5 100 1.9526099079 19528869988 X=(1.1390429205,0.8995565361)X=(1.1395300640,0.8991741051) 文前[8] 9.7584E-7 100 F0(X)=1.9522244940 F(X)=19522251858 X=(1.13903722,0.89955973) 文献[2] 5.630OE-6 F(X)=195223133 文献[3] 1.95222 X=(1.1390,0.8996) 文献[4] 1.5741 文献[4]中为问题4.1;文献[3中为问题1) 混合也可以求解此类问题。 f(X)=x2+x2;f2(X)=(2-x1)2+(2-x2)2 该算法不但给每个分量函数都是凸函数的离散 f3(X)=2 exp(x,+x 型非线性极小极大问题提供了一种新算法,而且为 在此选取的参数p和文献[2]一样为105。学习粒子群算法与经典算法相结合、发挥各自优势开发 中因子1==2.从1.0减小到04,群体规模数为混合算法提供了新思路数值结果表明该算法收 20,最大进化代数为100,粒子的搜索范围[-2,2]。 敛快、数值稳定性妤,是求解此类非线性极小极大问 在硬件环境:CPU: Pentium4293GHz、内存:512MB 题的一种有效算法。 等和软件环境 WindowsⅫP系统下用VC++60编程运 一个有意义的问题是对含有非凸分量函数的离 行。内层算法运行10次,取最差值作为外层算法的散型非线性极小极人问题能否有良好的收敛性,这 下一次迭代的初始点,精度要求为0.0010计算结将是下一步需要研究的问题 果见表1。 数据分析:文献[2-4]都是确定性算法,所以在表2参考文献 中没有最差值”和搜索的成功率”。最大误差计算「1黄震字,沈祖和解一类非线性极大极小问题的熵函数方 由式F(x)f(x)计算,本文取10次搜到的最差解来 法门科学通报,1996,41(17):1550-1554 12」李兴斯一类不可微优化问题的有效解法山中国科学:A 算误差。由表1可以看出:采用木文的PSO-PPA混合 缉,1994,24(4):371-377. 算法时,外循环只需5次迭代就可以达到0.0001的[3]欧宜贵,邓谋杰洪世煌.一类极大极小优化问题的信赖域 精度要求,内循环最大迭代代数为100代,计算速度 算法门工程数学学报,2004,21(8):41-57 整体比文献[8快,文献[8需要5000代进化。本文算41薛毅求解Mmmx优化问题的SQP方法巾系统科学与数 法需从初始点出发,但不需要导数信息。 学,2002,22(7):355-364 15 Kennedy J, Eberhart R Particle Swarm Optimization[C/ 6结论 Proc IEEe Int Conf Neural Networks. Piscataway: IEEE 本文针对一类每个分量函数都是凸函数的离散 Press,1995:1942-194 16 Shi Y, Eberhart R A modified Particle Swarm Optimizer[c/ 型非线性极小极大问题,利用极大熵函数法进行光 Proceedings of the ieee international Conference on evo 滑化处理,并结合邻近点算法给出了此类问题的一 lutionary Computation. Piscataway, NJ: IEEE Press, 1998 种新的有效混合算法,该算法无需使用初始点和导 69-73 数信息。显然,使用其他智能算法和邻近点算法相 (下转45页)

...展开详情
试读 4P 论文研究-一类非线性极小极大问题的粒子群-邻近点算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-一类非线性极小极大问题的粒子群-邻近点算法.pdf 5积分/C币 立即下载
    1/4
    论文研究-一类非线性极小极大问题的粒子群-邻近点算法.pdf第1页
    论文研究-一类非线性极小极大问题的粒子群-邻近点算法.pdf第2页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >