王海红，李 林，刘 莉

(青岛科技大学 信息科学技术学院，山东 青岛 266061)

0 引言

现实中大部分的网络系统都可以用最小生成树作为简化模型来分析。在特定情况下，为了确保图的畅通性，通过在最小生成树模型中添加节点度数的限制，从而生成了度约束的最小生成树模型(DCMST)。如何求解该问题是一个NP问题，许多专家、学者对此进行了大量的研究工作。在求解有约束的问题时，智能控制方法往往具有操作简单，适用性强的优点，因此受到广泛关注。越来越多的智能控制方法在该问题上得到很好的应用，如禁忌搜索算法[1]、模拟退火算法[2]、灰狼算法[3]、布谷鸟算法[4]等。文献[5]提出了一种能够生成优质近似解的算法，并采用改进的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。文献[6]使用最小生成树模型构造网络，采用人工蜂群算法来进行节点寻优。文献[7]针对同时考虑多目标和度约束情况下的最小生成树求解问题，对传统的蚁群算法进行优化，设计了三种信息素数量模型，并对信息素的持久度进行设计更新，进而影响蚁群寻优轨迹，提高求解效率。从实验过程和数据来看，上面的提到的这些智能方法一定程度上存在操作过程相对复杂，改进效果并不十分明显等问题。

遗传算法由于其编码方式简单，实现容易且效果较好，而在该问题上有更广泛的应用和改进[8]。文献[9]对传统遗传算法进行优化，提出了一种带有加速和调节算子作为激励的遗传算法，从正反两方面出发来加速搜索最小生成树过程。……