李月 王敏
摘 要： 自然界生物的迁徙具有一定规律，其会自动形成群体集合，队列排序具有一定的规律。群体动画行为是基于生物的迁徙规律得来的。首先对布谷鸟算法进行深入研究，而后以混沌动态步长布谷鸟算法为基础依据，进行相应的群体动画的仿真模拟。布谷鸟算法当中混沌序列的引入能够使鸟窝数据在更新过程中进行步长选择，防止局部最优的情况发生。实验结果表明，在群体动画行为的控制方法中，应用混沌动态步长布谷鸟算法要优于传统的布谷鸟算法。
关键词： 布谷鸟算法; 混沌动态步长; 群体动画行为; 改良算法; 控制方法; 仿真模拟
中图分类号： TN911.1?34 文献标识码： A 文章编号： 1004?373X（2020）01?0035?05
Research on group animation behavior control method
based on chaotic dynamic step cuckoo algorithm
LI Yue1， WANG Min2
Abstract： The migration of animals in nature has a certain law， can autometically form groups， and their queues also has certain sequential laws. The behavior of group animation is got on the basis of the migration law of biology， so the cuckoo algorithm is studied in depth， and the analogue simulation corresponding to group animation is carried out based on the chaotic dynamic growth cuckoo algorithm. The introduction of chaotic sequence can make step size selected in the updating process of the bird nest data and the local optimization prevented. The experimental results show that the chaotic dynamic step cuckoo algorithm is better than the traditional cuckoo algorithm in the control of group animation behavior.
Keywords： cuckoo algorithm; chaotic dynamic step size; group animation behavior; improved algorithm; control method; analogue simulation
0 引 言
群体动画是指对大自然中生物进行群体性运动行为的仿真模拟，在诸多动画类型的影视作品当中，依据成熟的计算机技术和相关算法呈现出了场面宏大、效果震撼的群体动画画面[1]。近几年，群体动画作为新兴技术，是国际上很多学者所热衷的研究对象。同时群体动画在虚拟现实、模拟实训以及影娱作品当中得以普遍应用。基于此，学者与相关研究人员研究了多种算法为群体动画控制行为做技术支撑。
布谷鸟算法是其中的一种，同时还有遗传算法、粒子群算法等。相比之下，布谷鸟算法比遗传算法、粒子群算法更为简便，问题优化更好。但是布谷鸟算法由于局部搜索能力不高，导致其搜索的速度较为缓慢，随机的初始位置的选择也导致初始位置的选择难度增大。
为进一步提高算法性能，优化群体动画控制行为的算法支撑，对传统的布谷鸟算法做出改良，提出基于混沌动态步长布谷鸟算法。
1 群体动画简述
首先，对于群体的定义应当是同一时间下，运动在同一领域同时具有相互关联的多个个体[2]。在现实生活中，每一类群体都有其特定的组成体系，群体中的个体在其中具有相关角色，承当相关义务，享受相应权利，同时具有相关的独特而又互相联系的行为表征。大自然中的多数动物以群居的方式生殖繁衍，这一现象给相关研究人员很大的启发，并对此种现象做出了研究和开发。
群体动画以计算机技术作为基本的技术支撑，对现实场景进行模拟再现，同时通过各种情况的虚拟行为刺激，对真实世界可能发现的各种情况进行预判、规划和控制[3]。群体动画发展至今，广泛应用在军事虚拟演训、社会安全预估以及影视娱乐设计等方面，如图1～图3所示。
图1中的军事虚拟演训也是群体动画得以研究后的最初应用。群体动画能够更好地帮助军队在实际的军事演练中减少战损，控制人员伤亡，最大化的节省资源和提高部队协调能力与作战能力。随着时代发展，群体动画已经相对普及地应用到军事虚拟演训中。
同时，群体动画还被广泛应用到公共安全方面。如图2所示，在紧急情况下，办公地点、地铁站等公共场所的人员疏散都能够借助群体动画进行模拟，从而规划出最为合适的避险方式，减少紧急情况下带来的人员伤亡和财产损失。
图3是群体动画在影视娱乐设计方面的应用。在群体动画不够成熟之前，影视作品当中大型场面的拍摄为达到理想的拍摄效果，需要耗费大量的财力、物力、人力。同时，大规模的群众演员拍摄，十分容易造成事故，引起伤亡。群体动画的引入，既能够使整体的场面与真实场面基本相同，做到整体场面上的协调与流畅，个体表情与动作的真实与连贯，同时也能做到节省投资成本，提高拍摄的安全系数。
以上实例表明，在信息技术的不断发展过程当中，群体动画的发展越来越成熟，应用也更加广泛。
2 布谷鸟算法及相关简述
2.1 布谷鸟算法研究现状
Deb等人在2009年首先提出Cuckoo Search（CS），即布谷鸟算法的概念，其主要以布谷鸟的寻窝产卵行为以及莱维飞行为依据[5]。2010年，布谷鸟算法在工程优化问题中得以应用，相比工程优化问题之前所用到的粒子群算法效果要好很多。而后几年，研究者将布谷鸟算法与人工蜂群算法、粒子群优化算法以及微分进化算法做出比较。结果显示，布谷鸟算法在四种算法中结果最优。
布谷鸟算法从提出至今，受到了国内外很多专家学者的青睐。相比其他算法，布谷鸟算法主要具有以下优点：布谷鸟算法需要的参数相对较少，操作上方便简单，相对来说容易上手。如今在日常生活以及科研领域等多个方面，都能够见到布谷鸟算法的应用。当然，布谷鸟算法虽然经过十余年的发展和完善，但是仍然处在初级阶段，尚有许多不足之处。基于混沌动态步长的布谷鸟算法也是对布谷鸟算法的进一步改进和优化。
2.2 布谷鸟的生活习性
在自然界当中，多数鸟类对于幼鸟的哺育方式是进行筑巢哺育，但是也有例外。几乎36%的布谷鸟（杜鹃）哺育幼鸟的方式是寄生哺育，也即所谓的巢寄生。在鸟类繁殖当中，巢寄生是相对特殊的一种[6]。
将巢寄生作为繁殖哺育的鸟类并不是自己孵化和哺育幼鸟，而是产卵于其他鸟类的巢中，孵化和哺育都由其他鸟代之。在布谷鸟的寄生过程当中，会对宿主进行选择。布谷鸟对宿主选择的主要依据是其与布谷鸟自身是否具有相似习性，具体选择依据有：雏鸟是否具有相似的习性，卵的形状与颜色是否相似，孵化期是否大致相同等。
一般情况下，宿主选择好之后，布谷鸟会选择宿主产卵前离巢后的合适时机，迅速在其巢中进行产卵。每年的产卵数量大约在2～10个。同时，布谷鸟为提高幼鸟的生存可能，在任何宿主的鸟巢都只留一个蛋，而且会移走鸟巢中原有的一枚或者全部蛋，以得到更高保证。即便幼鸟得以孵化，布谷鸟也会把非本族类的鸟赶离鸟窝，保证自己的幼鸟哺育，而且研究表明，布谷鸟会对宿主鸟类的幼鸟声音进行模仿，以此获得义亲的哺育，提高自己族类的繁殖。
2.3 莱维飞行
莱维飞行由法国数学家保罗·皮埃尔·莱维引入。在大自然中多数动物进行觅食的方式是随机觅食，也就是说这是一个随机的过程。随机过程中，当前位置决定了下一步应当如何移动，而方向选取与其使用何种数学模型相关。
莱维分布要用到以下几个参数：位移[x]，尺度[γ]，特征指数[β]，方向参数[δ]。莱维分布可以看作其特征函数所对应的Fourier变换，公式如下：
[Pβ·δk;μ，γ=FPβ·δx;μ，γ=-∞∞eikxPβ·δx;μ，γdx=expiωk-γβkβ1-iδkkω（k，β）]
其中，[ωk，β=tanπβ2， β≠1，0<β<2-2πlnk， β=1]。
莱维飞行究其根本是一种关于实际步长的计算。当前对于莱维飞行的模拟大多采用Mantegna算法。用Matlab对随机行走以及莱维飞行进行仿真模拟，如图4所示。
不难发现，莱维飞行的搜索能力以及搜索范围都要优于随机行走。因此，在布谷鸟算法的改进过程中进行全局莱维飞行的应用。
2.4 布谷鸟算法
布谷鸟算法具体可以分为全局的随机搜索过程以及局部随机的搜索过程。局部随机的搜索过程可以表述如下：
[Xt+1i=Xti+α·Ls，γ]
[Ls，γ=γΓγsinπγ2π·1s1+γ，0 式中[S0]为初始的步长。 在基于混沌序列的自适应步长中，对鸟窝更新时所固有的随机步长做了进一步的调整。在原有的布谷鸟算法中，对步长因子给出如下定义： [dk=nk-nbestdmax] 式中：[nk]为第[k]代鸟窝所处的位置;[nbest]为在第[k]代时，鸟窝可以处在最佳状态时的位置;[dmax]为当下的其他鸟窝与此时能够处在最佳状态的鸟窝的位置之间的距离。对于原有布谷鸟算法中的步长因子的调整，提出了自适应步长调整方式： [stepsizek=stepmax-stepmindk+stepmin] 式中：[stepmin]表示步长最小值;[stepmax]表示步长最大值。 3 基于混沌动态步长的布谷鸟算法 基于混沌动态步长的布谷鸟算法，首先是在布谷鸟算法中引入各种混沌序列，然后对其做出比较。经过实验，混沌序列引入布谷鸟算法得到的结果较好的是Logistic混沌序列。Logistic迭代可以表示如下： [xt+1=μx（t）（1-x（t））] 式中：[t]表示迭代时间;[x（t）]在[0，1]的范围内;[μ]为可调控制变量。当[μ>3.54]时，系统震荡周期变长;当[μ]接近3.6时，系统震荡周期接近无限大，系统逐渐进入混沌;在[μ∈3.6，4]时，系统处于混沌状态;当[μ=4]，系统完全混沌。 在布谷鸟算法的应用中，通过混沌迭代得出布谷鸟的鸟巢初始位置，然后通过动态步长进行自适应优化的搜索。对布谷鸟（杜鹃）的鸟窝位置的发现概率定义为[Pα]，详细的步骤如下： 1） 对种群进行初始化。随机得出鸟窝的初始位置 [X1=（x11，x12，…，x1q）]，[X1]每个维度以上文给定的公式[xt+1=μx（t）（1-x（t））]进行计算，从而经过[n-1]次迭代得出对应数量的混沌变量。
