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

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中结点之间的最短路径。问题的主要种类有：确定起点的最短路径问题；确定终点的最短路径问题；确定起点终点的最短路径问题；全局最短路径问题。其中全局最短路径是求连接图中所有点的最短路径，它的限制最少，答案的可能性却最多。同时当加入一定的限制条件后也可以相应的转化成前3种问题，所以更值得研究推广。
现有的解决最短路径问题的遗传算法大多是将图转化成一棵树，通过各种遍历手段，得到与这棵树唯一对应的一个数组排列(或向量)，并以此作为遗传算法的种群个体。生成树以及遍历方法的优劣就决定了该种遗传算法的好坏。本文并不是提出一种改进的生成树或遍历的方法，相反，完全随机生成树，不做任何限制，也未对树进行遍历，只是在遗传算法对每代种群进行优胜劣汰时，同时对不合格的个体进行淘汰。省略了生成树以及遍历的过程，也就相当于化简了编码解码过程。

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

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


2 编码
遗传算法的编码很重要，因为在整个过程中会不断地对基因做交叉变异以及适应度的运算，所以编码方式直接影响算法的速度。很明显，编码后的基因链越短，每个基因位上的基因种类越少，算法的运行速度越快。使用二进制编码的话，虽然每个基因位上的基因种类只有2种，但如果点的个数较多，将会使基因链过长，在遗传变异的过程中中间节点情况太多，使整个过程变得过于复杂，所以这里选择用十进制编码的方法。
一般的编码方法都是将节点和线段编号，再通过某种运算对用这些编号构成的向量进行一系列处理，得到较原向量更为简单或与连接方法能一一对应的新向量，并以此作为种群个体。本文的方法中，线段不但有编号，而且具有方向性。利用其方向性线段编号可以直接作为个体使用，省略了一般情况下的编码解码过程，所以运算更加简单快捷。
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个点，两两相连共有lO条线段，形成个体需要其中的4条线段，图l所示的2个个体对应的基因链即种群个体分别为{1、3、4、5}和{1、2、5、10}。

2．2 合法性判断
很明显不是任意4条线(以图l的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}(图l第2个个体)，连接了所有点，但1、2、5构成回路导致5个点被分成了两部分，相当于有一部分没有被连接进网络，此个体也要直接淘汰。
为了判断上述3个条件是否满足，需要建立2个数组，点信息数组Point[]和线信息数组Line[]。Point[]是二维数值数组，按点的编号顺序存储，每一行存有一个点的横纵坐标2个数。Line[]是二维数值数组，按线段的编号顺序存储，每一行存有一条线段信息，包括线段的端点和长度3个数。图2为5节点时LabVIEW前面板的模拟图及2个数组的存储情况。

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