基于一种近邻传播的多目标分布估计算法_傅红宇.pdf

2023 年 无线电工程 第 53 卷 第 1 期105doi:103969/jissn10033106202301014引用格式:傅红宇基于一种近邻传播的多目标分布估计算法J 无线电工程，2023，53(1):105113FU Hongyu A Multi-objective Distribution Estimation Algorithm Based on Affinity Propagation J adio Engineering，2023，53(1):105113基于一种近邻传播的多目标分布估计算法傅红宇(重庆邮电大学 自动化学院，重庆 400065)摘要:在基于规则模型的多目标分布估计算法(egularity Model-based Multi-objective Estimation of DistributionAlgorithm，M-MEDA)基础上，为减小聚类数目的随机性和不确定性对算法性能产生的影响，提出了一种基于规则模型的近邻传播(Affinity Propagation，AP)多目标分布估计算法(AP-M-MEDA)。在算法迭代初期引入 AP 聚类算法，根据种群传递的信息对种群进行初聚类，得到聚类数目。同时，为了减小 AP 聚类算法带来的计算开销，提出了一种关于聚类数目的重用策略，并通过实验验证了其有效性。为了提高算法的求解能力，混合差分变异算子生成新的个体。为了验证所提算法的性能，选取 M-MEDA、基于差分进化采样(Differential Evolution Sampling，DES)的多目标分布估计算法(DES-M-MEDA)和基于规则模型的无聚类多目标分布估计算法(FM-MEDA)作为对比算法，分别在两目标和三目标测试函数上进行测试。实验结果表明，所提算法的整体性能有所提高。关键词:多目标分布估计算法;规则模型;近邻传播聚类;测试函数中图分类号:TP18文献标志码:A开放科学(资源服务)标识码(OSID):文 章 编 号:10033106(2023)01010509A Multi-objective Distribution Estimation Algorithm Based onAffinity PropagationFU Hongyu(College of Automation，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)Abstract:Based on the regularity Model-based Multi-objective Estimation of Distribution Algorithm(M-MEDA)，an AffinityPropagation egularity Model-based Multi-objective Estimation of Distribution Algorithm(AP-M-MEDA)is proposed to reduce theinfluence of randomness and uncertainty of cluster number on algorithm performance At the beginning of algorithm iteration，APclustering algorithm is introduced to perform initial clustering of the population according to the information transmitted by thepopulation，and the number of clusters is obtained In order to reduce the computational cost of AP clustering algorithm，a reusestrategy based on the number of clusters is proposed，and its effectiveness is verified by experiments In order to improve the solvingability of the algorithm，the differential mutation operator is mixed to generate new individuals In order to verify the performance of theproposed algorithm，M-MEDA，DES-M-MEDA and FM-MEDA are selected as the comparison algorithms，and tested on the two-objective and three-objective test functions respectively Experimental results show that the overall performance of the proposedalgorithm is improvedKeywords:multi-objective estimation of distribution algorithm;regularity model;affinity propagation clustering;test function收稿日期:20220913基金项目:国家自然科学基金(61673079，61703068);重庆市基础研究与前沿探索项目(cstc2018jcyjAX0160)FoundationItem:NationalNaturalScienceFoundationofChina(61673079，61703068);Chongqing Basic esearch and Frontier Explo-ration Project(cstc2018jcyjAX0160)0引言目前，多目标优化问题(Multi-objective Optimi-zation Problem，MOP)已出现在众多工程领域，与传统单目标优化问题不同，MOP 中存在多个相互冲突的目标，如何获得所有目标的最优解，一直是学术领域和工程领域关注的焦点1。自 1985 年 Scahffer2 首次提出求解 MOP 的算法 基于矢量评价遗传算法(Vector Evaluated Genetic Algorithm，VEGA)以来，众多的多目标优化算法也相继被提出。信号与信息处理1062023 adio Engineering Vol.53 No.1分布估计算法(Estimation of Distribution Algo-rithm，EDA)是众多优化算法中的一种3，因其亮眼的表现，也被应用于 MOP4。与传统的优化算法相比，EDA 没有交叉和变异操作，而是通过提取全局统计信息来建立概率分布模型，然后采样生成新的解决方案。在 一 定 的 平 滑 情 况 下，根 据 Karush-Kuhn-Tucker 条件，连续 MOP 的中帕累托解集 PS 是一个(m1)维的分段连续的流形5，其中 m 为目标函数的个数。基于此，Zhang 等5 于 2008 年提出基于规则模型的多目标分布估计算法(egularity Model-based Multio-bjective Estimation of Distribution Algo-rithm，M-MEDA)来解决 MOP。在 M-MEDA 中，采用 LPCA 算法建立 K 个概率模型来分别描述子种群的分布信息，然后采样生成新个体。同时，M-MEDA 也存在以下不足:该算法的全局搜索能力较弱，从而影响了算法的收敛速度;概率模型的准确性依赖于聚类数目 K 值，具体问题的 K 值是不尽相同的，预设的 K 值过大或过小，都将影响概率模型的准确性，从而影响算法的性能。针对 M-MEDA 全局搜索能力较弱的问题，许多学者通过引入全局搜索能力强的多目标优化算法与之结合，在一定程度上提高了算法的性能。王剑文6 通过判断种群是否收敛来自适应地选择遗传操作或者建模采样操作来生成下一代种群，提高了算法的收敛性。向健7 将差分变异算子与 M-MEDA 相结合，混合产生新的个体，有效提高了全局搜索和局部搜索能力。2019 年王惠君8 在 M-MEDA 的基础上，与另一种基于逆模型的连续多目标分布估计算法相结合，自适应地通过 2 种算法生成新个体，在一定程度上提高了算法的整体性能和解的分布性。为了降低预设 K 值对算法性能的影响，当预设的 K 值大于实际情况时，Wang 等9 提出了一种去冗余聚类算子(CO)来修正 K 值，以此在进化过程中建立更精确的模型，提高了算法的收敛能力。当预设的 K 值小于实际情况时，无法建立正确的概率模型，从而降低算法的性能，故 Shi 等10 提出了去聚类操作，同时结合全变量高斯模型，提高了算法的整体性能。不同问题的 PS 所构成的流形结构不同，故所需的 K 值是不尽相同的，如何根据实际问题自动确定 K 值是研究的重要内容。基于以上分析，本文提出了一种基于近邻传播(Affinity Propagation，AP)的多目标分布估计算法(AP-M-MEDA)。针对 M-MEDA 中预设的 K 值可能与实际不符从而导致无法建立准确的概率模型的情况，引入了 AP 算法来自动确定种群的聚类个数，从而避免人为设置 K 值的不确定性;考虑到迭代后期种群的数据信息逐渐趋同，提出了一种聚类数目重用策略，根据重用策略来判断是否进行聚类操作或重用之前的聚类结果，在一定程度上减小了聚类操作所带来的计算开销;针对 M-MED 全局搜索能力较弱的问题，除根据概率模型采样生成新个体外，还将混合差分变异算子产生部分新的个体，提高了算法的整体性能。1问题描述一个 MOP 通常由 N 个决策变量、M 个目标和若干约束条件组成11，表示如下:minF(x)=(f1(x)，f2(x)，fM(x)T，(1)stxgi(x)0;i=1，2，p，(2)hj(x)=0;j=1，2，q，(3)式中，x=(x1，x2，xM)为 M 个 N 维决策变量形成的变量集;fi(x):n，i=(1，2，M)为第 i 个目标函数;F(x)为 M 个目标函数组成的目标向量集。式(2)为 p 个不等式约束条件;式(3)为 q 个等式约束条件。大多数情况下，各目标函数之间是相互冲突的，同时使得所有的目标函数达到最优是不太容易实现的，故需要寻得一组均衡解集12，即 Pareto 解集，使得目标函数在满足给定约束条件的情况下尽可能达到最优。2AP-M-MEDA 算法在 M-MEDA 算法中，按照预设值，将种群分为K 类，并通过 PCA 算法建立相应的概率模型。但是对于不同的问题，预设的 K 值并不一定符合实际问题。如果 K 值设置得过大，对于实际问题的 Pareto前沿则显得冗余;如果 K 值设置得过小，则不能覆盖实际的 Pareto 前沿，从而无法准确地刻画种群的分布。因此，如何设定合理的 K 值是一个比较困难的问题。本文提出的一种 AP-M-MEDA，根据具体的种群数据信息对种群进行聚类，自动确定了种群的聚类数目，从而避免了人为设置 K 值的不确定性。21AP 聚类AP 算法是 Frey 等13 于 2007 年提出的一种聚类算法。与其他经典聚类算法不同的是，该算法不信号与信息处理2023 年 无线电工程 第 53 卷 第 1 期107需要指定聚类数目14 和初始聚类中心，而是以数据点集合的相似度矩阵作为输入，将所有的数据点作为潜在的聚类中心，通过传递、交换数据点之间的信息来确定聚类中心，从而得到聚类结果。在 AP 算法中，传递的信息参数包括吸引度(esponsibility)和归属度(Availabilit