基于遺傳算法的內(nèi)容編排模型設計*

劉 靜，沈奇威

（1.北京郵電大學網(wǎng)絡與交換技術(shù)國家重點實驗室 北京 100876;2.東信北郵信息技術(shù)有限公司 北京 100191）

1 引言

內(nèi)容管理系統(tǒng)(content management system,CMS)是三網(wǎng)融合時代3G增值業(yè)務系統(tǒng)架構(gòu)的一部分，是內(nèi)容提供者（content provider,CP）、業(yè)務媒介和內(nèi)容消費者的中間管理平臺。其目的是完成內(nèi)容在業(yè)務媒介中整個生命周期和分發(fā)播控管理，提供內(nèi)容導入、編輯、個性化發(fā)布等全套功能，實現(xiàn)對內(nèi)容型增值業(yè)務及應用的支撐。CMS的角色運營模式如圖1所示。

移動廣告業(yè)務是以提供個性化廣告發(fā)布為核心的移動數(shù)據(jù)增值業(yè)務，它利用移動通信業(yè)務渠道為廣告業(yè)提供了一種媒介傳播途徑[1]。移動廣告業(yè)務連接廣告主、業(yè)務提供者和移動終端用戶，負責廣告的運營管理和分發(fā)[2]。若將廣告視為一種特殊的內(nèi)容，則移動廣告業(yè)務中的廣告主/代理商可映射為內(nèi)容管理系統(tǒng)中的CP。因此CMS天然可作為移動廣告業(yè)務的承載，提供業(yè)務內(nèi)容及廣告內(nèi)容的管理、內(nèi)容存儲、編輯及廣告編排、分發(fā)、運營等功能。

內(nèi)容編排是實現(xiàn)內(nèi)容與承載業(yè)務或應用媒介綁定的過程，是CMS通過售賣內(nèi)容(如手機閱讀)或售賣媒介資源(如移動廣告)增值的關(guān)鍵。在移動廣告系統(tǒng)中，廣告主提交廣告訂單的需求可表征為：為廣告選擇適當?shù)拿浇槲恢茫粵Q定要購買多長時間或精確時刻發(fā)布廣告；對于提供精準營銷的媒介，廣告主還可基于產(chǎn)品消費者特征定向選擇投放受眾。因此，業(yè)務平臺所運營的媒介可以劃分為空間（space）、時序資源（timeline）和受眾（subscribers）3 個維度的載體模型進行資源管理。

CMS的內(nèi)容編排既要滿足訂單中投放廣告排期要求，也要能滿足業(yè)務自身要求，將業(yè)務內(nèi)容合理排期，保證資源規(guī)劃利益最大化。當訂單編排輸入信息進入系統(tǒng)時，系統(tǒng)還需要進行資源沖突檢測和編排。若出現(xiàn)資源沖突，則新訂單不接受，編排結(jié)果應回退到上一次記錄。這是一個復雜的資源規(guī)劃難題，當前學術(shù)和工程領域?qū)Υ藛栴}進行的研究較少。因此，如何為CMS提供基于訂單的智能化的內(nèi)容編排服務成為當前需要解決的一個重要課題。本文基于移動廣告業(yè)務、戶外視頻廣告、手機閱讀等多項業(yè)務，并參考電視媒體節(jié)目編排、生產(chǎn)排程[3]的相關(guān)理論，對該問題進行建模及算法求解。

2 基于訂單編排輸入的編排模型

在內(nèi)容編排問題中，首要任務是滿足眾多訂單編排輸入在空間、時序資源(時間軸)、受眾三維資源分配不引起沖突；還要減少資源配給浪費、降低精確時間提前/延遲的懲罰等，這是個典型的多目標優(yōu)化問題(multi-objective optimization problem,MOP)[4]。下文就編排問題的業(yè)務模型、數(shù)學模型和求解進行論述。

圖 2 業(yè)務模型數(shù)據(jù)的實體-聯(lián)系(ER)圖

2.1 業(yè)務模型建立

構(gòu)建業(yè)務模型的基本描述及關(guān)系如圖2所示。

