一种改进的鸟群优化算法

史旭栋，高岳林

(1.宁夏大学 数学统计学院， 银川 750021; 2.北方民族大学 信息与系统科学研究所， 银川 750021)

现实世界的优化问题包括连续、离散、线性、非线性、非光滑或非凸等不同类别的优化问题。连续可微的问题可以用传统的方法解决，如共轭梯度法；若遇到非常复杂的问题，如非凸或是不可微，则通过传统的方法可能无法有效地解决，尽管仍有方法可以解决那些复杂的问题，但在可容忍的计算量上有可能得不到最佳的结果。例如，在一个可容忍的时间内，传统的方法不能解决NP问题。

元启发式方法作为一种替代传统的方法，在可容忍的时间内，其优势是对于非凸又不可微的问题能找到可接受的解决方案。近年来，自然元启发式算法引起了研究者们极大的关注。

人类学习和设计新的元启发式算法的灵感来自于自然进化和生物系统的抽象。随着研究的深入，遗传算法(genetic algorithm,GA)[1]、差分进化算法(differential evolution,DE)[2]、文化算法(cultural algorithm,CA)[3]、模拟退火算法(simulated annealing algorithm,SAA)[4]等多种方法被提出。粒子群算法(particle swarm optimization,PSO)[5]、蚁群算法(ant colony optimization,ACO)[6]、人工鱼群算法(artificial fish swarm algorithm,AFSA)[7]、人工蜂群算法(artificial bee colony,ABC)[8]、 萤火虫群算法(glowworm swarm optimization,GSO)[9]、 布谷鸟群算法(cuckoo search,CS)[10]、蝙蝠群算法(bat algorithm,BA)[11]、 磷虾群算法(krill herd,KH)[12]、鸡群优化算法(chicken swarm optimization,CSO)[13]和鸟群优化算法(bird swarm algorithm,BSA)[14]等算法的灵感来自于社会动物的群体智能。灵感来自于植物的算法有杂草算法(invasive weed optimization,IWO)[15]、花授粉算法(flower pollination algorithm,FPA)[16]。而声搜索算法(harmony search,HS)[17]、 收费系统搜索算法(charged system search,CSS)[18]、头脑风暴算法(brain storm optimization,BSO)[19]等算法的提出则受物理原理和自然现象的启发。目前许多算法的开发是用来处理优化应用问题，尚不存在通用的算法。寻找更有效的算法的研究仍在继续。

1 基本的BSA算法

自然界中许多鸟类是群居的，例如雀。它们可能成群结队地居住、觅食、飞行。这些类似分离、队列、内聚等的行为被看作是自然发生且形成简单规则的行为。通过最简单的社会互动，群体行为可以发展成复杂的运动和相互作用。

鸟群的社会行为可以通过一些理想化的规则简化如下：

规则1 每只鸟可在警觉行为和觅食行为之间切换。无论是觅食还是保持警觉都被模拟为一个随机变量。

规则2 在觅食过程中，每只鸟都可以迅速地记录和更新其以往的最佳经验和最好的食物块。这方面的经验被用来寻找食物。社会信息在群体中是被共享的。

规则3 当保持警觉时，每只鸟都会尝试向鸟群的中心移动，这些行为可能会受到干扰从而引起群之间的竞争。警惕感更高的鸟比警惕感较低的鸟更可能靠近群体中心。

规则4 鸟群会定期飞到另一个栖息地。当飞到另一个栖息地时，它们的选择常常会于生产与乞讨切换，能力最高的鸟是生产者而能力最低的鸟是乞讨者。其他的鸟将在生产者与乞讨者之间随机选择成为其中之一。

规则5 生产者会随机寻找食物，而乞讨者会随机跟随生产者去寻找食物。

将这些规则公式化，通过精确的数学模型开发出新的元启发式算法。BSA的基本流程如图1所示。

1.1 觅食行为

每只鸟根据自己的经验和群体的经验寻找食物，规则2被公式化如下：

(1)

