基于蚁群算法在交通领域的应用综述

2013-09-01黄敏

海南开放大学学报 2013年2期

黄敏

(琼州学院电子信息工程学院，海南三亚 572022)

引言

蚁群算法是一种模拟仿生进化算法，具有模拟生物界群体觅食能力和正反馈特征，并且能够在实际路径搜索过程中对外界影响做出动态响应，因而在交通领域具有极大的可行性和适应性[1]。因此，针对实际交通问题与蚁群算法的直接对应性，本文将从蚁群算法在交通过程建模、规划和优化问题求解方面应用进行综述。

一蚁群算法原理及基本模型

(一)蚁群算法原理

近年来，生物行为模拟在许多领域备受研究者关注，蚁群在解决无法由单蚁完成的任务时显示了集体行为的强大作用。在蚁群中，信息素是蚂蚁之间传递信息的主要媒介。在蚁群搜索过程中，蚁群之间通过信息素作用交换路径信息，当某条路径上的信息量越来越大时，其他路径上的信息量会随着时间逐渐消减，最后整个蚁群会集中在信息量最大路径上，此条路径就是从巢穴到食物之间最短路径。通过对自然界中蚂蚁觅食行为及特点研究，研究者也从真实蚂蚁转换向人工蚂蚁研究。1991年，意大利学者M．Dorigo，V．Maniezzo等人首先提出了蚁群算法。蚁群算法运动和通信的简单规则包含六个主要方面:1．搜索范围;2．局部环境;3．觅食规则;4．移动规则;5．避障规则;6．通信规则。

(二)蚁群算法基本模型

二蚁群算法最新研究进展和发展趋势

蚁群算法这个真正的元启发式方法有数十个应用领域，随着蚁群算法性能不断提高及研究不断深入，近年来，改进的蚁群算法及其应用又有新进展和良好发展趋势。

(一)基于动态优化问题

动态问题可以定义为一个多量值的函数，这些量的值是由一个潜在系统动态设置的。文献在动态TSP中，随时间变化动态添加或删除城市结点，把问题变为如何找到能快速地重新计算新的TSP的方法。文献使用基于蚁群的ACO来解决动态问题，生成信息素矩阵的所有信息都来自蚁群体，一旦问题出现了动态变化，在蚁群中使用一个修复算子来修复解，然后再使用修复后的解重新生成信息素矩阵，使该方法在改变时间间隔较短动态情况下，具有更优性能。文献提出用最大生成1－树概念引入蚁群算法，通过一种新的量度来构造动态候选集。该算法有效防止解的退化问题，同时提高了搜索速度和搜索性能[9]。

(二)基于随机优化问题

随机优化问题是用于定义具有随机特性的问题。文献提出求解目标是要找到一条遍历所有城市并且期望长度最小的演绎回路，并按这条演绎回路中出现的顺序对城市一个随机子集进行访问，该算法的性能优于基于特定问题的启发式方法。文献通过使用一个可快速计算的近似函数和与具体问题相关的启发式方法在构建路径过程中指导蚂蚁，能够提高算法的性能。

(三)基于多目标优化问题

文献基于解决多目标组合优化问题是以向多个目标赋予优先级为基础，提出用于求解带有时间窗限制的车辆路由问题的双蚁群方法。文献使用两个相互合作的蚁群来解决双目标运输问题和双机器排列流车间问题，使用权重和的方法将两个目标函数组合成一个目标函数，每个启发式信息只对应于一个目标。文献将蚁群算法应用于证劵投资最优化问题，提出每一个目标都是一个信息素矩阵，蚂蚁按照信息素矩阵权重组合来构造解。该改进算法的性能优于模拟退火算法和非受控分类遗传算法。

(四)基于机器人路径规划问题

文献提出一种复杂静态环境下移动机器人避开路径规划的改进蚁群算法。基于栅格法的工作空间模型，通过模拟蚂蚁觅食行为，针对移动机器人的路径规划需要，赋予常规蚁群算法一些特殊功能[9]。

三蚁群算法在交通领域的应用

通过对蚁群算法的精心研究和应用开发，该算法被广泛利用于求解JOB－SHOP调度问题、二次指派问题、顺序排列问题、广义分配问题、网路路由问题、动态旅行商问题以及背包问题等。近几年来，算法不断改进，从而在数据分析、电力、协作运输、通信、机器人协作问题、水利建设、建筑、采矿、交通、网络等领域得到大量应用。

(一)交通过程建模

在现实生活中，有很多突发的交通现象是不能用数学模型准确分析和解释的，分析这类现象只能通过模拟每个智能体行为方式来进行。基于群体智能的多智能体系统交通传输模拟，如A-gent模型，就属于此类方法。它将各个分散的、独立的智能体结合成一个系统，这些智能体可以通过局部知识来影响其他智能体。这种智能体方法能从下往上地对那些模拟社会性昆虫特殊智能体进行建模。社会性昆虫的自然行为主要受其自治、分布式的机能和自组织能力的影响，系统的任何一个简单个体通过动态的相互作用就可以完成非常复杂的任务，所以大量的传统工程模型和算法都是以集中化控制为模型的。因此可以借助蚁群算法等自然化的群体智能法则来开发一个旨在解决复杂的交通传输问题的方法。

(二)交通过程优化及导航

通过改进蚁群算法的应用，可以解决TSP问题和其他类似优化问题。同样，在水路运输问题中也可加以类似应用。

基于蚁群算法的进化计算模式，用于车辆导航的进化式视觉传感。这种方法能很好地处理数字图像，而且能发现在南极冰雪面上前行的交通工具所留下的踪迹。这种由蚁群激发的策略是一种协作的智能体行为，行为者沿着图像像素移动，并且反复地改进初始的较粗糙的解决方案，如能够对恶劣的南极圈环境进行图像分析等。

(三)交通运输规划问题求解

基于蚁群算法，可以很好地对车辆路线规划问题进行求解，同时可依照计算效果来改进其性能。首先可以将问题进行分解，在此基础上，只要解决各个小的子问题就可以了。通过计算研究和统计学分析，从标准的基准问题和大范围的车辆路线规划问题方面出发，蚁群算法不仅能改进效率，而且能成为解决真实世界中实际交通运输规划问题的工具。每条河段有相应的运输能力，它的运输任务与运输能力都是对未来的一个预期，有一定随机性。根据这个特点，2005年，在国内相关研究人员努力下，对蚁群算法进行了相应改进，并配合随机分布技术，以上海市整个内河航道和集装箱运输为研究对象，对内河航道进行了合理规划，得出了上海市内河集装箱集散系统合理的分配方案，并提出为满足该合理系统所需进行的相应河道改造重点。从而解决了上海市内河航道最优航道选择情况和航道满载概率，以期求得各河段相应的改造概率，保证该运输网络的畅通。

另外，可将基于信息素传递的互助蚁群搜索方法用于车辆路线规划问题求解。在此类算法中，多智能体可以将问题进行有机分割，然后通过信息素来传递独立的搜索解。这是一种模拟真实蚂蚁之间通信模式的方法。