基于改进遗传与神经网络的同事合乘匹配混合算法研究

龚文浩 张 凯

(南京信息工程大学自动化学院 江苏 南京 210044)

0 引 言

为缓解交通拥堵情况,针对单位同事通勤合乘问题出现越来越多的讨论,文献[1]在2010年提出邻里合乘的概念,以社区为单位,进行合乘。文献[2]提出在2020年新冠疫情背景下的高效又安全的通勤合乘。但专门针对该问题的合乘匹配算法还未研究充分。

遗传算法是常用的求解路径选择问题的常用算法,其具有效率高、全局求解性好、简单通用等优势。人工神经网络由于其高效性、高度智能性,以及调用时的快速性,也在近些年在交通领域得到大规模应用。文献[3]研究了自适应的遗传算法求解满足个体偏好的合乘匹配问题。文献[4]混合遗传算法和模拟退火算法优化了合乘末端路径问题。文献[5]使用改进遗传算法解决路径规划偏角过大的问题。文献[6]讲述遗传算法在规避障碍的路径规划问题中的使用。文献[7]使用遗传算法研究复杂地貌下的路径规划。文献[8]使用遗传和蚁群算法应急物资的路径规划进行研究。

而遗传算法与神经网络的融合算法在路径规划各个方面均取得了很有价值的研究成果。文献[9]使用两者的混合算法优化了交通网络信号灯优先级。文献[10]使用两者的混合算法使用出行者信息进行路径选择。文献[11]使用两者的混合算法进行机器人的移动路径规划。文献[12]使用两者混合算法进行动态的路径规划。

针对现阶段同事合乘整体出行效率较低,相关算法发展速度慢,并且没有明确具体求解该问题算法的情况,本文提出一种基于遗传算法和人工神经网络的同事合乘路径匹配混合算法(Genetic Algorithm-Artificial Neural Network,GA-ANN),利用遗传算法全局求解性好,不易陷入局部最优解的优势,来获取区域内整体通勤效率最高的合乘匹配组合。通过对初始种群与交叉过程的改进进一步提升算法效率,再利用人工神经网络读取权值输出的过程,提高算法的快速性。

1 GA-ANN算法

遗传算法具有搜索范围广、自适应能力强、自学习能力强等优点,并且在大规模种族的背景下不易陷入局部最优解,但是种群世代的迭代过程占用大量的时间资源,所以结合人工神经网络的训练权重思想,将多次遗传算法产生的最优解基因组的权重载入网络,在规划路径时,直接调用网络结构,以达到在路径规划时具有足够的快速性和及时性。

1.1 遗传算法部分

在单位同事合乘的寻径方法中,由于约束条件的苛刻,传统的遗传算法,在初始化、交叉和变异阶段会产生大量的不满足实际需求的不可行解。对于上述情况,采用下文特定方式去按步骤产生初始种群以及执行交叉、变异操作,以产生可行解,提升算法的效率。

作出以下定义解释该问题的基因编排方式以及约束条件。

编排方式1。将员工所在位置定义为节点,以li表示第i个员工所在的位置(i≥0),li表示工作单位所在位置,li中包含经、纬度两个位置信息,li={lij,liw},节点集U包括所有的节点。

编排方式2。单位同事的合乘不同于运输合乘问题,染色体并不是一辆车从开始到结束的地点集合,而是同一单位的多辆车的位移集合。每一个车的行驶路径代表一个基因,多个基因组成一个染色体。一个基因由两个实数组成,例如基因1-2代表处于第一个坐标位置驾驶人驾车带着第二个坐标位置的同事前往公司,前面的实数1表示驾驶人l1所在位置,后者实数2表示乘坐人l2所在位置。

编排方式3。染色体由众多基因组成,如染色体1-2|3-4|5-6|7-8|…,全部需要前往公司的车辆行驶位移组合基因组成了一条染色体。不同的组合情况,构成不同的染色体。

约束条件1。由于一个实数就代表一个员工参与到合乘行为中,故每一条染色体的基因具有不可重复性。

约束条件2。单位同事的合乘与普通顺风车合乘模式有比较大的差别,驾驶发起人的驾驶体验很重要,所以绕行的距离要控制在合理的范围内。

1.1.1初始种群的生成

初始种群的无条件随机生成会降低遗传算法的效率,因此我们选择在生成初始种群时参考一些先验条件来优化算法,提升算法的效率。考虑到驾驶人的出行体验,当参与同事合乘行为时,前进方向应当与单位方向大致一致。因此,在执行合乘操作时,乘车人的经纬度位置应当位于驾车人位置和单位所在地之间。以li表示驾车人的位置,以lj表示乘车人位置,li∈U,lj∈U且li≠lj,偏移量α、β、η、λ为微小值,当满足上述先验条件时:

(1)

单个li-lj的组合构成基因,多个基因构成染色体,不同的多个染色体加上一轮轮盘赌的方法,可以生成具有优势的第一代种群,从而提高遗传算法的搜索效率。

1.1.2适应度函数

