人工蜂群算法及其在土地资源优化中的应用研究

张泊平, 吴国玺

(1.许昌学院计算机科学与技术学院,河南许昌461000;2.许昌学院城市与环境学院,河南许昌461000)

0 引言

目前,解决系统优化问题的有效工具之一是群智能优化算法,但是算法收敛速度慢、容易陷入局部最优解[1-2]。2005年Karaboga提出了人工蜂群算法(Artificial Bee Colony Algorithm,ABC)[3],以解决相关问题。该算法的主要思想是对蜂群内部的蜜蜂进行明确分工,蜜蜂通过跳舞和嗅气味等方式向同伴传达蜜源地的信息、筑巢或者采集花粉等活动,这种行为使蜂群能够迅速找到优质的蜜源地。人工蜂群算法与其他算法相比,在求解多变量、多峰值的全局优化问题时具有更好的适应性和鲁棒性[4]。

学界在土地资源优化领域的研究中引入了很多新的方法[5],这些方法虽然在一定程度上解决了土地资源优化模型的非动态、单目标性,但是仍存在诸多等缺点。文中从模拟生物(蜜蜂)对环境的适应性和能动性出发,设计了应用于土地资源优化的人工蜂群算法,试图构建基于多目标的土地资源优化模型,解决ABC算法应用于土地资源优化的过早老化的问题和收敛速度慢等两个难题[3],并以许昌市为例,运用文中模型,进行了许昌市多目标土地利用优化应用研究,获得理想的效果。

1 人工蜂群算法

在人工蜂群算法中首先将蜜蜂分为侦察蜂、引领蜂和跟随蜂3类。3类蜜蜂能够根据各自的分工进行活动,并实现蜂群内部的信息共享和交流。侦查蜂的任务是在邻域附近随机搜索蜜源地,引领蜂则把已经搜索到的蜜源地的信息存储起来,以概率的方式分享给其他蜜蜂;跟随蜂在蜂巢附近等待引领蜂跳舞,并根据舞姿选择最满意的蜜蜂跟随。这里蜜源的位置代表土地优化问题的可能解,蜜源的含蜜量表现为优化问题的适应度值。蜂群通过不断地搜索,找到含蜜量更高的蜜源地,最终找到含蜜量最高的蜜源地,从而得到问题的最优解。文献[1]给出了人工蜂群算法的主要步骤。

2 土地资源优化ABC算法的构造

2.1 蜜蜂的采蜜行为和土地资源优化问题对应关系

蜜蜂的采蜜行为和土地资源优化问题对应关系如表1所示。

表1 蜜蜂的采蜜行为和土地资源优化问题对应关系

2.2 土地资源优化的ABC算法构造

2.2.1 初始种群

初始化时,首先随机产生优化配置方案,设方案个数为L(0),然后采用贪婪原则构造出优化配置方案的译码算子,并进行译码。将译码从高到低排名,其中前50%的方案作为候选土地资源优化方案。随机产生一个可行解,形成初始种群。

2.2.2 适应度评估方法

在土地资源优化问题的ABC算法中,通过比较适应度衡量土地资源优化方案的质量。适应度通过由目标函数变换而成的适应度函数(Fitness Function)求取。根据问题的目标函数,求解最短路径 d,则适应度函数为距离的倒数,Fitness=。路径越长适应度越低,蜜源地被授予的可能性越小,被跟随蜂选择的概率就越低。

2.2.3 邻域搜索策略的选择

首先随机生成含有n个解的初始种群V,V={vij},i=1,2,…,n;j=1,2,…,S;S为搜索空间的维数,vi={vij｜j=1,2,…,S}表示第i只蜜蜂所在的位置。然后计算蜂群中各侦查蜂的适应度函数值,记录当前蜂群中的最大花蜜量及其蜜源位置。引领蜂根据记忆的信息在其邻域附近进行搜索,产生新位置pi={pij｜j=1,2,…,S}:

其中k是i附近的一个值,且k≠i,φ是[-1,1]间的随机数。为了加大算法的收敛性,参考文献[6]更新蜜源地。

2.2.4 侦查蜂选择新的蜜源地

搜索算法经过多次循环迭代,丢弃没有靠近最优解的解,随机产生新的解。当被丢弃的解是当前最优解时,随机产生新解,计算新解的适应度并与原解的适应度比较,如果优于原解就替换,否则取原解并重新开始循环,这样做即能保证当前的最优解不被丢弃,又避免了因放弃当前最优解造成的算法不收敛的情况,同时也没有限制侦查蜂寻找新的蜜源地,达到了算法跳出局部最优解的目的,提高了算法的收敛速度。

2.2.5 算法的终止条件

算法采用最大循环代数作为结束条件,一般取50～500代,文中取100代。

2.2.6 算法步骤

(1)初始化土地利用网络。首先设置初始参数:种群数、最大循环次数、引领蜂引领强度系数r、遗忘因子τ、邻域因子η、蜂群数量Total,限制参数Lim等,其中采蜜蜂和观察蜂各占50%,侦察蜂1个;

(2)随机产生种群L(0);

(3)侦查蜂搜索蜜源地,计算群体的初始适应度,循环开始;