为简单起见，规则1被公式化为一个随机变量。如果一个范围(0,1)且服从均匀分布的随机数小于p,p∈(0,1),则鸟以这个恒定值觅食；否则，将继续保持警惕。

图1 BSA基本流程

1.2 警惕行为

规则3给出，鸟将尝试移动到鸟群中心，这就无法避免它们之间的相互竞争。每只鸟不会直接移动到鸟群中心，它们的运动行为可以表示如下：

(2)

(3)

(4)

其中：k(k≠i)是一个范围为1～N的随机正整数；a1、a2是 [0,2]范围的正常数；pFiti表示第i只鸟的最好适应度值；sumFit表示群体最好的适应度值和；ε用来避免0分错误，是计算机中最小的常数；meanj表示第j个元素在鸟群中的平均位置。

当一只鸟向鸟群中心移动时，它将无法避免与其他鸟之间的相互竞争。为了简单起见，鸟群的平均适应度值被认为受每只鸟移动向鸟群的中心时的间接影响。鉴于每只鸟都想移到鸟群中心的事实，A1的结果不应超过1。A2在这里用来模拟鸟移向群中心时受到的特定干扰，如果第k只鸟的最好适应度值优于第i只鸟的适应度值，则A2>a2，这意味着第i只鸟遭受的干扰比第k只鸟要大。即使它们的移动是随机性的、不可预测的，第k只鸟移向群中心的可能仍要比第i只鸟要大。在本文中，除非有特殊说明，越小的适应度值代表越好的适应度值。

1.3 飞行行为

鸟群为了躲避被捕食威胁会飞往另一个位置。当到达一个新的位置时，它们会重新寻找食物，一些鸟充当生产者角色去搜索食物块，而另一些鸟试图享用被生产者发现的食物补丁。根据规则4，生产者和乞讨者将会被群分离，生产者和乞讨者的行为被公式化如下：

(5)

(6)

其中：rand是服从均值为0、标准差为1的高斯分布的随机数，k∈[1,2,…,N]且k≠i；FL∈[0,2]表示乞讨者会跟生产者寻找食物。

为简单起见，假设每一只鸟会以FQ的单位间隔飞到另一个地方，FQ是一个正整数。

2 一种改进的鸟群优化算法

2.1 模糊推理

本文利用文献[20-21]中的经典模糊推理，其形式如下：

(7)

2.2 惯性粒子

(8)

其中：

(9)

2.3 模糊推理机制

在文献[20]中，利用3个参数nfi、αi和wi对算法进行自适应改变，其中nfi由以下公式得出：

(10)

利用表1～2对参数进行调整。

得出Δαi和Δwi的类型后，再通过隶属度函数得到对应的模糊推理规则，见图2、3。

表1 参数αi调整的模糊规则

表2 参数wi调整的模糊规则

图2 Δαi的模糊推理规则

图3 Δwi的模糊推理规则

2.4 鸟群更新公式的改进

群觅食相对于凭感觉觅食可能会得到更多的信息，具有更好的生存优势和良好的觅食效率。如果一只鸟找到一些食物块，其他的鸟可以共同享用。

(11)

(12)

(13)

在文献[20]中，利用3个参数nfi、αi和wi对算法进行自适应改变，其中nfi由以下公式得出：

(14)

鸟类在觅食和保持警觉之间会随机选择，当他们发现捕食者时会发出警报叫声，一组的所有鸟会一起起飞。因此很容易总结出，群飞的鸟比单飞的鸟更有利于检测到潜在的危险。在许多鸟类中，以增加群体的规模来降低个体警惕已非常普遍。换言之，随着组大小的增加，单只鸟可以花更多的时间去寻找食物，而受攻击的影响不会增加。

飞行中乞讨者的更新公式改变如下：

(15)

式(15)中：FL是自适应的影响因子，当迭代次数增多时FL线性递减。

(16)

式(16)中：FLmax和FLmin分别表示影响因子的最大值和最小值；tmax为最大迭代次数；ti为当前迭代次数。