業(yè)務(service)：媒介渠道的基本信息，包括編號、名稱、描述、接收內(nèi)容的URL或FTP地址等。

載體(carrier)：業(yè)務或媒介渠道(如彩信手機報)能夠提供的內(nèi)容承載資源管理，稱之為“載體”。經(jīng)調(diào)研分析，所有載體均可表示為空間(space)、時序/時間軸(timeline)、受眾(subscribers)3個維度。例如，短信渠道，只需綁定一個空間維度資源，是最簡單的一種載體。彩信手機報中，若首頁指定某個特定模板，該綁定組合可作為一個載體對象；其他頁面，可自由選擇多個共享模板作為一個載體對象。另外，載體還包括內(nèi)容編排的基本要求，如在載體的時間軸區(qū)間內(nèi)，相同內(nèi)容允許投放的最大次數(shù),載體中單個內(nèi)容的最大、最小時序長度等。

空間 （space）：空間資源是業(yè)務管理員在某個業(yè)務下創(chuàng)建的所有模板及分屏布局，將平面拆分成多塊分屏式樣。例如，F(xiàn)lipboard應用使用豐富的模板式樣呈現(xiàn)內(nèi)容。

時序資源/時間軸(timeline)：時變的時序資源描述，主要針對分眾傳媒、數(shù)字電視等流媒體類型，或彩信的多幀序列(限定在一天時長內(nèi))。時間軸上具有同業(yè)務特性的時序區(qū)間定義成一個timeline對象。

受眾組別(subscribers)：與精準系統(tǒng)同步的業(yè)務的受眾類別分組，各組用戶是正交的、不交疊。在CMS及其支撐的應用中，受眾的組別或以一定的描述性命名區(qū)分，如樓宇廣告中，分為“商務寫字樓組”、“家庭住宅樓組”等；或是一定的用戶類別標簽如性別、年齡、職業(yè)、收入范圍等，基于各標簽的定義域值進行所有組合及用戶列表的綁定。

子載體(subcarrier)：子載體是載體中具體的空間資源與時序資源組合的資源塊。它一般是由業(yè)務管理員創(chuàng)建的一個獨立的內(nèi)容的承載資源塊，映射在移動廣告系統(tǒng)中即廣告位，如8:00～10:00視頻終端底部的滾動字幕框。

訂單（order）：訂單是CMS中的一個交易單元，它是由CP或業(yè)務管理員發(fā)起的，表示內(nèi)容與子載體以及交易價格的綁定關(guān)系（訂單編排輸入Input），同時需記錄交易的審批和運行狀態(tài)信息。

訂單與內(nèi)容編排模塊的關(guān)系及流程 （以CMS支持的移動廣告業(yè)務中，廣告主(CP)發(fā)起廣告訂單的流程為例）：廣告主創(chuàng)建訂單時，首先選定載體，并選擇廣告位(子載體)；按照子載體的時間段要求、支持的模板、分屏要求以及受眾組別的劃分，選擇該時序內(nèi)的投放次數(shù)、精準時刻的投放(可選項)、多個受眾組及各組選擇的用戶數(shù)(可選項)，完成提交訂單；訂單通過審批完成內(nèi)容編排方可生效。

2.2 MOP數(shù)學模型建立

為用數(shù)學語言描述和簡化模型求解，本文對內(nèi)容編排問題做了以下模型假設和符號表示。

· 載體是媒介編排模型的待規(guī)劃資源對象。在短/彩信、電子雜志或廣告等業(yè)務中，載體的空間資源具有第一維度的優(yōu)先級。因而可按具體位置拆分構(gòu)建多個編排模型，簡化為多組基于空間維度的時間軸和受眾資源的規(guī)劃問題。

· 時間軸資源在內(nèi)容編排中比受眾資源更重要、更有價值。因此，將時間軸作為第二維度，受眾資源作為以時間軸為基礎的第三維度資源。

· 訂單編排輸入(Input)是模型的輸入數(shù)據(jù)，按照進入模型的順序定義為Ii，i∈[1,N]，其中N為模型中Input的總數(shù)；交易價格為 Pi，Pi∈R+。