在生成种群之后,将每一条染色体上每一对基因组成的路程和作为评价染色体优劣的评价指标,路程和越短,染色体越优秀。每一对基因的路程是指驾车人位置到达乘车人位置的距离Hij加上驾车人位置到达单位位置Hj0的距离之和。由于合乘问题需要以实际的城区地图为基础,按照驾驶路程计算距离并同时需要考虑特殊道路例如单行道,禁左路口等因素,因此距离H通过调用高德地图的API接口,计算实际需要的驾驶距离。

若一条染色体长度为n,则完整的染色体表示的距离和为:

(2)

在遗传算法中,个体的适应度越大表示该个体对于环境适应越强,越接近最优解,但就运输问题来说,路程越短代表越优,所以将染色体距离和加1的倒数当做适应度函数,表示为:

(3)

1.1.3交叉过程

遗传算法常用的单点交叉、重组等交叉方法,而对于此问题会产生大量的不满足约束条件1的染色体,不适用于此问题。因此,采用顺序交叉的方式,具体过程如下:

步骤1首先从种群中随机挑选出两个染色体,如染色体1-2|3-4|5-6|7-8和染色体8-7|6-5|4-3|2-1。

步骤2随机选取交叉点,但由于单个基因是两个位置点构成的,如1-2、3-4等,因此在选取交叉点时,只可以选取偶数交叉点,以达到不破坏原有基因的效果。假设去第一个偶数交叉点和最后一个偶数交叉点,染色体1保留的基因为x-x|3-4|5-6|x-x,染色体2保留的基因为x-x|6-5|4-3|x-x。

步骤3选取好交叉点后,采用顺序交叉法,对于染色体1,取出保留部分x-x|3-4|5-6|x-x,然后选取染色体2第二个偶数交叉因子后的部分组成编码2-1|8-7|6-5|4-3,删除与第一个染色体重复基因因子|3-4|5-6|,将剩下的因子2-1|8-7顺序填入第一个染色体,染色体为8-7|3-4|5-6|2-1,同理染色体2变为1-2|6-5|4-3|7-8。

上述交叉过程可以有效地改变一部分基因,保留下一部分基因,从而生成染色体的同时可以保留下部分基因。

1.1.4变异过程

变异操作是防止遗传算法陷入局部最优解以及丰富种群的重要操作。由于约束条件1的存在,染色体中一位基因的改变一定伴随着其他基因的改变。具体过程如下:

步骤1从交叉完毕的种群中找出一条染色体。

步骤2随机选取一个变异点,从节点集合U中选取一个非原基因替代原基因。如染色体1-2|3-4|5-6|7-8,选取第3个基因位,用基因‘7’代替基因‘3’染色体变为1-2|7-4|5-6|7-8。

步骤3找到染色体中非变异点中与变异基因位基因相同的点,用包含在节点集合中,不在染色体中的基因互换,如上述染色体1-2|7-4|5-6|7-8变为1-2|7-4|5-6|3-8。

当节点集合U中的基因全部出现在染色体中时,变异操作可以理解为将一条染色体中的两个基因位进行互换。

1.2 ANN算法部分

由于单位同事的合乘问题总体上归于静态合乘问题,同时,由于各种临时变化,合乘问题也要具备一定的即时性和灵活性,路径规划还需进一步提升速度,所以引入人工神经网络,对于零散的节点进行二次规划,提高规划的速度及效率。

神经网络是模仿人神经元的工作,具体操作流程是先搭建网络,然后前向传播,之后根据损失函数反向修正权重,使神经网络模型能够快速准确地执行任务。但是人工神经网络根据损失函数采用梯度下降法,所以在训练过程中有收敛慢、易产生局部最优解等问题,因此用遗传算法的迭代过程代替人工神经网络的参数调整过程,用遗传算法迭代后的优选种族匹配组合概率代替人工神经网络调整的权值参数。利用神经网络强大的非线性组合映射能力,可以快速地给出路径选择,从而大幅度提高整体算法的运行速度以及效率。

1.2.1网络搭建及权重载入

由于本文的合乘是一对一模式,故将单位人数n作为神经网络输入层X神经元个数,同时将n作为神经网络隐层Y神经元个数,隐层为全连接层,输出层为一对一的匹配结果。通过建立各节点之间对应关系。网络实现输入值为某个节点,输出值为匹配结果。图1为n为6时的单个神经元网络图。

图1 ANN单一节点的结构图

图2 坐标标记图

使用前面多组遗传算法运行后产生染色体,将整条染色体切割成一对一的形如1-2、3-4的基因组,将满足约束条件二中规定绕行距离C的基因组以首位和尾位分别归类统计,首位为驾驶位,代表选择驾车出行的节点,尾位为乘坐位,代表选择乘车出行的节点。两种模式网络相同,区别在于载入的网络权重。以前者为例,筛选出首位相同,但尾位不同的不同基因组出现的概率作为中间层神经元Yi(1≤i≤n)的值,如节点数为6染色体中首位1的基因组1-2、1-5出现的概率分别为0.2、0.8,其他为0。则Yi(1≤i≤6)为0、0.2、0、0、0.8、0。神经元数值Yi(1≤i≤n)应满足下列约束条件:

