一种融合模拟退火和单亲遗传的优化求解算法

王海红，李 林，刘 莉

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

0 引言

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

遗传算法由于其编码方式简单，实现容易且效果较好，而在该问题上有更广泛的应用和改进[8]。文献[9]对传统遗传算法进行优化，提出了一种带有加速和调节算子作为激励的遗传算法，从正反两方面出发来加速搜索最小生成树过程。文献[10]提出了一种以过程控制为基础的生成树编码方法—PC编码，进而给出以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法来求解最小生成树。文献[11]采用单亲遗传算法来求解该问题，能提高个体的有效性，但仍存在变异产生不可行解以及解个体跳跃问题，求解效率不高。

针对以上问题，本文提出改进单亲遗传算法的变异算子方法，并引入自适应变异率，求解过程中可以避免不可行解的产生，并提高求解效率。同时融合模拟退火算法，来解决个体的跳跃问题，提高获得全局最优解的可能性。最后，进行实验验证，与标准单亲遗传算法的结果进行比较，证明了所提算法的有效性和优越性。

1 度约束的最小生成树模型

设G=(V,E,C)是一个连通赋权网络图。其中V={v1,v2,...,vn}是图G的节点集合，代表一个个节点。E={e1,e2,...,en}是图G的边集合，代表节点之间相互连接的边。C={c1,c2,...,cn}是每条边上的正实数权重，用来表示相邻节点间的距离。G的生成树规定为一棵能含有G中所有节点的无向树G′=(V,T)，T∈E，T中没有回路并且能将图中全部节点都连接起来。因此，构建G的最小生成树需要找到各边权重之和最小的生成树。若图T是图G的最小生成树，D={d1,d2,...,dn}是每个节点的度约束，且对于任意的节点vi∈V(i=1,2,...,n)都有dvi

度约束最小生成树目标函数如下：

(1)

约束函数如下：

(2)

(3)

(4)

xij∈{0,1}∀vi∈V,vj∈V,i,j=1,2,......n

(5)

约束条件(2)能够确保最终得到的生成树有n-1条边。约束条件(3)限定了在一步步得到最小生成树的操作期间任何一个节点都始终不包含通向自身的回路。

2 基于单亲遗传算法和模拟退火算法的改进SAPGA算法

2.1 初始化

本节研究算法的染色体采用Prufer数列[14]编码。根据度约束的最小生成树对节点的连接边都是有数量限制的原则，使用生成的Prufer数列作为初始种群时，需要考虑到度数限制，避免产生不可行解[15]，使求解更加高效。

假设这个问题的度约束序列是b=(b1,b2,..,bn)，那么根据每个节点的度约束可以得到一个数列S={1，1，…1，2，2，…2，…i，i，…，i，…n，n，…，n}，该数列中数字i的个数为bi-1个。获得初始种群的Prufer数的具体操作为：从数列S中随机地取出n-2个数组成一个新的数列。从上述数列中得到的任何一个包含n-2个数的随机排列组合，都能够作为一棵生成树对应的Prufer数，并且符合每一个节点的度约束要求。重复地进行从数列S中随机取n-2个数的操作，直至达到初始化种群所要求的最大个体数目N。这样就得到了初始种群 ，既充分满足每个结点的度约束，又不会出现不可行解。

设置初始较高温度为T0，最低温度Tmin，全局最优解Pg，及全局最优解对应的适应度Fg。

2.2 适应度函数

本文使用适应度函数来衡量遗传操作过程中每个个体的适应度，并以此来得出优胜劣汰的标准。根据前面描述的度约束最小生成树问题的模型，适应值函数F(x)设置如下。

(6)

2.3 选择过程

遗传算法的选择过程通常采取相对公平的轮盘赌策略[16]。轮盘赌选择的基本思想是每个个体被选中的概率与其适应度大小成正比。对于上一代种群中适应度非常好的个体，如果采取传统的轮盘赌选择策略可能会将其丢弃，所以本文采用轮盘赌策略加保留最优个体的选择方法。即先将最优个体保留下来，然后将父代和子代中按轮盘赌选出N-1个个体。

2.4 优化变异操作

变异的本质是将个体的遗传基因发生改变，但如果采用一般的变异方式会导致很多不可行解的产生，从而导致求解效率大大降低，根据种群生成可知，如果不产生新的数，只是改变数列中数字的排列顺序，则该数列解的可行性不会由此改变。据此，本文摒弃遗传算法中的交叉操作，只进行变异操作，并引入自适应变异率，提出两种新的变异算子来避免产生不可行解，这样在很大程度上简化了求解的复杂度。

2.4.1 优化变异算子生成方式

本文设计两种不会产生不可行解的变异算子，具体生成方法如下。

1)随机插入变异：首先要随机生成一个位置i(i不大于基因总数)，将它记为即将插入的位置。再从代表父辈个体的Prufer数列中随机地取出一个子数列，将取出的子数列插入刚刚标记的位置，这样就得到了新的子代个体。这个操作仅仅是移动原数列中的某些数字，因此不会导致不可行解的出现。

操作举例：随机选择的子串为4、5、6，随机产生的位置为10，则位移变异操作前后的子串情况如下：

P：1 2 3 [4 5 6] 7 8 9 10 11 12 13 ⟹P’：1 2 3 7 8 9 [4 5 6] 10 11 12 13

