A gene-constrained genetic algorithm for solving shortest path problem
A gene-constrained genetic algorithm for solving shortest path problem
复制标题
DOI：
10.1109/icosp.2004.1442291
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Wu Wei;Ruan Qiuqi
中科院分区：
文献类型：
--
作者：
Wu Wei;Ruan Qiuqi
本文提出了一种解决最短路径问题的基因约束遗传算法（G-C GA）。在该遗传算法（GA）中，对基因进行约束，以确保在整个搜索过程中每条染色体都代表一条无环的可行路径。与其他针对SP问题的遗传算法相比，我们的算法可以提高搜索能力，解的精度更高，收敛速度更快。无论是在有向图还是无向图中，G-C 遗传算法都更加通用和灵活，为更复杂的最短路径问题提供了基础。
In this paper, a gene-constrained genetic algorithm (G-C GA) to solve shortest path problem is proposed. In this genetic algorithm (GA), gene is constrained to ensure that each chromosome represents a feasible path without loop during the whole process of search. Contrasting with other genetic algorithm for SP problem, our algorithm can improve the searching capacity with a more accurate solution and more rapid speed of convergence. The G-C GA is more general and flexible no matter in a directed graph or in an undirected graph and it provides the foundation for more complicated shortest path problems.