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

Minimum connected dominating set solving algorithm based on immune particle swarm

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

As the minimum connected dominating set(MCDS)algorithms would cost high computation complexity with low efficiency and obtain poor accuracy for the large scale of networks,an immune particle swarm optimization(IPSO)algorithm was proposed to solve these problems.The algorithm transformed the dominating rules of the connected dominating set into the union constraint based on adjacency matrix,and the connected components constraint was introduced to design the optimization objective.The binary particle swarm optimization was adopted to solve the MCDS.Immune mechanism was introduced in the solution process,and antigenic factors were set according to the overlapping relationship between key nodes and dominating nodes of the network,which could guide the search direction of particle swarm and accelerate the convergence speed of the algorithm.Simulation experiments on stochastic networks show that the proposed algorithm can find the MCDS and improve the algorithm speed,while ensuring the solution accuracy.