基于支持向量机的改进遗传算法在模糊最短路问题中的应用

The Application of Improved Genetic Algorithm Based on Support Vector Machine in Fuzzy Shortest Path Problem

摘要: 最短路问题是图论中重要的优化问题之一。随着网络的增大，求最短路径的时间复杂度越来越大。本文基于模糊图中部分路径的长度，设计了基于支持向量机的改进遗传算法，并用该算法求得了模糊最短路问题的较好近似解。最后通过数值算例模拟该算法，并与标准的遗传算法作对比，结果表明该算法是有效的。

Abstract: The shortest path problem is one of the important optimization problems in graph theory. As the network grows, the time complexity of finding the shortest path is getting bigger and bigger. Based on the length of some paths in the fuzzy graph, this paper designs an improved genetic algorithm based on support vector machines, and uses this algorithm to obtain a better approximate solution to the fuzzy shortest path problem. Finally, the algorithm is simulated through a numerical calculation example and compared with the standard genetic algorithm. The result shows that the algorithm is effective.

1. 引言

最短路问题是图论中经典的优化问题之一。在经典最短路问题中，两点之间的边的权重是确定的数，一般通过边的权重找到最短路径。在最短路问题的应用中，边可以表示距离、时间、成本等其他变量，而这些涉及到的变量一般都是不确定的，因而用模糊数表示边的权重不失为一种有效方法。过去的20年里，一些学者已经对不同类型的模糊数作为边的权重的最短路问题进行了大量的研究。对于由有限个顶点和有向边所构成的网络，边的权重都可表示为模糊数，则路的长度为组成路的所有边权的和，找到长度最短的路即为模糊最短路问题。

Dubois和Prade [1] 首先对模糊最短路问题进行了研究，其算法推广了经典的Floyd和Ford-Moore-Bellman算法。Chanas和Kamburowski [2] 引入模糊偏好关系的概念，并将其应用于求最短路问题的算法中。Takahashi和Yamakami [3] 提出了有模糊边长的最短路问题，扩展了Okada [4] 提出的方法，并介绍了一种确定大型模糊图近似最短路径的遗传算法。Nayeem和Pal [5] 用三角模糊数和区间数表示边的权重，其提出的算法可以解决模糊最短路问题。Deng [6] 等人扩展了经典Dijkstra算法去求在不确定环境中的最短路问题。他们使用梯形模糊数表示模糊图边的权重，同时在算法中考虑了模糊数的分级平均值来确定模糊路径的长度，这也有助于比较两个不同模糊路径之间的模糊路径长度。Hassanzadeh [7] 等人使用基于α截集的加法运算来确定路径的长度，针对大规模模糊图中模糊数相加的复杂性，提出了一种求解模糊最短路问题的遗传算法。Lin [8] 等人使用梯形模糊数的分级平均值来比较模糊路径的长度，改变遗传算法的交叉过程来确定具有模糊边长的模糊图的源节点和目标节点之间的最短路径。关于最短路问题的研究可参阅文献 [9] [10] [11]。

在模糊环境下，许多学者已经做了大量的工作，给出了求解最短路问题的精确算法、启发式算法和元启发式算法。精确算法能获得图的起始节点到目标节点的精确最短路径。然而当图的规模较大时，精确算法需要大量的时间来获得最短路径。元启发式算法则能够有效地解决最短路问题，其中遗传算法是求解最短路问题的一种流行而有效的算法。在该算法中，染色体提供了决策问题的潜在解决方案，一组不同的染色体产生种群，种群中的染色体进行交叉和变异来产生新的染色体，后通过选择将适应度值较大的染色体淘汰，从而得到决策问题的最优解。

在现实生活中，由于道路状况、交通负荷、事故和变化的天气条件等，决策者很难决定任何路线的准确成本，所以用模糊数作为边的权重。随着网络的增大，求最短路径的时间复杂度越来越大。由于时间和经费的限制，只能对模糊图中从起始节点到目标节点的部分路径的总长度进行估算。为了求模糊图从起始节点到目标节点的最短路，需要分析已知路径的长度，以预测未知路径的长度。因此，针对上述问题，本文提出了基于支持向量机的改进遗传算法。首先把已知的路径作为输入数据，路径的长度作为输出数据训练支持向量机，通过训练后的支持向量机来预测未知路径的长度。其次把路径作为遗传算法中的染色体，把支持向量机预测的路径长度作为染色体适应度值，通过遗传算法得到最短路径及其长度。最后通过数值算例分析表明算法的有效性。

2. 预备知识

2.1. 基本概念

