﻿ 遗传算法在路径规划上的应用
 计算机系统应用  2020, Vol. 29 Issue (8): 255-260 PDF

1. 招商局重庆交通科研设计院有限公司, 重庆 400067;
2. 中山大学 智能工程学院, 广州 510006;
3. 广东工贸职业技术学院, 广州 510510

Application of Genetic Algorithm in Path Planning
LI Min1, HUANG Min2, CHENG Zhi-Feng3, ZHOU Jing1
1. China Merchants Chongqing Communications Technology Research & Design Institute Co. Ltd., Chongqing 400067;
2. School of Intelligent Systems Engineering, Sun Yat-sen University, Guangzhou 510006, China;
3. Guangdong Polytechnic of Industry and Commerce, Guangzhou 510510, China
Foundation item: National Natural Science Foundation of China (11574407); Science and Technology Program of Guangdong Province (2016A020223006); the Fundamental Research Funds for the Central Universities of China (17lgjc42)
Abstract: In order to reach the destination efficiently and quickly, it is necessary to find a travel path with the best comprehensive weight, and then set a guide sign on it to guide the destination. Based on this, this paper first describes the traffic network model according to the characteristics of the road network. Then, it expounds the basic concept and algorithm idea of genetic algorithm, and defines the path with the minimum comprehensive index of the driving distance and the number of intersections as the optimal path with the number of driving distance and intersections as the factors of route selection. Finally, it takes Sun Yat-Sen University in Guangzhou University City as an example under the condition that the starting and ending points are clear, the optimal path to Sun Yat-Sen University is found by using the method of genetic algorithm, which verifies the effectiveness of genetic algorithm in path planning.
Key words: traffic network     Genetic Algorithm (GA)     path planning     single source path

1 交通路网模型

 图 1 道路路网数据地图

2 遗传算法基本概念及算法模型 2.1 遗传算法基本概念

2.2 种群的初始化

 图 2 路由路径与其编码表示

2.3 适应度函数设计

 $F = a \times L \times {C_1} + b \times \left( {{T_1} \times + 1.5{T_2} + 2{T_3}} \right){C_2}$ (1)

ab—权重系数, 本文认为两个指标影响程度一致, 为此将二者权重比设为1:1;

L—行驶路径总长度(km);

C1—单位路段长度所需消耗的时间;

T1—交叉口所有直行方向的次数;

T2—交叉口所有右转方向的次数;

T3—交叉口所有左转及掉头方向的次数;

C2—单个节点上直行方向上所需消耗的时间.

2.4 选择-复制

2.5 交叉

 图 3 交叉前的染色体路径

 图 4 交叉后新的染色体路径

2.6 校正

 图 5 校正前后的染色体路径

2.7 变异

2.8 算法流程

OptV: 起点集合, 针对多入口路网;

Gen: 迭代的次数;

K: 起点的个数;

F: 各种群中染色体的适应度值;

L: 行驶路径的长度;

T: 交叉口的个数;

Fcpti: 第i次进化时的最优的适应度值.

 图 6 变异前的染色体路径

 图 7 变异后的染色体路径

 图 8 算法流程图

3 实例应用

 图 9 广州大学城出入口示意图

 图 10 广州大学城道路距离权值图

 图 11 总的最优路径规划图

4 结语

 [1] 赵敏杰. 城市指路标志信息连续性自动识别方法研究[硕士学位论文]. 重庆: 重庆交通大学, 2018. [2] 陈洁群. 基于遗传算法的计算机智能作曲模型. 计算机系统应用, 2016, 25(10): 192-198. DOI:10.15888/j.cnki.csa.005395 [3] 黄敏, 饶明雷, 李敏. 指路标志诱导系统指引连贯性的分析评价. 公路交通科技学报, 2012, 29(11): 110-114. [4] 邵海鹏, 慕伟, 叶益翔. 交叉口指路标志信息有效性量化模型研究. 交通运输系统工程与信息, 2017, 17(4): 70-75. [5] Huang M, Niu ZM, Li ED, et al. A data model for guide sign system and its application in guide sign placement. Proceedings of 2014 Fifth International Conference on Computing for Geospatial Research and Application. Washington, DC, USA. 2014. 110–116. [6] 邓兴栋. 城市道路指路标志信息选取方法研究. 交通科学与工程, 2010, 26(1): 97-102. DOI:10.3969/j.issn.1674-599X.2010.01.017 [7] 郭敏, 楼晓寅. 标志指路体系的模型. 公路交通科技, 2009, 26(10): 130-134, 148. DOI:10.3969/j.issn.1002-0268.2009.10.025 [8] 郑健, 黄敏, 张腾, 等. 求解指路标志指引路径规划问题的改进人工蜂群算法. 计算机应用研究, 2017, 34(8): 2355-2359. DOI:10.3969/j.issn.1001-3695.2017.08.027 [9] Ruiz E, Soto-Mendoza V, Barbosa AER, et al. Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering, 2019, 133: 207-219. [10] 毛锋, 黄敏, 郑健. 考虑关联标识的指引信息可达性分析模型. 第十一届中国智能交通年会论文集. 重庆, 中国. 2016. 285–291. [11] 王尧山, 朱毅, 卢军. 基于解空间优化的遗传算法的路径规划. 电子技术与软件工程, 2018(19): 98-99.