基于遺傳算法的復(fù)雜繪制系統(tǒng)性能瓶頸識(shí)別

梁子

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

計(jì)算機(jī)圖形學(xué)在電子游戲、虛擬現(xiàn)實(shí)、視覺(jué)仿真等領(lǐng)域應(yīng)用廣泛，通過(guò)實(shí)時(shí)繪制系統(tǒng)的構(gòu)建，完成不同領(lǐng)域的繪制需求。近年來(lái)，隨著這些領(lǐng)域的不斷發(fā)展，不同應(yīng)用領(lǐng)域?qū)φ鎸?shí)感渲染提出了更高的要求，這使得實(shí)時(shí)繪制系統(tǒng)需要包含更為復(fù)雜的繪制算法以滿足上述需求，如全局光照、物理仿真等繪制算法。每種繪制算法將通過(guò)若干算法參數(shù)控制實(shí)時(shí)繪制系統(tǒng)的渲染效果，同時(shí)這些繪制參數(shù)也直接影響實(shí)時(shí)繪制系統(tǒng)的繪制效率。

本文在基于文獻(xiàn)[1]的基礎(chǔ)上，重點(diǎn)關(guān)注全局最優(yōu)劃分解決方案的確定。即：利用遺傳算法完成繪制特征空間的全局最優(yōu)劃分以及對(duì)應(yīng)空間下性能瓶頸的識(shí)別。文獻(xiàn)[1]提出從繪制系統(tǒng)提供的大量繪制性能數(shù)據(jù)中挖掘信息，以自動(dòng)識(shí)別繪制系統(tǒng)中的性能瓶頸。繪制性能數(shù)據(jù)是指：繪制系統(tǒng)中所有與繪制算法相關(guān)的算法參數(shù)其有效取值與對(duì)應(yīng)繪制時(shí)間構(gòu)成的數(shù)據(jù)集；性能瓶頸是指：參與挖掘分析的若干算法參數(shù)中，參數(shù)數(shù)值的微小變化導(dǎo)致系統(tǒng)繪制效率急劇下降的參數(shù)。在完成上述工作的同時(shí)，針對(duì)在整體數(shù)據(jù)空間下無(wú)法確定性能瓶頸的情況，進(jìn)一步提出基于子空間劃分思想的方法，完成子空間下性能瓶頸的自動(dòng)識(shí)別。

文獻(xiàn)[1]采用局部最優(yōu)的貪心算法完成子空間的劃分，即：以當(dāng)前所在數(shù)據(jù)空間為基準(zhǔn)，嘗試所有的劃分策略并選擇本次最優(yōu)的劃分方式。針對(duì)這種方式無(wú)法保證全局最優(yōu)的空間劃分，以及劃分結(jié)果不穩(wěn)定的缺點(diǎn)，本文提出基于遺傳算法的劃分方式以實(shí)現(xiàn)全局最優(yōu)劃分方式的確定，同時(shí)提高劃分結(jié)果的穩(wěn)定性。

1 算法實(shí)現(xiàn)

1.1 基本思想

空間劃分方式仍然建立在文獻(xiàn)[1]的基礎(chǔ)上，完成設(shè)定次數(shù)的隨機(jī)劃分方案，根據(jù)不同的劃分方案可以將數(shù)據(jù)空間進(jìn)行不同的劃分得到劃分結(jié)果，某個(gè)劃分結(jié)果稱(chēng)為“個(gè)體”，而將對(duì)應(yīng)的劃分方案進(jìn)行編碼得到該個(gè)體的“染色體”，染色體是唯一能夠確定個(gè)體的屬性，因此算法的操作都將關(guān)注于染色體，所有個(gè)體共同構(gòu)成遺傳算法的“種群”。本文的基本思想是：通過(guò)優(yōu)勝劣汰的方式保留更適應(yīng)生存的個(gè)體，同時(shí)，利用優(yōu)質(zhì)個(gè)體擁有的優(yōu)質(zhì)染色體，通過(guò)遺傳的方式完成更優(yōu)個(gè)體探索尋找，以此不斷迭代直到種群趨于收斂。本算法提出“適應(yīng)度函數(shù)”（具體參見(jiàn)1.3.3）以完成對(duì)個(gè)體（即：空間劃分樹(shù)）對(duì)環(huán)境的適應(yīng)度評(píng)估。

