图的度量维数问题的0-1蚁群条件着色分辨算法研究

The 0-1 Ant Colony Conditional Coloring Resolving Algorithm for Solving the Metric Dimension Problem of Graphs

图的度量维数问题(MDP)是一类在机器导航、声呐系统布置、化学、数据分类等领域有重要应用的组合优化问题.针对该问题,本文通过引入图的分辨表存储结构,建立了非线性求解模型;同时,通过改进现有蚁群算法的参数设计,利用全局搜索和局部搜索相结合的策略,建立了求解模型的改进型蚁群算法.数值对比分析验证了算法的有效性:全局搜索和局部搜索的结合较大程度的改进了算法求解质量;在规则图上提高算法求解质量具有一定挑战;与遗传算法计算结果相比较,本文提出的算法不仅在求解质量方面有所提升,而且在最坏的情况下能为图提供极小分辨集.最后,本文探索了部分算法参数对算法求解质量的影响,并给出了进一步研究课题.

The metric dimension problem(MDP)of graphs is a kind of combinatorial optimization problem which has important applications in the fields such as machine navigation,sonar system layout,chemistry,and data classification.To solve this problem,we establish a non-linear model by introducing a resolving table storage structure for the considered graphs;simultaneously,an improved ant colony algorithm for solving the proposed model is established,by improving the parameters design of existing ant colony algorithms and leveraging the strategy of global search and local search.Numerical comparison analysis verifies the efficiency of the new algorithm:the combination of global search and local search improves the solution quality of the proposed algorithm to a large extent;it is a great challenge to improve the solution quality of the algorithm on regular graphs;compared with the results of genetic algorithm on MDP,the algorithm proposed in this paper not only improves the solution quality,but also provides the minimal resolving set for graphs in the worst case.Furthermore,we examine the influences of some parameters on the solution quality of the algorithm,and propose a further research topic.