论文研究-自适应混合多目标分布估计进化算法.pdf

所需积分/C币:9 2019-09-07 03:31:22 581KB .PDF
2
收藏 收藏
举报

针对多目标分布估计算法全局收敛性较弱的缺陷,提出了一种自适应混合多目标分布估计进化算法。其基本思想是:在多目标分布估计算法中引入全局收敛性较强的差分进化算法,当函数变化率较大时,用分布估计算法产生新种群;当函数变化率较小即算法可能陷入局部收敛时,用差分进化算法产生新种群。理论分析和数值实验结果表明,这种混合算法不仅具有良好的全局收敛性,而且解的分布性和均匀性较没有考虑目标函数变化率的混合多目标分布估计算法也有了一定程度的提高。
48 014,50(5) Computer Engineering and Applications计算机工程与应用 都进行精确概率建模会极大地降低算法的效率,所以在 (1)以下列概率随机产生整数τ∈{1,2,…,K} 实际中,分布估计算法通常是构造若T个超矩形y米 ol( 近似代替主曲线(面)。在二目标优化问题中,望表示 Prob(t=k) vol(y 线段;在三目标优化问题中,表示矩形。图2给出了 个二目标优化问题概率建模的示意图。 其中,vo(y)表示m-1维超矩形v的体积。 /.Parcto Sct (2)在超矩形P1十随机选取一个点x',并用高斯分 个体 布N(0,o,)得到噪声8,a的计算公式为 ∑ (16) n-m十 其中,为C的协方差矩阵的特征值。 (3)产牛新个体:x=x+E 图2二日标优化问题概率建模小意图 从分布佔计算法的进化过程可以看出,分布估计算 在构造超矩形之前,需要将群体划分为若干子法的特点是 群体。MEDA采用局部主分量分析法进行子群体聚类, (1)分布估计算法则是利用整个群体的分布信息建 其算法步骤如下出: 立解分布的慨率模型,直接描述鍪个群体的进化趋势, (1)初始化:从群体P中随机选取K个个体,产生是一种“宏观”层面的进化方法。 k个m-1维仿射空间Lm,=1,2,…,K。 (2)分布估计算法利用随机采样的方法生成新群 (2)聚类:将群体P聚类成K个子群体C,C2 体,特别适川于求解变量相关的复杂优化问题 (3)更新Lm1:Lm是子群体C中所有点集的主4适应混合多目标分布估计进化算法 成分,可根据该子群体点集的均值和协方差矩阵计箅得 与其他进化算法一样,分布估计算法也不可避兔地 到均值和协方差矩阵为: 存在着一些缺陷。主要表现在:(1)解的质量在很大程 度上取决于概率模型的精确性;(2)算法的全局收敛性 (9) 较差。 Cov= ∑(x-x)x-x) (10) 分布估计算法全局收敛性较差的主要原因是:(1) 算法仅利用了群体的宏观统计信息,未充分利用个体信息; L可以表示为: (2)算法采用的高斯采样本质上是一种局部搜索算了。 改进算法性能的方法有多种,将两种算法相互融合 xx=x+>a,aeR,/=1,2,…,m-1(1)以取长补短是一种比较有效的次进方法。木文将差分 进化算法( Differential Evolution,DE)与分布估计算法 其中U为Coν的第i个主分量。 MF冂∧有机结合,提出了一种自适应混合多目标分布估 (4)重复(2)和(3),直到聚类的子群体没有新变化 计进化算法 聚类后,再按照下列公式计算各聚类C;中的个体 4.DE及与其他算法的混合 在主分量方向上投影的范围: DE是1995年Sto和 Price提出的一种非常优秀 m x-x.U (12)的进化算法,基本思想是:采用选择、交叉、变异等遗传 u. =na (13)操作驱动群体不断往最优区域移动。 由于DE算法在求解全局优化问题时表现出极为优 其中x,和U!分别为聚类C的均值和第i个主分量 异的性能,其有全局收敛性强,分布性较好等特点,有些 量后得到的概率模型即m-1维超矩形v为 学者考虑将DE融入其他算法,提高算法的全局收敛性 和解的分布性。2007年, Zhang等将DE算法引入 =1x∈R"x=x+∑BU,l ≤ MOEA,提出了基于分解的多H标进化算法 MOEAID; 王林等提出了DE算法与NSGA-相结合的混合多目 441+441-4).=1,2, (14) 标进化算法;向健等"将DE算法与MEDA相结合,改进 32分布估计算法的随机采样过程 分布估计算法的全局收敛性。 建立概率模型后,MFA釆用蒙特卡罗方法对概率42DE和MEDA的自适应调用机制 模型进行随札采样获得新个体,具体步骤如下: 将DE引入MEDA的出发点是想在MEDA陷入局 梁玉洁,许峰:自适应混合多目标分布估计进化算法 2014,50(5) 49 部收敛时,利用DE摆脱早熟的困境。但在DE与 步骤6若满足终止条件,输出P()。否则转步骤2 MEDA的混合算法中,往往采用等概率随机调用DE和 MEDA,这就造成了DE调用的盲目性,不能适时地5数值实验与算法性能评测 充分发挥DF的作用,从而也不能充分改善MFDA的全 下面用本文算法和随机调川模式的DE和MEDA 局收敛性。另外,等概率选择方法还有可能影响混合算混仝算法分别对两个标准测试所数DTLZ1和DTLZ2- 法的收敛速度叫l 进行优化,并根据多目标进化算法最优解集的评价指 解决上述问题的潜在方法是寻找一种自适应调用标,对两个算法进行了性能比较和评测。 方法,这种方法不仅可以进一步提高算法的全局收敛 数值实验参数是:样体规模为200,进化代数为200 性,还有可能提高算法的收敛速度。 DE算法的缩放因子为0.6,交叉概率为0.3,MEDA算法 本文提出种基于目标函数变化率调用DE算法和的聚类数量为5 MEDA的自适应机制,其体方法为: (1)DTLZ1测试两数 定义 min/(x)=), [1+8(x ) Vfx‖- v. min yiv. max-Vf, min (17) m(x)=号x(-)+8(x (21) 其中 lin/(x)=(1-x,1+8(x3) vr(x)=(xp)5(xe) 0≤x,≤I,t=l,2,3 (18) 其中,X3表示后(n-2)个决策变量构成的向量,n为决 vf,max=max/(x)-(x) (19)策向量的维数。通常g(X)取下列函数 m=m(x2-(x2 028(×)=1005-00 X,X分别表示父代和子代个体 该测试函数取得 Pareto最优边界时,对应着属于X y实际上就是目标函数的离散相对变化率向量。的所有x,均为05,标函数值在平面上。此问题难以 当;的模小于设定的阙值c(通常取为102)时,选择收敛到 Pareto最优边界,因为对应的搜索空间包括 DE算法进化生成新群体,否则选择MEDA 11-1个PFa,一般会使MOEA收敛到这些局部最优 当算法陷入局部收敛时,目标函数的变化率很小,边界。函数的PFa为平面。 此时选用DE算法可跳出局部收敛,否则选用MEDA算 (2)DTLZ2测试函数 法以保讦解的质量 min/f(x)=[1+g(x,)cos( x /2)cos(x2 z 2) 43自适应混合多目标分布佔计进化算法 m1(x)=+8(x(m2)mx2)(2 下面给出自适应混合多目标分布估计进化算法的 min(x)=1+g(X,)sin(x, t/2) 具体步骤 0≤x:≤1,L=1,2,……,n 步骤1群体初始化 (1)随机产生初始群体P(0).t=0 其中,X3的含义同DILZ1,g(X3)=∑(x-0.5)。 (2)计算初始群体的适应度f。 该测试函数的 Pareto最优边界对应着属于X3的所 步骤2选择进化算法。 有x均为0.5。函数的PFm1是第一卦限内的单位球面 根据4.2节中的自适应机制选择DE(转步骤3)或 图3-6分别是川文献[11中的随机调川和本文提出 MEDA(转步骤4) 的自适应调用两种混合算法求出的DTLZ1和DTLZ2的 步骤3DE进化产生新群体O。 Pareto最优边界:可以很直观地看出,自适应算法在算 根据DE算法进化交叉、变异,产生新群休,转步骤5。法的收敛性和解的均匀性方面均明显优于随机调用算法。 步骤4MEDA进化产生新群体Q。 为了进一步定量地评价改进算法的性能,下面给 (1)根据3.1节中方法构建概率模型; 出随机调用和自适应调用算法的世代距离、错误率和分 (2)按3.2节中方式进行随机采样,产生新群体,转散性指标的对比数据。 步骤5 考到计算结果的随机性,表中给出的是20次实 步骤5选择 验结果的平均值 根据DE或MEDA算法从Q∪P()中选择N个优 从表1和表2中可以很清楚地看出,自适应算法的 秀个体作为P(t+1)。 冂指标明显优于随机算法,表明自适应算法的全局收 50 014,50(5) Computer Engineering and4 pplications计算机工程与应用 0.6 ,:2 0. 0 0.10.20.30.40.50.6 0400 0.4 4 f A(rm 图3DTLZ1的PF图(随机) 图4DTLZ1的PFon图(自适应) 1.2 3:2 0.2 0:《: 0.2 0.22}:?: 0.2 0.2 0.2 0.6 0.8 0.6 f( 0.8 1.0 f(x1) 1.D080.60.40.20 图5DTLZ2的PFn图(随机) 图6DTLz2的PFk图(自适应) 表1DTLZ1的随机/自适应算法优化指标结果 (2)因为如何衡量多次优化结果的一致性和稳定性 指标 GD ER SP 等问题目前尚未解决,所以世代距离、错误率和分散性 平均0.0129/002780.2883011560.10380234 三个量化评价指标并不能完全反映多标优化算法的 最小0.089009009809240074800145 性能。 最大0.0237/003980.83600.68770.13390.0957 标准差0.0033/0.00440.08860.03210.0637/0.0177 3)自适应选择机制在提高算法收敛速度方面的作 用很不明显,改进后算法的收敛速度总体仍然较慢,主 表2DILZ2的随机/自透应算法优化指标结果 要原因是分布估计算法的概率建模过程复杂度较高。 指标 D (4)分布估计算法与粒了群算法、蚁群算法、人工兔 平均0.03280.04070.42420.20290.1267/0.0607 疫系统、协同进化算法等均为近年来出现的新型进化范 最小0.0139001850.13390.11380.108600635 最大0.04160.05320.97890.74670.2073/0.1258 例,理论体系尚不完善,建模的精确性和效率有待提高, 标准差0.0123002130.09850.04920.08680.0385 收敛性等关键理论问题需要进一步研究。 敛性得到了明显改善。自适应算法的ER和SP指标较参考文献 随机算法也明显占优,表明自适应算法解的分布性和均 [1 Pareto V Cours economic politique, volume I and II[M 匀性也有显著提高。 sanne 综合图3~6和表1~2,可以得岀明确的结论:基于自(2]公茂果,焦李成,杨咚咚,等进化多目标优化算法研究[J] 适应调用机制的MEDA与基于随机调用机制的MEDA 软件学报,2009,20(2):271-289 在全局收敛性和解的质量方面有明显改善。 [3 Zhou A M, Zhang Q F,Jin Y, et al. Global multi-objective optimization via estimation of distribution algorithm 6结束语 with biased initialization and crossover[C]/Proc of the (1)本文将DE算法引入MEDA算法,并提出一种 Genetic and Evolutionary Computation Conf, GECCO 2007. New York: can Press, 2007:617-622 基于目标函数变化率的调用DE和MEDA算法的自适 应方法。数值实验结果和量化指标表明:与随机调4] Zhang Q F, Zhou A M, Jin YRM-Meda: a regularity model bascd multi- objective estimation of distribution DE和MEDA的混合多目标分布估计算法相比,新算法 algorithm[J].IEFF Trans on Evol Comput, 2007, 12(1) 的全局收敛性、收敛速度和解的质量均有了不同程度的 提高。 (下转207页)

...展开详情
试读 5P 论文研究-自适应混合多目标分布估计进化算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744270 如果觉得有用,不妨留言支持一下
2019-09-07
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-自适应混合多目标分布估计进化算法.pdf 9积分/C币 立即下载
    1/5
    论文研究-自适应混合多目标分布估计进化算法.pdf第1页

    试读结束, 可继续读1页

    9积分/C币 立即下载 >