1.2 算法實(shí)現(xiàn)

不失一般性，我們?cè)诶L制系統(tǒng)R中采集得到當(dāng)前繪制場(chǎng)景的性能數(shù)據(jù)集s，我們將利用該性能數(shù)據(jù)集S完成對(duì)當(dāng)前繪制場(chǎng)景中性能瓶頸的識(shí)別工作，具體算法如下：

（1）根據(jù)完整性能數(shù)據(jù)集S建立評(píng)估模型F（本文采用隨機(jī)森林模型）；

（2）不失一般性，我們稱(chēng)S集合的任意子集為Sk，利用F可以計(jì)算當(dāng)前Sk數(shù)據(jù)空間中，參數(shù)集P中各個(gè)參數(shù)pi的變量重要性I(pi)；

（3）根據(jù)瓶頸判定機(jī)制（具體參見(jiàn)1.3.1）確定當(dāng)前數(shù)據(jù)空間Sk下是否存在性能瓶頸，如果存在，停止Sk的劃分，輸出識(shí)別到的瓶頸集合，即計(jì)算得到的瓶頸集合就是當(dāng)前數(shù)據(jù)空間Sk下識(shí)別到的瓶頸，否則，執(zhí)行步驟（4）；

（4）判斷Sk是否滿足繼續(xù)劃分的條件，如果滿足，執(zhí)行步驟（5），否則，停止Sk的劃分；

（5）針對(duì)當(dāng)前數(shù)據(jù)空間Sk進(jìn)行二分劃分（參見(jiàn)文獻(xiàn)[1]）：利用數(shù)據(jù)空間劃分機(jī)制（具體參見(jiàn)1.3.2）完成Sk的劃分，生成新的子空間，遍歷S分別執(zhí)行步驟（2）；

（6）遍歷步驟（2-5）劃分得到的數(shù)據(jù)空間二叉樹(shù)，進(jìn)行染色體的編碼工作（具體參見(jiàn)1.3.4），并完成對(duì)該二叉樹(shù)（劃分結(jié)果）的個(gè)體適應(yīng)度評(píng)估（具體參見(jiàn)1.3.3）；

（7）按照預(yù)設(shè)種群規(guī)模重復(fù)執(zhí)行步驟（2-6）得到N個(gè)個(gè)體共同構(gòu)成遺傳算法的初始種群G0；

（8）完成種群Gi的選擇、交叉、變異算子（具體參見(jiàn)1.3.5），生成新的種群Gi+1，不斷迭代該步驟直到Gi、Gi+1的種群適應(yīng)度（具體參見(jiàn)1.3.5）差距小于判定閾值，結(jié)束整個(gè)算法。

1.3 實(shí)現(xiàn)細(xì)節(jié)

（1）瓶頸判定機(jī)制

在數(shù)據(jù)空間Sk下，計(jì)算參數(shù)集P所有參數(shù)pi的變量重要性I(pi)，以其中的最大值為范圍上界將參數(shù)的變量重要性范圍進(jìn)行三分，分為上中下三部分區(qū)域，如圖1（a）（b）所示，如果變量重要性落在上部分區(qū)域的參數(shù)個(gè)數(shù)小于等于設(shè)定閾值（閾值為2），同時(shí)，其余參數(shù)的變量重要性均落在下部分區(qū)域，則我們稱(chēng)之為Sk數(shù)據(jù)空間下已經(jīng)識(shí)別到瓶頸。為了更清晰地描述問(wèn)題，參見(jiàn)圖1（c）中落在上部區(qū)域的參數(shù)個(gè)數(shù)過(guò)多，（d）中落在中部區(qū)域的參數(shù)個(gè)數(shù)過(guò)多，因此（c）、（d）均沒(méi)有識(shí)別到瓶頸。

圖1 瓶頸判定示意圖

（2）數(shù)據(jù)空間劃分機(jī)制

本文基于參數(shù)變量重要性的啟發(fā)式方法完成種群的初始化工作。具體來(lái)說(shuō)：I(pi)數(shù)值越高的參數(shù) pi應(yīng)該在數(shù)據(jù)劃分過(guò)程中擁有更高的影響力，換言之，為了使得一個(gè)參數(shù)擁有更高的影響力，它就應(yīng)該在被選擇成為空間劃分屬性時(shí)擁有更高的概率。

