基于改进蚁群算法的放牧路径优化研究

刘建国,谷晓燕,陈 亮,陈梦彤

(北京信息科技大学信息管理学院,北京 100192)

1 引 言

现阶段国内很多牧区在进行放牧时还是采用连续放牧[1]等“竭泽而渔”式的传统饲养方式[2],放牧路径也是按照以往经验进行粗略估计[3],从而导致放牧路径规划的潜在价值没有得到完善体现[4]。因此,设计具有科学指导性的放牧路径具有重要的研究意义。

目前,针对放牧行为的研究,Gu[5]等将分配模型和载畜量约束相结合,建立了动态轮牧分配模型,使得资源在时间和空间上得到有效利用;李凤霞[6]等通过遥感卫星对青海省海晏县的牧场牧草质量,建成轮牧动态监测预测管理模型及业务服务平台,为科学放牧建立了技术支撑;张智起[7]等人针对中国北方干旱半干旱草地过度放牧和连续放牧等问题强调了科学放牧的重要性。但是没有从牧场条件多变的视角考虑如何科学的规划放牧路径。

针对路径规划问题,常用的算法主要有遗传算法[8]、人工势场法[9]、粒子群算法[10]、神经网络算法[11]和蚁群算法等。蚁群算法具有强鲁棒性和良好的搜索能力,在二维图上搜索效果好,适合在栅格化牧场环境模型图上进行路径搜索。部分学者把蚁群算法用于规划机器人的路径。胡春阳[12]和孙功武[13]通过对蚁群算法进行平滑改进为水面无人艇进行路径规划。李开荣[14]通过添加转角约束的算法为移动机器人进行路径规划。以上学者在为机器人设计路径时,着重于在规避障碍物的同时约束机器人的转弯角度,而放牧领域则不同,牲畜在规避障碍物时拥有良好的机动性,因此考虑的因素会有区别,如转弯角度并不是最优先考虑的。蒋强[15]和HUANG[16]使用蚁群算法在通过大量蚂蚁个体寻找最优路径上有比较好的表现,但收敛速度慢,不适合在条件多变的放牧场景下进行动态的路径规划。

在进行放牧路径规划时,通过对牧场进行二维栅格化环境建模后,在生成的二维栅格化地图中生成较优的无碰撞路径,因此本文针对放牧路径规划场景下蚁群算法存在的一些不足进行适应性改进,使之更加适合牲畜的运动习惯。在基本的蚁群算法中,每次迭代更新信息素时,可能出现信息素浓度差别不大的情况,从而出现收敛速度慢和规划的线路并不是较优线路的缺点,因此本文将对蚁群算法控制信息素变化方面加以改进。

本文首先对牧区进行栅格化环境建模。然后,针对蚁群算法在放牧路径规划场景下存在的不足进行适应性改进。接着根据实验牧区的详细条件[17]和实验数据集来源,划分小牧区。最后通过仿真为牲畜规划放牧路径,并与改进前的算法和其它算法进行对比验证模型的可行性和合理性。

2 环境建模

在进行蚁群算法规划路径前,要使用栅格图法[18]对所选取牧场进行二维环境建模,查找选定区域内不会生长牧草的裸露地,坡度过陡的地形,牧场退化牧草生长期不匹配、牧场过度放牧等地区,为了牧场可持续发展以及提高牲畜采食的有效性,把不适宜放牧的区域抽象为障碍物并做好障碍物标记,之后对整个区域进行栅格化建模,通过二进制的格式对整个区域进行编码处理,有障碍物为1,无障碍物为0,设各栅格的边长为1,白色栅格为可自由放牧区域,而黑色栅格为障碍物区域,让建立的模型尽可能地贴近实际牧场地形条件。

接下来对图像分别进行腐蚀和膨胀处理[19],其中腐蚀处理是对图像里不会对路径规划产生影响的细小障碍物进行消除;而膨胀处理则是对不规则的较大障碍物添加像素,使得所在栅格得以扩充。腐蚀和膨胀处理并不为不可逆运算,因此可以结合使用。

图1 二维栅格环境建模示意图

3 基于改进蚁群算法的放牧路径规划方法

使用蚁群算法规划放牧路径时还需要考虑到诸多实际问题,例如起点和终点的选择,牲畜的行动特点等。另外,考虑多变的牧场条件,因此设计路径的算法要有能快速应对牧场条件变化的能力,通过优化放牧路径来减少牲畜在放牧过程中的额外能量损耗。

3.1 问题描述

在放牧场景下,因牧草条件、河流改道和恶劣天气等不可抗因素较多,放牧路径规划方式要具有柔性,传统蚁群算法在进行路径规划运算时因收敛速度慢导致时间成本较高,若直接用于放牧场景下存在未根据牧场情况及时做好应对措施的风险,从而不满足牧场的实际需求,所以本文将针对蚁群算法在放牧场景下的即时性做适应性改进,使之在寻得较优路径的情况下降低时间成本。

