求解最小MPR集的蚁群算法与仿真

在分析利用贪心策略启发式算法求解最小MPR集的缺陷基础上,引入蚁群算法对最小MPR集进行求解.首先定义了节点及其出度和入度,并根据节点的出度和入度限制,给出了求解最小MPR集的蚁群算法.然后,对蚁群算法的3种模型Ant-Cycle、Ant-Quantity和Ant-Density加以改进,并对这3种改进模型的收敛性进行分析与实验.实验采用了圆形分布和理想均匀分布2种拓扑结构,前者实验结果表明Ant-Cycle模型的收敛速度较快,后者结果表明Ant-Cycle模型和Ant-Density模型各有优势.因此,最小MPR集的蚁群算法的模型选择需依据拓扑结构确定.最后,使用OPNET基于该算法对数据链的点对多点的点名呼叫工作方式进行模拟仿真,选择的统计量显示了节点的连通性和数据一致性,验证了该算法的合理性.

An ant colony algorithm and simulation for solving minimum MPR sets

Based on analyzing the defects of a heuristic algorithm of greedy strategy,an ant colony algorithm was imported to solve the minimum MPR set.First of all,a node and its out and in-degrees were defined,and in accordance with the out and in-degree constraints of the node,ant colony algorithms were given based on the graphics to find the minimum MPR set.Then,three kinds of ant colony algorithm models,the Ant-Cycle,Ant-Quantity,and Ant-Density models,were improved,and the convergence curves of the three kinds o...