基于Unity 3D的蚁群算法仿真

程廷，潘耘，姜瑞娟

(中国传媒大学 计算机学院，北京 100024)

基于Unity3D的蚁群算法仿真

程廷，潘耘，姜瑞娟

(中国传媒大学 计算机学院，北京 100024)

基于Unity3D引擎对蚁群寻路觅食场景进行了建模，通过C#语言编写信息素迭代机制、蚁群寻找最短路径的算法，并以可视化手段显示出最短路径，最后对蚁群算法的各个参数设置进行了探究。仿真结果验证了使用Unity3D进行算法仿真的可行性，直观易懂地呈现出蚁群算法的基本过程与原理，具有参数易控、视觉直观性强等优点。

蚁群算法；Unity3D；计算机仿真

1 引言

蚁群算法(Ant Colony Algorithm)是受自然界蚁群觅食过程启发而提出的一种智能优化算法，具有离散性、并行性、正反馈机制等特点[1]。为了能够清楚地表达基本蚁群算法的数学模型，通常借助经典的TSP(traveling salesman problem)旅行商问题对其进行描述[2]。其中包含较多数学模型，对于理解有一定的难度。为了使算法原理更加直观，可读性更强，考虑以可视化的形式呈现蚁群算法的仿真过程。因此，本文使用Unity3D引擎进行蚁群算法的仿真与实现。

Unity引擎是一款流行的3D/2D综合型游戏开发工具和引擎套件，其中包括图形、UI、物理、动画等多方面的引擎支持[3]。Unity内置的PhysX物理引擎可以高效、逼真地模拟出蚁群觅食寻路的运动状态。

本文使用Unity3D引擎对蚁群算法进行仿真模拟。首先创建了仿真场景的基本模型，然后使用C#语言编写信息素迭代机制、蚁群寻路行为相关算法。通过添加脚本，可以改变仿真参数，比较不同参数下的仿真结果及算法效率；在仿真过程中，还可以对环境中的物体进行实时控制，并且可以实时输出时间等数据，不必等到仿真结束再查看结果，提高了仿真实验的效率。与Matlab等算法仿真软件相比，本方法更加直观、易控，具有一定优势。

2 蚁群算法的基本原理

2.1 蚁群算法原理

自然界中，蚁群通过互相协作完成觅食等复杂的任务，并以此找到较短的路径。那么视觉系统发育不全的蚂蚁是如何完成觅食的呢？研究发现，蚂蚁会释放一种叫信息素的化学物质。蚂蚁在觅食的时候，经过一段时间，就能找到一条从巢穴到食物源的最短路径。这是因为，蚂蚁在爬行的路径上会释放信息素。同时，蚂蚁会实时感知信息素浓度，选择一条信息素浓度高的路径。当这条路径上的信息素浓度越高，蚂蚁选择该路径的概率越大，这样就会有更多的蚂蚁选择该条路径；相反，对于信息素浓度越低的路径，蚂蚁选择它的概率就越小，随着时间的推移，信息素浓度会越来越低，则以后蚂蚁选择该路径的可能性也变得更小。由于较短路径上的信息素被更多地保留下来，从而让更多蚂蚁聚集到最优路径上，这就是蚁群算法的正反馈机制[2]。

同时，当外部环境发生变化时，蚂蚁能够用很短的时间来适应这种变化。当在爬行路线上遇到障碍物时，蚂蚁能很快找到较好路径[1]。

为了便于理解，使用图1至图4说明蚁群觅食原理：

图1 无障碍物时的觅食情况

图2 有障碍物时的初始情况

图3 选择较短路径的蚂蚁多

图4 蚁群最终沿最短路径觅食

2.2 蚁群算法的数学模型

蚁群算法的数学模型通常以旅行商问题(TSP)来建立。TSP问题是：在给定城市个数和各城市之间距离的条件下，找到一条经过所有城市且每个城市只能访问一次的最短路线[4]。下式为信息素强度以及第k只蚂蚁选择某个城市的概率：

上述公式中i、j分别为起点和终点，τij(t)为时间t时，i到j的信息素强度。m为蚂蚁个数。ρ表示信息素的挥发率，如果它的值取得不恰当，得到的结果很可能是局部最优解[4]。概率公式中，ηij为i、j距离的倒数。allowedk为尚未访问过的节点集合。α值的大小表明留在每个结点上的信息素受重视的程度，α值越大，蚂蚁选择以前经过的路线的可能性越大；β的大小表明启发式信息受重视的程度。α和β两个因子决定了蚁群算法的全局寻优性能和快速收敛性能[5]。