在传统的蚁群算法中,信息素浓度和启发式信息是影响整个蚂蚁族群寻找最优路径时重要的两个因素,节点i和目标节点j之间的欧几里得距离dij是传统蚁群算法中启发式信息的重要影响因素,但是传统蚁群算法忽视了障碍物对于算法的影响,这是算法出现局部最优的非常关键的原因,设置更多初始的蚂蚁数量和改进信息素的更新方法虽然增强了寻找最优路径的能力,但是会较大程度的影响整个算法的收敛速度,所以本文会对以上重要因素进行一定程度的改进,改进后算法的快速寻路能力将有较大提升。

3.2 蚁群算法参数设定

在放牧路径规划过程中,可以将牧场环境建模后的每一个牧区栅格抽象为蚁群算法蚂蚁寻路的每一个节点,而每次迭代每只蚂蚁个体所寻得的路线也可以抽象为放牧路径。

针对放牧路径规划,基于蚁群算法的寻路方法:

当蚂蚁从起点出发,蚂蚁选择的下一节点和移动方向是随机的,并使用轮转赌法对下一节点的走向进行选择,具体公式如下

(1)

(2)

(3)

式(1)中

τij为牧区i到牧区j的信息素浓度;

ηij为牧区i到牧区j的启发因子;

α为信息素激励因子;

β为启发式因子期望;

dij为牧区i到牧区j的欧几里得距离。

在一段时间过后,环境里的信息素浓度会根据每一轮蚂蚁选择完路径后的信息素而稀释,产生挥发现象,具体挥发公式如下

τij=(1-ρ)τij

(4)

式(4)中,ρ为信息素挥发系数

在环境中,更新信息素的公式为

τij(t+1)=τij(t)*(1-ρ)+Δτij,0<ρ<1

(5)

蚂蚁在环境中释放的信息素计算公式为

(6)

(7)

式(7)中,A1为设置的信息素强度系数。

3.3 改进信息素更新机制

因为传统蚁群算法是一种自组织、并行且正反馈的算法,每只蚂蚁作为一个个独立个体,在行动时不会受其它个体影响,每只蚂蚁都采用同一种原则进行单独行动,且如果初始信息素常量如果过大,会影响整个蚂蚁族群的搜索范围,范围变小会使得过早收敛,陷入局部最优;而过小的话,算法运行后环境内各条路径的信息素浓度差别也会过小,会使得算法出现混沌现象。同时,蚂蚁在寻找路径过程中碰到死路或者绕路的情况时,同样会释放信息素,这些信息素无疑是干扰性的,只有找寻到合理路径的蚂蚁释放的信息素才是对整个路径规划有帮助的。基于以上问题,本文提出改进的蚁群算法,目的是减少错误路径上的蚂蚁信息素的影响,提升收敛速度,解决局部最优的问题。

算法的改进方式为:在蚁群算法中,添加一种可以将处在较优放牧路径上的蚂蚁和处在较差放牧路径上的蚂蚁进行区分的机制,也就是在经过每一次迭代后,收集每只蚂蚁个体的行动路径及长度,将找寻到最近路径的蚂蚁的路径上的信息素增强,同时,将找寻到最远路径的蚂蚁的路径上的信息素减弱。之后,经过一次次的反复迭代,最优路径上的信息素浓度越来越高,逐渐和其它非最优路径的信息素浓度产生差别,从而加快了算法的收敛速度,提出一种随迭代时间改变的信息素浓度更新机制,因此,下面要对信息素更新机制的公式进行进一步的改进:

τij(t+1)=τij(t)*(1-ρ)

(8)

(9)

式(9)中,

x为每次迭代找寻到的最近放牧路径的蚂蚁个体只数;

A2为下一次迭代增强的信息素因子指数;

L*为每次迭代的最近距离。

(10)

式(10)中,y为每次迭代找寻到的最远放牧路径的蚂蚁个体只数;B为下一次迭代增强的信息素因子指数;L**为每次迭代的最远距离。

3.4 改进算法步骤

本文提出的改进蚁群算法的步骤如图2所示。

图2 改进算法流程图

下面针对相应步骤进行说明:

Step1:初始化算法的各项参数,设置蚂蚁只数、初始启发因子、初始信息素因子和放牧路径的起点和终点等参数。

Step2:使用栅格图法,利用0-1编码构建栅格化障碍物牧场地图模型。

Step3:蚂蚁开始搜索路径,使用轮转赌法计算蚂蚁选择下一牧场节点的概率。

Step4:统计每一只蚂蚁个体经过的放牧路径及长度,更新禁忌表,判断蚂蚁是否成功到达设定终点牧场节点,若到达,进入Step5;若未到达,返回Step3。

Step5:改进更新信息素的方法,使得信息素浓度差异化,继续迭代,判断是否到达最大迭代次数,若到达,进入Step6,若未到达,返回Step3。

Step6:判断是否到达目标位置,若到达,结束算法,输出仿真结果;若未到达,宣告算法失败,结束算法。

4 仿真分析

4.1 实验数据

