基于改进蚁群算法的电动汽车行驶路径多目标优化

摘 要 针对目前电动汽车(electric vehicle, EV)锂电池容量有限、充电时间较长的问题，为优化电动汽车行动力，缓解用户出行顾虑，提出基于蚁群算法(ant colony algorithm, ACA)的电动汽车行驶路径多目标优化。蚁群算法具有较强的鲁棒性，优秀的分布式计算机制，并且易于与其他智能算法结合，适合求解复杂组合优化问题。本文在基本蚁群算法的基础上，多目标统一规范化后，对蚁群算法的启发函数和信息素更新函数进行了改进，从而使算法做到快速收敛，并且添加了随机变异策略最大可能获得所有Pareto最优解。实验结果表明，算法推荐的行驶路线是Pareto最优解，并且可以平衡电动汽车耗电和耗时，算法是有效的。 关键词 蚁群算法(ACA)，电动汽车(EV)，行驶路径，多目标优化，Pareto最优解，行动力

0 引言

电动汽车(electric vehicle, EV)行驶的最优路径问题是指在路网模型中两个节点或多个节点之间搜索一条可以最优化耗电和耗时的路径，是电动汽车行动力管理研究中的一个多

[1]

目标优化问题。电动汽车的行驶不同于一般汽车，受限于锂电池容量，能够行驶的距离有限，并且充电需要的时间较长，而且道路交通的运行情况使得行驶消耗的电量和时间并不一

[1-3]

致，甚至发生矛盾，如：在到达目的地的快捷路径上能耗很大，或者在耗时较多的路径上能耗较少，即实际情况中可能不存在同时达到能耗最低与耗时最少的路径。通过对最优路径问题的研究，可以在使用电动汽车出行时合理规划行驶路径，达到耗电和耗时尽可能最优，从而可间接最大化电动汽车的行动力。所以，对最优路径问题的研究可以提高电动汽车的实用性，推广低碳出行的理念。为此，本文提出了基于改进蚁群算法(ant colony algorithm, ACA)的多目标优化方法。蚁群算法是由意大利学者M.Dorigo于1991年首次提出，与其他智能算

[4,5]

法相比，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点。这一仿生优化算法已经成为人工智能领域的一个研究热点，并由解决一维静态优化问题发展到解

[6][7]

决多维动态组合优化问题。该算法已渗透到众多应用领域，在求解旅行商人、机器人路

[8]

径规划等问题中取得了很好的结果。本文针对电动汽车行驶路径问题的特殊性，对基本蚁群算法的启发函数和信息素更新策略进行了改进。

1 蚁群算法的基本原理

模拟蚂蚁群体觅食行为的蚁群算法是作为一种仿生智能模式引入的，该算法基于三个基

[9]

本假设：（1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响。（2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。（3）在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。

由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。

蚁群算法是一种智能多主体系统，其自组织机制使得蚁群算法不需要对所求问题的每一方面都有详尽的认识。自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态演化。 ①

国家“985工程”项目(TS0001141801)。

2 行驶路径的最优求解 2.1 路径优化的建模 确立解域。一个路径解是地图上从起点到终点的一系列节点组成的有向行驶路径，所以，地图的拓朴结构决定了解域。在优化电动汽车行驶路径过程中，我们可以去除地图拓朴结构中一些不必要的点，如无法到达的点，死胡同里的点（若终点在死胡同里，则必须保留）。在地图的拓朴结构中，起点和终点以外的节点表示路段的分岔口，至少有三条线与节点相连（若只有一条线连接节点，则该节点处在死胡同里；若只有两条线与节点相连，则这两条线可以合并为一条线）。随着道路建设的发展，地图的拓朴结构越来越复杂，即节点和分支越来越多，那么解域内的解也越来越多，遍历所有解，并比较它们的优劣需要大量的计算和时间。所以，需要在不遍历所有解的情况下搜索出最优路径。

确立目标函数。这里，电力驱动车行驶后的耗电和耗时是优化问题的两个子目标函数，函数的值域由路网模型中路线上的权重值决定，所以一个路径解对应一组和。对子目标函数优化，需要搜索到Pareto最优解，组成最优解集。Pareto最优解是不被可行解集中的任何解支配的解，若是Pareto最优解，当且仅当不存在解使得，都成立。由于多目标的Pareto

[10]

最优解不是唯一的，故采用综合评价函数来判断收敛情况： (1)

公式(1)中的与为尺度参数，用来统一子目标函数的数量范围。

2.2 蚁群算法的设计