由于蚁群搜索是一个正反馈的过程，所以蚂蚁数量越多，搜索速度应该越快。但是，蚂蚁数量越多意味着迭代次数越多，消耗的时间也越多[5]。因此，本文基于Unity3D的蚁群算法仿真通过设置不同蚂蚁数量、信息素的挥发时间等参数研究其对算法效率的影响，寻找出较高效的参数设置方法。

3 基于Unity3D的蚁群算法仿真设计

3.1 蚁群算法的仿真流程

使用Unity3D引擎进行蚁群算法仿真的具体流程如下：

初始化场景信息，设置蚂蚁数量、信息素挥发时间、蚂蚁搜索半径、蚂蚁速度等参数。

按照设置的蚂蚁数量生成蚁群。

所有蚂蚁按照概率随机分布到场景中进行寻路觅食，同时释放信息素。信息素强度随时间线性衰减。

蚂蚁在寻路过程中，自动绕过障碍物。当少数蚂蚁找到食物，取走食物块后，返回巢穴，同时释放信息素(信息素轨迹可见，随时间挥发)。

当其它蚂蚁感知到信息素后，则趋向于信息素较浓的路径，同时获得信息素携带的食物坐标，沿着路径找到食物，取走食物块返回巢穴，同时释放信息素。

通过迭代，最终大多数蚂蚁聚集在信息素浓度最强的最短路径上。图5为蚁群算法仿真流程图。

图5 蚁群算法仿真流程图

3.2 仿真场景设计

本次仿真建立了两个场景：1、单一目的地的最短路径寻找及避障场景；2、多目的地的寻路避障复杂场景。

为了模拟自然界中蚁群觅食的真实场景，需要建立的模型有：蚂蚁巢穴、蚂蚁、障碍物、食物。为简单起见，这些模型均使用立方体代替。在初始化时获取每类模型的材质分别设置为不同的颜色，用以区分各自类别。其中，蚂蚁是核心模型，为其添加刚体和寻路组件，创建信息素和食物块作为其子物体，然后将蚂蚁模型做为预置体，方便在仿真过程中实例化生成。

此外，创建平面作为地面，信息素的可视化效果使用Unity自带的粒子系统生成。UI方面，使用Unity的UGUI系统创建图例和计数UI。

3.3 仿真实现

Unity3D引擎支持的编程语言是C#和JavaScript[6]。本次仿真的程序设计使用的是C#语言。

3.3.1 场景初始化

在仿真初始时，为了生成相关参数，需要编写Setup脚本。该脚本定义信息素产生间隔、信息素挥发时间、蚂蚁移动速度、蚂蚁搜索半径、蚂蚁数量等参数，并制作成可视化控制面板。图6为Setup脚本生成的参数控制面板。

图6 Setup控制面板

初始化参数后，会按照设置的蚂蚁数量从巢穴生成相应数量的蚂蚁。为此，编写AntSetup脚本，获取Setup面板中设置的蚂蚁数量，在for循环体中使用Instantiate()函数实例化生成相应数量的蚂蚁。

3.3.2 蚁群行为脚本与信息素迭代机制

生成一定数量的蚁群后，蚂蚁开始随机分布进行觅食并释放信息素。为此，需编写蚂蚁寻路觅食的相关脚本。该脚本命名为AntBehavior，为蚁群算法核心脚本。

首先，蚂蚁在寻路过程中会有三个状态：寻路、跟随信息素、运输食物。每个状态执行相应的行为函数。因此，在脚本中利用枚举结构定义这三个状态。然后，设置不同的标签，用以判断蚂蚁不同状态的转换，这里定义了3个布尔型标签：是否找到食物、是否在运输食物、是否找到信息素轨迹。在Update函数(Update函数是Unity提供的函数，其在每一帧被调用[6])中，使用switch选择结构判断蚂蚁状态，并执行相应行为函数。伪代码如下：

switch(当前状态)