本文选取了位于青藏高原面积约为400公顷的牧场,该牧场所在地区气候类型为高原大陆性气候,主要的草场植被类型为高寒草甸类和高寒草原类等[20,21],如图3所示。经过环境建模后,可用面积约为330公顷,如图4所示。实验中放牧牲畜数量为300羊单位。

图3 目标牧区地图

图4 二维栅格环境建模

4.2 参数设计

为了验证本文改进后的蚁群算法的可靠性和合理性,本文使用Matlab R2016a软件进行改进前后的算法仿真对比实验,本次实验采用的计算机配置为11th Gen Intel® Core(TM) i5-1135G7 @ 2.40GHz 四核CPU,内存为16GB LPDDR4,GPU为Intel® Iris® Xe Graphics,构建的仿真环境为20×20经过腐蚀和膨胀处理过的平面栅格模拟环境,为了保障实验结果的严谨性和准确性,分别进行了若干次独立重复实验。

为了贴合实验牧场的实际放牧情况和测试不同路径上算法的表现,本文为牲畜的放牧路径设计了6种不同的路径,各条路径的起始点和终止点的设置情况分别为:

1)起始点:地图左上角栅格;终止点:地图右上角栅格。

2)起始点:地图左上角栅格;终止点:地图右下角栅格。

3)起始点:地图左上角栅格;终止点:地图左下角栅格。

4)起始点:地图右上角栅格;终止点:地图右下角栅格。

5)起始点:地图右上角栅格;终止点:地图左下角栅格。

6)起始点:地图右下角栅格;终止点:地图左下角栅格。

参数设置:因为信息素因子α过大会使蚂蚁的随机搜索性减弱,信息素因子α过小会使算法搜索范围减小,容易过早收敛,使得蚂蚁族群陷入局部最优,所以本文设置α=1;启发函数因子β过大,虽然会使收敛速度加快,但是反而容易陷入局部最优,相反,启发函数因子β过小会使蚂蚁族群陷入纯粹的随机搜索,增加寻找最优解的难度,所以本文中的β=7;信息素挥发因子ρ过大,会使信息素挥发速度加快,容易错失最优路径,使得最优路径被较先排除,ρ过小,又会使各条路径上的信息素浓度差别过小,导致影响收敛速度,因此本文设置ρ=0.3;蚂蚁数量m统一设置为100;最大迭代次数K统一设置为100。遗传算法迭代次数也为100,交叉概率为0.8,变异概率为0.2,种群数量为200。

4.3 仿真结果与算法对比

在所构建的20×20的环境模型中,改进前后的传统蚁群算法六种不同路径的仿真结果如图5所示。

图5 蚁群算法六条放牧路径规划结果图

图6 遗传算法六条放牧路径规划结果图

如上图5、6、7所示:左上右下路径、右上左下路径和右下左下路径改进之后效果较明显,本文用蓝色将该路径标注出来,图7的上述三条路径在应对相对复杂的障碍物环境条件时,选择的路径较蚁群算法和遗传算法选择的路径更为平滑,收敛后的路径距离也较改进前更优,对于改进前中出现的路径陷入局部最优情况也有较大的改善,避免出现较为严重绕路情况。至于左上右上路径、左上右下路径和右上右下路径,改进后的区别较小,主要原因是这三条路径上没有较为复杂的障碍物,所以“蚂蚁族群”在搜索的过程中不容易出现盲目搜索的情况。

图7 本文算法六条放牧路径规划结果图注:改进前后路径区别明显的由蓝色标注

对比图8改进前后的路径收敛曲线,本文提出的改进后的算法相对于同路径改进前的蚁群算法和遗传算法,收敛速度和运行明显加快。根据表1中改进前后的最短路径对比结果,可以看出六条路径中有五条改进后的路径的最小距离相较于改进前更短,另外的一条与改进前持平。综上所述,改进后的算法在路径优化和收敛性上要优于传统蚁群算法。

表1 算法运行结果比较

图8 蚁群算法、遗传算法和本文算法前后六条放牧路径收敛曲线

5 结束语

本文针对现阶段放牧存在的实际可操作性较复杂的问题,通过与适应性改进蚁群算法相结合,在一定程度上有效的解决该牧场的过度放牧和草场闲置问题;通过设计多条路径来应对多变的牧场条件和测试改进算法在不同路径下表现,来检测改进算法应对不同条件的适应能力,本文针对传统蚁群算法容易陷入局部最优和在迭代过程中信息素浓度差别不明显等问题进行相应的改进,在每次迭代后增加最短路径上的信息素浓度并减少最长路径上的信息素浓度来优化算法的收敛速度和寻找最优路径的能力。

本文设计的轮牧和路径规划相结合的方法不仅适用于实验牧场,通过修改相关参数,可以根据不同地区的放牧习惯和牧草特点进行个性化的轮牧划分设计;同时,通过设计不同的起点和终点,规划的路径可以更好的应对当地牧场条件的变化,选择合适的线路进行放牧作业,实验证明本文提出的改进方法具有一定的理论参考意义和实际应用意义。