·傳媒業(yè)在制作廣告編排表時，非常注重廣告的同一時效全受眾的強烈宣傳效果。如某廣告主要在11:59同時在多家電視臺播放廣告。本模型支持該廣告編排的專業(yè)要求，即同一訂單內(nèi)容在同一時段內(nèi)向其選定的所有受眾發(fā)布。

· 模型支持精準的受眾組別投放內(nèi)容，即可選擇向多個受眾組別關(guān)聯(lián)的用戶列表進行編排投放。受眾組別的用戶數(shù)可表示為向量={sj|j∈[1,G]}，G 為受眾的組別總數(shù)，sj為 j組別的用戶數(shù)。一個Input Ii的受眾組別選擇表示為={sij|j∈[1,G]}，

·模型同時支持非精準的受眾數(shù)目選擇，即訂單編排輸入時，可指定內(nèi)容投放的受眾數(shù)目，定義為Totali,i∈[1,N]。若Ii精準選擇受眾，則Ii的受眾數(shù)目為：

· 載體的時間軸資源，可以是連續(xù)，也可以是離散型的。在實際的內(nèi)容填充和廣告售賣中，時序的交易單元往往是有時間粒度的，例如G3傳媒的廣告位要求內(nèi)容的播放時長為5 s的倍數(shù)。模型將時序以最小劃分粒度timeunit，將連續(xù)的時間段離散化。時間軸資源的規(guī)劃則完全基于離散化的序列進行。此外，載體的時間軸資源可以是一個時間段，如[0,50]；也可以是多個不相鄰的時序，如[0,50]∪[75,90]，本質(zhì)是將不相交的兩個時間軸作為載體資源的兩個獨立部分進行編排，最終將結(jié)果歸并。因此，為簡化算法和模型的描述，假定載體的時間軸資源只有一個，定義為[0,T]。如黃金時段11:45～12:15的時間長度，以5 s為時間粒度劃分單位，則時間軸離散序列共有360個值集合，即T=360，時段描述為[0,360]。

·模型支持精準時刻的內(nèi)容投放，Ii的內(nèi)容時序長度為li,li≤T；期望的開始播放精確時序點為di,di∈[1,T]且di∈Z。定義單位價格單位時間單元的訂單編排精確時間提前或延遲的懲罰因子為α,α∈[0,1]。

（1）模型變量的定義

χij(t)，其中t是時間軸資源上的一個時序點，表示內(nèi)容編排在t時刻點開始，t+li時刻點結(jié)束。

（2）目標函數(shù)

如果時序資源過早地被歷史訂單輸入占據(jù)，剩余完整面向全受眾的時序過少，在廣告系統(tǒng)中會影響該載體資源的售賣。于是，訂單編排輸入編排后，將受眾組別不沖突或者非精準受眾的訂單編排輸入編排到同一時段上，節(jié)約占用的時間軸資源是有價值的。如圖3所示，在Input2不要求精準化受眾組別，只要求受眾人數(shù)為Input2時，若Input1的時間段里剩余受眾人數(shù)不小于Input2，則應將Input2和Input1編排至同一時間段中，以節(jié)省空白的全受眾的時間軸資源。于是構(gòu)建目標，表征不同訂單編排輸入在相同時段上共存，分享不同受眾組的編排結(jié)果的出現(xiàn)頻率越大越好。

圖3 時間軸與受眾資源規(guī)劃示意

該目標用數(shù)學式表達為：

編排結(jié)果應盡量滿足訂單中受眾數(shù)目及分組選擇。當訂單中只指定受眾數(shù)目時，系統(tǒng)需要為其編排具體的受眾分組集。多數(shù)情況下，該受眾分組集的受眾總和與訂單受眾數(shù)目要求不能恰好相等，編排結(jié)果需盡量減少受眾數(shù)配給的偏差比例。這是因為若編排的受眾數(shù)少于訂單要求數(shù)，則基于實際投放結(jié)果的計費結(jié)算收益會有損失；若編排的受眾數(shù)超標，則多投放的受眾資源不屬于訂單的計費結(jié)算范疇，對系統(tǒng)不產(chǎn)生收益，這無疑是對受眾資源的浪費。該目標用數(shù)學式表達為：

