多目标群体智能算法eMOFEOA的效果

2023-11-26 理论教育版权反馈

【摘要】：基于此，对eMOFEOA算法不同世代的烟花种群采用非线性递减的半径变化方式，而在同一代群体内则基于个体间Pareto支配强度的差异而被赋予不同的爆炸半径。选择火星eMOFEOA算法均匀随机初始化种群之后，从第二代起将当前种群中每一个个体都视为一个炸点，这些炸点爆炸后将会产生大量的火星，这些火星与炸点一起进行评估以选择出较优的火星(炸点)参与下一次爆炸。

(1)种群初始化方法

初始种群分布性对EA算法的性能有重要影响，为提高MOEA算法的解题性能，我们采用一种均匀化与随机化相结合的方法初始化种群。该方法的原理是将决策向量x中任意一维决策变量xi(i＝1，2，…，n)均匀划分成与种群规模相等的若干等长的子区间，初始代个体在任一基因位上的取值需要首先随机选定子区间，然后再在选定的子区间内产生随机值而获得。均匀划分后的各子区间有且仅有一次机会产生基因值，这样可在最大程度上保证初始群体基因的多样化。算法4.6给出了种群多样性的初始化算法的流程。

这种初始化方法既保持了选取子区间以及从子区间中产生基因值的随机性，又保证了决策变量区间划分的均匀性，算法执行的结果可获得一组在决策空间中均匀分布的初始解点，这就为算法的搜索提供了一个良好的开端。

(2)烟花爆炸半径精细化控制

基于烟花爆炸优化的方式如下:首先利用算法4.6产生规模为N的初始种群，即确定第一次爆炸的炸点位置，用以表征问题的初始解。例如，在n维搜索空间的第i个炸点可表示为xi＝(xi，1，xi，2，…，xi，n)，并设炸点执行均匀爆炸且预设的最大爆炸半径为r，即火星最大散开区域。若炸点爆炸的层数为w，那么每一层爆炸半径则为j·r/w(j＝1，2，…，w)。已有FEA算法一般将爆炸半径r设置为随迭代次数的增加而呈非线性递减的方式，以保证算法在初期可以执行全局勘探，而在算法末期执行最优前沿附近的局部精确搜索。

需要指出的是，现有烟花爆炸半径的变化仅局限于对烟花的群体采用逐代递减的策略，而并未考虑到同一世代的烟花因其支配强度的差异而赋予不同的爆炸半径。例如，在复杂多目标优化环境下，对于相同世代的烟花弹，非支配个体具有相对较好的质量，它们更靠近Pareto前沿，因而应在较小的邻域内进行求精；而那些被支配的个体质量相对较差，它们一般离Pareto前沿较远，其应在较大的邻域空间内进行勘探。通过精细化分配有限的搜索资源，可改善算法寻优的效率。基于此，对eMOFEOA算法不同世代的烟花种群采用非线性递减的半径变化方式，而在同一代群体内则基于个体间Pareto支配强度的差异而被赋予不同的爆炸半径。

下面给出同一代烟花群pop(t)中各烟花弹爆炸半径的计算方法。

基于Pareto关系计算第t代种群pop(t)中个体i的强度值fitnesst(i):

其中表示集合的势，即个体i占优群体内其他个体的数目。

计算第t代种群pop(t)的最大适应值fitness pagenumber_ebook=102,pagenumber_book=93 :

计算第t代种群pop(t)的爆炸半径r(t):

计算个体i∈pop(t)的爆炸半径ri(t):

第3步中r(t)通过缩放参数k将每一代烟花群体中各烟花弹的搜索范围控制在一个适当的范围内，其中Dmax和Dmin分别表示当代种群中所有个体各维决策变量中的最大值和最小值，α表示爆炸半径的衰减指数。第4步中引入最小正数η以防止分母为0，rend为预设的最小爆炸半径。而对于炸点i，其爆炸产生的火星计算方法如下:

xi为炸点i的当前位置，x∗i为炸点i爆炸产生的火星位置。考虑到算法在实际执行过程中由于时空资源的限制，同时也为了保证有足够的火星产生，这里规定火星与炸点之间的距离只有r/4，r/2，3r/4和r四种情况，且r＝r(t)表示第t代爆炸点的半径，因此式(4.24)的爆炸半径r1＝r，r2＝3r/4，r3＝r/2以及r4＝r/4。bk(k＝1，2，…，m)为爆炸的方向向量，m为烟花弹i爆炸的总方向数。对于低维度的搜索空间(如n≤10)，算法选择直观的标准坐标轴爆炸方向，即n维搜索空间问题的爆炸方向数为2n。但对于高维度的搜索空间(如n>10)，若仍采用2n个爆炸方向，则算法消耗的时空资源过大。因此在高维搜索空间中，每层爆炸方向采用从2n个标准坐标轴方向中随机选择n/3个方向，再加上每个方向的相反方向，构成2n/3个爆炸方向。

