第 30 卷 第 7 期
Vol. 30 No. 7
控 制 与 决 策
Control and Decision
2015 年 7 月
Jul. 2015
基于 CP-nets 的偏好感知交互式遗传算法及其个性化搜索
文章编号: 1001-0920 (2015) 07-1153-09 DOI: 10.13195/j.kzyjc.2014.0645
孙晓燕, 陆宜娜, 巩敦卫, 张抗抗
(中国矿业大学 信息与电气工程学院,江苏 徐州 221008)
摘 要: 针对用户显式评价导致用户疲劳, 进而限制交互式遗传算法搜索性能的问题, 研究基于用户交互行为和条
件偏好网络 (CP-nets) 的隐式评价模式的交互式遗传算法, 并将其应用于图书商品个性化搜索. 首先, 给出用户交互
行为的数学描述, 建立基于用户少量交互行为的条件偏好网络模型以拟合用户偏好; 然后, 利用 CP-nets 模型估计用
户对进化个体的评价值, 实施进化操作以帮助用户尽快找到满意解. 在个性化搜索中的应用验证了所提出算法的有
效性.
关键词: 交互式遗传算法;偏好感知;条件偏好网络;个性化搜索
中图分类号: TP273 文献标志码: A
Interactive genetic algorithm with CP-nets preference surrogate and
application in personalized search
SUN Xiao-yan, LU Yi-na, GONG Dun-wei, ZHANG Kang-kang
(School of Information and Electrical Engineering,China University of Mining and Technology,Xuzhou 221008,
China.Correspondent:LU Yi-na,E-mail:1027672571@qq.com)
Abstract: The explicit evaluation mode of interactive genetic algorithms(IGAs) often brings user fatigue, which greatly
limits the performance of IGAs in exploration. Therefore, an IGA with an implicit evaluation mode is proposed based
on the interactive actions performed by the user and the conditional preference nets(CP-nets). Firstly, the model of those
possible actions is built, and the CP-nets adopted to approximate to the preference of the user are constructed according to
few interactive actions. Then, the CP-nets model is adopted to estimate the assignments of those individuals not evaluated by
the user, and the evolution process is successfully conducted based on the estimated fitness to assist the user finding his/her
interested solution as early as possible. The proposed algorithm is applied to a personalized search for books, and the results
show the effectiveness of the proposed algorithm.
Keywords: interactive genetic algorithms;preference cognition;CP-nets;personalized search
0 引引引 言言言
在现实生活中, 需要人或者用户参与评价和决策
的优化问题广泛存在. 如旅游计划的制定问题, 不同
人对旅行中的路线、交通方式、时间以及费用等的综
合评价不同, 从而决策出不同的旅游路线. 上述问题
的本质是优化问题, 但是, 由于该问题需要人的参与,
无法用精确数学模型描述, 导致基于数学函数的传统
优化方法和各种智能优化算法不再适用. 融合了人类
智能评价的交互式遗传算法 (IGAs) 可有效解决此类
问题
[1]
. IGAs 是将人的智能评价与传统遗传算法优化
过程相结合的一类解决含个性化信息优化问题的有
效方法. 该方法需要人根据其对优化问题的个性化偏
好, 主观评价进化个体适应值, 进而实现进化优化. 虽
然交互式遗传算法已得到了大量成功应用
[2-4]
, 但是
该类算法在实现的过程中要求用户频繁地提供评价
值, 导致其极易厌烦和疲劳, 仅能评价极少量的决策
方案. 这使得交互式遗传算法只能采用小的种群规模
和少的进化代数, 在复杂、海量信息等实际问题 (如互
联网等环境下) 中的应用难以奏效
[5]
.
针对上述不足, Takagi
[6]
提出了两类解决用户疲
劳的措施: 设计友好的交互界面, 以减少用户评价的
生理和心理负担; 基于距离和聚类的适应值继承策
略, 在一定程度上减轻用户疲劳, 改善了算法性能. 构
建用户认知代理模型的适应值估计策略也是减轻用
收稿日期: 2014-04-29;修回日期: 2014-08-08.
基金项目: 中央高校基本科研业务费基金项目(2012QNA58);国家自然科学基金项目(61105063, 61473298).
作者简介: 孙晓燕(1978−), 女, 教授, 博士生导师, 从事交互式进化优化、多目标优化等研究;陆宜娜(1990−), 女, 硕士
生, 从事交互式进化优化的研究.