遗传算法求解最短路径问题

遗传算法求解最短路径问题3.3.1最短路径问题的图论描述在中，与V中的有序偶（Vi，Vj）对应的边e，称为图的有向边，同时与V中的顶点的无序偶Vi*Vj相对应的边e，称为图的无向边，并且如果在中，与V中的顶点的无序偶Vi*Vj相对应的边e，全部都是无向边的话，这个图就叫做无向图，与V中的有序偶（Vi，Vj）对应的边e，都是有向边的话，这个图就叫做有向图。为了方便实验，与进行仿真分析，本文所有实验的算法都选用的是无向图。3.3.2染色体编码具体在进行染色体编码的时候，我么对于各顶点号是进行按自然编排的，然后按照编排的顺序将每个待选的顶点作为一个染色体的基因，基因编排的顺序也就是一条路径之中出现的先后顺序，所以可以看出来，具体的染色体的总长度应该和顶点的个数保持持平。3.3.3适应函数对于前面假设的性能函数在此处可以进行一些稍微的改进，因为是求距离，所以此处我们将前面误差的平方和，看成是各个顶点之间距离的平方和，具体如下面公式（3-6）以及公式（3-7）所示：21xx=vxvxNTiifv（3-6）1,iivxdvv（3-7）具体就是对于求出来多个xi，计算出对应的fi,求出其中最小的minfx对应的就是最优解。3.3.4选择操作(,,)GVE(,,)GVEminx从上一次迭代过程之中的染色体，选择二个染色体作为双亲，而这里具体的染色体选择的是交叉的节点，这个是根据前面的适应函数选取的，原理就是选择操作更容易选择距离较短的二个顶点。3.3.5交叉与变异操作1、交叉操作：将被选中要进行操作的染色体在进行交叉操作的具体步骤是，先在染色体上产生一个随机数，然后弄清楚这个随机基因的具体位置，从而确定与这个随机基因交叉点的位置，一般来说是同一个位置，然后将与这个随机基因在交叉点交叉的基因进行互换。具体交叉操作的示意图如图3-1所示：图3-1交叉操作2、变异操作将被选中要进行操作的染色体在进行变异操作的具体步骤是，先在染色体上产生一个随机数，然后弄清楚这个随机基因的具体位置，然后将这个位置之上的基因从0变成1，或者从1变成0。变异操作虽然可以改变基因，但是有可能减缓遗传算法的计算速度。具体变异操作的示意图如图3-2所示：图3-2变异操作然后具体的设置的条件，也就是上面步骤1设置的目标函数的最优解，即达到距离最短，也就是我们所设置的条件。