基于遺傳算法的內容編排模型設計*

劉 靜，沈奇威

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

1 引言

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

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

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

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

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

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

圖 2 業務模型數據的實體-聯系(ER)圖

2.1 業務模型建立

構建業務模型的基本描述及關系如圖2所示。

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

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

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

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

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

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

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

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

2.2 MOP數學模型建立

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

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

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

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

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

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

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

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

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

（1）模型變量的定義

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

（2）目標函數

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

圖3 時間軸與受眾資源規劃示意

該目標用數學式表達為：

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

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

（3）約束條件

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

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

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

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

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

3 模型的求解

3.1 求解難題

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

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

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

3.2 基于并行遺傳算法求解

3.2.1 算法設計

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

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

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

3.2.2 模型的求解過程

（1）染色體編碼

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

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

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

（2）初始種群選擇

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

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

（3）適應度函數

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

（4）選擇、交叉和變異

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

其中N是種群規模，fj是種群中第j個個體的適應度值。其實現過程為：在[0,1]區間內產生隨機數r，若能滿足條件，則選擇i個體，其中P0=0。

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

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

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

4 實例仿真

4.1 仿真結果

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

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

表1 受眾組別人數取值

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

表2 部分訂單編排輸入數據

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

表3 部分運算結果

仿真結果計算出基于模型目標和約束的較優解，驗證了構建的模型能很好解決內容編排問題。

4.2 性能分析

本文采用加權平均法[8]基于各個目標的重要程度設定各個目標的加權系數，將多目標轉化為單目標，并采用經典的動態規劃方法進行求解對比。

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

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

4.3 改進方案

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

5 結束語

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

1 劉晨，沈奇威.移動廣告系統中廣告排期的設計與實現.計算機系統應用,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 周昕，凌興宏.基于遺傳算法的集成生產計劃排程系統.科技信息,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 馬小姝，李宇龍.傳統多目標優化方法和多目標遺傳算法的比較綜述.電氣傳動自動化，2010(3):48～53

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

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