基于改进人工蜂群算法的约束多目标进化算法

基于改进人工蜂群算法的约束多目标进化算法

为了确保满足多目标限制，有必要确保获得的最合适量解决方案接近真实的帕德，并均匀分布，这比复杂的多目标边界问题更复杂。现在的约束多目标处理方法主要有4种:①把约束违反度作为一个目标重新求解;②利用自适应罚函数法修改目标函数值;③利用约束支配关系直接求解;④利用外部种群分别存储可行解和不可行解,是目前最为优秀的约束多目标算法的处理方式,优化效果也较好。遗传算法、粒子群算法、差分算法等都已成为典型的约束多目标算法,它们结合相应的约束处理技术虽在一定程度上提高了约束多目标算法的收敛性和分布性,但要使其稳定、有效地找到近似Pareto最优解集并同时保证良好分布性仍很困难。人工蜂群算法是2005年提出的一种新型进化算法,因其参数设置少、收敛速度快、收敛精度高使其得到学者的逐渐关注。文献提出一种结合自适应罚函数法的约束多目标算法,由于该种约束处理技术的局限性,虽然取得了一定的效果,但收敛性和分布性都有待提高。本文选择目前最流行的建立外部种群分别存储可行解集和不可行解集的约束处理技术,在此基础上根据约束多目标问题的特点,对外部种群的更新方式、迭代种群的更新方式及人工蜂群算法进行改进。实验仿真结果表明,CMABC相对于目前性能较好的MOABC及HPSO具有一定优势,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,适合于约束多目标优化问题的求解。1基于人工蜂群算法的限制多目标优化1.1基于循环hartonic平均距离的可行解集本文采用文献中建立外部种群分别存储可行解集和不可行解集的约束处理技术。在文献的可行解集更新中,当优秀可行解数目大于其固有容量时,需依靠NSGA2算法中的拥挤距离实现均匀分布,但这种拥挤距离不能真实地反映个体间的疏密程度。研究表明,与NSGA2算法中的拥挤距离相比,harmonic平均距离能够更好地评价种群个体间的拥挤程度;其次,这种策略忽视了个体淘汰后对其邻域个体拥挤密度的影响,当拥挤距离较小的个体被删除后会导致周围个体的拥挤距离变大,按原有方法选择个体很可能将现在拥挤距离较大的个体删除,不利于分布性指标的达成,而循环拥挤策略却考虑了被删除的个体对余下个体的作用。鉴于此,本文提出循环harmonic平均距离剪切可行解集。个体i的harmonic平均距离di定义为di=k1di,1+1di,2+⋯+1di,k(1)式中:k为目标数减一;di,k为与i距离最近的k个个体的欧式距离。基于循环harmonic平均距离更新可行解集的方式如下:①计算所有个体的harmonic平均距离,挑选出最小距离的个体,将其删除;②删除剩余个体中harmonic平均距离最小的个体,直至剩余个体数目为可行解集容量。从本文采取的改进的个体更新方式可以看出,相比于原有方式,本文方法能够更为精确地反映个体间的密度,提高解集分布性。1.2不同算法中的进化策略进化算法的进化策略优劣对其收敛精度、收敛速度都有较大影响,而人工蜂群算法中的进化策略主要包括引领蜂、跟随蜂和侦查蜂的搜索策略,因此有必要根据约束多目标问题的特点对ABC算法中的搜索策略进行改进。1.2.1进优进展建议在ABC算法中,当某个解连续“limit”代没有变化时会启动侦查蜂,这时有可能达到全局的最优搜索,也有可能陷入局部最优。若陷入局部最优,侦查蜂靠随机搜索补充多样性对算法进化至关重要,但因其是在整个搜索空间内产生一随机解参与后续的引领蜂和跟随蜂的搜索,如果limit设置过小,会较多地引入随机性搜索,降低算法的收敛速度,甚至可能破坏种群保持的良好进化方向;如果limit设置过大,对产生优异新解及进化方向所起作用不大。考虑到侦查蜂行为的本质就是补充多样性,完全可以采取其他方式加以代替。分析发现,引领蜂和跟随蜂在某些选择压力的迫使下,随着进化的进行,其搜索区域将逐渐缩小,聚集在一个或几个区域,这是算法容易陷入局部最优的原因。其中,跟随蜂为了加快算法收敛,在引领蜂的基础上进行贪婪搜索,因此引领蜂的搜索策略成为算法多样性不足的主要原因。为增大种群多样性及充分利用个体信息,本文为引领蜂建立如下的两种搜索策略:将rand<Pm时的搜索方式称为方式一,另一种搜索方式称为方式二。其中,P′i、Pi分别为新旧蜜源,r∈代表贪心程度,k1、k2及k3为当代种群中随机选取的不同个体,Pm为按照方式一或方式二搜索的选择概率,Pk为按如下方式选取的个体:①每个初始蜜源(即初始群体中的个体)按照欧式距离建立各自的固定邻域。②计算各邻域的中心。③按照文献提出的选择方法选取距个体较近的邻域。④在该邻域内随机选择一个个体,即Pk。从上述搜索方式可以看出:搜索方式二保留了基本ABC算法的搜索策略;搜索方式一是本文为增大种群多样性设计的新的搜索策略,与完全破坏原有个体产生随机个体代替用以补充多样性的方式相比,本文选择在个体最初的邻域范围内选择某一个体参与进化,同样可以达到扩大种群多样性的目的;在一定程度上保留了原有个体的方向信息,且以当代种群作为步长扩展信息,不会过多地降低算法的收敛速度。1.2.2基于pbest的可行解提取在ABC算法中,跟随蜂的作用是在原有蜜源的基础上,选择某些优秀蜜源进行进一步探测,加快算法进化的收敛速度。基本ABC算法是根据个体适应度值进行优异蜜源选取的,因每个个体都有不止一个适应度值,所以无法赋予个体一个特定可比较的值,不适合解决约束多目标问题。文献把个体之间的支配排序作为个体适应度值,这种赋值关系存在以下问题:首先,它基于可行解一定优于不可行解的原则,不可行解很难参与进化,但在约束多目标问题中,与可行解一样,某些不可行解也至关重要,不能忽略优势不可行解的作用;其次,当种群趋于最优时,个体支配排序值相近,这种方式无法评价个体优劣,相当于随机选取个体参与进化,不利于收敛速度的提高。而在外部种群与其他进化算法相结合解决约束多目标问题时,都采用在外部种群中随机选取一个个体参与进化,这种方式的收敛速度也不高。上述方法收敛速度不高的主要原因是未给出合理的个体优劣比较准则,本文通过深入研究给出基于以下准则的搜索方式:p′i=r×pbest+(1−r)×pi+(−1+2×rand)×(pk1−pk2)(3)式中:pk1、pk2为在种群中随机选取的两个不同个体。经分析发现,在外部精英种群中,可行解集一定不空,但不可行解集有可能空,因此pbest需按以下方式有针对性地选取:(1)当不可行解集为空时,精英种群中的个体彼此是非支配的,因此,可以将拥挤距离作为可行解优异的评价标准,而贪婪的轮盘赌选择方式容易使算法陷入局部最优,故以文献中的选择方式在外部精英可行解集中选取较优个体作为pbest。(2)当不可行解集不空时,鉴于不可行解和可行解在约束多目标问题的求解中都占有重要作用,因此等概率地在可行解集和不可行解集中选取个体,若在不可行解集中搜索,为加强可行域边界的搜索,按文献中的选择方式以距离作为评判标准选取一个个体作为pbest;否则,在可行解集中搜索,按方式一选取pbest。另外,在引领蜂和跟随蜂的搜索过程中都有超出边界的情况,由于个体的每维信息都是在进化过程中逐渐积累的,因此以较大概率保留原有信息,以较小概率在边界内随机搜索,而不像现有方法一样将个体置于边界上或者在边界内随机产生一个个体。1.2.3可行性解与不可行解的区分:迭代种群的可解性迭代种群的确定方式是种群进化的主要压力,对收敛速度及多样性都有较大影响,现有的约束多目标算法的迭代种群的确定方式有:①按照文献中的比较准则对个体进行更新;②按照NSGA2算法中的精英种群的确定方式。上述的迭代种群确定方式都是以可行解优于不可行解为前提的,随着进化的进行在某代以后很可能导致最终的迭代种群全部为可行解,这就忽视了不可行解的作用。此外,NSGA2算法中的拥挤距离不是最合理的分布性达成标准。为充分重视优秀不可行解的作用及提高种群的分布性效果,提出如下的迭代种群的确定方式:(1)搜索前后的种群组合形成一个种群,并把新种群分成可行解集和不可行解集,设定迭代种群中不可行解数目TT。(2)新种群中的可行解部分按NSGA2算法中的精英种群的确定方式确定个体,对于最后加入精英种群的个体按1.1节中的循环harmonic距离进行选择。为加强可行域边界的搜索,不可行解选取离可行解距离最近的TT个个体。1.3外部种群的筛选综合以上改进,MABC算法流程如下:步骤1在约束多目标优化问题的决策变量空间里随机生成NP个个体,构成初始种群P,并构成各个体的邻域PP。步骤2计算P中每个个体的适应度值及约束违反度,确定外部种群中的优秀可行解集和优秀不可行解集。步骤3终止条件不满足则执行,否则转至步骤4。(1)对于种群中每个个体Pi1(i=1,…,NP)按1.2.1节中方式生成子代个体Ci,并计算Ci的适应度值和约束违反度。(2)合并父代种群P1和子代种群C形成种群R,对其按照1.2.3节中方式确定迭代种群p2。(3)更新外部种群。(4)对p2中每个个体按1.2.2节中方式搜索产生新的种群Q。(5)合并种群p2和Q,按照1.2.3节中方式确定迭代种群p3,并更新外部种群。(6)p3确定为迭代种群。步骤4输出外部种群中的优秀可行解集。1.4更新所需的时间复杂度这里仅考虑种群规模对算法时间复杂度的影响,设外部种群中可行解和不可行解的容量分别为N1和N2,种群规模为N,即引领蜂、跟随蜂的规模为N/2,每代生成的可行解、不可行解数目分别为Na、Ns,迭代种群中的不可行解数目为TT,目标数目为M。每次迭代的时间开销主要在于迭代种群的确定和外部种群的更新,所需的时间复杂度计算如下:(1)迭代种群的确定可行解部分的确定:非支配排序的复杂度为O(M(Na)2);harmonic循环拥挤排序的复杂度为O(∑i=N1N1+NaM(i)log(i)),由于O(∑i=N1N1+NaM(i)log(i))<O(NaM(N1+Na)2);比较算子的复杂度为O(Nalog(Na)),所以总的可行解部分确定的时间复杂度为O(NaM(N1+Na)2);不可行解部分的确定需进行Ns×Na次比较,其时间复杂度为O(NsNa),总的时间复杂度为O(NaM(N1+Na)2)+O(NsNa)。(2)外部种群的更新文献指出非可行解集更新的最坏时间复杂度为O(M(1+N1)(Ns+N2));而对于可行解集,考虑最差情况,从N1+Na个微粒中选出全部非劣解需M(Na+N1)2次比较,循环拥挤排序的计算复杂度为O(∑i=N1N1+NaM(i)log(i)),所以可行解集更新的最坏时间复杂度不大于O(NaM(N1+Na)2)。2实验装置和程序为了验证CMABC算法在约束多目标优化问题上的求解性能,将其与两种目前性能最优、最具代表性的算法MOABC和CHPSO在CTP测试函数集上进行对比实验,所有实验在硬件配置为IntelCentrinoDuo,CPU:T7250、1GB内存、主频2.0GHz的计算机上进行,程序采用MATLABR2007编写。各算法的收敛效果和分布性分别采用TSC(A1,A2)和世代距离SP来对比。2.1不可行解的2个代次100%将本文算法与仅去掉某项改进的算法进行对比。参数设置如下:初始种群设为100,迭代次数为250,外部种群中的可行解集和不可行解集的容量N1、N2都为100,邻域个体数目为5,每代保留的不可行解数目为5,Pm为0.5。2.1.1ctp6测试外部种群中可行解集更新方式的改进主要影响算法的分布性,所以选择对分布性效果明显的CTP6测试。保持初始种群和参数设置相同,对改进前后的算法随机运行5次,取最好结果对比如图1所示。从图1可以清晰看出,改进后分布效果明显改善,证明本文提出的有关外部种群中可行解集更新方式的改进是有效的。2.1.2ctp4算法效果对比测试将侦查蜂与引领蜂的行为相融合的改进搜索方式与算法的收敛效果有关,为验证该种改进对算法效果的影响,对较易陷入局部最优的CTP4进行测试,对比算法分别选择常用limit取值30,保证两种方法的初始种群相同,两算法各运行5次,取最好效果比较,如图2所示。从图2最终的分布效果可以看出,改进后算法效果明显改善,证明了这种改进的有效性。2.1.3算法有效性验证跟随蜂的搜索方式主要影响算法的收敛速度,随机选取外部种群中的可行解和不可行解作为较优个体,并在其附近搜索,是常用的搜索方式,作为本文改进前的搜索策略,为验证本文提出的改进策略的有效性,将改进前后的效果进行对比,保持初始种群相同,参数一致,两种算法各随机运行五次,取最好结果,对比效果如图3所示。从上述仿真结果可以看出:在进化到40代时,跟随蜂的搜索策略被改进后,算法的收敛效果和分布性效果都有明显改善,即改进后算法的进化速度有显著提高,与分析相符,证实了本文改进方式的有效性。2.1.4精英种群确定迭代种群的更新方式与算法进化的收敛效果关系很大,为验证本文提出方法是否有效,将本文方法与常用的NSGA-II中精英种群确定方式进行比较,为对比明显,选择最优可行解位于可行域与不可行域边界的CTP4作为测试函数,保证对比算法的初始种群相同,算法参数设置完全相同,两算法各随机运行5次,取最好结果对比,如图4所示。从图4可以清晰地看出,改进后算法的收敛性和分布性都有明显改善,由此证明本文改进策略的有效性。2.2tsc与mp的运行为验证本文提出的基于人工蜂群算法的改进约束多目标算法,将CMABC算法与CHPSO及MOABC算法在CTP测试函数上独立运行30次,统计TSC和SP的平均值及标准差,进行对比。为保证比较结果的公平性,所有算法的种群大小都为100、函数评价次数都为25000,且相同测试函数的所有算法的初始种群都相同。2.2.1真实图像结果表1为各算法对CTP类测试函数的实验统计结果,包括TSC的均值(括号外)和标准差(括号内)。这里将本文提出的CMABC算法、CHPSO算法及MOABC算法分别简记为A、B、C。从表1可以看出,本文算法得到的TSC结果更接近于1,这表明,与另两种方法相比本文算法所得结果支配或等于其他方法所得结果的个体更多,即本文算法所得结果更为接近真实的Pareto前沿。此外,与另两种方法相比本文算法的方差相对较小,说明本文算法最为稳定。2.2.2算法有效性测试为了对比3种算法的分布性效果,通过仿真实验给出了各算法