李月 王敏

摘 ?要： 自然界生物的遷徙具有一定規(guī)律，其會自動形成群體集合，隊列排序具有一定的規(guī)律。群體動畫行為是基于生物的遷徙規(guī)律得來的。首先對布谷鳥算法進行深入研究，而后以混沌動態(tài)步長布谷鳥算法為基礎(chǔ)依據(jù)，進行相應(yīng)的群體動畫的仿真模擬。布谷鳥算法當(dāng)中混沌序列的引入能夠使鳥窩數(shù)據(jù)在更新過程中進行步長選擇，防止局部最優(yōu)的情況發(fā)生。實驗結(jié)果表明，在群體動畫行為的控制方法中，應(yīng)用混沌動態(tài)步長布谷鳥算法要優(yōu)于傳統(tǒng)的布谷鳥算法。

關(guān)鍵詞： 布谷鳥算法; 混沌動態(tài)步長; 群體動畫行為; 改良算法; 控制方法; 仿真模擬

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： 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 ?引 ?言

群體動畫是指對大自然中生物進行群體性運動行為的仿真模擬，在諸多動畫類型的影視作品當(dāng)中，依據(jù)成熟的計算機技術(shù)和相關(guān)算法呈現(xiàn)出了場面宏大、效果震撼的群體動畫畫面[1]。近幾年，群體動畫作為新興技術(shù)，是國際上很多學(xué)者所熱衷的研究對象。同時群體動畫在虛擬現(xiàn)實、模擬實訓(xùn)以及影娛作品當(dāng)中得以普遍應(yīng)用。基于此，學(xué)者與相關(guān)研究人員研究了多種算法為群體動畫控制行為做技術(shù)支撐。

布谷鳥算法是其中的一種，同時還有遺傳算法、粒子群算法等。相比之下，布谷鳥算法比遺傳算法、粒子群算法更為簡便，問題優(yōu)化更好。但是布谷鳥算法由于局部搜索能力不高，導(dǎo)致其搜索的速度較為緩慢，隨機的初始位置的選擇也導(dǎo)致初始位置的選擇難度增大。

為進一步提高算法性能，優(yōu)化群體動畫控制行為的算法支撐，對傳統(tǒng)的布谷鳥算法做出改良，提出基于混沌動態(tài)步長布谷鳥算法。

1 ?群體動畫簡述

首先，對于群體的定義應(yīng)當(dāng)是同一時間下，運動在同一領(lǐng)域同時具有相互關(guān)聯(lián)的多個個體[2]。在現(xiàn)實生活中，每一類群體都有其特定的組成體系，群體中的個體在其中具有相關(guān)角色，承當(dāng)相關(guān)義務(wù)，享受相應(yīng)權(quán)利，同時具有相關(guān)的獨特而又互相聯(lián)系的行為表征。大自然中的多數(shù)動物以群居的方式生殖繁衍，這一現(xiàn)象給相關(guān)研究人員很大的啟發(fā)，并對此種現(xiàn)象做出了研究和開發(fā)。

群體動畫以計算機技術(shù)作為基本的技術(shù)支撐，對現(xiàn)實場景進行模擬再現(xiàn)，同時通過各種情況的虛擬行為刺激，對真實世界可能發(fā)現(xiàn)的各種情況進行預(yù)判、規(guī)劃和控制[3]。群體動畫發(fā)展至今，廣泛應(yīng)用在軍事虛擬演訓(xùn)、社會安全預(yù)估以及影視娛樂設(shè)計等方面，如圖1～圖3所示。

圖1中的軍事虛擬演訓(xùn)也是群體動畫得以研究后的最初應(yīng)用。群體動畫能夠更好地幫助軍隊在實際的軍事演練中減少戰(zhàn)損，控制人員傷亡，最大化的節(jié)省資源和提高部隊協(xié)調(diào)能力與作戰(zhàn)能力。隨著時代發(fā)展，群體動畫已經(jīng)相對普及地應(yīng)用到軍事虛擬演訓(xùn)中。

