在多目标粒子群优化 (MOPSO) 的设计中，管理收敛性和多样性是至关重要的，以搜索真实Pareto最优前沿的准确和良好分布的近似。粒子群优化算法由于其快速收敛性，在进化过程中会导致多样性的快速丢失。现有的MOPSOs在 leader selection、archive maintenance(归档集维护) 和 perturbation(扰动) 等方面提出了许多机制来解决这一不足。
然而，很少有多目标粒子群算法根据从进化环境中检测到的反馈信息来动态调整探索和利用的平衡。本文提出了一种新的方法 parallel cell coordinate system (PCCS)，该方法分别基于平行细胞距离(parallel cell distance)、潜能(potential) 和分布熵(distribution entropy) 的测量来评估包括密度(density)、等级(rank) 和多样性(diversity) 指标在内的进化环境。在 PCCS 的基础上，将提出的选择全局最优(global best) 和个体最优(personal best)、保持归档(maintaining archive)、调整飞行参数(adjusting flight parameters) 和扰动停滞(perturbing stagnation) 等策略集成到一个自适应 MOPSO ( pccsAMOPSO )中。对比实验结果表明，在 ZDT 和 DTLZ 测试集上，本文提出的 pccs AMOPSO 在所选性能指标上优于其他 8 个最先进的竞争者。MOPSO 中密度估计的附加实验表明，PCCS 在收敛性和多样性方面的性能优于自适应网格和拥挤距离。
为了在算法找到的近似Pareto前沿上取得良好的收敛性和多样性，需要一种机制来评估achieve中每个非支配解的环境适应度，以及整个种群的进化状态。更重要的是，该机制需要决定哪些解决方案更适合被选为领导者，或者在存档已满的情况下被丢弃，以容纳新的合格解决方案。如第二节所述，拥挤距离、自适应网格、非支配排序等是最流行的方法，尽管它们存在一些缺点。
Parallel coordinates 平行坐标[49]，[59]是可视化高维几何和分析多元数据的流行方法。受此启发，我们提出了一种新的机制PCCS来评估MOPSO中的进化环境。
在 PCCS 中，根据式(1)将存档 f k , m ， k = 1 ， 2 ， . . ， K ， m = 1 ， 2 ， . . ， M f_{k,m}，k = 1，2，..，K，m = 1，2，..，M f k , m ， k = 1 ， 2 ， .. ， K ， m = 1 ， 2 ， .. ， M 中第 k k k 个非支配解的第 m m m 个目标映射为 K × M K × M K × M 个单元格的二维网格内的整数标号，其中 K K K 为当前 archive 的大小， M M M 为 MOP 中的目标数
其中，
[x]
是一个 ceiling operator，返回不小于
x
x
x
的最小整数，
f
m
m
a
x
=
m
a
x
k
f
k
，
m
和
f
m
m
i
n
=
m
i
n
k
f
k
,
m
f^{max}_m = max_k f_{k，m}和f^{min}_m = min_k f_{k,m}
f
m
ma
x
=
ma
x
k
f
k
，
m
和
f
m
min
=
mi
n
k
f
k
,
m
分别是 archive 中第
m
m
m
个目标的最大值和最小值。
L
k
,
m
∈
1
,
2
,
.
.
,
K
L_{k,m}∈{ 1,2,..,K }
L
k
,
m
∈
1
,
2
,
..
,
K
是由实数
f
k
,
m
f_{k,m}
f
k
,
m
归一化后转化而来的整数。若
f
k
,
m
=
f
m
m
i
n
f_{k,m} = f^{min}_m
f
k
,
m
=
f
m
min
，且在特殊情况下避开零作为分母，则
L
k
,
m
L_{k,m}
L
k
,
m
设为 1.
值得注意的是，K不是一个新的用户自定义参数，而是随着当前archive的大小而动态变化，并以最大archive的大小为界。在非支配archive中，如果所有非支配解都完美地分布在近似帕累托前沿中，则每个解在每个维度上都被期望独占一个单元格。因此，在 PCCS 中，当 f m m a x 、 f m m i n f^{max}_m 、 f^{min}_m f m ma x 、 f m min 或 archive 大小中的任意一个发生变化时，单元格的长度都会自动调整。
图 1 给出了 PCCS 中的一个映射实例。在左子图上，为了简化，从具有三个目标的 DTLZ1 的 Pareto 前沿中任意采样的存档中只有9个非支配解。将归档映射为PCCS后，网格中的9行和3列显示在右子图上，分别对应归档中的9个解和MOP中的3个目标。在右子图上，左子图中解的每个目标被映射到右子图中唯一的细胞坐标。所有由解对应单元格坐标的标号编号表示的 components 都通过虚线连接起来以清晰显示。例如， P 4 P_4 P 4 的晶胞参数为 (6,2,2)。
笛卡尔坐标系中的任意一组点都可以用二维网格中的单元格坐标来表示，通过平行轴的方式可以直观地将其可视化。因此，这里我们称之为Callitpccs。
许多 MOPSO 算法在 selecting leaders 或 updating the archive 时，通常会参考环境适应度，如 density 和 ranking 。在这里，我们将利用 PCCS 来评估 archive 中非支配解的环境适应度。
在 PCCS 中，two vectors in the unit of cell 之间的距离，称为平行单元距离 (Parallel Cell Distance，PCD)，是所有目标上的单元坐标之差的总和。两个非支配解 P i P_i P i 和 P j P_j P j 的 P C D ， P C D ( P i , P j ) PCD，PCD(P_i , P_j) PC D ， PC D ( P i , P j ) ，在 PCCS 中通过 (1) 式分别映射到 L i , m L_{i,m} L i , m 和 L j , m L_{j,m} L j , m 后，可根据 (2) 式计算得到
在 (2) 中，如果 P i P_ i P i 和 P j P_ j P j 在 PCCS 中的所有 M 维映射到相同的 cells，PCD 值被设置为 0.5 以避免 (3) 中的除零。
由 archive 形成的超空间中 P i P_i P i 的密度可以通过 P i P_i P i 与 archive 中所有其他成员 P j ( j = 1 , 2 , . . . , K , j ≠ i ) P_j ( j = 1,2 , ... , K , j ≠ i) P j ( j = 1 , 2 , ... , K , j = i ) 之间的 PCD 来测量。
由(3)式可知， P i P_i P i 的密度受其所有邻居的影响。近邻越靠近 P i P_i P i ，密度对 P i P_i P i 的贡献越大。archive 中具有最小密度的解将被选为领导者组中的多样性 gBest (d-gBest )，将在第四节中详细描述。然而，当 archive 中没有空间容纳新的非支配解时，具有最大密度的解将被认为是被丢弃的候选解。
在多目标粒子群算法中，将非支配解排序用于 leader selection 是另一个重要问题，以加速近似帕累托前沿向真实帕累托前沿收敛。
在这里，我们介绍了一种新的基于势概念的排序方法，该方法可以与密度同时计算。势在物理学中被称为势能。预计每一项的势能档案中的个体通过进化过程逐渐减小到稳定状态，以提高收敛性。archive 中非支配解 P i P_i P i 的潜力 (potential energy) 由式( 4 )定义：
势通过结合PCCS中沿优化方向的序关系和单元内的度来量化存档中其竞争者之间的一个非支配解。。一个最小化MOP的解的潜力越小，该解越有可能接近真实的帕累托前沿。因此，具有最小势能的解优先被选为 leader group 中的收敛gBest (c-gBest)，在第四节中进行了详细的描述。图 2 给出了一个对存档中非支配解进行排序的例子。在图 2 中，提出的 pccsAMOPSO 在优化 ZDT4 时，在第 64 代获得了近似Pareto前沿。ZDT4是一个MOP来验证算法的收敛能力，因为它的目标空间有219个局部Pareto前沿[47]。为了简单起见，本例中存档的最大大小设置为 9。这九个非支配解在近似Pareto前沿中的笛卡尔坐标和平行单元格坐标列于表 I。图2中这九个解的潜力也列于表 I。P6在当前代中具有最小的潜力，7，是这九个非支配解中最有希望接近真实Pareto前沿的解。因此，P6是 c-gBest 引导整个种群尽可能早地向真实帕累托前沿移动的最佳候选。
如果我们能够从进化环境中概率地推断进化状态，如收敛(convergence)、多样性 (diversity) 和停滞(stagnation)，那将是探索和利用平衡中更有效的策略。 global archive 中的时变(time-varying) 内容可以很好地表达当前和历史上整个种群的环境信息，包括支配关系(dominance relation)、多样性 (diversity) 和均匀性 (uniformity)。因此，基于这些考虑，我们试图基于熵及其变化熵的概念来估计 MOPSO 的进化状态，以设计一种自适应策略来调整 PSO 的 flight parameters，以平衡开发和探索。
archive 中非支配集的熵衡量了近似帕累托前沿的均匀性。PCCS 中熵的定义如式 (5)所示：
这里， C e l l k ， m Cell_{k，m} C e l l k ， m 是在PCCS的第 t t t 次迭代中，位于第k行和第m列的单元格中标号为 L k ， m L_{k，m} L k ， m 的成员个数。给定一个空单元格 (empty cell)，使得 C e l l k , m ( t ) = 0 Cell_{k,m} (t) = 0 C e l l k , m ( t ) = 0 ，则其对熵的贡献为零。
计算时间步长 t 和 t - 1 之间的熵变化 Entropy
图3是本文提出的pccs AMOPSO在ZDT4整个进化过程中检测到的熵和Entropy的变化曲线。
从图3中可以观察到3种情况。首先，在整个演化过程中，熵值不断增加，以获得分布良好的近似帕累托前沿。如果每个单元格只包含解的一个分量，那么它将是具有最大熵的近似Pareto前沿的最佳分布。第二，熵的曲线有几个突变点。这些突变波动在前期(当 t < 60 时,不同的 MOP 和算法的划分值可能不同)分布密集，中期( 60 < t < 170 )分布稀疏，后期( t > 170 )分布稀少。这些大规模再分配的突然变化是由新的解决方案引起的，具有进入存档的资格，这支配了一些从存档中移除的旧解决方案。这一现象表明种群正在向真正的帕累托前沿迈进。我们称这种情况为一种收敛状态。第三，在大多数世代中，熵的曲线有许多轻微的变化。这些温和的变化是由新解产生的，也有进入存档的资格，因为新解的密度比旧解的密度小，所以只能替换一个旧解。我们将这种情景视为多样性状态。当然，如果熵曲线没有明显的变化，就称之为停滞状态。
图 4 给出了突变和缓变的一个简化例子。在图 4(a) 中，在一个熵为 2.30 的均匀分布的存档中存在五个非支配解。在图 4(b) 中，我们得到了一个新的笛卡尔坐标为 (6、3) 的解 P 6 P_6 P 6 支配 3 个 old solutions. ， P 1 ， P 2 P_1，P_2 P 1 ， P 2 和 P 3 P_3 P 3 分别以笛卡尔坐标(6、5)，(7、4)和(8、3)，熵突然减小到1.56。在图 4©中，一个较好的解 P 7 P_7 P 7 用密度较小的笛卡尔坐标(8.2,1)代替旧的解 P 4 P_4 P 4 用笛卡尔坐标(9、2)，如果(仅供参考)此时 archive 的最大尺寸重置为 3，熵略微增加到 1.79。值得注意的是，熵的突变和缓变与 archive 的大小有关。
这三种状态可以根据(6)中的熵来检测。当轻微变化发生时，通过估计熵的最大变化，可以确定区分收敛状态和多样性状态的阈值。在温和变化的情况下，我们假设，在最坏的情况下，旧解在所有目标上与其他非支配解共享所有的单元坐标，而新解在每个目标上占据空白单元(blank cells)。因此，熵的阈值δ是熵的最大可能变化，可以用下式来估计
我们可以将位于某一目标边界内的新解引起的 f m m i n f^{min}_m f m min 或 f m m a x f^{max}_m f m ma x 的变化视为特殊情况下的突变。
阈值δ是划分进化地位的标准，是选择进化地位的重要依据
selecting candidates for the leader group 并根据进化环境自适应PSO中的 flight parameters，以有效管理探索和利用，将在下一节中描述。
图 5 给出了该算法的所有组成部分，即基于PCCS的自适应 MOPSO (pccsAMOPSO)。下面对pccsAMOPSO的功能进行概述。
对于求解多目标优化问题，pccsAMOPSO 中含有 N 个粒子的 PSO 种群打算搜索一组非支配解，以预定义的最大尺寸存储在 global archive (gArchive) 中。初始化PSO种群后，每个粒子都会向其个人最优 (pBest) 和全局最优 (gBest) 引导的方向飞行。粒子的 pBest 选自 personal archive (pArchive)。粒子的 gBest 从 leader group 中选择，the leader group 由M(目标数量)个 rank 最小的 convergence gBests (c-gBests) 和gArchive中密度最小的M个多样性 gBests (d-gBests) 组成。pArchive 和 gArchive 由粒子根据归档更新算法找到的新解进行更新，归档更新算法是指由PCCS评价者评估的归档中每个非支配解的密度和 rank 。粒子通过 a flight controller 更新位置和速度，a flight controller 响应动力学参数和扰动信息。PSO parameter adapter 根据 PCCS Evaluator 检测到的进化环境的反馈信息 Entropy 来调整动力学参数 ω 、 c 1 ω、c_1 ω 、 c 1 和 c 2 c_2 c 2 。扰动信息由扰动器(perturbator)提供，以协助粒子逃离局部Pareto前沿。
pccs AMOPSO的关键部件详述如下：
类似于许多MOPSO，以及最近的MOEAs，pccsAMOPSO 还使用了一个具有 external repository with a prefixed maximal size 来存储所有粒子迄今为止找到的最佳非支配解的历史记录。在这里，我们称这个存储库为 global archive (gArchive)，因为其中的成员是全局最优解，它是从所有个人最优解中选择出来的。算法停止后，gArchive报告其内容作为算法的输出。
如果一个粒子找到的新解被已经在 gArchive 中的任一成员所支配，或者它的密度大于 gArchive 中任一成员在 gArchive 中满时的密度，那么这个解将被拒绝，不允许进入 gArchive。The updating algorithm of an archive，包括 gArchive 和 personal archive (pArchive)，如算法1所示
archive 中的任何非支配解都可以作为群体中粒子的gBest。然而，我们希望确保种群中的粒子在搜索空间中朝着更稀疏和更有前景的区域移动。为了更好地平衡开发和探索，所提算法从 gArchive 中选择一组存储在 Lead Group 中的 Leader，而不是现有 MOPSO 中所有粒子只选择一个 gBest 或者每个粒子选择不同的 gBest。The lead group 由 convergence gBests (c-gBests) 和 diversity gBests (d-gBests) 组成。
在每一代中，从gArchive中重新选择 leader group，由算法1对种群找到的新解进行更新。为了避免收敛到gBest所在的一个解或局部区域，在近似帕累托前沿中，选取由式(4)计算得到的潜力最小的gArchive中前M个(目标数)非支配解作为c-gBest，选取由式(3) 计算得到的密度最小的前M个非支配解作为 d-gBest。因此，领导者群体中有 2M 个理想解作为 gBest 的候选解，以平衡收敛性和多样性。
然而，对于每一代中的某个粒子，只有一个gBest从 leader group 中被选中。因此，使用环境信息 Δ \Delta Δ Entropy，来决定领导者组中的哪个候选者更适合当前情况下的粒子。对于一个粒子，从leader group中选择一个gBest有两个步骤。
第一步，根据(8)式，从 c-gBest 或 d-gBest 中概率地确定候选者的类型。
式中：δ为熵的阈值，定义在式 (7) 中，在第 III-C 节中分析，用于区分收敛状态、停滞状态和多样性状态。因此，当随机值大于 P r Pr P r 时，选择c-gBest类型；当随机值大于 P r Pr P r 时，选择 d-gBest 类型，比率为 1-Pr。
在第二步中，从第一步中选择的gBest中随机抽取一个候选，或者从M c- Best中随机抽取一个候选来促进收敛，或者从M d-gBest中随机抽取一个候选来提高多样性。
在大多数MOPSOs中，如果前一个pBest被新解支配，则由该粒子找到的新解来更新pBest；如果前一个pBest和新解互不支配，则在前一个pBest和新解之间随机选择pBest。在这些MOPSOs中，重要的信息用于对其当前landscape中的一个粒子描绘有前途的进化方向被丢失，因为单独一个解不能有效描述其 personal approximate Pareto front，只有少数的 MOPSOs [45]使用 personal archive (pArchive) 来存储粒子到目前为止发现的个人非支配解。在该算法中，每个粒子使用一个 pArchive 来存储类似于 gArchive 的个体非支配解，pArchive 也由算法1维护。但是，为了降低计算成本，pArchive 的最大前缀大小可以远小于 gArchive。例如，对于 pArchive，gArchive的四分之一前缀大小是经验性建议的。
粒子的另一个重要问题是如何从 pArchive 中选择一个 pBest，利用其 personal knowledge 指导该粒子。在PSO中，一个粒子将在其pBest和gBest共同引导的方向上飞行，最终在 ( c 1 r 1 ⋅ p B e s t + c 2 r 2 ⋅ g B e s t ) / ( c 1 r 1 + c 2 r 2 ) (c_1r_1 · pBest + c_2r_2 · gBest) / ( c_1r_1 + c_2r_2) ( c 1 r 1 ⋅ pB es t + c 2 r 2 ⋅ g B es t ) / ( c 1 r 1 + c 2 r 2 ) [46] 点停止，如果pBest和gBest停滞不前。在多目标粒子群算法中，pArchive 所呈现的个人近似 Pareto 前沿通常与 gArchive 所呈现的个人近似 Pareto 前沿并不相同。同时，gBest 在 MOPSO 中的变化频率高于 SOPSO. 然而，为了及时追踪粒子的 gBest，相应粒子的 pBest 应该与其 gBest 合作，以指导最有前途的飞行。因此，对于一个粒子 i i i ，它的 pBest 将根据由它的 pArchive 中的四个顶点，它的位置 x x x ，它的速度 v v v ，它的gBest和候选的 p B e s t k ( k = 1 , 2 , . . . , K ) pBest_k ( k = 1,2 , ... , K) pB es t k ( k = 1 , 2 , ... , K ) 围成的最小超盒从它的 pArchive 中选择 K 个个人非支配解。
给定粒子从其pArchive中选择pBest的简化方法如式(9)所示：
这里，d = 1，2，…，D 是决策变量的个数；K = 1，2，…，K，K是粒子pArchive的大小； L k , d m a x ( p B e s t k ) = m a x ( x d , v d , p B e s t k , d , g B e s t d ) ； L k , d m i n ( p B e s t k ) = m i n ( x d , v d , p B e s t k , d , g B e s t d ) ； p B e s t k , d L^{max}_{k,d} ( pBest_k ) = max(x_d , v_d , pBest_k , d , gBest_d)；L^{min}_{k,d} ( pBest_k ) = min (x_d , v_d , pBest_k , d , gBest_d)；pBest_{k,d} L k , d ma x ( pB es t k ) = ma x ( x d , v d , pB es t k , d , g B es t d ) ； L k , d min ( pB es t k ) = min ( x d , v d , pB es t k , d , g B es t d ) ； pB es t k , d 是pBest的第k个候选的第d个决策变量； g B e s t d gBest_d g B es t d 为其gBest的第d个决策变量，根据第III-B节已经选取。
PCCS评价器是该算法中的关键组件，因为它可以从gArchive中获取一些重要的环境信息，如密度(density)、潜能(potential)、熵(entropy)等，以 serve 于 gBest 选择、归档维护和参数调整。将 gArchive 映射到 PCCS 后，所有导出的信息都可以同步计算。对于一个包含 K 个成员和 M 个目标的档案库，评估环境信息的复杂度为 O ( M K 2 ) O(MK^2) O ( M K 2 ) 。
PSO中存在一种灵活的机制，通过简单地调整 ω 、 c 1 ω、c_1 ω 、 c 1 和 c 2 c_2 c 2 来平衡探索和利用。然而，为了合理地管理 MOPSO 的收敛性和多样性，需要获得环境信息来决定何时以及如何调整这些参数
熵的变化反映了PCCS的演化状态，在第三节中进行了详细的分析。因此，可以设计基于分布熵的参数自适应调整策略，有效地平衡MOPSO算法的收敛性和多样性。据我们所知，尽管SOPSO [31]，[40]中已有一些工作，但由于很难估计进化状态，MOPSO中自适应参数调整的工作很少。这里，自适应参数整定是基于对环境信息的反馈，而不是迭代计数器，如MOPSO中的线性递减惯性[3]。
值得注意的是，负熵已被用于构造耗散PSO [60]。然而，这里的熵是通过PCCS来测量的，以动态调整飞行参数。
在PSO中，较大的ω和c1以及较小的c2有利于全局探索，而较小的ω和c1以及较大的c2则倾向于促进局部开发[58]。在收敛状态下，新解周围的区域支配gArchive中的一些现有解，并有资格进入gArchive，是一个很有前途的区域，应尽快招募更多的粒子进行搜索。在这种情况下，根据第三节讨论的gBest选择策略，新解将被选择为 c-gBest，以更大的概率进入 leader group。相应地，较小的ω和c1以及较大的c2促使PSO收敛的策略将有利于推动近似帕累托前沿向前移动。相反，在多样性状态下，具有较大的ω和c1以及较小的c2的策略将增加近似Pareto前沿的多样性。当 population 处于停滞状态时，参数ω、c1和c2保持不变。基于以上考虑，pccsAMOPSO 中基于熵的飞行参数自适应策略ω、c1和c2分别可以表示为(10)、(11)和(12)
其中 S t e p ω Step_ω St e p ω ， S t e p c 1 Step_{c1} St e p c 1 和 S t e p c 2 Step_{c2} St e p c 2 分别是ω，c1和c2的值域区间，它们被从它们的上界到上界的最大生成 T m a x T_{max} T ma x 均匀地整除.根据[50]，ω的上界和下界分别设置为0.9和0.4；ω(t) 的初始值设定为其上界；c1和c2的上界均设置为2.5；c1和c2的下界均设为0.5；c1和c2的初始值均设置为它们的上界和下界的中间；而阈值δ是由(7)中基于熵确定的，熵是由PCCS计算得到的。
式(10) ~式(12)中，当收敛状态下0 < | Entropy | < δ时，参数ω和c1在时间上迅速减小到跟踪gBest；当多样性状态下| Entropy |≥δ时，参数ω和c1缓慢增加到充分利用邻域搜索空间。参数c2的作用与c1相反。我们将这种调整策略称为"快下慢上"。
图6给出了 pccsAMOPSO 在多模态 MOP 的代表ZDT4上进行自适应参数调整的例子，图3给出了与图6相对应的熵和Entropy在ZDT4上的变化曲线。在图6中，c1，c2和ω随着进化环境的变化而动态调整，通过熵检测，分别从1.5，1.5和0.9的初始值开始。在收敛状态(图3中| Entropy |≥δ)时，ω和c1在减小，c2在增大，以促进局部开采。在多样性状态(图3中0 < | Entropy | < δ)期间，ω和c1增加，而c2减少，以促进 global exploration.。
根据飞行方程，第i个( i = 1,2 , … , N , N为population规模)粒子沿着其pBest和gBest引导的方向飞行，改写为(13)，以突出时变参数 (time-varying parameters)
其中 d = 1，2，…，D 是决策变量的个数；w(t)，c1(t)和c2(t)根据环境信息Entropy由(10)-(12)动态调整；R1和r2是两个在(0、1)范围内均匀分布的随机变量；PBestd 和gBestd分别是第 i 个粒子的个体最优解和全局最优解的第d个决策变量。
粒子位置更新后，若 new solution 有资格进入，则算法1更新pArchive和gArchive。
在MOPSO中，快速收敛通常导致收敛到局部Pareto前沿。扰动算子可以帮助逃离局部帕累托前沿，提高探索能力。因此，自从第一个扰动方法在 MOPSO [19] 中被提出以来，几乎所有的MOPSO都采用了扰动算子。在本文中，我们采用带有高斯变异的精英学习策略(ELS) [40]作为扰动算子来加速收敛或逃离局部Pareto前沿。elitist learning 表现为
其中d是在决策空间的所有维度中随机选取的， x d u p p e r x^{upper}_d x d u pp er 和 x d l o w e r x^{lower}_d x d l o w er 分别为粒子在第d维的上、下边界. 分别, Gaussian(μ , σ2)是一个均值为μ，标准差为σ的高斯分布的随机数。
在这一部分中，使用两组 MOP 基准函数 ZDT 和 DTLZ，以及两类多目标进化范式 MOPSOs 和 MOGAs 来评估所提出的算法 pccsAMOPSO 的性能。
1) 测试问题： 本文采用了5个广泛使用的来自ZDT测试集[47]的双目标测试实例和7个来自DTLZ测试集[48]的三目标测试实例，将本文提出的算法与其他多目标进化算法进行比较。需要指出的是，测试实例ZDT5由于是布尔函数且需要二进制编码而被省略。每个测试实例的真实帕累托前沿( PF )中的特征、维度和样本容量如表II所示。
2) 对等算法： 为了验证本文提出的算法，实验中选取了8个最先进的MOEAs作为对等算法。这些算法可以分为两组。第一组是基于PSO的元启发式算法，包括sigmaMOPSO [26]，agMOPSO [19]，cdMOPSO [20]，clusterMOPSO [5]和pdMOPSO [15]。表3列出了这5种PSO算法和本文提出的pccs AMOPSO算法的特点和参数设置。表III中的PSO参数ω、c1、c2分别根据其原始建议设置。我们根据原始文献在MATLAB中开发了这五种比较算法。第二组基于遗传算法(genetic algorithm，GA) NSGA-II [25],1 [17], SPEA22 and MOEA/D [33]. 这些基于GA的算法的特殊参数是根据[33]设置的，其中MOEA/D和NSGA-II在ZDT测试集和DTLZ1-2上进行了比较。在基于遗传算法的算法中，交叉率为1.00，变异率为1/n，其中n为决策变量的个数。MOEA/D中的参数T (相邻子问题的个数)设置为20。MOEA/D中的参数H (总子问题的个数)对于两个目标和三个目标的测试实例分别设置为99和13。
3) 性能度量： 两个综合性能度量，即反向世代距离(IGD) [33]和超体积(HV) [61]，用于量化由算法得到的近似Pareto前沿的收敛性和多样性。对于IGD指标，需要测试实例的真实Pareto前沿来衡量性能指标。每个测试实例的真实Pareto前沿的样本量列于表II的最后一列。对于HV度量，体积是通过适当选择参考点的近似帕累托前沿计算得到的。对于所有测试实例，参考点的每个目标值都选择在整数值11处。
4) 仿真设置： 每个算法的种群规模和最大gArchive设置为100。每个粒子的最大pArchive大小设置为25。功能评价次数固定为30000次。由于测试算法是随机的，它们在每个测试实例上的性能是由30次独立运行得到的。所有的模拟都是在1.2 GHz CPU和4 GB内存的笔记本电脑上进行的。
5)实验结果： 9个对等算法在12个测试实例上生成的IGD的均值和标准差( Std.)的实验结果列于表4。这些测试算法中IGD的最佳值(最小值)在每个测试实例中都以黑体的形式显示出来。
由表4可知，本文算法在IGD方面优于其他多目标进化算法，因为pccsAMOPSO在ZDT1、DTLZ1-4和DTLZ6-7上获得了IGD的7个最佳值，而cdMOPSO和MOEA/D分别获得了其他测试实例的3个和2个最佳值。
为了说明研究结果的显著性，还从统计学意义上进行了非参数统计假设检验Mann-Whitney-Wilcoxon秩和检验[67]，用于比较pccsAMOPSO与其他算法的平均IGD。如果pccsAMOPSO算法产生的p-value，则pccsAMOPSO算法在每个测试实例上的IGD性能可能优于其他算法的( ’ + ')、相同的( ’ = ')或更差的( ’ - '). 而其竞争对手则通过双尾检验，在显著性水平为0.05的情况下，大于、等于或小于U检验的标准制表值。
表IV中的行得分显示了 ‘+’ 和 ‘-’ 的数量之间的差异，这给出了 pccsAMOPSO 和每个竞争算法在所有测试实例中的总体比较。例如，比较 pccsAMOPSO 和 MOEA/D，前者在9个测试实例(ZDT3、ZDT6、DTLZ1-7)上显著优于后者，在1个实例(ZDT1)上与后者几乎相同，在2个实例(ZDT2和ZDT4)上低于后者。在这种情况下，MOEA/D的最后一行和最后一列的得分由9-2计算得到7。
从表4可以看出，所提出的算法在四个竞争对手( agMOPSO、clusterMOPSO、pdMOPSO、NSGA-II)中获得了最高的分数( 12 )。在cdMOPSO上的最小得分是6，这表明pccsAMOPSO在大多数测试实例上普遍优于所有的同类算法。从目标个数来看，pccs AMOPSO在DTLZ系列三目标问题上的表现明显优于ZDT系列两目标问题。例如，pccs AMOPSO在DTLZ系列上优于除cd MOPSO在DTLZ5上外的所有竞争者。在ZDT系列上，MOEA / D在ZDT2和ZDT4上优于pccsAMOPSO，表明MOEA / D在复杂多峰双目标多目标优化问题上是有效的，因为它是通过分解进行单目标优化的，但在处理不连通的双目标多目标优化问题时，MOEA / D对预定义的权重表现敏感。相反，cdMOPSO在ZDT3和ZDT6上优于pccsAMOPSO，这表明由于拥挤距离的度量，cdMOPSO在不连通的两个目标MOPs中是有效的。
由表4可知，9种竞争算法在所有12个测试实例上的平均IGD排序结果如表5所示。例如，表5中pccsAMOPSO的 rank 1 值为 7，这意味着pccsAMOPSO在表IV中的9个对等算法中的12个测试实例上获得了7个最佳( rank 1 )的IGD均值。一般来说，较小的最终秩和较高的最终秩出现频率表明算法的性能较好。阴影区域表示特定测试算法的行列范围。阴影区域越短，算法的稳定性越好。在表5中，pccs AMOPSO位于词典排序的第一位，在所有12个实例(即其中7个处于1级, 4个处于2级, 1个处于3级)中排在第一位和第三位之间。显然，所提出的算法在所有选择的竞争者中被认为是最好的。
为了更全面地衡量一个算法的性能，准确性和稳定性应该同时被考虑[57]。给定一个秩集 R = { r 1 ， r 2 ， . . ， r ∣ R ∣ } R = \{ r_1，r_2，..，r_{|R|}\} R = { r 1 ， r 2 ， .. ， r ∣ R ∣ } ，|R|是测试实例的个数，对于一个算法A，A的精度可以用平均秩 μ A = 1 ∣ R ∣ ∑ r ∈ R r μ_A = \frac{1} {|R|} \sum_{r\in R} r μ A = ∣ R ∣ 1 ∑ r ∈ R r 来表示，而A的稳定性可以用秩的方差 σ A = 1 ∣ R ∣ ∑ r ∈ R ( r − μ A ) 2 σ_A = \frac{1} {|R|} \sum_{r\in R} ( r - μ_A)^2 σ A = ∣ R ∣ 1 ∑ r ∈ R ( r − μ A ) 2 来表示.如果算法 A 的 μ A μ_A μ A 和 σ A σ_A σ A 比它的竞争者低，则称算法A是好的。图 7 是 σ A σ_A σ A 与 μ A μ_A μ A 在 9 个测试算法的 12 个测试实例上的关系图
由于篇幅所限，文中未列出HV (类似于表4所示)的详细结果。表6和图8分别给出了秩(类似于表V)的频率概览结果和秩(与图7类似)的均值和方差图。从表6可以看出，pccsAMOPSO在HV方面再次被认为是最好的，因为它在rank排序中位于第一位，在所有12个实例中排在第一位和第三位之间。从图8中可以看出，pccsAMOPSO 算法在 12 个测试实例上的排名均值和排名方差都显著优于其他算法，因此在准确率和稳定性方面，pccsAMOPSO 算法明显优于其他算法。
PCCS 密度估计方法是本文提出的一种新的用于更新多目标粒子群算法(MOPSO)中的归档集和选择领导者的方法。然而，PCCS 与第二节调查的自适应网格[6]和拥挤距离[24]两种密度估计方法有很大不同，这两种密度估计方法在MOPSOs中被广泛用于更新归档和选择领导者。在本节的前一小节中，将使用PCCS的所提出的算法与使用Adaptive Grid的agMOPSO和使用拥挤距离的cdMOPSO作为集成解决方案进行了比较，但具有不同的参数设置，例如惯性权重，学习因子和扰动策略。在此，我们对PCCS、自适应网格和拥挤距离在相同基准条件下的性能差异进行了研究。
我们使用了与前一部分相同的12个测试实例，ZDT和DTLZ测试集，以及相同的性能指标IGD。基线设计A-0的设置如下：ω = 0.4，c1 = c2 = 1.429，N = 100 (种群规模)，L = 100(最大存档容量)，并在表三列出快速下降的扰动方法[19]。pBest选择策略为One pBest +占优，同样列于表III。所有测试算法在每个测试实例上独立运行30次，以减少随机不确定性的影响。A-PCCS、AAG和A-CD是基于A-0基线的3种测试算法，但分别使用PCCS、自适应网格和拥挤距离来估计密度，用于选择领导者和更新归档。A-AG中的划分个数根据原文[19]设置为10。
在初始种群完全相同的情况下，图9给出了A-PCCS，A-AG和A-CD在DTLZ2上首次运行得到的近似Pareto前沿。由PCCS密度估计器得到的图9(a)中的近似Pareto前沿的分布比由自适应网格和拥挤距离分别得到的图9(b)和©中的分布更均匀。此外，图9(a)在近似Pareto前沿[也就是说,称为优势抵抗解(DRSs)]之外的解的数量远少于图9(b)和
(c)
。这些结果表明，PCCS的密度估计比自适应网格和拥挤距离的密度估计在均匀性和收敛性上更有效。从其他由于篇幅限制没有给出近似Pareto前沿的测试实例中也可以得到相同的结论。
关于IGD性能的实验结果由图10中的箱体图法表示。从图10可以看出，在12个测试实例上，A - PCCS在IGD上的性能均优于A - AG。此外，A - PCCS在6个测试实例( ZDT4、DTLZ1 - 4、DTLZ7)上显著优于A - CD，仅在DTLZ5上劣于A - CD，而A - PCCS在其他5个测试实例( ZDT1 - 3、ZDT6、DTLZ6)上的表现与A - CD相同，通过双尾检验在0.05的显著性水平下通过u检验。
从本次密度估计实验来看，拥挤距离度量的A-CD在曲线Pareto前沿为(ZDT系列在二目标空间中, DTLZ5-6在三目标空间中)的多目标优化问题上效果较好，而在曲面Pareto前沿为(DTLZ1-4在三目标空间中)的多目标优化问题上效果较差。然而，A-PCCS可以很好地处理具有曲线或曲面Pareto前沿的MOPs。
多目标粒子群算法中基于密度的领导者选择和归档剪枝是影响算法收敛性和多样性等综合性能的关键因素。密度分别采用A-PCCS、A-AG和A-CD中的PCCS、自适应网格和拥挤距离进行估计。因此，从这个实验中我们可以得出结论，PCCS比自适应网格和拥挤距离更适合于MOPSO来估计密度。
W. Hu and G. G. Yen, “Adaptive Multiobjective Particle Swarm Optimization Based on Parallel Cell Coordinate System,” in IEEE Transactions on Evolutionary Computation, vol. 19, no. 1, pp. 1-18, Feb. 2015, doi: 10.1109/TEVC.2013.2296151.
NSGA 2 学习笔记 – crowding distance
多目标优化拥挤距离计算
