基于免疫粒子群的最小连通支配集求解算法

作者：吴明功; 李佳威; 温祥西^*; 刘飞

来源：华中科技大学学报(自然科学版)科技大学, 2019, 47(11): 90-95.

DOI：10.13245/j.hust.191116

• 最小连通支配集(MCDS)
• 二进制粒子群算法
• 复杂网络
• 免疫抗体
• 连通分支

为解决复杂网络最小连通支配集(MCDS)求解算法复杂度高、速度慢及解的精确度差等问题,采用一种免疫粒子群优化(IPSO)算法进行求解.该算法将连通支配集的支配规则转化为基于邻接矩阵的并集约束,并结合图连通分支约束设计优化目标,采用二进制粒子群算法对MCDS进行求解.在求解过程中引入免疫机制,依据网络关键节点与支配节点之间的重叠关系,设置抗原因子,指导粒子群搜索方向、加快算法收敛速度.在随机网络上的仿真实验表明:相较于传统算法,所提算法能够找出网络的MCDS,并且在保证解精度的前提下提高了求解速度.

• 单位
  空军工程大学