基于上述思想，我們使用如下策略完成針對(duì)某劃分空間二叉樹(shù)的一個(gè)非葉節(jié)點(diǎn)n（節(jié)點(diǎn)深度為d）其劃分屬性（參數(shù)）和劃分位置（參數(shù)數(shù)值）的確定：

①?zèng)Q定劃分參數(shù)

在某數(shù)據(jù)空間Sk下，計(jì)算參數(shù)集P所有參數(shù)pi的變量重要性I(pi)，之后，基于的輪盤(pán)賭策略將被采用以選擇劃分參數(shù)進(jìn)行節(jié)點(diǎn)n的劃分。從該策略中可以看出：擁有更高I(pi)的參數(shù)將更有機(jī)會(huì)被選為劃分參數(shù)，但隨著劃分層數(shù)的加深，這種影響力將逐漸減弱，各個(gè)參數(shù)被選中的概率趨于一致。

②計(jì)算劃分位置

一旦劃分參數(shù)確定后，具體的劃分位置應(yīng)該被確定成為該空間的劃分超平面（文獻(xiàn)[1]）?？紤]到當(dāng)數(shù)據(jù)空間的規(guī)模減小到一定程度時(shí)，通過(guò)隨機(jī)森林計(jì)算得到的變量重要性I(pi)將變得不穩(wěn)定，因此本文方法傾向于將數(shù)據(jù)空間進(jìn)行更為均衡的劃分，即：盡量不使兩個(gè)子空間中任何一個(gè)子空間的數(shù)據(jù)量過(guò)少。假設(shè)參數(shù)p的有效取值范圍是[pmin,pmax]，Ns個(gè)候選劃分位置由公式（1）生成，其中 i=1,2,...,N。s對(duì)于每個(gè)候選位置pican的劃分超平面，假設(shè)和是劃分后兩個(gè)子節(jié)點(diǎn)中數(shù)據(jù)的個(gè)數(shù)，候選位置的選取基于的正態(tài)分布原則。

（3）適應(yīng)度評(píng)估

適應(yīng)度函數(shù)在遺傳算法中起到至關(guān)重要的作用，它指導(dǎo)著種群的進(jìn)化方向，如公式（2）所示，適應(yīng)度函數(shù)F(·)描述數(shù)據(jù)空間S被劃分成n個(gè)子集S1,S2,...,Sn的好壞，即：某個(gè)空間劃分樹(shù)的適應(yīng)程度。

其中f(Sk)是某個(gè)子空間的適應(yīng)度函數(shù)，F(xiàn)(·)稱(chēng)為劃分適應(yīng)度函數(shù)。

本文遵循如下原則用來(lái)設(shè)計(jì) f(Sk)：

圖2

圖2即使（a）（b）中沒(méi)有識(shí)別到瓶頸，我們認(rèn)為情況（b）要優(yōu)于情況（a），因?yàn)椋╞）中紅色區(qū)域所標(biāo)注的最大落差大于（a）中最大落差。

圖3

圖3即使（a）（b）中均識(shí)別到瓶頸，我們認(rèn)為情況（b）要優(yōu)于情況（a），因?yàn)椋╞）中瓶頸個(gè)數(shù)小于（a）中瓶頸個(gè)數(shù)。

因此我們需要設(shè)計(jì)出滿足如下條件的函數(shù)：

①F(·)應(yīng)該是一個(gè)連續(xù)性的函數(shù)以保證可以用來(lái)比較任何兩種劃分結(jié)果的好壞；

②變量重要性I(pi)的值應(yīng)該影響 f(Sk)。具體包括兩個(gè)方面：（a）重要的參數(shù)（位于I(pi)上部分區(qū)域的參數(shù)）個(gè)數(shù)越少，f(Sk)值越高；（b）不重要參數(shù)（位于I(pi)下部分區(qū)域的參數(shù)）個(gè)數(shù)越多，f(Sk)值越高；

③劃分出的子空間總個(gè)數(shù)也應(yīng)該被考慮，以保證不會(huì)將原始數(shù)據(jù)空間S劃分成過(guò)多的子區(qū)域；

基于上述三方面的考慮，f(Sk)可以由公式（3）表示：