每次迭代开始时刻，将m只蚂蚁放在起点处。单只蚂蚁的行动与其他蚂蚁无关，只和线上的信息素相关。按照一定的选择策略，蚂蚁从一个节点走到另一个节点，直至到达终点，从而获得一个可行解。每一个可行解通过信息素更新策略求出该可行解中蚂蚁走过的路径的信息素增量，同时路径上原信息素进行适当的挥发，m只蚂蚁走完后，将信息素增量与残留信息素叠加。同时，在m个可行解中搜索出非支配解，更新外部非支配解集，并对信息素作全局更新。信息素更新结束后，进入下一次迭代。基本蚁群算法求解多目标优化路径问题的主要实现步骤如下：

(1)参数初始化。迭代计数器N=0，设置最大迭代次数Nmax，设置起点和终点，设置蚂蚁数量m，将m只蚂蚁放置于起点处，将二维禁忌表tabu初始化为空，初始化路网模型，为路网每条边赋予等量的信息素const，将外部非支配解集初始化为空。

(2)选择策略：位于节点i处的蚂蚁k在第N次迭代时，按以下选择策略选择边(i,j): (2)

式中，表示蚂蚁k由节点i转移到节点j的状态转移概率；表示蚂蚁k下一步允许选择的节点集合；为信息启发式因子，反映了蚂蚁在运动过程中所积累的信息素在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强；为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则；为启发函数，其表达式如下：

(3)

式中，和分别表示从节点i行驶到节点j需要的能耗和时耗，和是平衡数量级的常数。对蚂蚁k而言，越小，则越大，也就越大。所以，该启发函数表示蚂蚁从节点i转移到节点j的期望程度。

(3)信息素更新策略。为了避免残留信息素过多引起残留信息淹没启发信息，在m只蚂蚁走到终点后，要对残留信息进行更新。在新信息不断添加的同时，路径上的旧信息随着时间

的推移逐渐淡化。由此，路径(i,j)上的信息素按如下规则进行更新： (4)

(5)

式中，表示信息素挥发系数，为了防止信息素的无限积累，的取值范围为：；表示本次循环中路径(i,j)上的信息素增量，初始时刻，表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。

(6)

(7)

式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；表示第k只蚂蚁在本次循环中所走路径的总能耗和总时耗的函数值。

求出的非支配解与外部非支配解集进行比较，从而更新外部非支配解集。所有N次迭代结束之后，非支配解集中的解就是求得的Pareto全局最优解。

2.3 蚁群算法的改进 2.3.1 启发函数的修改

在启发函数中加入节点j到起点s和到终点d的直线距离的和，从而使状态转移概率倾向于离起点和终点的直线距离小的节点处。将公式（2）改为如下：

(8)

其中，是起点到节点j的直线距离，是节点j到终点的直线距离。

因为实际道路中外延节点很多，从而导致搜索速度下降，为了提高算法实用性，我们将搜索节点限制在以起点和终点为焦点的椭圆内，如果蚂蚁离开了椭圆，则立刻终止搜索行为，可以认为该蚂蚁走进了死胡同内。

(9) 其中，R为包围路网的椭圆的长轴的半径。

2.3.2 随机变异策略求局部最优解

在确定了路网范围之后，为了扩大搜索空间，有利于发现Pareto最优解，进一步采用遗传算法中的变异求局部Pareto最优解。在某次循环中，m只蚂蚁获得了m个可行解，其中随机选择蚂蚁k的可行解进行变异。其解由(S),,,„，,„,(T)这些节点构成，取变异概率随机决定对第m个节点进行变异操作，于是从与和相连的节点中随机选取一个非的节点来替换掉，于是产生了一个变异解。变异解同样参与信息素的更新。

在搜索节点较多，解空间较大时，可以考虑对多个可行解进行变异操作，或进行深度变异，能加大对解空间的探索力度。

2.3.3蚂蚁交流的信息素更新

在多目标优化过程中，解的优劣是相对的。蚂蚁k的解通过与蚁群中其他蚂蚁的解进行比较，得到Pareto支配关系，从而决定了在走过的路径上释放的信息量的多少。于是，将公式（5）进行修改得到：

(10) (11)

式中，表示第k只蚂蚁的解与其他m-1个解的支配与受支配关系。，，„，是m个不同的参数，且。

3 路网实验及其结果

图1是含有十多个节点的路网简化模型，节点之间以无向加权线相连，每个节点至少连

1

接附近的三条线。权值(x,y)中x表示的是耗电量（10mAh），y表示的是耗时量（秒）。该路网模型以邻接表的数据结构在程序中初始化。节点1为起点，节点15为终点，求起点到终点的Pareto最优路径。这里，通过公式（7）（8）修改启发函数，我们将搜索范围限定在椭圆内，椭圆外的可行解不予考虑。

图1 路网拓扑模型

图2是蚁群算法的程序结构简图，程序中含有三层主要循环迭代结构。算法中的基本参数有，最大迭代次数Nmax=400，蚂蚁数量m=8，信息启发式因子，期望启发式因子，，信息素挥发系数，信息素强度Q=50,尺度参数，，变异概率，支配关系参数，

