最小生成树(minimum spanning tree, MST)问题是运筹学、网络优化中的一个基本而又经典的优化问题[1],早在20世纪50年代就已圆满解决,在生活中有着大量的实际应用。此后,在此基础上,又逐步延伸出一系列的扩展问题,如:度约束最小生成树问题、多目标最小树问题、MIN-MAX度生成树问题、MIN-MAX度最小树问题等[2-8]。由于这些扩展问题在求解难度上与经典的最小树问题截然不同,目前都已归入所谓的NP难题范畴。其中,对生成树中各节点的度数有某种要求或限制,以及网络图本身就带有多个权重属性的多目标问题,在现实社会经济生活中经常会遇到,具有重要的应用价值。例如:集成电路布线中往往对相关节点连出的线数有某种工艺限制[9-10],这就是典型的度约束最小树问题。再如:通信网络实时响应时,为防止某些节点故障带来的全网脆弱性,需使其最大顶点度数尽可能小,这就是典型的MIN-MAX度生成树问题。类似地,管道排放系统或紧急疏散过程中,为防止由于某些节点过度拥堵从而造成疏通能力下降,也需要使网络中的最大顶点度数尽可能小。此外,在一些需要实时、快速响应的动态网络系统中,更会涉及到带有多目标的复合问题。
目前,国内外相关文献或仅单独研究度限制MST问题,或只探讨多目标意义下的MST问题,鲜有文献涉及将两者进行综合考虑。鉴于许多应用都可抽象归结为此类NP难题或其混合型问题,而目前这方面的研究又相当欠缺,因此,本文对一般的多目标MIN-MAX度最小树问题建立相应的数学模型,并设计一种基于蚁群寻优思想的智能算法。
1 数学模型设
${x_{ij}} = \left\{ \begin{array}{l} 1,{\kern 1pt} \; {\text{边}}(i,j){\text{在最优树上}}\\ 0, \;{\text{其他}} \end{array} \right.$ |
多目标MIN-MAX度最小树问题可表示为如下的数学规划模型:
$ \min\; {Z_0} = \max \sum\limits_{j = 1}^n {{x_{ij}}} $ | (1) |
$ \begin{array}{l} \min \;{Z_1} = \displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{j = 1}^n {w_{ij}^1{x_{ij}}} } \\ \quad\quad\quad \vdots \end{array} $ | (2) |
$ \min \;{Z_L} = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {w_{ij}^L{x_{ij}}} } $ | (3) |
$ \;\;\;\;\;\;\;\;\;\;{\rm{s.t.}} \left\{ \begin{array}{l} \displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{j = 1}^n {{x_{ij}}} } = n - 1\qquad\qquad\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\;4\;) \\ \displaystyle\sum\limits_{i \in S} {\displaystyle\sum\limits_{j \in S} {{x_{ij}}} } \leqslant \left| S \right| - 1, \forall S \subset V,S \ne \varnothing \;{\kern 1pt}\qquad\;\;\;(\;5\;)\\ {x_{ij}} \in \left\{ {0,1} \right\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\qquad\qquad\qquad(\;6\;) \end{array} \right. $ |
式中:目标(1)的作用在于使生成树的最大顶点度数最小;目标(2)~(3)使生成树的
这里,关于多目标优化的生成树Pareto有效解定义如下:
假设一棵生成树
${Z_r}(T') \leqslant {Z_r}(T), r = 1,2,\cdots ,L$ |
其中,至少有一个不等式严格成立(
由于算法中涉及度约束最小树的一个子算法,因此,这里先引入相关概念与思想。
对于
于是,可以采用如下的想法作为整个算法的一个子算法:若给定的网络图存在最小Hamilton圈,可先求出相应的最小Hamilton路,则对应生成树的最大顶点度恰好为2,即转化为最大顶点度数最小的MIN-MAX度生成树问题。
目前,一般情况下图的Hamilton性的充要条件尚未完全解决,理想的方法迄今仍未找到,相关研究仍是图论中一个重要的难题[11-12]。比较经典的判别定理是:若图
由于一般情况下不能保证给定图一定存在Hamilton路,因此,本文求解多目标MIN-MAX度最小树问题的算法基本思路是:先采用快速启发式算法,寻找图中的最小Hamilton路(即最大度为2的生成树);若不存在Hamilton路,则退而求其次,设计一种改进的蚁群优化算法进行搜索,由单个蚂蚁按转移概率逐个节点进行搜索,则每个蚂蚁经过的节点度数除出发点之外都为2,并行n个蚂蚁后,最终输出的结果将是使得顶点度较小且总权值也相对较小的解。
下面,给出求解多目标MIN-MAX度最小树问题的算法主要步骤:
Step 1 读入数据,随机产生
Step 2 初始化路径数组
Step 3 找寻距离
Step 4
Step 5 若
Step 6 将
Step 7 输出最大度为2的生成树,并计算相应
$ {Z_r} = \sum\limits_{i,j \in {E_T}}^{} {{x_{ij}}w_{ij}^r} ,\;\;r = 1,2, \cdots ,L $ |
Step 8 设置蚁群算法预定迭代次数、轨迹强度常数
Step 9 将各蚂蚁初始出发点置于当前解集中,对每个蚂蚁
Step 10 计算各蚂蚁的目标函数值
Step 11 对各路径计算信息素轨迹增量
Step 12 置
Step 13 计算当前生成树的
上述步骤中,Step 2~7融入了最小Hamilton路的求解策略,使生成树的最大顶点度最小;当Hamilton路不存在时,则转而进行Step 8~13蚁群优化算法的操作。此外,Step 9中将转移概率由基本的指数形式改进为线性形式,可大幅提高计算效率,但同时不影响计算质量,具体形式可表示为
$P_{ij}^k = \dfrac{{\alpha {\tau _{ij}} + \beta {\mu _{ij}}}}{{\displaystyle\sum\nolimits_l {\left[ {\alpha {\tau _{il}} + \beta {\mu _{il}}} \right]} }}$ |
式中:
此外,Step 11中的信息素浓度增量
${\rm{\Delta }}\tau _{ij}^k = \left\{ \begin{array}{l} Q, \; {\text{若}}(i,j){\text{在最优路径上}}\\ {\rm{0}} ,\; {\text{其他}} \end{array} \right.$ |
由算法流程可知,若给定图存在Hamilton路,则算法运行至Step 7即可结束,可省却其后若干步寻优过程,此时时间复杂度为
因此,相较于其他启发式算法,本文算法可根据实际图的不同特征,采取相应优化策略:当给定图存在Hamilton路时,可大大节省运算时间;否则,将采用退而求其次的改进蚁群算法实施优化计算。
3 计算实验上述算法用Embarcadero Delphi实现,在Windows 7(64位)系统下运行通过。为方便起见,仅对双目标问题进行了大量测试,均能在短时间内获得理想效果。下面,给出部分实例计算结果并予以说明。
例1 (源自文献[5])
${{{W}}^1} = \left[ {\begin{array}{*{20}{c}} \infty &{10}&{79}&{41}&{39}&{54}&{31}&{46}&{53} \\ {10}&\infty &{31}&{11}&{30}&6&{89}&9&{26} \\ {79}&{31}&\infty &{86}&5&{84}&{84}&{26}&{75} \\ {41}&{11}&{86}&\infty &{47}&{46}&1&{17}&{96} \\ {39}&{30}&5&{47}&\infty &{28}&{94}&{71}&2 \\ {54}&6&{84}&{46}&{28}&\infty &{78}&{42}&{55} \\ {31}&{89}&{84}&1&{94}&{78}&\infty &3&{41} \\ {46}&9&{26}&{17}&{71}&{42}&3&\infty &{91} \\ {53}&{26}&{75}&{96}&2&{55}&{41}&{91}&\infty \end{array}} \right]$ |
${{{W}}^2} = \left[ {\begin{array}{*{20}{c}} \infty &{62}&{76}&{95}&{50}&{62}&{10}&{13}&{37} \\ {62}&\infty &{89}&{77}&{65}&{71}&{70}&{67}&{17} \\ {76}&{89}&\infty &{100}&{95}&{23}&{10}&{92}&{79} \\ {95}&{77}&{100}&\infty &7&{12}&{11}&{84}&{23} \\ {50}&{65}&{95}&7&\infty &{89}&{39}&{39}&{38} \\ {62}&{71}&{23}&{12}&{89}&\infty &{84}&{93}&{62} \\ {10}&{70}&{10}&{11}&{39}&{84}&\infty &{33}&{88} \\ {13}&{67}&{92}&{84}&{39}&{93}&{33}&\infty &{68} \\ {37}&{17}&{79}&{23}&{38}&{62}&{88}&{68}&\infty \end{array}} \right]$ |
在无顶点度约束的情况下,文献[5]共求得该算例的28个Pareto解,最大顶点度数为3和4,且集中于某几个关键点。
如同时考虑生成树的最大顶点度尽可能小,则本文算法运行10轮后,剔除劣解,可获得的Pareto解集如表1所示。
例2 (源自文献[13])
在无顶点度约束情况下,文献[13]中共求得该算例的21个Pareto解(原文列出了22个,但其中有一个是劣解,应舍去),其最大顶点度数分别为:3,4,5,6。生成树最大顶点度数越高,稳定性越差。
因此,为使生成树的最大顶点度数尽可能小,运行本文算法10轮后,剔除劣解,可得最大顶点度仅为2的Pareto解如表2所示。
例3 考虑Hamilton路不存在的情况,
${{{W}}^1} = \left[ {\begin{array}{*{20}{c}} \infty &{41}&{24}&{19}&{28}&9&{28}&0 \\ {41}&\infty &{27}&{31}&{31}&0&0&{17} \\ {24}&{27}&\infty &{23}&{13}&0&0&{22} \\ {19}&{31}&{23}&\infty &{35}&0&0&{47} \\ {28}&{31}&{13}&{35}&\infty &0&0&{21} \\ 9&0&0&0&0&\infty &0&0 \\ {28}&0&0&0&0&0&\infty &0 \\ 0&{17}&{22}&{47}&{21}&0&0&\infty \end{array}} \right]\;$ |
${{{W}}^2} = \left[ {\begin{array}{*{20}{c}} \infty &{21}&{10}&1&{48}&{25}&{25}&0 \\ {21}&\infty &{49}&{21}&6&0&0&8 \\ {10}&{49}&\infty &{28}&3&0&0&{42} \\ 1&{21}&{28}&\infty &{40}&0&0&{15} \\ {48}&6&3&{40}&\infty &0&0&{26} \\ {25}&0&0&0&0&\infty &0&0 \\ {25}&0&0&0&0&0&\infty &0 \\ 0&8&{42}&{15}&{26}&0&0&\infty \end{array}} \right]$ |
由于给定图的Hamilton路不存在,算法跳过了第一个子算法,直接进入改进的蚁群算法进行求解,相关参数按文献[8]的方式设定:
目前,此类使最大顶点度数最小的多目标MIN-MAX度最小树问题的优化研究较少,相应的求解算法也较为鲜见。本文针对这一问题设计了求解方法,采用大量数值算例反复求解,并分别与度约束最小树和多目标最小树等相关问题计算结果进行比较,有效避免了生成树某些顶点度数过大、过于集中而造成的不稳定问题,并能得到多个Pareto有效解,效果令人满意。尤其是当问题规模较大时,本文算法仍能在短时间内给出理想的结果,这在一些需要快速、实时响应的大型系统中具有明显优势。
4 结束语多目标MIN-MAX度最小树问题由多目标最小树问题和MIN-MAX度生成树问题以及度约束最小树等问题延伸扩展而来,在现实生活中有着一系列的应用。本文设计了相应的快速优化算法进行求解,取得了满意的效果。特别是本文算法思想还可面向一些对最大顶点度极度敏感的问题,或动态变化环境下需快速响应的实时动态网络规划问题等,后续将研究更完善的求解方案和技术,探索对特定实际网络图的解决方案。
[1] |
JOTHI R, MOHANTY S K, OJHA A. Fast approximate minimum spanning tree based clustering algorithm[J]. Neurocomputing, 2018, 272: 542-557. DOI:10.1016/j.neucom.2017.07.038 |
[2] |
GAO X, JIA L F, KAR S. Degree-constrained minimum spanning tree problem of uncertain random network[J]. Journal of Ambient Intelligence and Humanized Computing, 2017, 8(5): 747-757. DOI:10.1007/s12652-017-0493-5 |
[3] |
CLÍMACO J C N, CAPTIVO M E, PASCOAL M M B. On the bicriterion-minimal cost/minimal label - spanning tree problem[J]. European Journal of Operational Research, 2010, 204(2): 199-205. DOI:10.1016/j.ejor.2009.10.013 |
[4] |
ZHOU G, GEN M. Approach to the degree-constrained minimum spanning tree problem using genetic algorithm[J]. Engineering Design and Automation, 1997, 3(2): 157-165. |
[5] |
熊小华, 马良, 宁爱兵. 多目标最小生成树的竞争决策算法[J]. 系统工程, 2010, 28(4): 89-93. DOI:10.3969/j.issn.1001-2362.2010.04.061 |
[6] |
JOTHI R, RAGHAVACHARI B. Degree-bounded minimum spanning trees[J]. Discrete Applied Mathematics, 2009, 157(5): 960-970. DOI:10.1016/j.dam.2008.03.037 |
[7] |
DE ALMEIDA A M, MARTINS P, DE SOUZA M C. Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[J]. International Transactions in Operational Research, 2012, 19(3): 323-352. DOI:10.1111/j.1475-3995.2011.00830.x |
[8] |
马良, 蒋馥. 度限制最小树的蚂蚁算法[J]. 系统工程学报, 1999, 14(3): 211-214. DOI:10.3969/j.issn.1000-5781.1999.03.002 |
[9] |
孙治国, 滕弘飞. 布线设计的模型和算法研究进展[J]. 系统工程与电子技术, 2003, 25(12): 1536-1541. DOI:10.3321/j.issn:1001-506X.2003.12.028 |
[10] |
PREMKUMAR G, CHU C H, CHOU H H. Telecommunications network design-comparison of alternative approaches[J]. Decision Sciences, 2000, 31(2): 483-506. DOI:10.1111/j.1540-5915.2000.tb01631.x |
[11] |
史小红, 贾新娟, 王燕. 基于Hamilton路模型的蛋白质结构预测的研究[J]. 数学的实践与认识, 2009, 39(22): 100-104. |
[12] |
温雪莲, 娄定俊, 陆芸婷, 等. 求Halin图中给定两点之间最优Hamilton路的有效算法[J]. 计算机科学, 2007, 34(9): 176-180, 217. DOI:10.3969/j.issn.1002-137X.2007.09.047 |
[13] |
ANDERSEN K A, JÖRNSTEN K, LIND M. On bicriterion minimal spanning trees: an approximation[J]. Computers & Operations Research, 1996, 23(12): 1171-1182. |