航海上蚁群算法研究及应用范文

摘要:本文介绍了自然界中蚁群的觅食行为、基本蚁群算法的数学模型和程序结构流程、蚁群算法的改进以及蚁群算法在航海上的应用等方面，最后将蚁群算法在航海领域中的研究问题和未来研究方向进行了总结，对从事船舶路径规划和船舶自动避碰等问题的学者来讲，具有重要参考价值．

关键词:蚁群算法;路径规划;自动避碰

在计算机技术飞速发展的21世纪，随着科技的成熟，人类正朝着智能化、机械化、自动化稳步迈进，无人车、无人飞机、无人船等纷纷问世．随着海运强国战略的实施，航运事业飞速发展，近年来涌现出一大批专家和学者，围绕无人驾驶船舶路径规划和航线自动生成等问题展开研究．在此之前，机器人路径规划技术已经趋于成熟，鉴于机器人路径规划与无人驾驶船舶路径规划、航线自动生成的相似性，例如遗传算法、人工势场算法、粒子群优化算法、蚁群算法等，都可以应用于无人驾驶船舶路径规划或船舶航线自动生成等航海问题．蚁群算法因其强大的鲁棒性，广泛的适用性，优良的分布式计算以及与其他算法的简单组合而得到广泛应用．其他学者大多写蚁群算法在非航海方面的应用，并无学者将蚁群算法在航海上的应用总结出来，本文将蚁群算法在航海方面的应用(如无人船路径规划、潜艇导航规划、船舶避碰规划等)以及研究中发现的问题和未来研究方向总结出来，对从事无人驾驶船舶路径规划或船舶航线自动生成等与航海相关的学者来讲具有参考价值．

1蚁群算法的算法原理

蚁群算法(antcolonyoptimization，ACO)，又称蚂蚁算法或蚁群优化算法，是由意大利学者MarcoDorigo等人于1991年在法国巴黎召开的第一届欧洲人工生命会议(EuropeanConferenceonArtificialLife，ECAL)上提出［1］．然而，截至1996年，它一直没有引起国内外学者的广泛关注，直到后来MarcoDorigo又发表了“Antsystem:optimizationbyacolonyofcooperationagents”这篇文章，蚁群算法这才引起了学术界的关注．

1．1蚁群行为描述仿生学家通过对蚂蚁生活习性的长期观察，发现蚂蚁并不像其他动物那样拥有视觉，且个体蚂蚁的智慧并不高，然而，群体蚂蚁在寻找食物的过程中寻找路径的行为反映出了高度组织的结构化．该研究发现，在觅食的过程中，蚂蚁会分泌一种特殊的化学信息素，蚂蚁通过这些信息素传递信息，协同合作，形成集体自催化行为，然后找到从蚁巢到食物来源的最短路径［2］．蚂蚁选择特定路径的趋势与发现的路径上的信息素浓度正相关，即通过路径的蚂蚁越多，蚂蚁留下的信息越多，道路上存在的信息素浓度就越大，其他蚂蚁选择这条道路的可能性就越大．在寻找食物的过程中，蚂蚁寻找路径的这种行为形成了积极的正反馈机制［2］．由于信息素的浓度随时间逐渐降低，因此路径越长，信息素的浓度越小．图1是自然界蚂蚁的觅食原理［3］．A为食物源，D为蚁巢，B和C为障碍物的端点．如图(a)所示，在通往食物源的途中，如果没有障碍物，蚂蚁将始终选择最短的路径．如图(b)所示，如果蚁巢和食物源之间存在障碍物，蚂蚁将以相同的概率选择DBA和DCA路径．如图(c)所示，因为路径DCA的长度小于路径DBA，所以等时通过路径DCA的蚂蚁比通过路径DBA的蚂蚁多．然后，蚂蚁在DCA上分泌的信息素浓度高于蚂蚁在DBA上分泌的信息素浓度．后续蚂蚁就倾向于选择路径DCA．如图(d)所示，最终蚂蚁都会选择路径DCA，蚁群正是通过这种方法，才用最短的路径寻找到了食物源．