定义1 [8] 称模糊数 $\tilde{U}=\left\{\underset{\_}{u},u_1,u_2,\bar{u}\right\}$ 为梯形模糊数，如果其隶属度函数可以表示为：

${\mu }_{\tilde{U}}\left(y\right)=\{\begin{array}{l}\frac{y-u_1}{u_1-\underset{\_}{u}}如果u_1\ge y\ge \underset{\_}{u}\\ 1如果u_1\ge y\ge u_2\\ \frac{\bar{u}-y}{\bar{u}-u_2}如果\bar{u}\ge y\ge u_2\\ 0如果y<\underset{\_}{u}或y>\bar{u}\end{array}$ (1)

其中 $u_1$ 和 $u_2$ 是两个主要的可能值， $\underset{\_}{u}$ 和 $\bar{u}$ 分别是最小可能值和最大可能值。

定义2 [8] 设 $\tilde{U}=\left\{\underset{\_}{u},u_1,u_2,\bar{u}\right\}$ 为梯形模糊数，则 $\tilde{U}$ 的分级平均值可定义为：

$P\left(\tilde{U}\right)=\frac{1}{6}\left(\underset{\_}{u}+2u_1+2u_2+\bar{u}\right)$ (2)

定义3 [8] 设 $\tilde{U}=\left\{\underset{\_}{u},u_1,u_2,\bar{u}\right\}$ 和 $\tilde{V}=\left\{\underset{\_}{v},v_1,v_2,\bar{v}\right\}$ 为梯形模糊数，则

1) 如果 $P\left(\tilde{U}\right)=P\left(\tilde{V}\right)$，那么 $\tilde{U}=\tilde{V}$ ；

2) 如果 $P\left(\tilde{U}\right)>P\left(\tilde{V}\right)$，那么 $\tilde{U}>\tilde{V}$ ；

3) 如果 $P\left(\tilde{U}\right)<P\left(\tilde{V}\right)$，那么 $\tilde{U}<\tilde{V}$。

定义4 [8] 设 $\tilde{U}=\left\{\underset{\_}{u},u_1,u_2,\bar{u}\right\}$ 和 $\tilde{V}=\left\{\underset{\_}{v},v_1,v_2,\bar{v}\right\}$ 为梯形模糊数，则 $\tilde{U}$ 和 $\tilde{V}$ 的加法运算定义为：

$P\left(\tilde{U}\oplus \tilde{V}\right)=\frac{1}{6}\left(\underset{\_}{u}+2u_1+2u_2+\bar{u}\right)+\frac{1}{6}\left(\underset{\_}{v}+2v_1+2v_2+\bar{v}\right)$ (3)

2.2. 支持向量机

支持向量机是一种泛化能力强、精度高的回归算法，适用于解决小样本、非线性、高维数据等问题，其基本思想是在特征空间中构建最优超平面，使得学习器得到全局最优解。

设训练样本集为 $T=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_n,y_n\right)\right\}$，其中 $x_i$ 为样本特征， $y_i$ 为样本属性值。根据文献 [12]，构造损失函数并采用以下极小化优化模型来确定回归函数，即

