必经点最短路径问题模型及相应遗传算法研究

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (2): 459-462.

必经点最短路径问题模型及相应遗传算法研究

徐庆征^1,2, 柯熙政¹

1. 西安理工大学自动化与信息工程学院, 陕西, 西安, 710048;
2. 西安通信学院, 陕西, 西安, 710106

收稿日期:2007-10-27 修回日期:2008-02-26 出版日期:2009-02-20 发布日期:2010-01-03
作者简介:徐庆征(1980- ),男,讲师,博士,主要研究方向为智能计算.E-mail:syesun@hotmail.com
基金资助:
国防重点实验室基金(9140C3601010701);陕西省教育厅科技专项基金(07JK332);陕西省自然科学基金(2007F12);广东省交通厅科技计划基金(2007-26)资助课题

Models and genetic algorithm for designated-points shortest path problem

XU Qing-zheng^1,2, KE Xi-zheng¹

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

Received:2007-10-27 Revised:2008-02-26 Online:2009-02-20 Published:2010-01-03

摘要/Abstract

摘要： 根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型.以分类保序最短路径为例,设计相应的改进遗传算法.该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群.通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度.仿真结果验证了算法的有效性.

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.

中图分类号:

TP301.6

徐庆征, 柯熙政. 必经点最短路径问题模型及相应遗传算法研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(2): 459-462.

XU Qing-zheng, KE Xi-zheng. Models and genetic algorithm for designated-points shortest path problem[J]. Journal of Systems Engineering and Electronics, 2009, 31(2): 459-462.

[1]	路复宇, 童宁宁, 冯为可, 万鹏程. 自适应杂交退火粒子群优化算法[J]. 系统工程与电子技术, 2022, 44(11): 3470-3476.
[2]	闫世瑛, 颜克斐, 方伟, 陆恒杨. 基于差分进化邻域自适应的大规模多目标算法[J]. 系统工程与电子技术, 2022, 44(7): 2112-2124.
[3]	汤安迪, 韩统, 徐登武, 周欢, 谢磊. 使用高斯分布估计策略的改进樽海鞘群算法[J]. 系统工程与电子技术, 2022, 44(7): 2229-2240.
[4]	庞维建, 李辉, 黄谦, 李朋, 马贤明. 基于本体的无人系统任务规划研究综述[J]. 系统工程与电子技术, 2022, 44(3): 908-920.
[5]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[6]	丁嘉辉, 汤建龙, 于正洋. 轻量化的增量式集成学习算法设计[J]. 系统工程与电子技术, 2021, 43(4): 861-867.
[7]	刘家义, 岳韶华, 王刚, 姚小强, 张杰. 复杂任务下的多智能体协同进化算法[J]. 系统工程与电子技术, 2021, 43(4): 991-1002.
[8]	徐涛, 吴志帅, 卢敏, 吕宗磊, 李忠虎. 面向拥堵问题的枢纽航线网络优化模型[J]. 系统工程与电子技术, 2020, 42(11): 2553-2559.
[9]	姚智海, 刘建平, 王建平, 李伟, 任勃. 地面测控资源调度效能评估指标体系[J]. 系统工程与电子技术, 2020, 42(8): 1751-1758.
[10]	刘家义, 岳韶华, 王刚, 张杰, 姚小强. 多平台分布式协同作战下基于MPC-MAS的指挥控制模型设计[J]. 系统工程与电子技术, 2020, 42(7): 1582-1589.
[11]	孙胜祥, 韩霜. 基于双层决策的装备订购多因素激励定价模型与算法[J]. 系统工程与电子技术, 2020, 42(6): 1338-1347.
[12]	李慧贤, 庞辽军, 蔡皖东. 基于信息熵对遗传算法中杂交概率的研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(7): 1743-1745.
[13]	邹益民, 汪渤. 基于量子遗传算法的滤波器参数优化[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1346-1349.
[14]	尚政国, 赵春晖, 汤春瑞, 刘金梅. 基于无“缠绕”FRIT目标边缘检测方法[J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1198-1203.
[15]	周康, 覃磊, 同小军, 许进. 0-1规划问题的闭环DNA算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(4): 947-951.