基于混沌動態步長布谷鳥算法的群體動畫行為控制方法研究

李月 王敏

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

關鍵詞： 布谷鳥算法; 混沌動態步長; 群體動畫行為; 改良算法; 控制方法; 仿真模擬

中圖分類號： 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]次迭代得出對應數量的混沌變量。