(4)侦查蜂分享蜜源地信息,按式(1)选择其中一个蜜源地,按文献[6]方法进行邻域搜索算法寻找新的蜜源地;

(5)计算新蜜源地的适应度值,依据贪婪原则选择更优的蜜源地;

(6)判断是否满足种群约束条件,如果满足约束条件则计算种群的整体适应度(个体适应度之和),否则重新分配不满足约束条件的蜜源地,并重新计算种群的整体适应度;判断整体适应度是否发生变化,如果变化就返回(4);否则结束算法,存储此最优解;

(7)循环次数加1;

(8)满足终止条件,达到最大循环次数。

3 实例仿真

为了验证算法的有效性,以许昌市土地资源优化为例,整理已有的土地利用数据,把研究区域的土地利用类型分为居住用地、商业用地、工业用地、可耕地等4种类型。仿真实验的系统环境为CUP双核3.20G,内存4GB,软件环境为Delphi 2010,选取了3个基准函数进行对比测试[7]。

3.1 实验参数的设置

实验中种群个数设置为50,引领蜂和跟随蜂的个数均为25,测试函数分别取30维、50维,相应的最大迭代次数分别为 1000和2000,α∈[0.8,1],β∈[1,1.2]之间,蜂群数量 50,其中采蜜蜂和观察蜂各占50%,侦察蜂1个,限制参数Limit为50,针对每个测试函数各算法均随机运行30次求其平均值。

3.2 测试函数的选择

在仿真实验中,选择了Sphere函数、Rosenbrock函数和Penalized函数这3个测试函数,其定义如下:

(1)Sphere函数

f1(x)=测试结果如图1所示。

(2)Rosenbrock函数

f2(x)=测试结果如图2所示。

(3)Rastrigin函数

f3(x)=测试结果如图3所示。

图1 Sphere测试函数

图2 Rosenbrock测试函数

图3 Rastingin测试函数

上述3个测试函数中,f1(x)是单峰连续函数,f2(x)是一个经典的复杂优化问题,取值范围内走势平坦,只能为算法提供少量的信息,要达到全局最优点的机会很小,f1(x)、f2(x)常用于检验算法收敛速度。函数 f3(x)是复杂非线性多峰函数,具有许多局部极值点,可有效检验算法的全局搜索的性能和避免早熟的能力。

3.3 实验结果分析

3.3.1 寻找最优解的迭代次数

图4是文献[5]的适应度函数,与图1、图2和图3比较可以看出,在相同迭代次数下,人工蜂群算法比文献[5] 算法表现更出色。

3.3.2 收敛率

收敛率是指优化算法找到全局最优解的概率。收敛率越高,优化算法越容易找到全局最优解,算法的优化性好。以50维的实验结果为例,在固定的进化情况下,文中算法的收敛速度快,收敛率高于文献[4]算法,其运行效率比文献[5]的提高了25%,总体适应度提高了8.9%,最大误差不超过1%,短中期优化精度吻合更好,可以为政府和城市规划工作者制定用地政策提供定量的辅助决策依据。

3.3.3 优化结果

图5(a)是许昌市2005年上述4类用地的空间分布格局,图5(b)是许昌市2010年优化后的空间分布格局。对比可以看出:优化后的居民用地整体上分布更加集中,土地利用斑块内部的空地减少,城市近郊的零星土地利用斑块也有所减少,同类土地利用的空间集聚度增高,新增城市用地的增长方式大多是内部填充式的,避免了城市用地的进一步扩张。

图4 文献[5]的适应度函数

图5 优化配置前后许昌市土地利用空间格局比较图

由分析结果可以看出,随着“工业许昌”的建设,可耕地总量下降是必然的。鉴于许昌的自然环境和经济能力,实现耕地使用平衡的难度很大,因此,优化模型得出的短中期优化值将更接近许昌市未来的真实情况,远期优化值则仅具参考意义。

4 结束语

把人工蜂群算法应用于土地资源优化,构建了基于ABC算法的土地利用优化配置模型;解决了ABC算法应用于目标优化的两个难题:收敛速度慢的问题和过早老化的问题;以许昌市土地资源优化为例,验证了本算法的应用。结果表明:优化模型得到的土地利用格局、算法的适应度和收敛速度的均有明显提高。

[1] 郑伟,刘静,曾建潮.人工蜂群算法及其在组合优化中的应用研究[J].太原科技大学学报,2010,31(6):467-471.

[2] 张国有,曾建潮.基于黄蜂群算法的群机器人全区域覆盖算法[J].模式识别与人工智能,2011,24(3):431-438.

[3] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[4] Ligmarm-Zielinska A,Church R,Jankowski E.Spatial optimization as a generative technique for sustainable multi objective land-use allocation[J].International Journal of Geographical Information Science,2008,22(6):601-622.

[5] 张鸿辉,曾永年,刘慧敏.多目标土地利用空间优化配置模型及其应用[J].中南大学学报,2011,42(4):1056-1067.

[6] 王辉.改进的蜂群算法[J].计算机工程与设计,2011,32,(11):3869-3873.

[7] 胡珂,李迅波,王振林.改进的人工蜂群算法性能[J].计算机应用,2011,31(4):1107-1111.