1．2基本蚁群算法的数学模型本文借助于经典的旅行商问题(TravelingSalesmanProblem，TSP)，对基本蚁群算法的数学模型进行说明．即人工蚂蚁k(k=1，2，3，…，m)从n个城市中任选一个作为起点，随机前往下一个城市，中途不能折回，一个城市不能重复走过，最后返回起点，最终找到一条最短的路径．为了确保蚂蚁k不重复经过一个城市，这里用禁忌表tabuk(k=k=1，2，3，…，m)记录蚂蚁k当前走过的城市，则人工蚂蚁t时刻从一个城市i到另外一个城市j的转移概率为:式中，α为信息启发式因子，表示轨迹的相对重要程度，其值越大，其他蚂蚁选择该路径的可能性越大;β为期望启发式因子，表示能见度的相对重要程度，其值越大，其他蚂蚁选择该路径的可能性越大．τis(t)为t时刻城市i到城市j路径上存在的信息量，ηis(t)为t时刻蚂蚁从城市i到城市j的期望程度，且，ηis(t)越小，pkij(t)就越小，即转移概率就越小．为了避免残留信息素淹没启发信息，需要对残留信息素进行更新处理，t+n时刻，路径(i，j)上的信息素调整为:式中，1－ρ为信息素残留因子，且ρ［0，1］;Δτijk(t)表示第k只蚂蚁在路径(i，j)上留下的信息量;Δτij(t)表示循环结束后路径(i，j)上信息素的增加量;Q表示信息素强度;Lk表示第k只蚂蚁在本次循环中行走的路径长度．

1．3基本蚁群算法的程序结构流程以旅行商问题为例，基本蚁群算法的程序结构流程如图2所示:

2蚁群算法的改进

尽管蚁群算法具有许多优点，但必须考虑其存在的缺陷．蚁群算法需要花费大量时间进行计算，搜索速度太慢，算法收敛时间太长．启发式因子α，预期启发式因子β，信息素强度Q，信息素挥发因子ρ等参数的设置均基于经验，没有足够的理论依据［4］．为了解决这方面的问题，国内的段海滨、高尚、孙焘、丁建立、陈崚、杨勇、汪镭等，国外的GutjahrWJ、MarcoDorigo、StützleT、HouYH、YooJH、BadrA等许多学者对蚁群算法的方法或模型或策略进行了改进．在一定程度上，减少了蚁群算法的计算时间，提高了收敛速度，避免了局部最优．StützleT和HolgerHoos在1997年提出了最大－最小蚂蚁系统［5］(MAX-MINAntSystem，MMAS)，MMAS是一种基于协同搜索的元启发式算法，它改进了传统的蚁群算法(AntSystem，AS)，为组合优化问题的解决方案提供了自适应框架．MMAS在每次迭代中仅允许最佳的蚂蚁更新路径信息素强度，并且信息素强度在所有路径上初始化为最大值τmax．在每次迭代之后，仅允许最佳路径的信息素保持在较高水平，而其他路径上的信息素将随时间逐渐挥发．信息素的挥发使信息素强度降低一个因子，导致更少的后续蚂蚁选择这条路径，信息素强度持续降低．如果不及时处理，信息素的强度将降至零，为此需要设置信息素的强度不能低于一个最小值τmin．换句话说，需要将信息素的强度τ设置为τmin≤τ≤τmax．这种处理方法有效地克服了蚁群算法容易出现停滞现象的缺陷，但是最大－最小蚂蚁系统每一步搜索结束之后都要对所有路径上的信息素进行实时更新，导致消耗大量的时间．此外许多参数(如τmax、τmin等)的设置仍然凭借经验，没有严谨的数学证明作为理论依据．StützleT和HolgerHoos在2000年发表了《MAX-MINAntSystem》对最大－最小蚂蚁系统进行了改进—信息素平滑处理［6］．当MMAS搜索停止时，比较每条路径的信息素差值，并且当差异大时，对每条路径的信息素强度进行加权平均．加权平均后每条路径的信息素间隙减小，有利于生成新的搜索路径，但算法的搜索效率会较慢．杨延庆等［7］从信息素τ的限制、信息素的更新方式两方面对最大－最小蚂蚁系统进行了改进，将传统最大－最小蚂蚁系统的信息素强度τ设置为固定值，可在一定程度上提高计算效率．另外，在完成每个循环之后，MMAS对各条路径长度进行加和平均，路径长度小于平均值，则基于原始信息素强度适当增强．相反，如果路径长度大于平均值，则基于原始信息素强度适当减弱;最短路径上的信息素和蚂蚁行进的最远路径被更新，而另一条路径上的信息素不被处理．然而，由于信息素随时间挥发，因此最短路径上的信息素与最远路径之间的差异增大，从而提高了算法的搜索效率．王胜等［8］通过禁忌策略改进蚁群算法，避免局部最短路径中的蚁群停滞．由于缺乏参数的自适应调整策略，需要改进算法旅行商问题的寻优能力．张军英等人［9］从城市选择策略的参数选择，信息量更新方式和局部搜索策略等方面对蚁群算法进行了改进．改进的算法加速了算法的收敛，降低了早熟收敛和搜索停滞的可能性．段海滨等人［10］提出利用云模型理论实现蚁群算法，避免了在大搜索空间条件下出现局部最优解，能够更快地找到全局最优解．GambardellaLM等［11］在1999年提出了多重蚁群算法(MultipleAntColonySystem，MACS)的概念，并利用该算法解决了多目标优化问题，大大降低了最优解的求解速率．CSolnon［12］提出了Ant-P-solver，这是一种基于蚁群优化的元启发式算法，通过与本地搜索技术相结合求解约束满足问题(ConstraintSatisfactionProblem，CSP)，将问题建模为在图中搜索最佳路径，人工蚂蚁以随机的方式走过该图，人工蚂蚁通过在图的边缘释放信息素进行通信，寻找最优路径．DGaertner和KLClark［13］使用遗传算法(GeneticAlgorithms，GA)的思想修改了ACO实例，以形成遗传基因改进的蚁群系统(GeneticallyModifiedAntColonySystem，GMACS)．在该算法中，每个蚂蚁用随机参数组合初始化，其中参数值从合理范围中选择．随着时间的推移，蚂蚁的数量不断增加，使用更好的参数组合培育蚂蚁，从而找到改进的解决旅行商问题实例的方案．

