论文研究-基于个体邻域的改进NSGA-II算法.pdf

所需积分/C币:13 2019-09-16 11:22:04 1.06MB .PDF

带有精英策略的非支配排序遗传算法(NSGA-II)是在NSGA的基础之上,提出拥挤度和拥挤度比较算子,代替了需要指定共享半径的适应度共享策略,是解决多目标优化问题的经典算法之一。但是NSGA-II算法在保持种群多样性时采取的拥挤距离排挤机制有着pareto前沿分布不均匀的缺陷,因此,提出一种基于个体邻域的改进NSGA-II算法SN-NSGA2。SN-NSGA2将密度聚类算法DBSCAN中邻域的思想应用到排挤机制中去,提出一种个体邻域的构建方法,采用相应的淘汰策略去除个体邻域中的其他邻居个体。实验结果表明相对于NSGA-II算法来说,新算法求出的pareto解集有着更好的分布性以及良好的收敛性。
() 计算机工程与应用 由上述分析可知, 算法中基丁拥挤距离的序排序后的个体集合为x=(x1xy…,xm),然后求 排挤机制无法准确地衡量个体問围的密集程度,这就会 出在此目标函数密度半径下的个体邻城。密度半径与 造成最终最优解分布的拥挤与密集,个别区域也会出现种群在此目标函数下的分布范围相关,不同的目标函数 解的“中断”等情况 下种群有着不同的密度半径,目标函数(x)下的种群 在此基础之上,结合 算法中邻域的思想 密度半径计算公式为 本文提出一种 算法中种群个体邻域的构建方 法,用以衡量进化过程屮个体周围的密集程度 其中,厂和厂表示种群在目标函数下fx)的最大 基于个体邻域的排挤机制 值与最小值,m为种群规模。换言之,B即表示种群在 个体邻域的构建 算法是一种典型的基于蜜度的聚类算 (x)投影下两个体间的平均距离,这既保证了种群个 法,其核心思想是用一个点的邻域内的邻居点数衡量 体的均匀分布,也考虑到了不同目标函数之间的值域 点所在的空间密度。它可以找出形状不规则的聚类,且 差距。 聚类时不需要知道 的个数。 算法中有 由公式()、()可以得出个体i在目标函数∫(x) 个重要参数0,即密度半径。如图所示,以点为中心 下的a;邻域。以此类推,个体在H标函数集合 的密度半径内听有点的集合称为该点在此密度半径下{f(x)(x)…(x)下的邻城集合为{n,2,…,n 的邻城。则有: 那么i于整个目标函数空间的邻域为 设x∈X,称: 0(i)=0:∩02∩…∩a N(x)2={y∈X(xx)≤ 综上,取各目标函数下邻城的交集作为个体最终的 为x的邻域。显然,x∈N(x)。 邻城集合。其屮θ()中个体的数目即为i周围的空间 密度。 因此,以二维H标函数空间为例给出种群中个体邻 域的定义,其中的定义与概念可以很容易推广到高维目 标函数空间中去。 定义设两目标两数为fx,,相应的密度半径分 别为,0,Q表示种群集合,p(x,y)∈Q,称 5(P)={0)∈Q-x<9,-y|< 为p的邻域。显然,力∈N()=式中xy分别表 在两目标函数下的函数值。 图 算法中点邻域的计算方式 通过以上分析叮知,个体邻域可以准确地衡量个体 x的0邻城中点的个数即为x周围的空间密度 周围的密集程度,其邻域中邻居个体的数目即为个体周 经过研究之后发现,点周围的空间密度可以良好地反应围的空间密度。而邻居个体对进化过程中的种群多样 该点周用的点密集程度,通过对此种方式加以改进并性有着重要的影响,具体表现在 代替原有 算法的排挤机制是可行的。在种群 )种群个体及其邻居个体之间有着极其相似的染 进化的过程中,可以将种群看作是空间中分布的点集色体基因,过多的邻居个体会造成种群所携带的信息量 合而个体的邻城即为此个体在一定半径范围内的邻居元余,冗余重复的基因信总对种群进化没有任何催化作 个体的集合。 用,还会占据种群信息存储空间。在筛选父代种群的过 为了解决 算法所带来的种样分布均匀性程中,造成许多具有多样性的个体被淘汰。 上的不足,本文引入 算法中的邻域思想。假 )过多的邻居个体会缩小 算法的搜索范 设多目标优化问题为 围,进而干扰种群的进化方向。种样个体的周围空间密 mnF(x)=((x)(x)…(x)…(x) 度越大则表示其邻居个体越多,这也是算法在迭代的过 程中搜索区域重叠的结果。搜索区域的重叠会造成种 x∈g2 群搜索新的可行解的能力变弱,形成恶性循环,最终使 其中x=(x1,x2,…,xn),g为可行解空间。 得解集岀现大量重复解的情况。 现有初始种群P,其规模为m,在不考虑个体层级 所以,在保证算法收敛效率的同时,对种群进行适 的前提下,首先将种群按照某一目标函数f(x)进行排当的“修剪”,减小邻居个体对种群多样性的影响,是很 董骏峰,等:基于个体邻域的改进 算法 有必要的。由此,本文提出一种基于邻域的个体淘汰 机制。 基于邻域的个体淘汰机制 新算法排挤机制的主要思想是川基于邻域的个体 淘汰机制来代替原来的拥挤距离。其中个体邻城能够 准确地衡量个体周围的空间密集程度。现有目标函数 集合{f(x)(x)…(x).…(x 第n+1层 其体步骤如下 第n层 步骤指定一个此前未选取过的目标两数f(x 然后对听有个体进行排序,进而找出个体在此目标函数 图个体筛选后的种群分布图 下的邻域 c另一方面通过合理地构建个体邻域,使得邻域中的个 步擊。重复步,直至所有的目标函数均被选取体之间有着极其相似的染色休基因淘汰其他邻居个体 过,得到个体的等域集合为(,0,…}并由公式()有利于降低种详信息量冗余,且不会造成有效信息的过 可以计算得出个体在整个H标函数空间的。 度缺失,做到合理的“修剪” 步骤遵循依次从低层级到高层级对种群进行筛 基于邻琙的排挤机制的优势 选的原则。其中筛选同一层级个体的步骤:首先将该 相较于拥挤距离排挤机制,基于邻城的个体淘汰机 层级中的全部个体归为待保留种群pc。然后依次遍 制的优势在于 历pkcp中的个体,判断其是否有已淘汰标志,若已淘汰 )拥挤距离排挤机制是根据同一层级中的个体之 则直接跳过,若没有则将个体邻域中的听有邻居个体均间的离作为个体拥挤度计算的依据。这对个体在整 标记为已淘汰,以此类推,直至遍历完所有个体。最后个种群分布空间中的拥挤度考虑不足而基于邻域的个 剔除pe所有带有淘汰标志的个体。 体淘汰机制从种群的整体分布情况岀发,将个体的周围 如图所示,以二维目标函数空间为例,对丁第n空间划分为基于密度半径的邻域,且在计算个体邻域的 层级中的个体E,其邻域屮包含着A与G,则将A与时候并没有考虑层级的概念能够更好地反应个体周围 G标记为已淘汰;F的邻域为空,无个体淘汰;D邻城种群分布的密集度,进而为下步邻域中个体的筛选打 中包含着C,则将C标记为已海汰。继续对第n+1层下良好的基础。 级中的个体进行筛选,∧已被标记为淘汰个体,则直接 〕拥挤距离是通过对周闱个体目标函数值之间的 跳过;B的邻城中包含着H与I,则将H与标记为距离求和得出,然而周围个体的距离并不能如实地反映 淘汰个体。最后,则将所有带有淘汰标志的个体别个体本身的分布情况。例如有些条件下当两个体的拥 除。保留的个体如图所示,可以看出其具有良好的种挤距离相同时,更好的选择反而是保留其中的一个。基 群分布。 于邻域的个体淘汰机制以各目标函数下邻域的交集为 依据,结合相应的邻域个体洵汰策略,保证了种群中个 体的离散程度,使得个体在种样中的分布更加均匀,更 兼顾到了不同目标函数下个体周围密集程度的差异 ()通过划分个体邻域,可以找出进化算法在迭代 过程中搜索区域的重叠部分。并采取基于邻域的个体 淘汰机制,淘汰邻域中的邻居个体,以此降低邻居个体 第n+1层 所带来的信息冗余,使得更多的具有种群多样性的个体 第n层 得以保留,从而扩大可行解的搜索范围,增强搜索能力。 算法 在对 图带有邻域的种群个体分布图 算法的分析以及与改进算法的对比 的基础之上,给出 算法的伪代码 从低层级到高层级的方向来筛选个体可以使得精 设定种群规模,进化代数,交 英个体更容易被保留下来。同时,和 算法相又概率,变异概率 同,在组成新父代种群时,新算法会优先考虑种群中个 最终的非劣解集 体的层级属性,在此基础之上对部分层级进行筛选,使 ();初始化目标函数集 得在提高种群多样性的同时,保证了种群的收敛效率 );得到初始种群 () 计算机工程与应用 为O(MN计算个体邻域的时间复杂度为O(PMN), 其中P表示邻域中个体数目的平均值。整个算法的时 ();对进行快速非支配排序 间复杂度为O(MN2),与 算法的时间复杂度 );采取轮盘赌的方法选取参。相当 与交义、变异的种群,大小为 实验与分析 测试函数与参数设置 选取了个目标测试函数 以及个目标测试函数 ●。这些测试函数最终的最优解集的形状 各异有凹的凸的、非连续、多维度等其能够较全面地 验证算法在处理不同的前沿时所表现出来的性 能。测试函数的其体形式如表所示。 实验对 个算 法的性能进行分析,其屮 是文献提出 的一种带差分局部搜索的改进 算法。算法的执 对父种群进行交叉、变异操作,得到子代种 行参数设置如下:对于目标测试问题,设置种群规模 群 为,进化代数为,交叉概率为,变异概率为 合并父子代种群 。对于目标测试问题,设置种群规模为,进化 ();对合并种群进行快速 非支配排序 代数为,交叉概率为,变异概率为 ();计算个体邻域 评价方法 为了更加直观具体地比较 三个算法在解决多H标优化问题时所表 ):按照基于邻域的个体淘现出来的分布性,本研究将采取 所提出来的评 汰机制去除部分个体 价方法。此评价方法能够快速地比较种群在进化过程 中的分布的多样性,评价两数如下: SP (d-d =m>()(引(a=2…, 其屮,d是所有d的平均值,n是解集中个体的数目,k 选取合适的个伓进入到下·轮迭代进化 中;选取规则:从低到高依次将各层级中的个体添加到新的种 表示目标函数的维度。SP的数值越小,说明种群分布 群中。如果的个体数目大于种群规模时,按照基于邻域 得越均匀。当SP=0时,说明种群中的个体完全均匀地 的个体淘汰机制去除当前层中部分个体;然后再次与进行分布。 比较,若仍然大于,则直接进入下一轮迭代;反之,则将下 另外,将采用世代距离G作为收敛性评价指 层级添加到种群中,并判断规模是否大于,并根椐判断 标、用以衡量求得的非攴配解对真实最优解的逼 结果重复以上操作 近程度。GD的数值越小,说明越接近真实最优 解集。 GD ();最后对种群进行分层其中,n是解集中个体的数目,d2是每个非支配解距离 排序,并将第一层的个体作为最优解集 真实前沿的最小距离。 计算效率比较 算法的时间复杂度为 实验结果展示 O(MN2),其中计算拥挤距离为O(2MN) 分別使用 算法的计算复杂度主要集中在快速非支配排序和个体算法对表中的多目标测试函数进行求解,得到的 邻域的计算过程中,其中快速非攴配排序的时问复杂度前沿如图所示。 董骏峰,等:基于个体邻域的改进 算法 表测试网数 函数名称 函数形式 约束条件 /1(x1) m=30:0≤x;≤1 ()=1 8x(1-6/g v1/g)sin( 30:0≤x;≤1 i(x1)=x1 g(x)=1+10(m-1)+>(x2-10cos(4r) f(r1)=1-exp(-4ri)sin" (6ral) -(/g) g(x)=1+9∑x/(m-1) fix)=(1+g)cos(xjr/2)ces(x2T:/2) 2(x)=(1+g)cos(x1x/2) 0≤ f(x)=(1+g)in(1x/2) m=3,4,…,7 r=x ∫(x)=(1+g)xh (1+sin(3/) 图 的测试曲线 从图可以看出 算法的前沿而某些区域却存在着明显的“间断”,这是由于最 比 和 算法有着更好的分布性。优解的分布不均匀所造成的。 算法相较 算法在某些区域中个体出现拥挤、重叠的现象,于 而言,在种群的分布上较为均匀,但仍然存 () 计算机工程与应用 f(x-) fiD j(. 图 的测试曲线 () 图 的测试曲线 图 的测试曲线 f(x1) 图 的测试曲线 在着部分区域个体过于稀疏的现象;而改进后的 法在不同测试函数下运行次所获得的(D值。从 算法在保持与 同样的收敛速度的同时,表中的数据可以看出,新算法在收敛效率方面基本与 在均匀性方面要明显优于前两者。 算法持平,表明在个体淘汰的过程中无信息的 为了能定量地分析实验结果,表展示了三种算过度损失。 董骏峰,等:基于个体邻域的改进 算法 图 的测试曲线 f( fr2 f( 图 的测试曲线 表三种算法的值比较 算法 算法 算法 测试函数 最大值最小值 平均值最大值最小值 半均值 最大值最小值半均值 表三种算法的值比较 算法 算法 算法 测试函数一最大值最小值平均值最大值最小值平均值—最大值最小值平均值 表展示了三种算法在不同测试函数下运行鲁棒性和适应性。 次所获得的SP值。从表中的数据可以看出,三种算 为了进一步地验新算法在进化过程中的稳定性, 法经过次运行实验后所获得的SP均值的关系为:在代进化过程屮,每过代计算次SP值。图 展示了数下三种算法在进化过程中的SP值情 最大值与最小值的关系也是如此。由此说明 况。通过对比可以发现,在进化同等代数的情况下,新 算法相较于后两者具有更均匀的分布性。 算法的S尸值降低得更快,且保持得更加稳定。 图则展示了三种算法在数下运行次 中每次的SP值变化情况。通过折线图对比可以发现, 结束语 的SP值始终在更低的数值上下波动,并且 通过对 算法中基于拥挤距离的排挤机制 波动范围较小,表明新算法的稳定性更强,只有良好的的不足深入分析之后,融合了 算法中有关邻 () 计算机工程与应用 徐江雁,仲高艳,杨守峰改进 Ⅱ算法及其在切 削加工参数优化中的应用计算机工程与应用,, 图》/种第法次运行的值对比图 陈志旺,黄兴旺,陈志兴,等区间多目标优化非支配排序 云模型算法计算机工程与应用, 汪文文,方玺,何朗,等 算法的改进及其在应 急管理中的应用计算机工程与应用.,() 黄超,胡德敏,余星·种基于向量空间模型的 改进算法小型微型计算机系统, 王进,周宇轩,戴伟,等 算法的改进及其在风火 机组多日标动态组合优化中的应川电力系统及其自 动化学报, 图 种算法次迭代的值对比图 域的思想,提出一种基于个体邻域的改进 算法 。新算法利用H标函数空间来划分个体邻 城,将不同目标函数密度半径下邻域投影的交集作为最 终邻域。并采取“由低到高”基于层级的个体淘汰策略, 有效地解决了种群分布的均匀性问题。最后,通过对 算法的对比实验 表明,新算法具有更好的分布性和稳定性。下一步将会 针对 算法中存在的收敛效率问题展开深入研 究,并将其应用判实际工程中去。 参考文献: (): 谢承旺,李凯,廖树勇一种带差分局部搜索的改进型 算法计算机科学,,():

...展开详情
试读 9P 论文研究-基于个体邻域的改进NSGA-II算法.pdf
img
  • 至尊王者

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

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于个体邻域的改进NSGA-II算法.pdf 13积分/C币 立即下载
    1/9
    论文研究-基于个体邻域的改进NSGA-II算法.pdf第1页
    论文研究-基于个体邻域的改进NSGA-II算法.pdf第2页
    论文研究-基于个体邻域的改进NSGA-II算法.pdf第3页

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

    13积分/C币 立即下载 >