當訂單編排輸入有精準時刻投放要求時，若編排結(jié)果未滿足該要求則會造成提前或延遲的懲罰金。因此應當使懲罰金額極小化，其數(shù)學式表達為：

（3）約束條件

任意兩個不同的訂單編排輸入Ii,Ik坌i≠k，i,k∈[1,N]，不能夠在相同的時間段占用相同的用戶組。否則將引起資源沖突，屬于不可行解范疇。該約束數(shù)學式表達為：

χij(r)=0,坌r∈[t,t+lk] if χkj(t)=1 （4）

訂單型需求的編排輸入中的確定性要求，由于是訂單價格的基礎，必須滿足或盡最大可能保證。

編排結(jié)果要滿足每個訂單編排輸入的受眾數(shù)目要求，數(shù)學式表達為：

針對有精準受眾組別要求的訂單編排輸入，編排結(jié)果要滿足受眾組別選擇要求，用數(shù)學式表達為：至此，構(gòu)建出多目標優(yōu)化問題的資源規(guī)劃模型。

3 模型的求解

3.1 求解難題

· 只可求Pareto解[5]：一般來說，多目標優(yōu)化[6]問題并不存在一個最優(yōu)解，所有可能的解都稱為非劣解，也稱為Pareto解。各個子目標可能是相互沖突的，為改善一個子目標將有可能引起另一個子目標性能的下降。因此，多個子目標同時達到最優(yōu)是不可能的，只能協(xié)調(diào)各個子目標折中考慮，最終求得較優(yōu)解。

· 組合爆炸：經(jīng)典的組合優(yōu)化問題[7]的求解，主要依靠約束條件來實現(xiàn)。只要約束條件充分，那么最優(yōu)的組合方案就能被唯一確定。但實際工作中，問題規(guī)模的增大，組合對象的數(shù)量增長極快，求解就變得十分復雜，這稱為“組合爆炸”[3]。經(jīng)典的規(guī)劃方法對于此類問題的求解，往往在理論上是可行的，卻不宜用于實際問題中。因此，如何從實際情況出發(fā)，采取適當?shù)拇胧?，抑制“組合爆炸”，采用合適的算法，

縮小搜索空間，成為編排求解中一個關(guān)鍵問題。

3.2 基于并行遺傳算法求解

3.2.1 算法設計

遺傳算法(genetic algorithm)，是一種通過對生物的遺傳和進化過程選擇、交叉和變異機理的模仿，來完成對問題最優(yōu)解的搜索算法[3]。遺傳算法具有并行搜索、群體尋優(yōu)、魯棒性強等特點，目前已廣泛用于解決非線性規(guī)劃問題。

目前常用的幾種多目標遺傳算法有：并行選擇法、非劣分層遺傳算法、基于目標加權(quán)法的遺傳算法、多目標粒子群算法等[6]。在本模型中，由于目標函數(shù)的值域不可歸一化處理，不適合采用目標加權(quán)法解決。因此，選擇處理步驟相對簡單的并行選擇法，又稱“向量估計多目標遺傳算法”。

基于并行選擇的遺傳算法實現(xiàn)該內(nèi)容編排模型求解的核心思想是：用染色體的基因編碼值表示編排結(jié)果；將初始種群按照目標的數(shù)目均分成若干個子種群；每個種群在各自分配的一個單目標函數(shù)以及約束條件下進行遺傳算法全空間的求解，并重點在性能高的局部搜索，不易陷入極小的局部求解空間，從而產(chǎn)生新的子種群；將所有新的子種群合并，進行選擇交叉變異；再循環(huán)此前處理到終止條件，即可求得問題的Pareto最優(yōu)解。其流程如圖4所示。

3.2.2 模型的求解過程

（1）染色體編碼

