李月 王敏

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

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

中圖分類號(hào)： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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)畫是指對(duì)大自然中生物進(jìn)行群體性運(yùn)動(dòng)行為的仿真模擬，在諸多動(dòng)畫類型的影視作品當(dāng)中，依據(jù)成熟的計(jì)算機(jī)技術(shù)和相關(guān)算法呈現(xiàn)出了場(chǎng)面宏大、效果震撼的群體動(dòng)畫畫面[1]。近幾年，群體動(dòng)畫作為新興技術(shù)，是國(guó)際上很多學(xué)者所熱衷的研究對(duì)象。同時(shí)群體動(dòng)畫在虛擬現(xiàn)實(shí)、模擬實(shí)訓(xùn)以及影娛作品當(dāng)中得以普遍應(yīng)用?；诖?，學(xué)者與相關(guān)研究人員研究了多種算法為群體動(dòng)畫控制行為做技術(shù)支撐。

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

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

1 ?群體動(dòng)畫簡(jiǎn)述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 ?萊維飛行

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

萊維分布要用到以下幾個(gè)參數(shù)：位移[x]，尺度[γ]，特征指數(shù)[β]，方向參數(shù)[δ]。萊維分布可以看作其特征函數(shù)所對(duì)應(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)于實(shí)際步長(zhǎng)的計(jì)算。當(dāng)前對(duì)于萊維飛行的模擬大多采用Mantegna算法。用Matlab對(duì)隨機(jī)行走以及萊維飛行進(jìn)行仿真模擬，如圖4所示。

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

2.4 ?布谷鳥算法

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

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

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

式中[S0]為初始的步長(zhǎng)。

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

[dk=nk-nbestdmax]

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

[stepsizek=stepmax-stepmindk+stepmin]

式中：[stepmin]表示步長(zhǎng)最小值;[stepmax]表示步長(zhǎng)最大值。

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

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

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

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

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

1） 對(duì)種群進(jìn)行初始化。隨機(jī)得出鳥窩的初始位置

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