基于蚁群算法的自动循迹小车路径规划研究

蒋鸣东，朱荣军

（安徽工业经济职业技术学院，安徽 合肥 230051）

基于蚁群算法的自动循迹小车路径规划研究

蒋鸣东，朱荣军

（安徽工业经济职业技术学院，安徽 合肥 230051）

本文通过对蚁群算法的初步应用及研究，提出自动化小车全局路径规划的自适应算法，考虑小车体积及转弯状况，自动择选小车运行最优路径。运用仿真实验及分析，研究证明蚁群算法的智能规划。

蚁群算法；路径规划；研究

近年来，最优路径规划问题，伴随着智能化小车的发展，越来越受到重视与发展。基于蚁群算法的自动循迹小车路径规划问题，许多专家学者提出多种优化算法。智能循迹小车以单片机为微型控制器，它用红外反射式的光电管探测路径，并且用最短的时间完成路径规划的循迹问题。

1 蚁群算法的研究及应用

蚁群算法也称为蚂蚁算法，它是用图来寻找优化路径的一种机率型算法。这种算法由1992年提出，模拟蚂蚁在寻找食物过程中发现路径的行为。蚂蚁算法也是一种模拟进化算法，且具有诸多优良品质，对于PID控制器参数优化设计的问题，相对于其他算法，蚁群算法更具有有效性和应用价值[1]。

1.1 蚁群优化算法

蚁群算法是从自然界得到的一种算法，蚂蚁是一种群居生物，它们存在于一个群落中，他们的行为不是自己个人决定的，而是整个群落。所以通过它们的群居生活给我们带来许多启示。一些人发现它们蚂蚁可以发现食物所在地和所在洞穴的最短距离。所以它们是怎么做到的呢？蚁群算法，是说明一群人工蚂蚁通过复杂的离散问题去寻找一个最优解。相互协作是其最重要的部分，它们彼此之间创立了一个机制，致使他们相互作用，相互交流，便顺理成章的解决了问题。

经过多次实验表明：蚂蚁移动过程中在地上释放一种物质被称之为信息素，同时形成一种信息轨迹。蚂蚁通过嗅觉闻到信息浓度大的路径，从而使它们找到了最短距离。

1.2 蚁群算法的应用

蚁群算法，是说明一群人工蚂蚁通过复杂的离散问题去寻找一个最优解。相互协作是其最重要的部分，它们彼此之间创立了一个机制，致使他们相互作用，相互交流，便顺理成章的解决了问题人工蚂蚁具有两面性，一方面，它们像真的蚁群一样通过彼此沟通，跟踪信息素轨迹来寻找最佳路线；另一方面，它们具备一些一群无法具备的性质及功能[2]。

蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。

每只蚂蚁在自己能感知的范围内去寻找是否有食物，若有就直接过去。否则看是否还有信息素，并感知自己的感知范围内信息素的多少，从而指引蚁群的移动。而且每只蚂蚁的错误率都非常小。

蚁群会随着信息素最多地方移动，当周围没有信息素时，它们会朝着自己原来运动方向运动，而且为了防止原地绕圈，它会记住自己先前走的路线，避免自己找不到前进的方向。

倘若蚂蚁移动路线受到阻碍，他会随机找到另一个方向，并且如果有信息指引的话，会按照觅食规则行为。每只蚂蚁在刚找到食物或者自己的洞穴散发的信息素最多，但随着自己走的距离信息素会越来越少。

2 基于蚁群算法的小车循迹路径规划

2.1 循迹路径规划模型的建立

在我们处理实际问题时，我们要首先考虑既方便又节能。理论上，旅行商问题是车辆路径问题的一个简化，一个特例。例如：车辆路径问题，它是一类交通运输优化问题，存在各种VRP问题。其具体算法如下：通过车辆的幅度，使车辆总行程最短。