{

case寻路：

explore()；//寻路函数

if(正在运输食物)

{当前状态 = 运输食物；}

if(找到信息素)

{当前状态 = 跟随信息素路径；}

break；

case跟随信息素路径：

followTrail()；//跟随轨迹函数

if(正在运输食物)

{当前状态 = 跟随信息素路径；}

if(!找到食物)

{当前状态 = 寻路；}

break；

case正在运输：

transportFood()；//运输函数

if(!正在运输){

if(食物位置 != 初值)

{当前状态 = 跟随信息素路径；}

else

{当前状态 = 寻路；}

}

break；

}

蚂蚁在不同状态下会执行相应的行为函数。图7为蚂蚁行为脚本的4个核心函数。分别为寻路函数、跟随信息素轨迹函数、触发函数和运输函数。

图7 蚂蚁行为脚本的核心函数

生成蚁群后，每只蚂蚁的初试状态都为寻路，即执行explore()函数。该函数实现了寻路算法，使蚂蚁每1至2秒内重定向寻路。首先设置定时器timestamp用于计时。使用Random类的insideUnitSphere属性随机返回半径为1的球体内的一个点的坐标，该坐标与蚂蚁移动半径相乘得到一个Vector3型的随机方向变量。通过此变量实现蚂蚁在寻路时随机转向的功能。使用导航网格类的SamplePosition()函数在导航网格上的指定范围内寻找最近的点。该函数对网格进行采样并寻找最近的点，采样范围从设置的第一个参数采样起点开始到蚂蚁运动半径距离内。寻路目的地为碰撞信息类的碰撞位置。同时，信息素释放并线性衰减。下面列出了寻路算法的关键代码：

