基于混沌动态步长布谷鸟算法的群体动画行为控制方法研究

来源:用户上传      作者:

　　摘  要： 自然界生物的迁徙具有一定规律，其会自动形成群体集合，队列排序具有一定的规律。群体动画行为是基于生物的迁徙规律得来的。首先对布谷鸟算法进行深入研究，而后以混沌动态步长布谷鸟算法为基础依据，进行相应的群体动画的仿真模拟。布谷鸟算法当中混沌序列的引入能够使鸟窝数据在更新过程中进行步长选择，防止局部最优的情况发生。实验结果表明，在群体动画行为的控制方法中，应用混沌动态步长布谷鸟算法要优于传统的布谷鸟算法。
　　关键词： 布谷鸟算法; 混沌动态步长; 群体动画行为; 改良算法; 控制方法; 仿真模拟
　　中图分类号： 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?S;1<γ≤3]
　　式中[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]次迭代得出对应数量的混沌变量。 　　2） 通过公式[Xid=Ld+1+xid·（Ud-Ld）2]，将公式[Xt+1i=Xti+α·Ls，γ]中的[n]个变量迭代到对应的解空间，从而对[n]个鸟窝确切的位置进行确定，记作：[N0=][Z01，Z02，…，Z0n]。
　　3） 对步骤2）中最优的初始位置进行计算，求得相应适应值：[Fr，  r=1，2，…，n]。
　　4） 保存上一代鸟窝位置的最优解，利用莱维飞行公式进行迭代更新，得到下一代鸟窝的最优位置更新，新的鸟窝最优位置记作[Pr]。
　　5） 对两代的迭代位置作比较，而后选择最优解，作为当前鸟窝的最优位置：[P=Zt1，Zt2，…，Ztn]。
　　6） 将鸟窝位置[P]与给定的[Pα]进行比较，最终选定的鸟窝要求概率最小，记作[P]，若有鸟窝位置不符合要求，通過自适应步长做出相应调整，从而得到符合要求的鸟窝，新鸟窝生成后继续参与比较，得到最优鸟窝的结果[Pnew=Zt1，Zt2，…，Ztn]。
　　7） 对算法满足迭代次数与否进行判断，若是，则[Pnew]为最优位置，算法结束;否则，返回到步骤4）继续执行。
　　算法的流程图如图5所示。
　　4  实验仿真
　　实验仿真使用Matlab 2016进行模拟演算，对比对象为传统的布谷鸟算法和基于混沌动态步长的布谷鸟算法。目的是验证基于混沌动态步长的布谷鸟算法与传统算法相比是否最优。对算法进行验证的过程中采用2个测试函数。验证过程中，迭代次数最大设置为500，种群个数定义为[k]（[k]=8），扰动因子定义为[β=0.05]。测试函数见表1。
　　测试函数的寻优结果如图6，图7所示。
　　从实验结果不难看出，在布谷鸟算法中引入混沌动态步长，能够获得更好的初始位置以及更优的收敛速度。群体动画行为具体表现为两个方面：一是个体自身的运动;二是群体相互之间的运动。基于混沌动态步长的布谷鸟算法针对原有的布谷鸟算法做出改进，帮助其在群体动画行为控制当中取得最优效果，在全局的随机选择过程中实现了更好的控制。
　　5  结  语
　　为实现群体动画行为的更好控制，对传统的布谷鸟算法做出改进和研究，提出基于混沌动态步长布谷鸟算法的群体动画行为控制方法。仿真过程中，通过选取合适的函数对基于混沌动态步长的布谷鸟算法进行测试，同时进行多次迭代，以进行最优位置的选取。实验结果表明，基于混沌动态步长的布谷鸟算法对群体动画行为控制最优，能够更好地进行群体动画中最优位置的选取，以促进其更为合理和逼真。
　　参考文献
　　[1] 郑延斌，刘晶晶，王宁.基于智能算法的群体动画设计与实现[J].中原工学院学报，2013，24（4）：26?30.
　　[2] 郑洪清.改进的布谷鸟搜索算法求解批量流水线调度问题[J].计算机系统与应用，2014，23（10）：159?160.
　　[3] 胡欣欣，尹兆龙.求解连续函数优化问题的合作协同进化布谷鸟搜索算法[J].模式识别与人工智能，2013，26（11）：1043?1047.
　　[4] TOULOUSE M， CRAINIC T G， SANSO B. Self organization in cooperative tabu search algorithms [J]. IEEE international conference on systems， 1998， 3： 2380?2381.
　　[5] CHOUDHARY K， PUROHIT G N. A new testing approach using Cuckoo search to achieve multi?ovjective genetic algorithm [J]. Journal of scientific computing， 2011， 3（4）： 117?119.
　　[6] 郑洪清，周永权.一种自适应步长布谷鸟搜索算法[J].计算机工程与应用，2012，30（8）：65?67.
　　[7] 陆化普，李瑞敏.城市智能交通系统的发展现状与趋势[J].工程研究，2014（1）：6?19.
　　[8] 赵娜，袁家斌，徐晗.智能交通系统综述[J].计算机科学，2014（11）：7?11.
　　[9] 李松，刘力军，解永乐.遗传算法优化BP神经网络的短时交通流混沌预测[J].控制与决策，2011，26（10）：1581?1585.
　　[10] WANG G G， GANDOMI A H， ZHAO X， et al. Hybridizing harmony search algorithm with Cuckoo search for global numerical optimization [J]. Soft computing， 2016， 20（1）： 273?285.
　　[11] 冯青平，李星毅.基于大数据的非参数回归短时交通流预测方法[J].无线通信技术，2015（3）：38?43.
　　[12] 丁恒，郑小熊，刘燕.基于小波分析的交通参数组合预测方法[J].系统仿真学报，2012，24（2）：377?381.
　　[13] 金玉婷.基于混沌和小波神经网络的短时交通流预测方法研究[D].成都：西南交通大学，2014.
　　[14] HUGHES T J R， REALI A， SANGALLI G. Efficient quadrature for NURBS?based isogeometric analysis [J]. Computer methods in applied mechanics and engineering， 2010， 199： 301?313.
　　[15] LAZZ?S J A， RIVERA M， L?PEZ?CARABALLO C H. Parameter estimation of Lorenz chaotic system using a hybrid swarm intelligence algorithm [J]. Physics letters A， 2016， 380（11/12）： 1164?1171.
　　[16] BARAZZETTI L， BANFI F， BRUMANA R， et al. Creation of parametric BIM objects from point clouds using nurbs [J]. Photogrammetric record， 2016， 30（152）： 339?362.
　　作者简介：李  月（1984—），女，湖北武汉人，博士，讲师，主要研究方向为动画。
　　王  敏（1986—），女，土家族，湖北恩施人，博士，副教授，主要研究方向为设计管理与品牌传播。
转载注明来源:https://www.xzbu.com/8/view-15122277.htm