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

Minimum connected dominating set solving algorithm based on immune particle swarm

作　　者：吴明功 李佳威 温祥西[1] 刘飞 WU Minggong;LI Jiawei;WEN Xiangxi;LIU Fei(Air Traffic Control and Navigation College,Air Force Engineering University,Xi’an 710051,China;National Key Laboratory of Air Traffic Collision Prevention,Air Force Engineering University,Xi’an 710051,China)

机构地区：[1]空军工程大学空管领航学院,陕西西安710051 [2]空军工程大学国家空管防相撞技术重点实验室,陕西西安710051

出　　处：《华中科技大学学报（自然科学版）》2019年第11期90-95,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金青年基金资助项目(71801221);陕西省自然科学基础研究计划资助项目(2018JQ7004)

摘　　要：为解决复杂网络最小连通支配集(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.

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

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]