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

针对最小加权顶点覆盖问题中顶点被赋予多个权重的情况,提出了一种基于分解的多目标最小加权顶点覆盖算法.利用权重聚合方法将多目标问题分解为单目标问题.在初始化过程中,利用异步更新规则下的雪堆博弈形成初始种群.在局部搜索阶段,利用删除、交换、添加三个操作算子引导目标朝着最优方向进化,为了更好的加快搜索收敛速度,引入自适应策略搜索解空间.在基准实例上对算法进行验证,并与MONSD和NSGA2算法作对比.实验结果表明,该算法在收敛性和多样性方面要优于另外两种算法.

加权最小顶点覆盖的加权分治算法

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性.