基于LabVIEW仿真的全局最短路径的遗传算法设计

杨多星，刘蕴红

（大连理工大学 电气工程学院，辽宁 大连 116023）

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中结点之间的最短路径。问题的主要种类有：确定起点的最短路径问题；确定终点的最短路径问题；确定起点终点的最短路径问题；全局最短路径问题。其中全局最短路径是求连接图中所有点的最短路径，它的限制最少，答案的可能性却最多。同时当加入一定的限制条件后也可以相应的转化成前3种问题，所以更值得研究推广。

现有的解决最短路径问题的遗传算法大多是将图转化成一棵树，通过各种遍历手段，得到与这棵树唯一对应的一个数组排列（或向量），并以此作为遗传算法的种群个体[1-3]。生成树以及遍历方法的优劣就决定了该种遗传算法的好坏[4]。本文并不是提出一种改进的生成树或遍历的方法，相反，完全随机生成树，不做任何限制，也未对树进行遍历，只是在遗传算法对每代种群进行优胜劣汰时，同时对不合格的个体进行淘汰。省略了生成树以及遍历的过程，也就相当于化简了编码解码过程。

1 问题描述

在一定区域内分布着一些点，要使用线段将所有点连接到同一个网络下。如何连接这些点才能令使用到的所有线段的总长度最短。建立相应的数学模型。设有M个点，坐标记为Pi（xi，yi），1≤i≤M 则每两个点之间的距离为

要连接M个点并使总距离最短，则至少要有M-1条线段，那么目标函数即总距离

2 编 码

遗传算法的编码很重要，因为在整个过程中会不断地对基因做交叉变异以及适应度的运算，所以编码方式直接影响算法的速度。很明显，编码后的基因链越短，每个基因位上的基因种类越少，算法的运行速度越快。使用二进制编码的话，虽然每个基因位上的基因种类只有2种，但如果点的个数较多，将会使基因链过长，在遗传变异的过程中中间节点情况太多，使整个过程变得过于复杂，所以这里选择用十进制编码的方法[5]。

一般的编码方法都是将节点和线段编号，再通过某种运算对用这些编号构成的向量进行一系列处理，得到较原向量更为简单或与连接方法能一一对应的新向量，并以此作为种群个体。本文的方法中，线段不但有编号，而且具有方向性。利用其方向性线段编号可以直接作为个体使用，省略了一般情况下的编码解码过程，所以运算更加简单快捷。

2.1 个体确定

M个点两两相连，共有M（M-1）/2条线段，将所有线段编号。编号的顺序规则为：

1）从1号点出发，按顺序依次连接2号点、3号点......M号点的线段，编号为1～M-1；

2）从2号点出发，按顺序依次连接3号点、4号点......M号点的线段，编号为M～2M-3；

3）直到M-1号点连接M号点的线段为最后一条线段。

每个基因就是1条线段，那么每个基因就有种可能，要使用数量最少的线段就连接所有点，需要M-1条线段。如图1所示网络，共有5个点，两两相连共有10条线段，形成个体需要其中的4条线段，图1所示的2个个体对应的基因链即种群个体分别为{1、3、4、5}和{1、2、5、10}。

图1 5节点网络和2个个体Fig.1 Five-node network and two individuals

2.2 合法性判断

很明显不是任意4条线（以图1的5个点为例）都适合作为初始种群的个体，所以在使用每个种群个体前判断其合法性就相当于减少了基因的种类，大大化简了运算过程，免去一些不必要的计算，加快收敛速度。合法性可以通过以下3个条件进行判断：

条件1：不能出现重复编号。

如{1、1、2、3}，其实只有 3 条线，这个个体必然是错误的，在最开始就可以淘汰，不需要进入循环中运算。

条件2：4条线的编号必须从小到大。

如{1、2、3、5}和{5、3、1、2}是 2 种不同的种群个体，但实质上是同样的4条线，进行了从小到大的定义后就可以避免产生大量的最优解，导致运算混乱。

条件3：必须保证所有点连在一起（或者没有回路）。

如{1、2、5、10}（图 1 第 2 个个体），连接了所有点，但 1、2、5构成回路导致5个点被分成了两部分，相当于有一部分没有被连接进网络，此个体也要直接淘汰。

为了判断上述3个条件是否满足，需要建立2个数组，点信息数组Point[]和线信息数组Line[]。Point[]是二维数值数组，按点的编号顺序存储，每一行存有一个点的横纵坐标2个数。Line[]是二维数值数组，按线段的编号顺序存储，每一行存有一条线段信息，包括线段的端点和长度3个数。图2为5节点时LabVIEW前面板的模拟图及2个数组的存储情况。