2)后移变异：首先生成一个随机数j(j小于基因总数)，将父代个体的Prufer数列依次后移j个位置，该操作简单易行，并且很明显在这个过程中可以保证解的可行性。操作举例如下：

假设生成随机数为1，则每个数都后移一位。

P：1 2 3 4 5 6 7 8 9 10 11 12 13 ⟹P’：13 1 2 3 4 5 6 7 8 9 10 11 12

2.4.2 改进变异率

为加快算法的求解速度，设计自适应变异率。训练前期较大的变异率能够保证较高的个体多样性，而后期应该采取较小的变异率，能加快收敛。因此，设计自适应更新学习因子如下：

pv=pv·e(1-k/kmax)

(7)

其中:k表示目前迭代次数，kmax表示最大迭代次数。随着求解的进行，变异率随迭代次数的增加而变小，最终趋近于0。使得迭代后期逐渐减小变异操作的变化率，以加快算法的收敛速度。

2.5 判断是否接受新解

模拟退火算法的思想是以一定概率接受一个较差的解[6]，对于每一个温度Tk，执行如下操作：

计算新生成染色体的适应度函数值F(x)，以概率p接受这个新解，在0到1中生成一个随机数q，若p>q，则更新解个体；否则，保持原来的解个体。

(8)

2.6 改进算法流程

本文所提算法的基本步骤总结如下。

步骤1：按照前面的方法生成一个含有N个个体的初始群体P0，将初始温度设为100 ℃，最低温度设为0 ℃。设置固定温度下的最大迭代次数kmax，记录初始种群中适应度最小的Pg为全局最优解，以及全局最优解对应的适应度Fg。

步骤2：判断是否达到最低温度，如果T≤Tmin，算法终止，输出最优解及其适应度；否则继续向下执行。

步骤3：令迭代次数k=1，开始T温度下的内循环。

步骤4：计算种群Pk里面含有的每一个染色体的F(x)。

步骤5：使用最优个体保留方法和轮盘赌方法从父子两代种群中选出N个个体。

步骤6：根据两种变异方法来对上面选出的个体上实行变异。

步骤7：根据概率p判断是否接受新解。

步骤8：判断是否继续循环，如果k达到最大迭代次数kmax，比较全局最优适应度Fg和局部最优适应度Fl，如果Fl

改进算法的具体流程图如图1所示。

图1 改进SAPGA算法流程图

3 实验结果与分析

为了验证所提出算法的有效性，与单亲遗传算法[17]进行实验对比。本文实验环境是Core(TM) i7-8550U CPU @1.80 GHz 1.99 GHz，内存8.00 GB，开发工具是Matlab 2016a。

给定九个节点的图G的权值矩阵W(数据取自文献[17])如下，各节点的度约束都为3。

实验1:设置种群规模为100，最大迭代次数为100，初始变异率为0.1。使用所提算法和标准的单亲遗传算法分别求其最小生成树代价值，结果如图2所示。

图2 最优值对比

从图2中可以看出，两种算法均随迭代次数的增加，不断趋近最优值，但明显SAPGA算法的趋近速度更快。说明自适应变异率的加入确实能使算法加速收敛，自适应变异率前期较大，能增加种群的多样性，加快解的优化；后期减小，能加快收敛效率。

实验2:设置最大迭代次数为100，初始变异率为0.1，在种群规模为10到100的情况下，对比两种算法的运行时间，结果如图3所示。从图3中可以看出，本文所提SAPGA算法用时始终比PGA算法少，并且随着种群规模的扩大，差距会越来越明显。因为变异算子的改进，能避免不可行解个体的产生，且自适应变异率能加速收敛，所以SAPGA算法的运行时间能得到有效的改善。

图3 运行时间对比

实验3:在种群大小为50和100的情况下，使用所提算法与单亲遗传算法的求解方法进行对比，验证所提算法得到最优解的概率。本文提出的算法SAPGA进行求解，得到度约束下两种算法在两种群规模下各运行100次结果对比见表1。

表1 运行结果对比

从表1可知，两种算法均能得到最优的最小生成树代价2 256。在种群规模为50时，运行100次中，SAPGA算法有67次得到了最优解，比单亲遗传算法PGA的结果提高了12%左右。在种群规模为100时，运行100次中，SAPGA有83次得到了最优解，比单亲遗传算法PGA提高了15%左右。从解的平均值也可以看出，SAPGA算法的效果在两种规模下都比PGA算法好。从实验结果可以看出，本文所提算法因为有了模拟退火思想的加入，能解决解个体的跳跃问题，提高获得全局最优解的可能性，所以在求解DCMSTP时能得到较好的结果，最优解出现的次数有一定的增加。

4 结束语

本文针对度约束的最小生成树模型求解问题，提出了改进SAPGA算法。改进后的算法融合并改进了单亲遗传算法和模拟退火算法。单亲遗传算法中变异算子改进的两种方法都不会出现不可行解，省去了解是否可行的检测，并且自适应的变异率能加速收敛，因此大大加快了求解速度。同时，算法中模拟退火的思想能增加解的多样性，保证种群跳出局部最优，收敛到全局最优，改善单亲遗传算法的解的跳跃问题，提高得到全局最优解的可能性。该模型的求解方法可以在网络通信架构等多个问题中得到很好的应用。