烟花爆炸时炸点和火星可能会越界，需要对它们的位置边界进行限制。设xi(i＝1，2，…，n)为n维搜索空间中任一维决策变量，且xi∈[ai，bi]，如果炸点x爆炸过程中产生的火星xj跳出边界[ai，bi]成为非可行解，则将xj在第i维决策变量上的值xji按式(4.25)进行重置，以改善搜索的有效性。(www.chuimin.cn)

其中，rand(·)是区间[ai，bi]上均匀分布的随机数。

(3)选择火星

eMOFEOA算法均匀随机初始化种群之后，从第二代起将当前种群中每一个个体都视为一个炸点，这些炸点爆炸后将会产生大量的火星，这些火星与炸点一起进行评估以选择出较优的火星(炸点)参与下一次爆炸。算法4.7给出了从炸点和火星集合中选择较优个体参与下一代进化的过程。

　　需要指出的是，步骤3和步骤5中较好个体选择的依据是个体适应度值进行的。

(4)档案群体多样性维护

随着进化过程的推进，MOEA算法种群中非支配解快速增多，而外部档案的规模受到计算资源的限制一般设置为固定大小，因此需要对档案进行修剪，并维持档案群体的多样性。

迄今已发展了多种多样性保持方法，其中代表性的包括:PAES算法中的自适应网格法[48]、NSGA-Ⅱ中计算拥挤距离的方法[22]、SPEA2中的k-最近邻方法[23]和Deb等提出的ε占优[27]等，其中以k-最近邻方法表现尤为突出。k-最近邻方法将个体的密度值定义为个体与它的第k个最邻近个体之间的距离，且取，其中NP为种群规模，N′为外部档案的最大容量。

在SPEA2算法运行过程中，若档案规模已达到上限，则档案中每加入一个新解就要从中移出一个个体，比如个体A，个体A应满足:对于档案中所有的个体B，A<dB成立。其中A<dB定义为当且仅当对于所有的l＝1，2，…，N′:DlA＝DlB；或者对于某个l，DlA<DlB，而对于任意的l′<l:Dl′A＝Dl′B。其中DlA(DlB)定义为个体A(B)与它的第l个最邻近个体的距离。不难发现，这种解个体密度的估计过程较为复杂，而且需要对所有的个体和所有的l＝1，2，…，N′比较个体间Dl上的差异，时间开销较大。

因此，我们使用一种简化的k-最近邻方法保持档案群体的多样性。简化方法中取k＝log(NP＋N′)，其个体密度的估计方法可定义如下:A<dB当且仅当对于l＝1，2，…，k:DlA＝DlB；或者对于某个l≤k:DlA<DlB；而对任意的l′<l:Dl′A＝Dl′B。由于简化后的k小于原方法中的k，因此，简化后的k-最近邻方法在时间复杂度上会有所改善。

(5)eMOFEOA算法流程

在前面几小节的基础上，下面给出eMOFEOA算法的流程，如算法4.8所示。

假设待优化问题的目标数目为m，决策空间的维度为n，种群规模为N，外部档案最大容量为N′，算法最大迭代次数为Tmax，则eMOFEOA算法的时间复杂度可分析如下:

算法第1步中生成多样性的初始种群的时间为O(nN)，将种群中非支配解复制到外部档案所需要的时间是O(mN2)，因此算法第1步所消耗的时间为O(nN)＋O(mN2)＝O(mN2)。算法从第2步开始进入迭代循环过程，在循环体内部存在烟花爆炸产生火星的过程(步骤3至步骤5)，其中一个烟花产生火星所需要的时间复杂度是O(8n2/3)，那么N个烟花产生火星所需要的时间复杂度则为O(8Nn2/3)。步骤6利用归一化排序方法构造非支配集更新群体所需要的时间复杂度为O(m(N＋N′)log(N＋N′))。步骤7利用简化的k-最近邻方法维持外部档案的多样性所需的时间复杂度为O(m(NP＋N′)2 log(NP＋N′))。步骤8所需的时间复杂度是O(1)。因此，循环体内部的时间复杂度应为O(8Nn2/3)＋O(m(N＋N′)log(N＋N′))＋O(m(NP＋N′)2log(NP＋N′))＋O(1)＝O(m(NP＋N′)2 log(NP＋N′))。由于算法一共执行了Tmax次迭代，因此算法迭代部分的时间复杂度为O(Tmaxm(NP＋N′)2log(NP＋N′))。算法最后输出档案中全部的解个体所需要的时间复杂度是O(N′)。

综上所述，eMOFEOA算法的时间复杂度应为O(Tmaxm(NP＋N′)2log(NP＋N′))，亦即，eMOFEOA算法的复杂度取决于档案群体修剪方法的复杂度。

多目标群体智能算法eMOFEOA的效果

相关推荐