图2 点信息数组、线信息数组和模拟图Fig.2 Point information array、line information array and simulated diagram

条件 2易满足，为满足条件 1和条件 3，定义（M-1）×M阶判断矩阵A，表示被选中的线段与各节点的关系。每一行对应一条线段，每一列依次对应M个节点。在定义Line[]的2个端点时，都是序号小的节点在前，大的在后，所以不妨把每条线段看成有方向的矢量，从小号节点指向大号节点。在矩阵对应的位置，起点为-1，终点为1，其他点为0。以图1为例，2 个个体 对应的判 断矩阵分 别为 A1、3、4、5和 A1、2、5、10。

判断矩阵 A1、3、4、5的行向量线性不相关，秩是列数 4，也就是被选中的线段个数即每个个体的基因数。个体{1、2、5、10}因为 1、2、5 构成了回路，可以得到 1+5=2，其判断矩阵 A1、2、5、10中对应的3个行向量必定是同样的关系，则这3个行向量线性相关。 所以判断矩阵 A1、2、5、10的秩必然小于列数 4。 由矢量图能看出，每多一条回路，判断矩阵的秩就会减少1。当出现重复编号时，如{1、1、2、5}，则有 2个行向量相同，其判断矩阵A的秩必然也小于列数4.

综上，Point[]是已知的。由Point[]可以得到Line[]（如图3（a））。任意给定4条线的个体，由Line[]和Point[]得到判断矩阵 A，如果 rank（A）=M-1，则满足 3 个条件（如图 3（b））；否则，该个体非法。

3 初始种群获取

图3 求Line[]并判断合法性Fig.3 Getting Line[]and judging legitimacy program

根据上面的说明，本文在获取初始种群时，每一个个体首先是从M（M-1）/2条线段中随机取出M-1条。取得的方法是：

1）建立M（M-1）/2阶布尔数组，数组里每个元素是假常量；

2）产生一个0～1的随机数与M（M-1）/2相乘并向下取整，随机得到一个整数 n，则 n∈[0，M（M-1）/2-1]；

3）将布尔数组中第n个元素替换为真常量；

4）重复2、3步直到布尔数组中有了M-1个真常量；

5）依次提取布尔数组中的每个真常量的索引值并加1。其取得方法的框图如图4所示。

图4 利用随机数产生一个随机个体Fig.4 A random individual with randam number

得到的M-1阶常数数组就是一个随机产生的初始个体，而且此个体直接满足条件1和条件2。对这样的个体进行合法性判断，如果不合法舍去重新产生新个体。如果合法保留再生成下一个个体。用for循环来控制种群大小。

4 适应度函数

因为目标函数是求最小值，而且D肯定大于0，所以不妨直接以目标函数的倒数作为适应度函数。

5 遗传策略

本文基于Srinivas提出的自适应遗传算法（Adaptive GA，简称AGA）[7]提出新的编码方式下的遗传策略。

式中，pc表示交叉率，pm表示变异率，fmax表示种群最大适应度值，favg表示种群平均适应度值，f′表示在要交叉的两个个体中较大的适应度值，f表示要变异的个体适应度值。k1，k2，k3，k4是在0和1之间取值的常数，其中，k3和k4较大。

式（3）和式（4）是AGA根据适应度值调节后的交叉率和变异率，它较好地解决遗传算法中全局搜索和局部搜索的平衡问题，提高了收敛速度。

5.1 杂交

杂交运算是遗传算法扩大优秀基因影响的重要方法。但本文使用的编码方法中，如果使用简单的单点交叉方法，无疑很大概率上将产生不合法的无效子代。如图1中的5个点，两个父代{1、2、3、4}和{4、5、8、10}做交叉运算，无论交叉点在哪都会产生含有2个4号线段的非法子代，不满足条件1。

为了改善这种情况，本文摒弃了双父代杂交而采用一种"群体精英父代杂交"的方法[6]。因为杂交运算就是为了使优秀基因快速繁殖，扩大影响，所以不妨直接判定哪些基因是有较大概率优秀的。举例说明判断方法，选择所有f′＞favg的父代个体，这些个体明显都是优秀的，从这些优秀父代中提取出共有的或出现次数较多的基因，因为优秀父代中含有优秀基因的可能大，所以这些共有的基因就更可能是优秀基因。保留这些基因，在剩余的基因位上随机产生新的基因。最后从产生的这些新个体和f′＜favg的低适应度父代中选出适应度高的一部分作为子代，它们与开始的那些优秀父代一起合成新的子代。因为实际上并没有使用单点杂交的方法，所以不使用式（3）。