从以上可以看出：FL随迭代次数的增加而减小，在算法前期生产者对乞讨者的影响大，有利于增强乞讨者的全局搜索能力；在算法后期，由于算法逐渐收敛，生产者对乞讨者的影响减小，有利于增强乞讨者的局部搜索能力。

2.5 混沌Gauss映射

为了使算法在迭代后期仍然具有较好的多样性，本文采用混沌扰动，设计算法1如下：

步骤1 随机生成一个初始点x0，设最大混沌迭代次数为m，令m=1；

步骤2 令粒子数n=1；

步骤3 令维数d=1；

步骤4 根据Tent映射[22]混沌方程计算混沌序列xd，即

(17)

步骤5 对第n个支配解的第d维进行混沌局部搜索

xid=xid+α·β·xd

(18)

步骤6 对超出边界的粒子进行处理；

步骤7d=d+1,如果d≤D,则转步骤4；

步骤8n=n+1,如果n≤N,则转步骤3；

步骤9 判断新生成的解是否为最优解；

步骤10m=m+1，如果m≤M，则转步骤2；否则，结束搜索。

3 验证和比较

为了研究BSA的有效性、实用性和稳定性，对表2中的6个测试函数进行优化。BSA的公式揭示了IBSA与著名的元启发式算法BSA、CSO、TLBO之间的自然关系，同时将它们进行对比。将案例研究统计结果用来分析BSA鸟群算法的优越性。本文以问题的最小化为例，改进的鸟群算法的基本步骤如下：

步骤1 初始化：设定种群中有N只鸟，在D维数空间中飞行，最大迭代次数为M。

步骤2 根据初始化条件随机产生第一代粒子，求得第一代的每个粒子的最优解(最强的鸟)和最差解(最弱的鸟)，则BSA的种群为：

步骤3 判断：如果rand(0,1)

步骤4 保持飞行，求出全局最优解和全局最差解坐标，全局最优解作为生产者以式(5)进行觅食，全局最差解作为乞讨者以式(15)跟随生产者享用被生产者找到的食物补丁；其他鸟将在生产者与乞讨者之间随机切换。

步骤5 利用算法1进行混沌扰动。

步骤6 评价产生新解的适应度值，更新最优解，伪代码如下：

fori=1:N

if fitness(x(i,:))

y(i,:)=x(i,:);

end

end

fori=1:N

if fitness(y(i,:))

pg=y(i,:);

end

end

步骤7 终止准则：如果达到终止条件，则输出最优解；否则返回步骤2。

测试函数见表3。所有算法迭代1 000次，独立运行100次。实验中使用同一台计算机(3.2 GHz四核处理器，2国标内存，视窗7操作系统，Visual Studio 2010)。表4给出了各算法的相关参数值。

根据表5给出的结果发现：IBSA明显优于BSA和CSO，对于测试函数f1、f2、f3、f4、f6，PSO可能限于局部最优解；对于f4和f5，BSA陷入局部解，在求解时BSA有可能过早收敛；在精度和稳定性方面，IBSA可以产生比CSO和BSA更准确和稳定的结果，在f1、f2、f3、f4测试函数中，IBSA具有较好的精度，但是对于f5、f6，TLBO算法与IBSA精度相当。

上述4种算法的精度和收敛性比较见图4～6。在求解f2、f3、f4、f5、f6时相对于CSO、TLBO、BSA，IBSA显著提高了收敛速度，减少了计算量，且未影响到结果的准确性。与TLBO相比，BSA在解决除f5、f6以外的其他问题时也提高了收敛速度，但在解决f5、f6的问题时收敛速度略差于TLBO。

根据表5和图4～6给出的结果进行比较，发现IBSA在优化精度、效率、稳定性和收敛性等性能上优于CSO、BSA。

表3 测试函数

表4 试验参数

表5 数值试验

注：以上数据是在维数100时由算法运行30次得出的平均值。

图4 四种算法对 f1、 f2的收敛曲线

图5 四种算法对 f3、 f4的收敛曲线

图6 四种算法对 f5、 f6的收敛曲线

4 结束语