图3是蚁群算法求解图，横轴是迭代次数N，纵轴是每一次迭代的综合评价函数值。图3(a)为基本算法的求解结果，图3(b)为改进算法的求解结果，从迭代次数可以看出图3(a)中收敛速度小于图3(b)，同时图3(a)较晚才搜索到全局最优解。最终，图3(a)与图3(b)的求解结果是一致的，在循环发生50次之后，Pareto最优解集比较稳定的收敛于三个解：

(1)1-3-7-10-13-15，f1=23，f2=24，f=2.2632； (2)1-2-5-12-15，f1=29，f2=19，f=2.2609； (3)1-3-7-11-14-15，f1=25，f2=23, f=2.2975。

目前，该算法的实际应用平台由电动汽车TWIKE（10Ah电池组）、力帆LF7002EV（100Ah电池组）以及 “智能电池行动力管理服务”系统组成。路径上的能耗与时耗数据从电动车内取得后，经无线3G数据传输模块向远程服务器发送，远程服务器端接收数据后统计平均每条路径的能耗与时耗数据，在用户输入起点与目的地后进行路径优化分析。

图2 基本程序流程图

4 结论

本文给出的蚁群算法较好地解决了电动汽车行驶路径的多目标优化问题，在实际应用中可以提高电动汽车的行动力，增强用户使用电动汽车的信心。从实验结果可以得出如下结论：

（1）在算法应用到实际道路中时，简化路网拓扑模型，可以缩小解域，减小算法的时间和空间复杂度，同时将直线距离加入到启发函数中也可以启发蚂蚁向最优解收敛。

（2）将随机变异策略加入到本文的算法中可以使搜索到Pareto最优解的概率提高，这对解决优化目标更多的新问题提供了参考，是有价值的改进。

（3）通过蚂蚁之间的交流分配信息素，可以提高收敛速度，但参数的选取会影响到最优解集的完整性，需要不断调整，在实际应用中要做到参数的自适应，这是有待解决的问题。

（4）本文的算法在应用中响应快速，但目前针对电动汽车的路网信息还在完善中，同时在加入充电站后，算法需要不断测试以适应实际应用。

(a) 基本算法求解图

(b) 改进算法求解图

图3 蚁群算法求解图

参考文献

[1] 于新宝，李少波，杨观赐等．基于强度Pareto进化算法的有约束并联混合动力汽车多目标优化．计算机应用，2011，31（11）：3091-3093 [2] 林成涛，李腾，田光宇等．电动汽车用锂离子动力电池的寿命试验．电池，2010，40（1）：23-26

[3] 马华伟，靳鹏，杨善林等．时变车辆路径问题的启发式算法．系统工程学报，2012，27（2）：256-262

[4] Marco Dorigo, Eric Bonabeau, Guy Theraulaz. Ant algorithms and stigmergy. Future Generation Computer Systems, 2000, 16(8): 851-871

[5] Dorigo M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66

[6] QU Yan-feng, JIANG Dan, LIU Bin. A multi-pipe path planning by modified ant colony optimization. CADDM, 2011, 21(1): 1-7

[7] Rongwei Gan, Qingshun Guo, Huiyou Chang, et al. Improved ant colony optimization

algorithm for the traveling salesman problems. Journal of Systems Engineering and Electronics, 2010, 21(2): 329-333

[8] 何少佳，刘子扬．基于惯性蚁群算法的机器人路径规划．计算机工程与应用，2012，48（15）：245-248

[9] 段海滨.蚁群算法原理及其应用.北京:科学出版社,2005.24-26

[10] DOU Liqian, ZONG Qun, JI Yuehui, et al. Adaptive muti-objective optimization based on feedback design. Transactions of Tianjin University, 2010, 16: 359-365

Improved Ant Colony Algorithm for EV Path Multi-Objective Optimization

Abstract

Aiming at the issues that the battery of the electric vehicle (EV) have limited power capacity and its charging process takes long time, an improved multiple-objective ant colony algorithm (ACA) is proposed to optimize EV driving path and battery energy usage, which may reduce users’ worry over the driving range. ACA has excellent properties of robustness and distribution computation mechanism. It can also be easily integrated with other intelligent algorithms. Thus, ACA is quite

suitable to solve complicated combinatorial optimization problems. After unifying the different units of objectives based on standard ACA, we modify the heuristic function and pheromone update function of ACA to achieve faster convergence, and introduce a random mutation strategy to acquire all the Pareto optimal solutions. The experiment results show that the advised driving paths are Pareto optimized solutions, and can balance EV's consuming energy and time consumption, which validates the proposed improved multiple-objective ACA.

Key words: ant colony algorithm (ACA), electric vehicle (EV), driving path, multi-objective optimization, Pareto optimal solution, mobility