python遗传算法最短路径问题有几种类型_基于遗传算法的最短路径问题求解

2008, 44(23) Computer Engineering and Applications 计算机工程与应用 1 引言 遗传算法是基于生物进化原理的一种全局性优化算法, 是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法, 是生物遗传技术和计算机技术结合的产物。它采用的是启发性知识的智能搜索算法, 在高空间复杂问题上比以往有更好的结果。 最短路径算法根据不同的具体要求可以是长度最短或行驶时间最短。由于问题的特征、网络特性等的纷繁复杂最短路径算法表现出多样性。传统的 Dijkstra 算法已经成为 LS 算法的代名词, LS 算法又称为列表搜索算法, 其代表算法有 Bell-Ford-Moore 算法、D’Esopo-Pape 算法等。总的说来 Dijkstra 算法简单易用能 100%搜索到最短路径, 是目前应用较多的算法, 但它的基础是求出到每个搜索到的结点的最短路径, 它在所有方向上都搜索, 而不管目的结点的位置, 当网络中结点过多时, 就会导致计算量急剧增加产生“组合爆炸”问题, 搜索开销会相当大、效率很低, 这是 Dijkstra 算法的缺陷。 本文讨论了利用遗传算法求解最短路径问题的思路及方法, 并提出了一种交叉变异算法, 在仿真实验中获得了较为满意的结果。 2 最短路径的遗传算法设计 2.1 编码表示 在标准遗传算法中, 如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。人们一般习惯于用二进制编码, 但二进制编码方法的缺点也是明显的, 对很多实际问题, 它很难直接描述出问题的性质, 而且它的精度也有问题, 为了追求精度, 可能会导致很长的编码, 直接影响遗传算法的性能。人们根据问题域的性质提出了很多其它的编码方法, 如约束优化的实数编码、组合优化的整数编码等。 假定将所有城市组成的一个列表记为 W, 给每个城市分配一个 1~n 之间的序号, 将这个序号的排列也表示为 W, 即: W=( v1 , v2 , v3 , v4 , ⋯, vn) | | | | | W=( 1, 2, 3, 4, ⋯, n) 用编码串 T:1 2 3 4 5 6 7 8⋯n, 来表示这样的一条城市遍历路线: 从城市 v2 , v3 , v4 , v5 , ⋯, Vn