模拟自然界的特征来解决优化问题是热门的研究，受鸟群启发而设计的鸟群算法是一种新的解决优化应用问题的方法。鸟群主要有3种行为，分别是觅食行为、警惕行为和飞行行为，通过这些行为鸟群能够在与其他个体进行社会交往时获得生存优势。

本文将模糊推理和惯性粒子引入鸟群算法，并改进了乞讨者的更新公式，使得算法的全局搜索能力和局部搜索能力增强。与CSO、TLBO、BSA进行性能比较，6个基准函数的试验比较结果表明IBSA比CSO、TLBO、BSA更加高效、稳定和准确。

参考文献：

[1] KUO H C,LIN C H.A directed Genetic Algorithm for global optimization[J].Applied Mathematics and Computation,2013,14:7348-7364.

[2] DAS S,SUGANTHAN P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15:4-31.

[3] JIN X D.Solving constrained optimization problems using cultural algorithm and regional schemata[D].Detroit,MI:Wayne State University,2001.

[4] SMITH J E.Coevolving Memetic Algorithms:A review and progress report[J].IEEE Transaction on System,2007,1:6-17.

[5] JORDEHI A R,JASNI J.Parameter selection in particle swarm optimisation:A survey[J].Journal of Experimental & Theoretical Artificial Intelligence,2013,4:527-542.

[6] DORIGO M,STUTZLE T.Ant colony optimization[M].Cambridge,MA:MIT Press,2004.

[7] GAO X Z,WU Y,ZENGER K,et al.A knowledge-based artificial fish-swarm algorithm[C]//Proceedings of the 13th IEEE international conference on computational science and engineering.Hong Kong:IEEE Computer Society,2010:327-332.

[8] KARABOGA D,BASTURK B A.Powerful and efficient algorithm for numerical function optimization:Artificial bee colony (ABC) algorithm[J].Journal of Global Optimization,2007,3:459- 471.

[9] KRISHNANAND K N,GHOSE D.Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009,3:87-124.

[10] YANG X S,DEB S.Cuckoo search:Recent advances and applications[J].Neural Computing & Applications,2014,24:169-174.

[11] YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge & Technology,2010:284,65-74.

[12] GANDOMI A H,ALAVI A H.Krill herd:A new bio-inspired optimization algorithm[J].Communications in Nonlinear Science Numerical Simulation,2012,17:4831- 4845.

[13] MENG X B,LIU Y,GAO X Z,et al.A new bio-inspired algorithm:chicken swarm optimization[C]//Proceedings of the 5th International Conference on Swarm Intelligence.Hefei:Springer International Publishing,2014:86-94．

[14] MENG X B,GAO X Z.A new bio-inspired optimisation algorithm:bird swarm optimization[J].Journal of Experomental & Theoretical Artificial Intelligence,2016(28):673-687.

[15] MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1:355-366.

[16] YANG X S,KARAMANOGLU M,HE X S.Flower pollination algorithm:A novel approach for multiobjective optimization[J].Engineering Optimization,2014,46:1222-1237.

[17] MANJARRES D,LANDA-TORRES I.A survey on applications of the harmony search algorithm[J].Engineering Applications of Artificial Intelligence,2013,26:1818-1831.

[18] KAVEH A,TALATAHARI S.A novel heuristic optimization method:Charged system search[J].Acta Mechanica,2010,213:267-289.

[19] SHI Y H.Brain storm optimization algorithm[C]//Proceedings of 2th International Conference on Swarm Intelligence.Chongqing:IEEE Computational Intelligence Society,2011:303-309.

[20] WANG W J,LIN H R.Fuzzy control design for the trajectory tracking on uncertain nonlinear systems[J].IEEE Trans.Fuzzy Syst,1999,7:53-62.

[21] TENG Y W,WANG W J.Constructing a user-friendly Ga-based fuzzy system directly from numerical data[J].IEEE Trans Syst.Man Cybern Part B:Cybern,2004,34:2061-2070.

[22] LIU Bo,WANG Ling,JIN Yihui,et al.Improved particle swarm optimization combined with chaos[J].Chaos,Solitons Fractals,2005,25(5):1261-1271.