if(timestamp

{

Vector3randomDirection=Random.insideUnitSphere*setup.moveRadius；

randomDirection+=transform.position；

NavMeshHitnavMeshHit；

NavMesh.SamplePosition(randomDirection，

outnavMeshHit，setup.moveRadius，1)；

Vector3finalPosition=navMeshHit.position；

navMeshAgent.destination=finalPosition；

timestamp+=Random.Range(1f，2f)；

}

trailRenderer.time=Mathf.Lerp(trailRenderer.time，0f，0.01f)；// 信息素强度线性衰减

蚂蚁在寻路过程中，如果找到信息素，就会执行followTrail()函数。该函数使蚂蚁沿着信息素轨迹找到食物。

蚂蚁跟随信息素路径找到食物后，会执行transportFood()函数，此函数设置了寻路的目的地为巢穴位置。蚂蚁会取走食物块并返回巢穴，且此时信息素渲染可见，返回的路径将以可视化的手段显示。

触发算法也是核心之一。本仿真中，可能会与蚂蚁发生触发事件的对象有三类：食物、巢穴、信息素。要触发碰撞，首先应给蚂蚁、食物、信息素和巢穴这4类对象添加碰撞体。

Unity引擎提供了碰撞体和触发器组件，碰撞体是物理组件的一类，它要与刚体一起添加到游戏对象上才能触发碰撞[6]。本仿真基于Unity自带的进入触发和持续触发函数，编写了触发算法。根据触发者的不同，蚂蚁执行不同的行为。图8为触发算法流程图：

图8 触发算法流程图

综上完成了蚁群行为的相关算法。

每只蚂蚁在寻路过程的同时释放信息素，信息素根据初始化场景时设置的信息素挥发时间进行线性衰减，直至消失。随着时间推移，最优路径上的信息素越来越多，会有更多的的蚂蚁跟随信息素轨迹聚集到最优路径上，这就是本仿真使用的信息素迭代机制。

3.3.3 其他仿真细节

在本仿真中，食物由食物块组成，当食物块被蚂蚁运输完毕，食物自动消失。因此，所有食物预置体都添加碰撞体组件。当触发者是蚂蚁时，如果食物剩余且蚂蚁状态为正在运输，则蚂蚁取走食物块，食物体积相应减少直至消失。食物新的体积使用幂函数进行求解。

自然界中，蚂蚁实时连续释放信息素。在本次仿真中，为了节省资源，设置计时器，实现每隔n帧释放信息素的功能，n的具体数值由设置的信息素速率参数决定。以帧为单位是由于Unity的Update函数执行单位是帧[6]。当信息素挥发完毕时，使用Destroy()方法销毁信息素。

仿真结果与分析

本仿真所用的计算机配置为英特尔酷睿i3处理器，4G内存，NvidiaGeForceGT620显卡，64位Windows7操作系统。使用的Unity版本为5.4.1f1(64bit)。

为了研究不同参数下本算法仿真的效率，使用Time类计时，所消耗的时间位于截图最下方。蚂蚁数量初值设为70。

图9至图11是场景一(单一目的地的最短路径寻找及避障场景)蚁群寻路的仿真过程截图，图12为场景二(多目的地的避障寻路场景)的仿真截图。

图9 仿真初期蚁群生成

图10 中期蚁群分布

图11 终期蚁群聚集到信息素浓的最短路径

图12 场景二(多目的地的避障寻路场景)

本次仿真基于场景一，比较了不同蚂蚁数量、信息素挥发时间参数下，蚁群找到最短路径所花的时间。

表1 不同蚂蚁数量的蚁群找到最短路径的时间

表2 不同信息素挥发时间下，蚁群找到最短路径的时间

表1至表2为不同蚂蚁数量、信息素挥发时间参数下，蚁群找到最短路径的时间。分析发现这些参数设置过大过小时都会导致算法效率下降。当蚂蚁数量过小时，算法全局搜索能力差，收敛时间长；而蚂蚁数量过大时，迭代次数增多，系统资源占用增多，也会导致效率下降。当信息素挥发完的时间过快时，信息素累积时间慢，收敛时间长；而信息素挥发完的时间过慢时，易造成局部收敛，降低算法结果精确性。

4 总结

本文基于Unity3D引擎，进行蚁群寻路觅食场景建模，通过C#语言编写了蚁群寻找最短路径等算法，最后对蚁群算法的各个参数设置进行了探究，探究发现蚂蚁数量、信息素挥发时间等参数过大过小时都会导致算法效率下降。仿真结果验证了使用Unity3D进行算法仿真的可行性，以可视化的方式直观易懂地呈现出蚁群算法的基本过程与原理，为算法的仿真提供了一种较好的方法。

本文以可视化的形式实现了蚁群算法的仿真过程，但仍存在可改进的方面。在本仿真中，蚁群算法是通过信息素的累积和更新收敛于最优路径上的。但是，在求解初期，蚂蚁释放的信息素匮乏，求解速度慢，而一旦信息素积累到一定程度，就能够快速收敛到最优解。针对蚁群算法在初期求解速度慢这一缺点，可考虑结合遗传算法进行组合优化。遗传算法在种群进化前期具有快速随机的全局搜索能力[7]，与蚁群算法结合可以弥补前期求解慢的缺点。

[1]何小虎. 基于改进蚁群算法的图像边缘检测[D]. 西北大学，2015.

[2]段海滨，王道波，于秀芬. 蚁群算法的研究现状及其展望[J].中国工程科学，2007，9(2)：98-102.

[3]丁明华，李允旺，王勇. 基于Unity3d的麦克纳姆轮移动平台避障算法仿真[J].中国科技论文，2016，11(10)：1191-1195.

[4]叶志伟，郑肇葆. 蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例[J]. 武汉大学学报(信息科学版)，2004，29(7)：597-601.

[5]段海滨，王道波. 一种快速全局优化的改进蚁群算法及仿真[J].信息与控制，2004，33(2)：241-244.

[6 ]陈泉宏. Unity API解析[M].北京：人民邮电出版社，2014.

[7]何娟，涂中英，牛玉刚. 一种遗传蚁群算法的机器人路径规划方法[J].计算机仿真，2010，27(3)：170-174.

(责任编辑：宋金宝)

Simulation of Ant Colony Algorithm Based on Unity 3D

CHENG Ting，PAN Yun，JIANG Rui-juan

(Computer Science School，Communication University of China，Beijing 100024，China)

Based on Unity3D engine，this simulation creates scenes and designs ant colony algorithm through the c# script，and the shortest path is visible.Finally，the parameters of ant colony algorithm are researched.The results verify the feasibility of using Unity3D for algorithm simulation，being straightforward to show the basic process and principle of ant colony algorithm，with the advantage of visualization and easy control.

ant colony algorithm；Unity3D；computer simulation

2016-12-24

程廷(1994-)，男(汉族)，浙江衢州人，中国传媒大学计算机学院研究生.E-mail：ct_cuc@163.com

TP

A

1673-4793(2017)03-0057-06