最优行车路径规划算法的设计

杨东泽 贾萱 解明翰 冯丽茹 程慧

摘要：行车路径规划问题是城市智能交通的重要组成部分，它是一种行程路径的设计与优化。合理的行车路径，一方面可以避免因路况不熟悉而造成停车使用者迷路的情况，减少车辆在复杂路网中的交通时长，优化交通流在道路网络中的分布，另一方面可以减少停车使用者因长时间找不到停车位，而选择路边非法停车，在一定程度上提高了交通安全。本文结合遗传和蚁群算法的各自优点，将两种算法的寻优过程循环多次结合。在蚁群算法的每一次循环迭代后，将蚁群算法产生的最优解加入到遗传算法中，用以加快遗传算法的迭代速度。同时，将遗传算法算出的解设为较优路径来更新蚁群算法中的信息素分配，实现参数调整。多次相互指导能有效解决蚁群算法前期效率低和遗传算法后期冗余迭代问题。

1.遗传算法

遗传算法（Genetic algorithm，GA）是根据达尔文的进化论提出的仿生学算法，通过适应度函数对较优个进行不断选择的过程。同时为保持种群的多样性和具有求全局最优解的能力，较优个体需进行交叉和变异操作产生新的种群。通过不断地选择和迭代进化，从而找到最优个体，也就是最优解。

2.基本原理

遗传算法由一些问题的初始解表示最初的父代基础种群，也就是算法的初代进化种群，然后通过编码将每一个初始解用基因编码的形式表示，通常每一个个体称作为基因码或者染色体表示具体的一个有效解。生物学上的遗传特性都在染色体上，即是多个基因特征的的集合，表现为基因码的形式，它决定了个体的具体特征集合。因此，在算法的开始需要将具体需要解的特征用基因码来表示，即算法过程中的编码，由于个体特征较多，编码过程较为复杂，因此常常根据实际解的需求选取主要特征要求，然后通过 0 或者 1 的二进制码来表示，以此来简化编码过程。编码完成即产生初始种群，之后按照“适者生存和优胜劣汰”生物进化理论，对每一个个体进行适应度计算，逐代选取进化产生的较优解。整个过程的不断迭代就像自然界中生物种群的进化一样，越靠后的种群将有更好的适应能力，末代种群中的最优个体经过解码，即可以作为符合求解问题的近似最优解。

结语：相较于室内路径规划，室外交通路网复杂很多，从平面图看有“节点多”和“路况复杂”等特点。本章首先基本蚁群算法和遗传算法原理、流程和步骤做了详细介绍，并做了对比和分析。然后在分析了仿生学算法解决复杂路网最优路径问题的优越性基础上，结合遗传、蚁群算法的特性和优点，设计一种混合遗传蚁群算法（GACHA）用于行车路径规划中。该算法从基本蚁群算法入手，将两种算法的寻优过程循环多次结合，并在蚁群算法的每一次循環迭代后将蚁群算法产生的最优解加入到遗传算法中，加快了遗传算法的迭代速度。同时该算法将遗传算法算出的解设为较优路径来更新蚁群算法中的信息素分配，实现参数调整。多次的相互指导有效解决了蚁群算法前期效率低和遗传算法后期冗余迭代问题。实验结果表明，GACHA算法具有良好的优化和收敛性，能够准确地找到满足路网综合要求的最优路径。

参考文献：

[1]任怀志.探析云计算和物联网技术组合应用.农业网络信息.2011，（11）：83--84

[2]J Dean， S Ghemawat. Map Reduce： Simplified Data Processing on Large Clusters. Communications of the ACM， 2016

[2]张海江，赵建民，朱信忠.基于云计算的物联网数据挖掘.研究与设计.2012，28（6）：10--13

基金项目：2021年浙江省大学生科技创新活动计划暨新苗人才计划项目—基于Android的智能停车引导系统研究与实现（2021R435008）资助。