$\begin{array}{l}\min \frac{1}{2}{\Vert \omega \Vert }^2+C{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left({\xi }_i^{*}+{\xi }_i\right)}\\ \text{s}\text{.t}.\{\begin{array}{l}{y}_i-\langle \omega ,\varphi \left(x_i\right)\rangle -b\le \epsilon +{\xi }_i^{*}\\ \langle \omega ,\varphi \left(x_i\right)\rangle +b-y_i\le \epsilon +{\xi }_i\\ {\xi }_i^{*},{\xi }_i\ge 0\left(i=1,2,\cdots ,n\right)\end{array}\end{array}$ (4)

式中： $\omega$ 为权值； $\frac{1}{2}{\Vert \omega \Vert }^2$ 控制模型的泛化能力；C为惩罚因子； ${\xi }_i^{*},{\xi }_i$ 为松弛因子； $\varphi \left(x\right)$ 是将数据映射到高维空间的非线性变换；b为偏置； $\epsilon$ 为误差上限。

利用拉格朗日乘子法求解该模型可得到支持向量机回归函数：

$f\left(x\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left({\alpha }_i-{\alpha }_i^{*}\right)k\left(x_i,x_j\right)}+b$ (5)

其中： ${\alpha }_i$ 和 ${\alpha }_i^{*}$ 为拉格朗日乘子， $k\left(x_i,x_j\right)=\varphi \left(x_i\right)\varphi \left(x_j\right)$ 为核函数，需满足Mercer条件，本文选取高斯核

函数，为

$k\left(x_i,x_j\right)=\exp \left(-\frac{{\Vert x_i-x_j\Vert }^2}{2{\sigma }^2}\right)=\exp \left(-g{\Vert x_i-x_j\Vert }^2\right),g>0$ (6)

可见，在支持向量机计算过程中涉及两个参数，即，惩罚因子C和核函数参数g，这两个参数的位置对于支持向量机回归模型有较大影响，因此，本文采用粒子群算法对参数进行优化 [13]。

3. 模糊最短路问题

给定一个有向赋权的模糊图 $D=\left(V,E\right)$，设节点集为 $V=\left\{v_1,v_2,\cdots ,v_p\right\}$，边集为 $E\subseteq V\times V$。每条边用节点的有序对 $\left(v_i,v_j\right)$ 来表示，且 $v_i\ne v_j$，并假设从节点 $v_i$ 到 $v_j$ 至多只有一条有向边。路径的起始节点为u，目标节点为v。考虑与边 $\left(v_i,v_j\right)$ 有关的非负梯形模糊数 ${\tilde{c}}_{v_i{v}_j}$， ${\tilde{c}}_{v_i{v}_j}$ 表示从节点 $v_i$ 到 $v_j$ 的模糊费用。

给定任意一条从源节点到目标节点的路径，对所有的边 $\left(v_i,v_j\right)$ 赋值，如若边 $\left(v_i,v_j\right)$ 在该路径中，则 $x_{v_i{v}_j}=1$，否则 $x_{v_i{v}_j}=0$。该模糊最短路问题的线性规划模型如下：

$\begin{array}{l}\min {\displaystyle \underset{v_i\in V}{\sum }{\displaystyle \underset{v_j\in V}{\sum }{\tilde{c}}_{v_i{v}_j}{x}_{v_i{v}_j}}}\\ \text{s}\text{.t}\text{.}{\displaystyle \underset{v_j\in V}{\sum }{x}_{v_i{v}_j}}-{\displaystyle \underset{v_j\in V}{\sum }{x}_{v_j{v}_i}}=\{\begin{array}{l}1v_i=u\\ 0v_i\ne u,v\\ -1v_i=v\end{array}\\ x_{v_i{v}_j}\in \left\{0,1\right\}\\ \forall v_i\in V\end{array}$ (7)

4. 标准遗传算法

遗传算法是模拟自然界生物进化现象发展起来的随机全局搜索优化方法，主要包括以下步骤：

1) 染色体编码

创建由染色体组成的大小为N的初始种群。一条从起始节点到目标节点的路径代表一个染色体。

2) 计算适应度值

染色体的适应度值是区分种群中染色体好坏的标准。在最短路问题中，目标是确定模糊图中指定的起始节点u和目标节点v之间的最短路径。因此染色体的适应度值可以用模糊路径的长度来表示。一条从u到v的路径，使用梯形模糊数的加法运算计算该模糊路径的梯形模糊数，后使用梯形模糊数的分级平均值来计算路径的长度，即该染色体的适应度值。

3) 选择、交叉和变异的方法

染色体通过执行选择、交叉和变异产生新的染色体，形成新的种群。

① 选择：选择是从旧种群中选择优质个体，淘汰部分个体，产生新种群的过程。一般采用轮盘赌选

择方法 [14]，假设初始种群数量为N，种群中每个染色体的适应度值为 $f_i\left(i=1,2,\cdots ,N\right)$， $g_i=\frac{1}{f_i}$，每个染色体的选择概率为 $p_i=\frac{f_i}{{\displaystyle \underset{k=1}{\overset{N}{\sum }}{f}_k}}\left(i=1,2,\cdots ,N\right)$，累积概率为 $Q_i={\displaystyle \underset{k=1}{\overset{i}{\sum }}{p}_k}\left(i=1,2,\cdots ,N\right)$。由上述方法可知，每个染色体的适应度值越小，被选择的可能性越大。

② 交叉：在选定的父染色体上执行交叉，可以生成新的染色体，即子染色体。交叉概率表示执行交叉操作的频率，是执行交叉操作的主要参数。一般采取单点交叉 [14]，同时为了避免交叉后产生不可行解，将两条染色体之间的关系分为以下两种情况：

情况1：两条染色体中间存在公共边；

情况2：两条染色体除了前后有公共边之外，无任何其它公共边。

交叉操作的思路是根据交叉概率选择是否执行交叉，若交叉则随机选择两条染色体，从两条染色体的起始边开始对比，寻找是否存在相同边，若存在相同边之后有不同边存在，则将从不同边开始到目标节点的所有边进行交换。