(4)

将两层神经元之间的连接权重设置为两者对应节点为因参与合乘产生的绕行距离rij(1≤i≤n,1≤j≤n),由于绕行距离与结果负相关,所以修正权重wij=C-rij,权重w应当满足条件:wij≥0。中间层的输出为:

(5)

考虑到无论是驾驶人或者乘车人的出行体验是很重要的因素,因此中间层和输出层的权重hij采用前期其他乘客对该驾驶人驾驶行为的评价,由于wij和Yi均小于1,所以hij不宜过大,应保证hij∈(0,0.5),输出层的输入公式为:

(6)

进入输出层神经元后,神经元做筛选操作,取出最大的值输出,输出值为Yi的下标i,表示合乘匹配对象是第i个节点的同事。

1.2.2约束条件的分布化

对于合乘问题,在实践中有诸多限制。首先,有时间约束条件,如出行的时间要与合乘执行的时间有所重合。有司机选择约束条件,如司机不愿意绕路太远。有乘客选择约束条件,如不愿乘坐异性的车辆。这些不同的约束条件往往会使问题复杂化,而由于个体的差异性,对于不同对象,这些约束条件往往区别较大。

通过使用人工神经网络可以将这些个体的差异选择与路径规划算法本身区分,神经元本身带有属性,如司机性别、司机可接受的绕行距离等。只有满足条件才可激活神经元进行选择。

2 实验及结果分析

2.1 实验环境及测试目的

本文采用Python语言进行改进GA-ANN算法的实现与测试。测试节点配置为Inter(R) Core(TM) i5-4210M 2.6 GHz,内存8 GB,操作系统64位Windows 8.1。

实验旨在测试改进GA-ANN算法的有效性及匹配结果效率,以及对比传统的遗传算法和融入神经网络前后的算法效率。

2.2 实验数据及参数设置

通过调查走访,得到南京一单位的33名职工的地址信息,并将地址信息转化为经纬度坐标保存在TXT文件中。将这些地址信息作为基因,将地址编号的拼接组合作为染色体,测试试验中,种群初始数量为200个,迭代次数为200次,交叉率为0.45,变异率为0.1。

2.3 实验测试及分析

2.3.1算法有效性测试

采用前期调查的文本坐标数据对本文算法进行验证。图3为随机抽取的一幅适应度函数最大值、平均值曲线图,可以看出遗传算法在进入60代前快速收敛,75代左右收敛变慢,但随后种族继续得到优化并在150代附近获得近似的最优解。

图3 种族进化曲线

图4 驾驶路径图

因为本文算法将距离和倒数作为适应度函数,而不同组合的距离之和是非线性的,为了保证基因组合的多样性,将适应度函数大于0.004 5的组合作为满足条件的染色体。经过多次实验,发现在算法第100代-第125代之间会找出优秀的染色体,即多辆车辆合乘的组合表示。结果表明,改进的GA对于同事合乘问题的求解具有有效性。

2.3.2算法效率对比测试

实验1是改进GA与限制绕行距离合乘搜索算法的对比测试。由于传统的合乘搜索算法在进行搜索时,会由于绕行约束距离的限制,导致出现合乘的效率不高,但搜索速度足够。而对于改进的GA,通过种群世代的迭代过程,大幅度地提升了适应度,减少了出行总距离。从结果来看,改进的GA得出的较优解染色体中的基因,从整体来看,近似最优解的结果要优于合乘搜索算法得出的解。同时,由于在生成初始种群的时候加入了先验条件,相对随机生成初始种群,在迭代次数上也会有一定的降低,提升了效率。

表1 运算结果表

实验2是融合人工神经网络前后改进GA的对比测试。

融合人工神经网络前,改进的GA在结果上已经可以得到较好的解,但是由于合乘问题对于求解时间的要求,在算法速度上还需要进一步突破。同时。在实际运用中,常常是点对点的具有约束条件的搜索,为了使算法具有实际的实用性,融入ANN神经网络,加快整体的算法运行速度。

表2 运算结果表

通过GA-ANN算法可以得出合乘对象的匹配结果,以输入22、输出8的结果为例,实际的意义为从编号22的起点出发,途经8号位置接上合乘的同事前往单位。

3 结 语

同事合乘是缓解上下班通勤拥堵的解决办法之一,可以有效地减少上路车辆,减少一个单位所有员工驾车出行的总距离,从而达到节能减排、减少拥堵等效果。本文提出的遗传算法和人工神经网相融合的合乘匹配算法,通过带先验条件的初始种群生成,特殊的交叉、变异操作后,可以有效地得出结果,再加上人工神经网络的部分以提高算法整体的快速性。

从结果来看,该算法可以快速、有效地找到合乘的优势组合,从整体上将出行距离充分缩短,提高出行效率,降低出行成本。