劉 靜，沈奇威

（1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100876;2.東信北郵信息技術(shù)有限公司 北京 100191）

1 引言

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

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

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

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

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

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

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

2.1 業(yè)務(wù)模型建立

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

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

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

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

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

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

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

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

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

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

為用數(shù)學(xué)語(yǔ)言描述和簡(jiǎn)化模型求解，本文對(duì)內(nèi)容編排問(wèn)題做了以下模型假設(shè)和符號(hào)表示。

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

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

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

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

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

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

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

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

（1）模型變量的定義

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

（2）目標(biāo)函數(shù)

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

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

該目標(biāo)用數(shù)學(xué)式表達(dá)為：

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

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

（3）約束條件

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

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

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

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

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

3 模型的求解

3.1 求解難題

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

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

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

3.2 基于并行遺傳算法求解

3.2.1 算法設(shè)計(jì)

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

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

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

3.2.2 模型的求解過(guò)程

（1）染色體編碼

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

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

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

（2）初始種群選擇

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

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

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

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

（4）選擇、交叉和變異

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

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

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

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

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

4 實(shí)例仿真

4.1 仿真結(jié)果

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

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

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

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

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

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

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

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

4.2 性能分析

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

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

因而，并行遺傳算法在訂單較多、編排要求復(fù)雜、非實(shí)時(shí)請(qǐng)求響應(yīng)的工程中具有較高應(yīng)用價(jià)值。

4.3 改進(jìn)方案

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

5 結(jié)束語(yǔ)

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

1 劉晨，沈奇威.移動(dòng)廣告系統(tǒng)中廣告排期的設(shè)計(jì)與實(shí)現(xiàn).計(jì)算機(jī)系統(tǒng)應(yī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)計(jì)劃排程系統(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 馬永.基于遺傳算法求解排課問(wèn)題的研究.福建電腦,2008(6):110～111

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

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

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