同時，群體動畫還被廣泛應(yīng)用到公共安全方面。如圖2所示，在緊急情況下，辦公地點、地鐵站等公共場所的人員疏散都能夠借助群體動畫進行模擬，從而規(guī)劃出最為合適的避險方式，減少緊急情況下帶來的人員傷亡和財產(chǎn)損失。

圖3是群體動畫在影視娛樂設(shè)計方面的應(yīng)用。在群體動畫不夠成熟之前，影視作品當(dāng)中大型場面的拍攝為達到理想的拍攝效果，需要耗費大量的財力、物力、人力。同時，大規(guī)模的群眾演員拍攝，十分容易造成事故，引起傷亡。群體動畫的引入，既能夠使整體的場面與真實場面基本相同，做到整體場面上的協(xié)調(diào)與流暢，個體表情與動作的真實與連貫，同時也能做到節(jié)省投資成本，提高拍攝的安全系數(shù)。

以上實例表明，在信息技術(shù)的不斷發(fā)展過程當(dāng)中，群體動畫的發(fā)展越來越成熟，應(yīng)用也更加廣泛。

2 ?布谷鳥算法及相關(guān)簡述

2.1 ?布谷鳥算法研究現(xiàn)狀

Deb等人在2009年首先提出Cuckoo Search（CS），即布谷鳥算法的概念，其主要以布谷鳥的尋窩產(chǎn)卵行為以及萊維飛行為依據(jù)[5]。2010年，布谷鳥算法在工程優(yōu)化問題中得以應(yīng)用，相比工程優(yōu)化問題之前所用到的粒子群算法效果要好很多。而后幾年，研究者將布谷鳥算法與人工蜂群算法、粒子群優(yōu)化算法以及微分進化算法做出比較。結(jié)果顯示，布谷鳥算法在四種算法中結(jié)果最優(yōu)。

布谷鳥算法從提出至今，受到了國內(nèi)外很多專家學(xué)者的青睞。相比其他算法，布谷鳥算法主要具有以下優(yōu)點：布谷鳥算法需要的參數(shù)相對較少，操作上方便簡單，相對來說容易上手。如今在日常生活以及科研領(lǐng)域等多個方面，都能夠見到布谷鳥算法的應(yīng)用。當(dāng)然，布谷鳥算法雖然經(jīng)過十余年的發(fā)展和完善，但是仍然處在初級階段，尚有許多不足之處?；诨煦鐒討B(tài)步長的布谷鳥算法也是對布谷鳥算法的進一步改進和優(yōu)化。

2.2 ?布谷鳥的生活習(xí)性

在自然界當(dāng)中，多數(shù)鳥類對于幼鳥的哺育方式是進行筑巢哺育，但是也有例外。幾乎36%的布谷鳥（杜鵑）哺育幼鳥的方式是寄生哺育，也即所謂的巢寄生。在鳥類繁殖當(dāng)中，巢寄生是相對特殊的一種[6]。

將巢寄生作為繁殖哺育的鳥類并不是自己孵化和哺育幼鳥，而是產(chǎn)卵于其他鳥類的巢中，孵化和哺育都由其他鳥代之。在布谷鳥的寄生過程當(dāng)中，會對宿主進行選擇。布谷鳥對宿主選擇的主要依據(jù)是其與布谷鳥自身是否具有相似習(xí)性，具體選擇依據(jù)有：雛鳥是否具有相似的習(xí)性，卵的形狀與顏色是否相似，孵化期是否大致相同等。

一般情況下，宿主選擇好之后，布谷鳥會選擇宿主產(chǎn)卵前離巢后的合適時機，迅速在其巢中進行產(chǎn)卵。每年的產(chǎn)卵數(shù)量大約在2～10個。同時，布谷鳥為提高幼鳥的生存可能，在任何宿主的鳥巢都只留一個蛋，而且會移走鳥巢中原有的一枚或者全部蛋，以得到更高保證。即便幼鳥得以孵化，布谷鳥也會把非本族類的鳥趕離鳥窩，保證自己的幼鳥哺育，而且研究表明，布谷鳥會對宿主鳥類的幼鳥聲音進行模仿，以此獲得義親的哺育，提高自己族類的繁殖。

2.3 ?萊維飛行