本文染色體采用二進制編碼策略，將問題的解空間即染色體映射到一個二進制位串空間{0，1}l[5]。位串的長度的選取原則是基于問題所要求解的精度和范圍，要求位串的值能夠覆蓋變量定義域均勻離散化的所有取值。

考慮到模型變量的定義，需聲明3種類型的基因原子：訂單內(nèi)容的起始時刻點、訂單內(nèi)容的結(jié)束時刻點、受眾組別。將3個基因原子的串接構(gòu)成一個表征編排結(jié)果的基因；再根據(jù)N個訂單編排輸入的編號次序順次連接N個基因，形成染色體。

假設本文需要解決的問題有3個訂單，5個受眾分組。那么，可定義染色體的位數(shù)為45，第1～5位代表1號訂單內(nèi)容的起始時刻點，第6～10位代表1號訂單內(nèi)容的結(jié)束時刻點，第11～15位代表1號訂單對5種受眾分組的選擇情況(可選擇多個分組)。第2～5號訂單基因按照第1號基因的結(jié)構(gòu)進行組織，并順次接續(xù)其后，共構(gòu)成45位的染色體。這樣，就將解空間和染色體的基因空間映射起來，只要將染色體按照組織結(jié)構(gòu)的逆過程進行解碼即可得解。

（2）初始種群選擇

初始種群具有多樣性，可采用隨機方法和選擇經(jīng)驗法獲得。考慮到某些訂單有確定性要求需要滿足，如受眾分組的選擇、精確時間投放等，因此，本文采用選擇經(jīng)驗法，生成滿足這些確定性要求的初始種群。于是，模型的約束條件(f)和目標函數(shù)(c)退化消失(基因出現(xiàn)變異操作時例外)，解空間在初始種群選擇中被收斂，生成的群體離最優(yōu)目標解空間距離會比隨機種群近，可以提高求解速度。

由于本文采用并行選擇的遺傳算法求解，因此將初始種群規(guī)模拆分成3個種群。

（3）適應度函數(shù)

個體的適應度是遺傳算法對個體進行優(yōu)勝劣汰的基礎。最常用的適應度評價方法，即“原始適應度函數(shù)”[7]，直接利用問題的目標函數(shù)作為適應度函數(shù)。模型中的3個約束條件構(gòu)造成懲罰函數(shù)，需要附著在3個目標函數(shù)上，作為 3 個種群的適應度函數(shù) F1、F2、F3。

（4）選擇、交叉和變異

選擇是優(yōu)勝劣汰的過程，適應度高的以較大的概率遺傳復制到下一代。選擇算子的選擇有多種，如精英個體保留策略、錦標賽選擇方法等。鑒于編排模型的復雜性，本文選擇“輪盤賭方法”。個體的選擇概率為：

其中N是種群規(guī)模，fj是種群中第j個個體的適應度值。其實現(xiàn)過程為：在[0,1]區(qū)間內(nèi)產(chǎn)生隨機數(shù)r，若能滿足條件，則選擇i個體，其中P0=0。

交叉是在兩個父代個體的部分基因相互替換產(chǎn)生新個體的過程。本文采用均勻交叉的方法：隨機產(chǎn)生染色體長度的二進制位串作為交叉模板，其中0表示不交換，1表示交換；根據(jù)模板進行交叉，得到新個體。交叉概率一般取值為0.4～0.99，本文采用的交叉概率為0.6。

變異是為了改變算法的局部搜索能力，維持種群多樣性，從而采取將個體的某些基因改變的方法，在二進制編碼的染色體上，變異就是將某些基因上的基因值取反的過程，即1變0，0變1。本文采用均勻變異的方法，并設定變異概率為0.05。

進化代數(shù)一般取100～1000次，由于采用并行選擇遺傳算法，每個種群均采用200次的進化代數(shù)。

4 實例仿真

4.1 仿真結(jié)果

在普通微型計算機環(huán)境下，利用Matlab軟件對前文所述的并行遺傳算法進行實現(xiàn)。假設當前移動廣告業(yè)務中，載體資源由1個空間位置、5個受眾分組 [1，5]，10個時間單元[1，10]構(gòu)成。由于媒介資源限制，需要在這些時間軸和受眾資源下規(guī)劃訂單。