情况1：从边w之后染色体1与染色体2进行交叉，交叉前后分别为：

染色体1： $1\to 2\to 4\to w\to 8\to 10\to 14\to 17$ 染色体1'： $1\to 2\to 4\to w\to 7\to 9\to 11\to 13\to 17$

染色体2： $1\to 5\to w\to 7\to 9\to 11\to 13\to 17$ 染色体2'： $1\to 5\to w\to 8\to 10\to 14\to 17$

情况2：此时若进行不同边的交叉，即染色体1变为了染色体2，染色体2变为了染色体1，无任何意义。因此采用如下方法：寻找染色体1与染色体2中有双向边相连的边，即：染色体1中某边的邻接边同时也是染色体2中某边的邻接边，此时，引入边w对染色体1与染色体2进行交叉。交叉前后分别为：

染色体1： $1\to 2\to 4\to 8\to 10\to 14\to 17$ 染色体1'： $1\to 2\to 4\to w\to 7\to 9\to 11\to 13\to 17$

染色体2： $1\to 5\to 7\to 9\to 11\to 13\to 17$ 染色体2'： $1\to 5\to w\to 8\to 10\to 14\to 17$

若选择的两条染色体不满足情况1，2，则重新选择两条染色体进行交叉。

③ 变异：选择一条的染色体，以指定的变异概率执行变异。一般采用的变异策略 [14] 为：根据变异概率选择是否执行变异，若变异则随机选择一条染色体进行变异，然后随机选择要进行变异的边w，将染色体从该边处断开，按照如下方法产生边w的前一条边a和后一条边b之间的随机路径：

步骤1若边a只有w一条邻接边，则重新选择变异位置。否则，执行步骤2；

步骤2判断边a的邻接边中有没有终点为边b起点的边(除去边w)，如有则用此边替换边w，终止程序。若没有，执行步骤3；

步骤3选择边a的所有邻接边中终点与边b的起点距离最短的边c，将其替换掉边w，并执行步骤2；

步骤4若随机路径中插入了5条边，仍没有连接到边b，则重新选择变异位置；

步骤5将产生的随机路径插入到原路径的变异位置。

4) 更新

所有新生成的染色体放入当前种群中生成新的总体，用于进一步的计算。

5) 终止条件

判断该算法是否达到最大迭代次数，若达到，终止算法并返回该种群中适应度低的染色体，该染色体为决策问题的最优解；否则，转到步骤(2)继续执行直到满足条件。

5. 基于支持向量机的改进遗传算法

本文提出了基于支持向量机的改进遗传算法，其基本步骤如下：

1) 染色体编码

在算法中，每个染色体都描述了模糊图的起始节点和目标节点之间的路径。模糊图中的每个节点都被赋予唯一的整数。在模糊最短路问题中，染色体的第一个节点总是起始节点。为了创建编码染色体所需的路径，首先由起始节点生成路径的下一个节点。为了解决这个问题，从起始节点的相邻节点列表中随机选择一个节点，例如w。如果所选节点w不存在于染色体中，则节点w被用作染色体中起始节点的下一个节点，再由w作为起始节点，执行上述方法直到到达染色体的目标节点。循环上述方法直到到达染色体的初始种群数目。

2) 基于支持向量机计算染色体适应度值

染色体的适应度值是区分种群中染色体好坏的标准。给定模糊图及其边的权重，随机生成N条从起始节点到目标节点的路径作为样本集，通过梯形模糊数的加法及分级平均值的定义计算路径的长度，将其作为样本的属性值，将生成的N个样本作为训练集。采用基于粒子群算法优化支持向量机，从而得到支持向量机回归函数。在算法中，对任意给定的一条从起始节点到目标节点的路径，采用支持向量机回归函数预测得到样本属性值并将其作为染色体的适应度值。

3) 选择、交叉和变异的方法

① 选择：选择方法用于选择更多数量的具有较低适应度值的染色体，随机选取的方式，保证染色体选择的偶然性和随机性。该算法采用二元锦标赛选择技术，从当前种群中随机选择两个染色体，根据每个个体的适应度值，选择其中适应度值低的个体进入下一代种群。多次重复上述过程，直到新的种群规模达到原来的种群规模。

② 交叉：采用交叉方法重组两条父染色体，生成新的子染色体。在该算法中，使用了以下交叉方法：

步骤1从当前种群中随机选择两个父染色体F₁和F₂。

步骤2从F₁中随机选取一段基因(起始节点和目标节点除外)。

步骤3使用获取的该段基因生成子染色体，该段基因在子染色体中的位置与在F₁中的位置相同，子染色体的起始节点和目标节点与F₁相同，且子染色体的长度与F₁相同。