萊維飛行由法國數(shù)學(xué)家保羅·皮埃爾·萊維引入。在大自然中多數(shù)動物進行覓食的方式是隨機覓食，也就是說這是一個隨機的過程。隨機過程中，當(dāng)前位置決定了下一步應(yīng)當(dāng)如何移動，而方向選取與其使用何種數(shù)學(xué)模型相關(guān)。

萊維分布要用到以下幾個參數(shù)：位移[x]，尺度[γ]，特征指數(shù)[β]，方向參數(shù)[δ]。萊維分布可以看作其特征函數(shù)所對應(yīng)的Fourier變換，公式如下：

[Pβ·δk;μ，γ=FPβ·δx;μ，γ=-∞∞eikxPβ·δx;μ，γdx=expiωk-γβkβ1-iδkkω（k，β）]

其中，[ωk，β=tanπβ2， ? β≠1，0<β<2-2πl(wèi)nk， ? β=1]。

萊維飛行究其根本是一種關(guān)于實際步長的計算。當(dāng)前對于萊維飛行的模擬大多采用Mantegna算法。用Matlab對隨機行走以及萊維飛行進行仿真模擬，如圖4所示。

不難發(fā)現(xiàn)，萊維飛行的搜索能力以及搜索范圍都要優(yōu)于隨機行走。因此，在布谷鳥算法的改進過程中進行全局萊維飛行的應(yīng)用。

2.4 ?布谷鳥算法

布谷鳥算法具體可以分為全局的隨機搜索過程以及局部隨機的搜索過程。局部隨機的搜索過程可以表述如下：

[Xt+1i=Xti+α·Ls，γ]

[Ls，γ=γΓγsinπγ2π·1s1+γ，0

式中[S0]為初始的步長。

在基于混沌序列的自適應(yīng)步長中，對鳥窩更新時所固有的隨機步長做了進一步的調(diào)整。在原有的布谷鳥算法中，對步長因子給出如下定義：

[dk=nk-nbestdmax]

式中：[nk]為第[k]代鳥窩所處的位置;[nbest]為在第[k]代時，鳥窩可以處在最佳狀態(tài)時的位置;[dmax]為當(dāng)下的其他鳥窩與此時能夠處在最佳狀態(tài)的鳥窩的位置之間的距離。對于原有布谷鳥算法中的步長因子的調(diào)整，提出了自適應(yīng)步長調(diào)整方式：

[stepsizek=stepmax-stepmindk+stepmin]

式中：[stepmin]表示步長最小值;[stepmax]表示步長最大值。

3 ?基于混沌動態(tài)步長的布谷鳥算法

基于混沌動態(tài)步長的布谷鳥算法，首先是在布谷鳥算法中引入各種混沌序列，然后對其做出比較。經(jīng)過實驗，混沌序列引入布谷鳥算法得到的結(jié)果較好的是Logistic混沌序列。Logistic迭代可以表示如下：

[xt+1=μx（t）（1-x（t））]

式中：[t]表示迭代時間;[x（t）]在[0，1]的范圍內(nèi);[μ]為可調(diào)控制變量。當(dāng)[μ>3.54]時，系統(tǒng)震蕩周期變長;當(dāng)[μ]接近3.6時，系統(tǒng)震蕩周期接近無限大，系統(tǒng)逐漸進入混沌;在[μ∈3.6，4]時，系統(tǒng)處于混沌狀態(tài);當(dāng)[μ=4]，系統(tǒng)完全混沌。

在布谷鳥算法的應(yīng)用中，通過混沌迭代得出布谷鳥的鳥巢初始位置，然后通過動態(tài)步長進行自適應(yīng)優(yōu)化的搜索。對布谷鳥（杜鵑）的鳥窩位置的發(fā)現(xiàn)概率定義為[Pα]，詳細的步驟如下：

1） 對種群進行初始化。隨機得出鳥窩的初始位置

[X1=（x11，x12，…，x1q）]，[X1]每個維度以上文給定的公式[xt+1=μx（t）（1-x（t））]進行計算，從而經(jīng)過[n-1]次迭代得出對應(yīng)數(shù)量的混沌變量。