| 必经点最短路径问题模型及相应遗传算法研究 |
| |
| 引用本文： | 徐庆征,柯熙政.必经点最短路径问题模型及相应遗传算法研究[J].系统工程与电子技术,2009,31(2):459-462. |
| |
| 作者姓名： | 徐庆征 柯熙政 |
| |
| 作者单位： | 1. 西安理工大学自动化与信息工程学院, 陕西, 西安, 710048;2. 西安通信学院, 陕西, 西安, 710106 |
| |
| 基金项目： | 国防重点实验室资助项目，陕西省教育厅科技专项基金，陕西省自然科学基金，广东省交通厅科技计划 |
| |
| 摘 要： | 根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型.以分类保序最短路径为例,设计相应的改进遗传算法.该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群.通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度.仿真结果验证了算法的有效性.
|
| 关 键 词： | 遗传算法 最短路径 分类必经点 保序节点 军事运输 |
| 收稿时间： | 2007-10-27 |
| 修稿时间： | 2008-02-26 |
Models and genetic algorithm for designated-points shortest path problem |
| |
| XU Qing-zheng,KE Xi-zheng.Models and genetic algorithm for designated-points shortest path problem[J].System Engineering and Electronics,2009,31(2):459-462. |
| |
| Authors: | XU Qing-zheng KE Xi-zheng |
| |
| Institution: | 1. Faculty of Automation and Information Engineering, Xi'an Univ. of Technology, Xi'an 710048, China;2. Xi'an Communication Inst., Xi'an 710106, China |
| |
| Abstract: | On the basis of the special requirements of military transportation in routing,the designated-points shortest paths problem is divided into three categories and their mathematics models are established.The improved genetic algorithm for the grouped and order-preserving designated-points shortest paths problem is presented.The algorithm constructs a unique fitness function,which makes that a chromosome with shorter distance and more designated-points would be selected to rebirth into next generation more easily.An order-preserving operation is proposed to ensure that some particular points are connected based on the determined order.By using novel mutation,the global search capability and convergence speed are improved.The experimental results show the effectiveness of the proposed algorithm. |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《系统工程与电子技术》浏览原始摘要信息 |
| 点击此处可从《系统工程与电子技术》下载免费的PDF全文 |
|