G=（V，A，d）是一个完全有向权图，其中V={v0，v1，v2，...，vn}是顶点集合，A={(vi，vj):i≠ j}是连接顶电弧的集合。顶点v0表示库房，而V中其余的顶点则表示为城市或客户，与弧（vi，vj）相关联的非负权值dij表示vi和vj之际的距离（或者为旅行时间，或旅行费用）。对每一个客户vi而言，都有一个确定非负需求qi和一个非负时间§i，并使其满足：

·每个客户被一辆车车辆访问的次数只有一次；

·所有车辆从库房出发，最后返回库房；

·对每一条车辆路径，其总需求量都不能超过车辆的载重量Q；

·对每一条车辆路径，其路径长度不超过一个给定的上界L。

2.2 蚁群算法设计

步骤一：nc=0（nc为迭代步数或搜索次数）；每条边边上的t=c（常数），并且△t=0；放置m个蚂蚁n个城市上。

步骤二：将各蚂蚁的初始出发点置于当前解集tabu中；对每个蚂蚁k（k=1，...，m），按概率移至下一个城市就j；将城市就j置于tabu中。

步骤三：经过n个时刻，蚂蚁k可走完所有的城市，玩成一次循环。计算每个蚂蚁走过的总路径长度L，更新找到的最短路径。

步骤四：更新每条边上的信息量t（s+n）。

步骤五：对每一条边置△tt=0；nc=nc+1。

步骤六：若nc＜预定的选代次数NCMAX，则转步骤二；否则，打印最短路径，终止整个程序。

2.3 蚁群算法小车循迹

VRP问题是以最小为目标，一般VPR问题可描述若干车辆从配送中心出发，到不同地理位置送货，然后返回配送中心，其中一次配送距离的最大行驶距离。要求合理安排车辆，得到最优解。

从蚁族算法发现至现在，已经有无数的成功过的例子解决各种组合最优解。因此可分为：静态组合优化问题和动态组合优化问题。

静态组合优化问题，就是一旦一个被给出，所有内容也就确定下来，并且也不会随机改变。

3 总结

本文首先回顾了蚁群算分的过程和基本的蚁群算法，再介绍了一群算法再每个有代表性的问题中的基本解决方法。然后分析了基于蚁群算法的自动循迹小车路径规划的问题。在介绍了国内研究的一个基本状况的同时也介绍了国外的研究现状，对本文的研究内容和背景进行了阐述。

传统的蚁群算法，由于一些原因，在某些应用时，给那些没用过的使用者来说有许多不方便的情况。所以提出了一些其他的算法——基于时间模型的蚁群算法。时间蚁群算法和普通的蚁群算法一样，作为一种新型的智能优化方法具有许多优点，但也有许多不足，为此需将它两相结合，形成互补状态，用于一些应用中。

总得来说，蚁群算法是通过信息素的累积和更新而收敛于最优路径。

[1]王烨 .基于Android系统的智能导航小车设计控制科学与工程[D].天津:天津大学.2013.

[2]高攀龙 .基于网络控制的四轮驱动巡检小车的设计与应用.控制工程.南昌: 南昌大学.2014.

The car of automatic tracking path planning based on ant colony algorithm

JIANG Ming-dong， ZHU Rong-jun

(Anhui Technical College of Industry and Economy， Hefei Anhui 230051)

Based on ant colony algorithm preliminary application and research， put forward adaptive algorithm for global path planning of automated car， consider car volume and turning condition， automatic，the car running optimal path. Using the simulation experiment and analysis， the research proves that the ant colony algorithm of intelligent planning.

Ant colony algorithm; Path planning; Research

P441+.3

A

10.3969/j.issn.1672-7304.2016.05.016

1672–7304(2016)05–0033–02

安徽工业经济职业技术学院质量工程特色专业项目“电子信息工程技术”（项目编号：2013YTSZY01）。

（责任编辑：张时玮）

蒋鸣东（1981-），男，安徽合肥人，研究方向：计算机技术、计算机控制。