其中，各受眾分組的人數(shù)設定如表1所示。

表1 受眾組別人數(shù)取值

訂單編排輸入數(shù)據(jù)的個數(shù)規(guī)模每次遞增5個，依次取值為{5，10，15，…，45，50}，輸入數(shù)據(jù)形如表 2 所示。假設懲罰金系數(shù)α=0.3，進行求解。

表2 部分訂單編排輸入數(shù)據(jù)

求解模型變量χij(t)，轉(zhuǎn)化為自然語言描述結(jié)果的部分如表3所示。

表3 部分運算結(jié)果

仿真結(jié)果計算出基于模型目標和約束的較優(yōu)解，驗證了構(gòu)建的模型能很好解決內(nèi)容編排問題。

4.2 性能分析

本文采用加權(quán)平均法[8]基于各個目標的重要程度設定各個目標的加權(quán)系數(shù)，將多目標轉(zhuǎn)化為單目標，并采用經(jīng)典的動態(tài)規(guī)劃方法進行求解對比。

仿真效率如圖5所示，動態(tài)規(guī)劃方法則隨問題規(guī)模增加，迭代次數(shù)和運行時間近似指數(shù)增長，即存在組合爆炸問題；而并行遺傳算法的時間性能較為穩(wěn)定，平均收斂時間比動態(tài)規(guī)劃方法短。尤其當訂單規(guī)模多于30個時，并行遺傳算法適于解決該問題。當訂單較少時，可用相對簡單的動態(tài)規(guī)劃方法。

因而，并行遺傳算法在訂單較多、編排要求復雜、非實時請求響應的工程中具有較高應用價值。

4.3 改進方案

當問題規(guī)模擴大、時間精度提高時，染色體的二進制碼串會快速增長，可采用實數(shù)編碼的遺傳算法[5]進行染色體和算法設計，可降低遺傳算法的搜索空間。采用增加算法的進化代數(shù)方法，增加解空間的個體數(shù)，提高找到Pareto最優(yōu)解的概率。

5 結(jié)束語

本文將內(nèi)容媒介編排的媒介資源，構(gòu)建成以載體為核心，描述模板分屏空間、時序資源、受眾分組等三維度的立體資源模型，并基于訂單需求約束和資源高利用率、精確投放時間目標構(gòu)建出多目標資源優(yōu)化數(shù)學模型——內(nèi)容編排模型。進一步描述了基于并行遺傳算法的模型求解算法，該算法有效驗證了該模型，并可指導應用于工程實踐。

1 劉晨，沈奇威.移動廣告系統(tǒng)中廣告排期的設計與實現(xiàn).計算機系統(tǒng)應用,2011(20)：218～221

2 Jun Ma,Jianxin Liao,Xiaomin Zhu,Chun Wang,Yuting Zhang.Mobile terminal capability management for services enabling.In:IEEE International Conference on Wireless and Mobile Communications 2006 (ICWMC2006),Session ICWMC18,ISBN 0-7695-2629-2,Bucharest,Romania,2006

3 周昕，凌興宏.基于遺傳算法的集成生產(chǎn)計劃排程系統(tǒng).科技信息,2010(9):452～453

4 Ramamoorthy C V，Chandy K M，Gonzalez Mario J.Optimal scheduling strategies in a multi-processor system.IEEE Trans Comput,1972,C-21(2):137～146.

5 馬永.基于遺傳算法求解排課問題的研究.福建電腦,2008(6):110～111

6 馬小姝，李宇龍.傳統(tǒng)多目標優(yōu)化方法和多目標遺傳算法的比較綜述.電氣傳動自動化，2010(3):48～53

7 雷德明，嚴新平.多目標智能優(yōu)化算法及其應用.北京：科學出版社，2009

8 高超.淺析加權(quán)平均法在多目標決策中的應用.電腦知識與技術(shù)，2010(6):4495～4496