基于MOEA/D算法求解最小加权顶点覆盖问题  

Solving minimum weighted vertex cover problem based on MOEA/D algorithm

作　　者：马洪玲 马璐 MA Hong-ling;MA Lu(School of Computer Science&Technology,Tiangong University,Tianjin 300387,China)

机构地区：[1]天津工业大学计算机科学与技术学院,天津300387

出　　处：《哈尔滨商业大学学报（自然科学版）》2022年第5期530-536,共7页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：天津市自然科学基金(20JCYBJC00140,19JCYBJC15800)。

摘　　要：针对最小加权顶点覆盖问题中顶点被赋予多个权重的情况,提出了一种基于分解的多目标最小加权顶点覆盖算法.利用权重聚合方法将多目标问题分解为单目标问题.在初始化过程中,利用异步更新规则下的雪堆博弈形成初始种群.在局部搜索阶段,利用删除、交换、添加三个操作算子引导目标朝着最优方向进化,为了更好的加快搜索收敛速度,引入自适应策略搜索解空间.在基准实例上对算法进行验证,并与MONSD和NSGA2算法作对比.实验结果表明,该算法在收敛性和多样性方面要优于另外两种算法.Aiming at the situation that the vertices are given multiple weights in the minimum weighted vertex cover problem,this paper proposed a decomposition-based multi-objective minimum weighted vertex cover algorithm.The multi-objective problem was decomposed into single-objective problem by weight sum approach.In the initialization process,the snowdrift game under the asynchronous update rule was used to form the initial population.In the local search stage,three operators delete,swap,and add were used to guide the target to evolve toward the optimize direction.To better accelerate the search convergence speed,an adaptive strategy was introduced to search the solution space.The algorithm was verified on benchmark instances and compared with the MONSD and NSGA2 algorithms.The experimental results showed that the proposed algorithm was superior to the other two algorithms in terms of convergence and diversity.

关 键 词：多目标优化 最小加权顶点覆盖 权重聚合 雪堆博弈 局部搜索 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]