多目标MIN-MAX度最小树问题及其求解

魏 欣， 马 良

（上海理工大学 管理学院，上海 200093）

最小生成树（minimum spanning tree, MST）问题是运筹学、网络优化中的一个基本而又经典的优化问题[1]，早在20世纪50年代就已圆满解决，在生活中有着大量的实际应用。此后，在此基础上，又逐步延伸出一系列的扩展问题，如：度约束最小生成树问题、多目标最小树问题、MINMAX度生成树问题、MIN-MAX度最小树问题等[2-8]。由于这些扩展问题在求解难度上与经典的最小树问题截然不同，目前都已归入所谓的NP难题范畴。其中，对生成树中各节点的度数有某种要求或限制，以及网络图本身就带有多个权重属性的多目标问题，在现实社会经济生活中经常会遇到，具有重要的应用价值。例如：集成电路布线中往往对相关节点连出的线数有某种工艺限制[9-10]，这就是典型的度约束最小树问题。再如：通信网络实时响应时，为防止某些节点故障带来的全网脆弱性，需使其最大顶点度数尽可能小，这就是典型的MIN-MAX度生成树问题。类似地，管道排放系统或紧急疏散过程中，为防止由于某些节点过度拥堵从而造成疏通能力下降，也需要使网络中的最大顶点度数尽可能小。此外，在一些需要实时、快速响应的动态网络系统中，更会涉及到带有多目标的复合问题。

目前，国内外相关文献或仅单独研究度限制MST问题，或只探讨多目标意义下的MST问题，鲜有文献涉及将两者进行综合考虑。鉴于许多应用都可抽象归结为此类NP难题或其混合型问题，而目前这方面的研究又相当欠缺，因此，本文对一般的多目标MIN-MAX度最小树问题建立相应的数学模型，并设计一种基于蚁群寻优思想的智能算法。

1 数学模型

多目标MIN-MAX度最小树问题可表示为如下的数学规划模型：

式中：目标（1）的作用在于使生成树的最大顶点度数最小；目标（2）～（3）使生成树的个目标函数值都尽可能小，即多目标意义下的Pareto有效解；约束（4）则保证了所得解的边数满足树的基本要求和性质；约束（5）中为集合中所含图的 顶点个数，保证了所得解中没有任何子回路的产生。

这里，关于多目标优化的生成树Pareto有效解定义如下：

2 算法设计

由于算法中涉及度约束最小树的一个子算法，因此，这里先引入相关概念与思想。

于是，可以采用如下的想法作为整个算法的一个子算法：若给定的网络图存在最小Hamilton圈，可先求出相应的最小Hamilton路，则对应生成树的最大顶点度恰好为2，即转化为最大顶点度数最小的MIN-MAX度生成树问题。

目前，一般情况下图的Hamilton性的充要条件尚未完全解决，理想的方法迄今仍未找到，相关研究仍是图论中一个重要的难题[11-12]。比较经典的判别定理是：若图中 任意两个不相邻顶点和都有，则含有一条Hamilton路。

由于一般情况下不能保证给定图一定存在Hamilton路，因此，本文求解多目标MIN-MAX度最小树问题的算法基本思路是：先采用快速启发式算法，寻找图中的最小Hamilton路（即最大度为2的生成树）；若不存在Hamilton路，则退而求其次，设计一种改进的蚁群优化算法进行搜索，由单个蚂蚁按转移概率逐个节点进行搜索，则每个蚂蚁经过的节点度数除出发点之外都为2，并行n个蚂蚁后，最终输出的结果将是使得顶点度较小且总权值也相对较小的解。

下面，给出求解多目标MIN-MAX度最小树问题的算法主要步骤：

Step 9 将各蚂蚁初始出发点置于当前解集中，对每个蚂蚁，按概率转移到顶点，并将顶点置于当前解集，更新当前各顶点度数；

上述步骤中，Step 2～7融入了最小Hamilton路的求解策略，使生成树的最大顶点度最小；当Hamilton路不存在时，则转而进行Step 8～13蚁群优化算法的操作。此外，Step 9中将转移概率由基本的指数形式改进为线性形式，可大幅提高计算效率，但同时不影响计算质量，具体形式可表示为

由算法流程可知，若给定图存在Hamilton路，则算法运行至Step 7即可结束，可省却其后若干步寻优过程，此时时间复杂度为；否则，算法的时间复杂度由蚁群算法决定，这时，整个算法的时间复杂度为。

因此，相较于其他启发式算法，本文算法可根据实际图的不同特征，采取相应优化策略：当给定图存在Hamilton路时，可大大节省运算时间；否则，将采用退而求其次的改进蚁群算法实施优化计算。

3 计算实验

上述算法用Embarcadero Delphi实现，在Windows 7（64位）系统下运行通过。为方便起见，仅对双目标问题进行了大量测试，均能在短时间内获得理想效果。下面，给出部分实例计算结果并予以说明。

在无顶点度约束的情况下，文献[5]共求得该算例的28个Pareto解，最大顶点度数为3和4，且集中于某几个关键点。

如同时考虑生成树的最大顶点度尽可能小，则本文算法运行10轮后，剔除劣解，可获得的Pareto解集如表1所示。

表 1 例1计算结果Tab.1 Calculation results of example 1

图 1 实例2网络图Fig.1 Network graph of example 2

在无顶点度约束情况下，文献[13]中共求得该算例的21个Pareto解（原文列出了22个，但其中有一个是劣解，应舍去），其最大顶点度数分别为：3，4，5，6。生成树最大顶点度数越高，稳定性越差。

因此，为使生成树的最大顶点度数尽可能小，运行本文算法10轮后，剔除劣解，可得最大顶点度仅为2的Pareto解如表2所示。

表 2 例2计算结果Tab.2 Calculation results of example 2

由于给定图的Hamilton路不存在，算法跳过了第一个子算法，直接进入改进的蚁群算法进行求解，相关参数按文献[8]的方式设定：，，运行10轮后，剔除劣解，获得Pareto解如表3所示。

表 3 例3计算结果Tab.3 Calculation results of example 3

目前，此类使最大顶点度数最小的多目标MIN-MAX度最小树问题的优化研究较少，相应的求解算法也较为鲜见。本文针对这一问题设计了求解方法，采用大量数值算例反复求解，并分别与度约束最小树和多目标最小树等相关问题计算结果进行比较，有效避免了生成树某些顶点度数过大、过于集中而造成的不稳定问题，并能得到多个Pareto有效解，效果令人满意。尤其是当问题规模较大时，本文算法仍能在短时间内给出理想的结果，这在一些需要快速、实时响应的大型系统中具有明显优势。

4 结束语

多目标MIN-MAX度最小树问题由多目标最小树问题和MIN-MAX度生成树问题以及度约束最小树等问题延伸扩展而来，在现实生活中有着一系列的应用。本文设计了相应的快速优化算法进行求解，取得了满意的效果。特别是本文算法思想还可面向一些对最大顶点度极度敏感的问题，或动态变化环境下需快速响应的实时动态网络规划问题等，后续将研究更完善的求解方案和技术，探索对特定实际网络图的解决方案。