其中f1(Sk),f2(Sk),f3(Sk)是影響f的三個(gè)不同的因子，公式（4）具體闡述了其具體計(jì)算公式：

其中，Nsig是落在上部區(qū)域的參數(shù)個(gè)數(shù)，Nmid表示中部區(qū)域的，Ntri表示下部區(qū)域的；Isaigvg是落在上部區(qū)域的參數(shù)其變量重要性的平均值，Itarvig表示下部區(qū)域的；|*|表示數(shù)據(jù)空間中數(shù)據(jù)量；而w1，w1，w1是控制三個(gè)分量的比重因子，由用戶指定。

（4）染色體編碼

遺傳算法要求所有的個(gè)體擁有一個(gè)統(tǒng)一格式的染色體編碼方式使得遺傳算子能夠順利地操作于不同的個(gè)體上。但由于我們有數(shù)量龐大的不同劃分方式來(lái)實(shí)現(xiàn)原始數(shù)據(jù)空間的劃分，同時(shí)，不同劃分結(jié)果所包含的子空間個(gè)數(shù)也不盡相同，這使得對(duì)空間劃分結(jié)果進(jìn)行染色體編碼成為一件極富挑戰(zhàn)的工作。

受計(jì)算機(jī)圖形學(xué)領(lǐng)域廣泛應(yīng)用的分層數(shù)據(jù)結(jié)構(gòu)（如光線跟蹤技術(shù)中的KD-Tree[2]）的啟發(fā)，我們提出使用偽滿二叉樹(shù)表示任意維度的劃分過(guò)程以及劃分結(jié)果。其關(guān)鍵思想如下：

①采用二叉樹(shù)表示空間劃分的過(guò)程和結(jié)果；

②每個(gè)非葉節(jié)點(diǎn)n可以被認(rèn)為隱式地生成分裂超平面，將數(shù)據(jù)集劃分為兩部分。節(jié)點(diǎn)n與參數(shù)pi∈P關(guān)聯(lián)并且生成的超平面與 pi對(duì)應(yīng)的軸垂直。如圖4所示，節(jié)點(diǎn)n記錄一個(gè)信息對(duì)（pi,piv），其中 piv是參數(shù) pi軸上的一個(gè)有效取值；

③我們?cè)谠摱鏄?shù)中引入空節(jié)點(diǎn)進(jìn)而將其轉(zhuǎn)化為偽滿二叉樹(shù)。如果所有的偽滿二叉樹(shù)被要求擁有相同的深度，則所有的劃分結(jié)果均可以被表示為一個(gè)統(tǒng)一的形式；

圖4 二叉樹(shù)表示數(shù)據(jù)劃分過(guò)程，與光線跟蹤技術(shù)中的KD-Tree相似

圖5 編碼后的染色體

所有位于偽滿二叉樹(shù)中的節(jié)點(diǎn)通過(guò)上述方式可被儲(chǔ)存在一維數(shù)組中。根節(jié)點(diǎn)的索引下標(biāo)為0，節(jié)點(diǎn)索引下標(biāo)為i時(shí)，其左右孩子節(jié)點(diǎn)將分別被儲(chǔ)存在下標(biāo)為2i+1和2i+2，如圖5所示。最終該一維數(shù)組即為本文所述的染色體。

（5）遺傳算子

①選擇算子

該算子的目標(biāo)是從本代種群中選擇優(yōu)質(zhì)個(gè)體以生成新子代個(gè)體。我們采用輪盤(pán)賭策略來(lái)完成選擇任務(wù)。具有較高適應(yīng)性的候選個(gè)體具有更高被選擇的可能性用來(lái)培育新一代。

②交叉算子

為了產(chǎn)生新的子代個(gè)體，通過(guò)交叉算子，本代種群中的一對(duì)個(gè)體將作為父代進(jìn)行交叉以產(chǎn)生新的子代個(gè)體，為了加速收斂，我們通過(guò)公式（5）計(jì)算交叉發(fā)生的概率 Pc，同時(shí)，一個(gè)隨機(jī)數(shù) t∈[0,1]生成，當(dāng) t＞Pc時(shí)，交叉操作應(yīng)用于兩個(gè)選定的父代。

