基于遗传算法的内容编排模型设计*

刘 静，沈奇威

（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