一种多目标粒子群优化算法

一种多目标粒子群优化算法

0基于多目标进化算法的群体决策在过去10年中，先进的计算方法在解决多目标优化问题上发挥了良好的优势，因为它可以找到多个解算方法，并将其收敛到相对均匀的区域，分布相对均匀。现在进化计算方法与决策理论结合在一起,在多目标决策中发挥作用,是一个重要的研究热点。其特点是不再注重于近似整个Pareto前沿,而是集中于决策者所关心的那些Pareto最优解,使得搜索的效率更佳。但多目标进化算法应用于群体决策方面的研究还非常缺乏。文献中介绍了解决群体决策问题的一种遗传算法方法,决策者的偏好用参考点(概念详见2.1节)表示,再通过分层排序或者距离引导种群向群体解进化。而在决策支持系统中,有关群体决策的研究已经较为深入。但是其中大部分研究都是基于以下两点不是很符合实际问题的假设:其一,大部分情况下,只有少数几个可选方案,而在这几个方案中必须选择一个作为最后群体解决方案,而很少关注到如何在一个数量巨大的可选择空间中进行优化;其二,通常假设群体是同类的,因此可以整合到一个通用的偏好函数。基于以上假设后,可以应用名义群体技术、DELPHI方法、层次分析法等方法以类似于单决策者的方式进行决策。但是,决策群体都同意一个公共的偏好函数,是不太实际的,特别是对于群体成员较多的情形,是非常困难或者根本无法得到公共偏好函数的。本文的目的,是将多目标粒子群优化方法应用于群体决策,决策者的偏好也以参考点表示,但不再直接使用分层排序或距离方式,而是在支配概念或者距离阈值下,使用了群体决策中应用最广的投票规则进行求解。我们的重点在于搜索群体关心的一小集合的Pareto最优解,并且用ZDT问题进行验证。1般mopso算法多目标优化问题(MOP)一般定义如下:其中X是Rn空间中的决策变量,D是其定义域,fi:Rn→R,i=1,2,…,k是目标函数;gi,hj:Rn→R;i=1,2,…,m;j=1,2,…,q是约束函数。对于多目标优化问题,一般没有一个使得所有目标函数均为最优的解,所以采用的多是Pareto解。在MOPSO中,由粒子群到当前为止所发现的非支配解都存储在外部种群档案(externalarchive)中。每个粒子除了向自己所经历的某个非支配历史位置(pbest)学习外,同时从外部种群档案中按照一定规则选择一个解作为引导者(leader)。外部种群档案随着计算的进行不断更新,其所包含的解在运行结束时一般也是最终输出结果。一般MOPSO流程如下:算法1一般的MOPSO算法BeginInitializeswarmInitializeleadersinanexternalarchiveQuality(leaders)Iteration=0While(Iteration<max_Iteration)ForeachparticleSelectleaderUpdatePosition(Flight)MutationEvaluationUpdatepBestEndForUpdateleadersintheexternalarchiveQuality(leaders)Iteration++EndWhileReportresultsintheexternalarchiveEnd其中“Quality(leaders)”一般是计算粒子的拥挤距离或适应度或其它粒子密度的评价值,以便后面有一定规则为每一粒子从外部种群档案中选择leader,使得粒子在向Pareto前沿飞翔的同时保持较好的分布性。在MOPSO中,各种算法不同的地方,主要在于外部种群档案的设计及剪枝策略、leader的选择方法、pbest的更新方法。2基于选定的mopso参数2.1群体偏好信息在决策者偏好信息方面,有多种表示方式。决策者不同,其给出的偏好信息也会不相同。在相关文献中,主要有以下几种方式:目标的重要性优先次序,目标的重要性权重,参考点,参考区域,参考方向等定义。本文假设群体成员的偏好信息以参考点表示。偏好参考点表示用户的期望目标,表现为目标空间中一个点。设群体中有N个决策者,每个决策者偏好都用一个参考点Rn(Rn1,Rn2,RnNF),n=1,2,…,N描述,NF是目标函数个数。任一解x与参考点的距离用欧几里德距离公式定义:(2)其中fi是第i个目标函数,fmaxiimax(x)、fminiimin(x)是第i目标函数的最大值、最小值,其作用在于进行规范化。2.2决策参与规则收集好群体成员的偏好后,进行决策时,就要根据不同的决策方法对其偏好进行整合,以期找到群体偏好的解。在群体决策中,应用最广的是投票方法,群体成员根据每个人自己的偏好,对决策方案进行投票,然后进行汇集,根据约定的规则,选择最后方案。应用最多的是多数规则,即多数决策者同意的解是最终群体解,但也有其它规则。对于以参考点表示的群体成员偏好,我们定义如下的投票规则,以应用多目标优化方法进行求解。(1)参与群体成员的参考点定义1(基于支配的解定义)某个解是群体决策的完全一致解,当且仅当它是非支配解并且它支配所有群体成员的参考点。定义1对解的要求非常高,很容易无解。如果某个参考点不在可行域,则此方法将找不出任何解。此方法也叫一票否决制。定义2(基于距离的解定义)某个解是群体决策的完全一致解,当且仅当它是非支配解并且它与所有群体成员的参考点的距离都小于阈值δ。(2)支配多数群体成员的参考点定义3(基于支配的解定义)某个解是群体决策的绝对多数决定解,当且仅当它是非支配解并且它支配多数群体成员的参考点。定义4(基于距离的解定义)某个解是群体决策的绝对多数决定解,当且仅当它是非支配解并且它与多数群体成员的参考点的距离都小于阈值δ。这里与完全一致是相近的,只是现在需要满足多数决策者参考点要求,而不是全部。按规则,多数可能是1/2或2/3等。(3)支配的参考点定义5(基于支配的解定义)某个解是群体决策的相对多数决定解,当且仅当它是非支配解并且它相对于其它解来说,支配更多的群体成员参考点。此定义不要求支配超过半数的参考点,只要求其相对其它解而言支配更多的参考点即可。定义6(基于距离的解定义)某个解是群体决策的相对多数决定解,当且仅当它是非支配解并且它相对于其它解来说,与更多的群体成员参考点距离小于阈值δ。此定义不要求与超过半数的参考点距离小于阈值δ,只要求其相对其它解而言与更多的参考点距离小于阈值δ即可。根据以上定义,在搜索群体解时,即是搜索既靠近Pareto前沿而又满足基于支配概念或距离概念下投票规则的解。2.3嵌入操作机制的ledas更新规则以参考点定义用户偏好后,MOPSO所要找到的解除了满足收敛到Pareto前沿并具有分布均匀特点外,还要靠近群体的偏好域。以下介绍解决群体决策问题的基于参考点和相对多数决定投票规则的MOPSO算法策略:(1)基于投票机制的锦标赛选择leader的方法首先对外部种群档案按其支配的参考点个数(或距离阈值δ内的参考点个数)进行排序,支配参考点(或距离阈值δ内的参考点个数)较多的前50%精英粒子作为候选粒子。然后采用锦标赛方式,从候选粒子中选择支配参考点个数(或距离阈值δ内的参考点个数)较多的解为leader。本文采用的锦标赛规模为2。(2)嵌入投票机制的pbest更新规则从当前粒子和历史最优中选择两者中非支配解为pbest;若相互不支配,则选择支配参考点个数(或距离阈值δ内的参考点个数)较多的解为pbest;若相互不支配,支配参考点个数(或距离阈值δ内的参考点个数)又一样,则随机选择一个为pbest。(3)外部种群档案leaders更新规则若当前粒子相对整个外部种群档案中粒子而言为非支配解,则加入到外部种群档案中。并删除外部种群档案中被新加入粒子支配的解。(4)嵌入投票机制的外部种群档案剪枝规则档案容量超过预设大小时,如果其中的粒子支配参考点个数(或距离阈值δ内的参考点个数)不一样,则首先删除支配参考点个数(或距离阈值δ内的参考点个数)少的粒子。如果每个粒子支配的参考点个数(或距离阈值δ内的参考点个数)都一样,则去除密度较大的粒子,以达到均匀分布要求。基于参考点和投票机制的MOPSO群体决策方法,主要是在各步骤中嵌入了投票规则,使得粒子向与群体多数决策者偏好的Pareto前沿收敛。因为只用找出部分的Pareto前沿,在种群规模、进化代数方面可以大大减少,使得算法的效率更佳。3模拟实验3.1zdt1优化问题ZDT1问题具有凸的、连续的Pareto前沿。以下实验均以ZDT1优化问题为例进行说明。多目标粒子群算法的种群大小是100,最大进化代数为100,外部种群档案大小为20,距离阈值δ=0.3。(1)基于距离阈值的正演分析假设三位决策成员偏好的参考点分别是(0.2,0.9)、(0.3,0.8)和(0.8,0.3),它们均位于可行域。为了节省篇幅,基于支配概念和基于距离阈值下应用相对多数投票规则运行的结果显示在一起,如图1所示。从图1可以看出,对于参考点均是可行点而言,基于支配概念或距离阈值应用投票规则均可以得到群体决策解,两者解稍有不同,但对于决策而言影响不是很大。(2)群体解的验证三位决策成员偏好的参考点分别是(0.1,0.6),(0.2,0.5)和(0.8,0.3),它们均位于不可行域。结果如图2所示。从图2可以看出,对于参考点都在不可行区域的情况,基于距离与基于支配概念的群体决策结果非常不一样。基于支配概念的解,分散于整个Pareto前沿,实际上其支配的参考点数目都是0,可以认为此时没有找到群体解。但基于距离的方法可以求出与多数参考点相近的部分Pareto前沿,与多数规则相符合。(3)基于距离和选举规则的多目标优化分两种情况讨论。第一种情况是可行参考点较少,不可行参考点较多,结果如图3所示。可以看出,基于支配概念与基于距离概念的解相差悬殊,同样可以看出,基于距离概念所得到的群体解,与大部分决策成员的意愿较相近,而基于支配概念的解只与少数参考点在可行域的决策者意愿相近。第二种情况是可行参考点较多,不可行参考点较少,结果如图4所示。结果与图1是几乎一样的。从以上仿真结果可以看出,在决策者给出其偏好参考点情况下,基于距离和投票规则的多目标粒子群优化方法都可以用较小的种群规模和较少的进化代数就可以找出分布较好、与真实Pareto前沿贴近的,并较符合群体偏好的部分Pareto解,这对于加快群体决策是非常有益的。而基于支配概念的方法对参考点的要求较高,只在部分情况下可以求出相应较符合群体意愿的解。所以后面实验只以基于距离和投票规则进行说明。3.2因素参考点ZDT3问题的Pareto解是非连续的。实验中设置了四位决策者的参考点,距离阈值δ=0.4,结果如图5所示。从图5可以看出,对于非连续的多目标优化问题,基于距离和投票规则的粒子群算法,也可以找出较好的群体解。3.3外部种群档案粒子输出对于绝对多数决定和完全一致决定,算法主要过程与相对多数决定是一样的,只在最后一步“外部种群档案中的最终leaders为结果”要进行修改,不能输出全部