其中Fmax，F(xiàn)min分別是當(dāng)前一代的最大和最小適應(yīng)度，Icur和Imax分別是當(dāng)前一代和最大一代的數(shù)量，是當(dāng)前一代的適應(yīng)度方差，F(xiàn)more是來(lái)自兩個(gè)選定的父候選解決方案的較大適應(yīng)值，而Fless是另一個(gè)父親的適應(yīng)值。公式（5）表明交叉的可能性受以下三個(gè)因素的影響：第一個(gè)因素是Pc在進(jìn)化的早期階段會(huì)更大；第二，它與當(dāng)前一代的適應(yīng)度方差正相關(guān)；最后，Pc會(huì)隨著兩個(gè)父母之間的適應(yīng)度差異的增加而增加。所有這些策略都旨在提高GA（遺傳算法種群）的收斂速度。

③變異算子

變異算子的目的是避免GA收斂到某些局部最優(yōu)解。它有助于維持人口的遺傳多樣性。在我們的工作中，我們將隨機(jī)選擇一些候選解決方案，并在一些隨機(jī)位置改變它們的染色體。

2 實(shí)驗(yàn)結(jié)果

2.1 實(shí)驗(yàn)環(huán)境

PC配置：Intel Core i7-6900k3.2GHz CPU，32G 內(nèi)存，NVIDIA GeForce GTX-1080顯卡；

場(chǎng)景配置：54011個(gè)三角面片的DiningRoom模型，分布有300個(gè)動(dòng)態(tài)光源，25個(gè)透明物體。

參數(shù)空間說(shuō)明：繪制系統(tǒng)基于延遲渲染框架，執(zhí)行Light-Linked-List（LLL）算法[3]產(chǎn)生大規(guī)模動(dòng)態(tài)光源光照效果，執(zhí)行 Order-Independent-Transparency（OIT）算法[4]實(shí)現(xiàn)場(chǎng)景透明物體，執(zhí)行SSAO算法[5]基于屏幕空間優(yōu)化繪制效果。

本文算法中參數(shù)集P采用的參數(shù)列表：

表1

為了采集場(chǎng)景性能數(shù)據(jù)集，我們?cè)趫?chǎng)景中隨機(jī)漫游采集到150,000條數(shù)據(jù)構(gòu)成整個(gè)性能數(shù)據(jù)集。

2.2 實(shí)驗(yàn)結(jié)果

第一個(gè)實(shí)驗(yàn)用來(lái)驗(yàn)證使用本文提出的方法生成初始種群的有效性，種群規(guī)模為200個(gè)個(gè)體。圖6展示了隨著種群的不斷迭代，種群平均適應(yīng)度的變化情況，其中藍(lán)色折線表示采用我們提出的方法進(jìn)行初始種群的生成，橙色折線表示完全隨機(jī)的生成初始種群個(gè)體。圖中可以看出，利用本文的方法確實(shí)能夠提高初始準(zhǔn)群的質(zhì)量進(jìn)而進(jìn)一步加速迭代的收斂；同時(shí)也證明了本文遺傳算法策略對(duì)于提高種群的適應(yīng)度是有效的。

圖6

實(shí)驗(yàn)二中，我們比較了本文方法與BAT方法[1]的結(jié)果。圖7（a）（b）分別展示了本文方法和BAT方法對(duì)于同一個(gè)場(chǎng)景處理的結(jié)果，由圖可知，由于我們的方法可以在任一局部數(shù)據(jù)空間中確定單個(gè)的瓶頸，因此具有更好的處理結(jié)果。同時(shí)，再次考慮劃分結(jié)果的適應(yīng)度，本文方法所得到的最終結(jié)果其適應(yīng)度分?jǐn)?shù)為0.86262，要高于BAT方法得到的得分0.771819。

圖7

3 結(jié)語(yǔ)

本文提出一種復(fù)雜繪制系統(tǒng)算法級(jí)別的性能瓶頸識(shí)別方法，針對(duì)復(fù)雜性更高的繪制系統(tǒng)越有可能出現(xiàn)不存在全局瓶頸的情況，進(jìn)一步改進(jìn)了繪制數(shù)據(jù)空間劃分的算法，提出利用遺傳算法進(jìn)行全劇最優(yōu)的數(shù)據(jù)空間劃分算法，旨在合理劃分全局?jǐn)?shù)據(jù)空間到不同子空間，使得在各個(gè)子空間中識(shí)別到局部性能瓶頸。