3蚁群算法在航海上的应用

自1991年引入蚁群算法以来，许多学者积极探索并大胆尝试，在蚁群算法研究方面取得重大进展和突破．如旅行商问题、指派问题(QuadraticAssignmentProblem，QAP)、序列排序问题(SequentialOrderingProblem，SOP)、图形着色问题(GraphColoringProblem，GCP)、车辆路径问题(VehicleRoutingProblem，VRP)、车间作业调动问题(Job-shopScheduleProblem，JSP)、以及网络路由问题(QuantityofService，QoS)、线性系统参数辨识问题、最优PID控制问题、故障诊断问题、图像处理、聚类分析、数据挖掘、航迹规划、空战决策、岩土工程问题(如边坡非圆弧临界滑动面搜索问题)、化学工业问题(如2－氯苯酚在超临界水中氧化反应动力学参数估计问题)、生命科学问题(如蛋白质折叠问题)、机器人路径规划问题、无人驾驶车辆路径规划、无人机路径规划等．蚁群算法在这些方面的应用前人多有阐述，本文重点阐述蚁群算法在航海领域的应用，如无人船路径规划、无人水下航线器路径规划、船舶航线自动设计、潜艇导航规划、船舶避碰规划等．何立居，李启华［14］以电子海图显示和信息系统为基础，采用前向策略和后向策略作为搜索策略．蚁群算法从海域网格划分，网格点信息素，信息素更新，搜索策略，路径选择和路径平滑等方面进行了改进．通过实例证明了蚁群算法用于航线自动生成的可行性．刘利强［15］提出了一种改进的基于协同和空间收缩的蚁群优化算法，以及一种改进的连续域蚁群优化算法，具有收敛速度快，搜索能力强的特点．采用空间网格法模拟三维空间环境，为潜艇进行三维空间导航．陈晓等［16］利用构造自由空间的Maklink图论法对海图进行预处理，生成无向网络图，接着采用动态规划Dijkstra算法生成初始路径，最后用蚁群算法进行路径优化．这与在传统的纸质海图上手绘航线或者在电子海图显示与信息系统(ElectronicChartDisplayandInformationSystem，ECDIS)中输入航路点生成航线相比，能够节省较多时间，给船员减轻了负担，但是由于没有考虑到动态障碍物避险以及风、浪、流等自然因素的影响，有待进一步研究．赵红［17］将人工势场法与蚁群算法相结合，形成了一种用于波浪动态滑翔机路径规划的势场蚁群算法．在基于改进势场蚁群算法的波浪动态滑翔机路径规划仿真实验中，文献考虑了导航过程中的动态障碍，以及波浪、海流等自然因素的影响，设置了波浪权重和水下海流权重等海洋环境参数．该方法提高了算法全局优化的能力，提高了波动力滑翔机的导航速度，缩短了波动力滑翔机的行驶时间．最重要的是使波动滑翔机能够成功避开动态障碍物并产生了一条安全的最短路径．陈立家等［18］论述了基于电子海图的在多约束条件下(风浪、水深、船速、航行费用等)综合成本最低的最优航线生成算法(optimalroutegenerationAlgorithm，ORGA)．基于航线网络图，该算法使用Dijkstra算法找到最短路径，并使用改进的蚁群算法找到最优路径．该算法提高了搜索效率，可以更快地找到最佳路径．朱青［19］介绍了基于分布均匀性的自适应蚁群算法，利用连接图法(Maklink方法)动态调整信息素更新策略和状态转移概率，来解决算法收敛速度慢和早熟收敛的现象．最后，平滑路线以获得最佳路径．张金水等［20］将遗传算法与蚁群算法向融合，以获取最优航线．先用蚁群算法产生航线初始种群，然后用遗传算法对之前产生的航线初始种群进行遗传操作—选择、交叉、变异、删除［21］，得到最优航线．AgnieszkaLazarowska［22］介绍了在导航决策支持系统(DecisionSupportSystem，DSS)中使用蚁群优化技术的智能应用程序，以及在导航DSS中实现的ACO原理和基于ACO的算法，开发的导航DSS体系结构以及路径规划和避碰问题等．该系统解决问题的能力包括在公海和限制水域中的船舶的路径规划和船舶避碰，增强了船舶安全控制过程的自动化程度．JBEscario［23］基于细胞自动机(CellularAutomata)和改进蚁群优化算法给自动船舶操纵进行最优或次优路径规划．细胞自动机是对的连续搜索空间进行粗略的离散化，并提供推荐的船舶姿态的集合，而没有任何明确的船舶动力学参考．考虑到船舶动力学所施加的限制，这些姿态将成为蚁群算法计算连续轨迹的起点而提出的改进蚁群优化算法，则是用来处理具有动态特征的“蚂蚁”(船只)，最终达到给自动船舶操纵进行最优或次优路径规划的目的．国内外众多学者利用蚁群算法，围绕船舶路径规划与优化、船舶避碰、波浪动态滑翔机路径规划、潜艇导航规划等航海领域展开研究，取得了不错的成绩，但是蚁群算法在数学上缺少严谨的可靠性的理论证明，且很多参数的设置都是凭借经验，没有理论依据，再加上蚁群优化算法本身原理机制复杂，编程代码复杂，实现难度较大．

4结论

随着航运事业蓬勃发展，蚁群算法在航海领域的应用更有待挖掘，船舶路径规划和船舶自动避碰等航海领域问题需要进一步深入研究．为了给后续学者提供研究思路，特将研究中发现的问题总结如下:(1)海洋环境复杂多变，用栅格法、拓扑法、Maklink图论法等对环境进行处理后，与真实环境存在差距，真实性和可靠性有待提高．环境建模多采用栅格法，建模后的分辨率大小问题也要考虑，如何采用动态栅格，是一种研究思路．(2)岛屿、暗礁、浅水区等航行过程中必须考虑的因素的处理方法有待改进．对这些因素进行膨化处理的尺度很难把控，膨化过大，设计出来的航线可能不是最优航线，膨化过小可能存在安全隐患．(3)航线路径规划多针对静态环境(理想环境)，动态环境下，尤其是复杂动态环境下(风浪流等)，进行航线规划难度较大．

作者：张文拴 徐海军 闫哲 单位：大连海事大学