5.2 变异

按式（4）计算，如果一个父代个体要变异时，从其中随机取一条线段除去换上一条新的线段。为了提高变异操作提供新基因的效率，防止无方向性的变异产生大量冗余，新的线段要有一个端点不变。如图5所示，当除去线段12时，新产生的线段必须以节点3或6为端点，不算线段12，节点3、节点6分别还可以与其他M-2个节点产生共2M-4个子代个体，当然其中有很多新个体是不合法的，从合法的子代个体中选择适应度最高的遗传到下一代。这样，经过几代变异后，个体就会逐渐趋于所求目标。

图5 个体变异过程Fig.5 The mutation process of individuals

为了防止局部收敛，即使产生的子代个体适应度不如父代个体，也要淘汰父代个体。

5.3 精英保留

根据上述方法，在进化中很可能导致高适应度个体被意外的破坏，减缓进化速度甚至导致局部收敛。所以每次进化前取出当代个体中适应度最高的一个个体直接进入下一代，保证最优基因的安全。

6 仿真实验

选取一组数据（见表1）进行仿真实验，种群数量取50个，计算100代。

表1 20个点的编号和坐标Tab.1 Serial numbers and coordinates of 20 points

得到仿真结果如图6所示。

图6为分别截取了运行到不同代数时的结果。图6（a）表示所有点的位置及所有可能的连线，图6（b）～图6（d）中数字含义，括号内的数字表示运行代数，括号外是此时线段的总长度。图6（d）显示最终总长度为1087.77。

图6 仿真结果Fig.6 Simulation result

7 结 论

综上所述，此方法可以有效地解决全局最短路径问题。相对于“旅行商问题”单一起点终点的“一笔画”情况和繁复的编码解码运算，本文的方法更具有广泛性。因为节省了一般的编码解码过程，所以运算更加快捷，结果更易识别。随着约束条件的改变，只需相应的修改目标函数即可，不会影响程序的其他功能。该方法可以适用多类工程设计，如Zigbee无线模块组网、城乡间道路和配电网设置、农田灌溉点之间的管道连接、多目标的运输问题等等。

[1]章文俊，程浩忠，王一，等.基于树形结构编码单亲遗传算法的配电网优化规划[J].电工技术学报，2009，24（5）:154-160.ZHANG Wen-jun， CHENG Hao-zhong， WANG Yi，et al.Distribution network optimal planning based on tree structure encoding partheno-genetic algorithm [J].Transactions of China Electrotechnical Society， 2009（5）:154-160.

[2]何忠华，孟祥瑞.基于节点编码的最小生成树算法[J].黑龙江科技信息， 2008（34）:90.HE Zhong-hua，MENG Xiang-rui.Minimum spanning tree algorithm based on node-encoding [J].Heilongjiang Science and Technology Information， 2008（34）:90.

[3]马孝义，范兴业，赵文举，等.基于整数编码遗传算法的树状灌溉管网优化设计方法[J].水利学报，2008，39（3）:373-397.MA Xiao-yi， FAN Xing-ye， ZHAO Wen-ju，et al.Tree-type pipe network optimization design method based on integer coding genetic algorithm[J].Journal of Hydraulic Engineering，2008， 39（3）:373-397.

[4]田小梅，龚静.遗传算法在度约束最小生成树问题中的应用 [J].湖南环境生物职业技术学院学报，2009，15（3）:1-4.TIAN Xiao-mei，GONG Jing.Applications of genetic algorithm to degree-constrained minimum spanning tree[J].JournalofHunan EnvironmentBiologicalPolytechnic，2009，15（3）:1-4.

[5]陆锁军，郭钊侠，方建安.基于多父辈交叉的次序编码遗传算法及其性能[J].东华大学学报：自然科学版，2008，34（4）:449-453.LU Suo-jun， GUO Zhao-xia， FANG Jian-an.On the performance of order based genetic algorithm with multiparent crossover[J].Journal of Donghua University:Natural Science，2008， 34（4）:449-453.

[6]胡宏银，朱绍文，张大斌，等.用实数编码的遗传算法构造斜决策树[J].计算机科学，2001，28（2）:108-110.HU Hong-yin， ZHU Shao-wen， ZHANG Da-bin，et al.Oblique decision tree construction with decimal-coded genetic algorithm[J].Computer Science， 2001， 28（2）:108-110.

[7]Srinivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithm [J].IEEE Transactions on Systems：Man and Cybernetics， 1994， 24（4）:656-667.