多目标度约束最小生成树的蚁群优化算法求解  

An Ant Colony Optimization Algorithm for Multi-criteria Degree-constrained Minimum Spanning Tree

作　　者：魏欣[1] 马良[1] 张惠珍[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《数学理论与应用》2017年第1期81-89,共9页Mathematical Theory and Applications

基　　金：国家自然科学基金资助项目(71401106);教育部人文社科规划基金项目(16YJA630037)资助

摘　　要：多目标最小生成树问题与度约束最小生成树问题分别是网络优化中两个NP难题,在实际中一直有着重要的应用.本文针对同时考虑多目标和度约束情况下的最小生成树求解问题,采用蚁群优化算法思想,设计了一种求解方案,并在计算机上用Delphi予以实现.经大量数值算例求解测试,验证了算法的有效性和可行性.Both multi--criteria minimum spanning tree problem and degree--constrained minimum spanning tree problem are NP--hard problems in network optimization. They always have many important applications in practice. To solve the minimum spanning tree problem by considering both the multi--criteria and degree-- constraints, this paper proposes an algorithm （coded in Delphi） which is based on the ideas of ant colony opti- mization. The computational numerical experiments show the efficiency and effectiveness of the algorithm for the multi--criteria degree--constrained minimum spanning tree problem.

关 键 词：多目标 度约束 最小生成树 蚁群优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]