步骤4从左到右依次选取F₂中的节点(起始节点和目标节点除外)，如果F₂中的节点没有出现在子染色体中，那么将该节点放入到子染色体中第一个空缺位置中，否则重新选取F₂中的节点。重复上述选取方法直到将子染色体的所有空缺位置填满。

若通过上述方法无法将子染色体的空位填满，则重新选择两条染色体进行交叉。

③ 变异：染色体以指定的变异概率执行变异操作。该算法先随机选取一条染色体，后随机指定染色体上的某一节点进行变异。

4) 更新染色体

为了减少运行时间，本算法采用上述交叉和变异方法。但上述交叉和变异方法产生的个体不一定为可行解，为了增加可行解的个数，此算法要尽可能增大交叉和变异的次数。因此需要判断交叉和变异的次数是否等于M，若等于则停止交叉变异；否则，继续交叉变异。

通过上述交叉和变异方法会生成的新的个体，该算法需要判断新生成的个体是否为染色体。若新生成的个体为染色体，则该个体是一条从起始节点u到目标节点v的路径。首先假设新生成的个体的起始节点u的下一个节点为w，判断节点w是否为起始节点u的相邻节点，若节点w不为起始节点u的相邻节点，则新生成的个体不为染色体，若节点w为起始节点u的相邻节点，则从节点w作为起始节点并执行上述方法直到到达新生成个体的目标节点v。将所有新生成的染色体放入当前种群中生成新的种群，用于进一步的计算。

5) 终止条件

判断该算法是否达到最大迭代次数，若达到，终止算法并返回该种群中具有最小适应度值的染色体，该染色体为模糊图中从起始节点到目标节点的最短路；否则，转到步骤(2)继续执行直到满足条件。

算法的流程图如图1所示。

Figure 1. Flow chart of improved genetic algorithm based on support vector machine

图1. 基于支持向量机的改进遗传算法流程图

6. 数值算例分析

考虑图2所示的交通网络模糊图，包含24个节点和43条边，在此模糊图上执行标准遗传算法与基于支持向量机的改进遗传算法。假设模糊图的起始节点为1，目标节点为24。表1给出了模糊图边的权重，表示从一个节点到另一点节点的模糊成本。

算法采用MATLAB R2019b软件，在Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz 2.30 GHz，内存8.00 GB，Window10平台上编码实现。本文对两种遗传算法的参数设置均相同，并取迭代次数为20次，种群规模为24，每一代交叉和变异的次数为100次，交叉概率与变异概率分别为0.7与0.6。

Figure 2. Fuzzy graph of traffic network

图2. 交通网络模糊图

Table 1. The length of fuzzy graph

表1. 模糊图的弧长

为验证本文所提算法的有效性，本文分别用标准的遗传算法和基于支持向量机的改进遗传算法进行20次实验，程序结果列于表2。

Table 2. Program results of the two algorithms

表2. 两种算法的程序结果

通过表2可知两种算法的对比结果列于表3。

Table 3. Comparison results of the two algorithms

表3. 两种算法的对比结果

由表3可知，使用标准的遗传算法求得的模糊最短路为： $1\to 4\to 7\to 10\to 16\to 20\to 24$，模糊最短路的平均长度为34.3333；使用基于支持向量机的改进遗传算法求得的模糊最短路同样为： $1\to 4\to 7\to 10\to 16\to 20\to 24$，模糊最短路的平均长度为34.34332，两种算法求得的最短路相同，长度近似相等。由此可知，本文所提出的基于支持向量机的改进遗传算法可行的。与此同时，在两种算法各进行20实验后，标准的遗传算法得到正确最短路结果的次数为6次，而本文提出的基于支持向量机的改进遗传算法得到正确最短路结果的次数为9次，由此可知，本文所提算法在保证结果正确的同时具有更为稳定的结果。

7. 结论

模糊最短路问题是模糊图论领域的一个非常流行的组合优化问题。随着网络的增大，求最短路径的时间复杂度越来越大。由于时间和经费的限制，只能对模糊图从起始节点到目标节点的部分路径总长度进行估算。为了找出模糊图中起始节点到目标节点的最短路径，本文使用支持向量机算法通过已知路径及其长度对未知路径的长度进行预测，并将其作为遗传算法中染色体的适应度值。然后使用遗传算法对该模糊图的最短路问题进行求解。最后，在数值实例中，通过与标准的遗传算法进行对比，表明本文所提出的基于支持向量机的改进遗传算法是有效且较稳定的。

NOTES

^*通讯作者。