论文部分内容阅读
在多目标最小生成树问题和MIN-MAX度最小树问题的基础上，探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质，在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同，当网络图不存在Hamilton路时，引入改进的蚁群优化算法，将转移概率由基本的指数形式改进为线性形式，在不影响求解质量的前提下，提高计算效率。针对以上策略，设计了相应的求解方案，并在计算机上用Delphi编程实现。大量数值算例验证表明，算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。