遗传算法求解最短路径问题(共3页).docx

文档介绍：精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
遗传算法求解最短路径问题
-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
遗传算法求解最短路径问题

在中，与V中的有序偶（Vi，Vj）对应的边e，称为图的有向边，同时与V中的顶点的无序偶Vi*Vj相对应的边e，称为图的无向边，并且如果在中，与V中的顶点的无序偶Vi*Vj相对应的边e，全部都是无向边的话，这个图就叫做无向图，与V中的有序偶（Vi，Vj）对应的边e，都是有向边的话，这个图就叫做有向图。为了方便实验，与进行仿真分析，本文所有实验的算法都选用的是无向图。

具体在进行染色体编码的时候，我么对于各顶点号是进行按自然编排的，然后按照编排的顺序将每个待选的顶点作为一个染色体的基因，基因编排的顺序也就是一条路径之中出现的先后顺序，所以可以看出来，具体的染色体的总长度应该和顶点的个数保持持平。

对于前面假设的性能函数在此处可以进行一些稍微的改进，因为是求距离，所以此处我们将前面误差的平方和，看成是各个顶点之间距离的平方和，具体如下面公式（3-6）以及公式（3-7）所示：
（3-6）
（3-7）
具体就是对于求出来多个xi，计算出对应的fi,求出其中最小的对应的就是最优解。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业

从上一次迭代过程之中的染色体，选择二个染色体作为双亲，而这里具体的染色体选择的是交叉的节点，这个是根据前面的适应函数选取的，原理就是选择操作更容易选择距离较短的二个顶点。

交叉操作：
将被选中要进行操作的染色体