基于CP-nets的偏好感知交互式遗传算法及其个性化搜索资源-CSDN文库

53 浏览量 2021-01-14 05:29:28 上传评论收藏 653KB PDF 举报

资源推荐

资源详情

资源评论

第 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 ﬁtness to assist the user ﬁnding 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−), 女, 硕士

生, 从事交互式进化优化的研究.

1154

控制与决策

第 30 卷

户疲劳的可行途径之一

[7]

, 即根据用户已评价进化个

体信息, 采用合适的机器学习方法和模型, 如神经网

络、支持向量机等, 逼近用户评价, 然后在进化过程

中, 利用该模型估计进化个体适应值.

虽然交互式遗传算法在解决减轻用户评价疲劳

的问题上已取得丰硕的研究成果, 但已有研究都是建

立在要求用户对其所见方案进行打分的显式评价基

础上的, 仍不能根本改善算法性能. 因此, 改变当前交

互式遗传算法要求用户显式评价进化个体适应值的

模式迫在眉睫. 仅需用户进行简单的人-机交互行为

(如浏览、点击等), 隐式获取其认知和偏好, 进而构建

客观的适应度函数, 则可根本改善现有交互式遗传

算法的不足. 近年来, 电子商务的个性化推荐正是基

于人-机交互行为, 构建用户兴趣模型, 进而搜索用户

可能感兴趣的信息, 但已有成果均未将该过程与进化

优化相结合. 此外, 用于多属性决策的条件偏好网络

(CP-nets) 是一种刻画用户定性偏好的有效工具

[8]

, 该

网络可直观反映决策变量间的偏好依赖关系, 但该方

法目前尚未与个性化推荐和交互式进化优化相结合.

鉴于此, 本文借鉴个性化推荐的研究成果, 以如

何实现个性化快速搜索为目标, 提出基于用户交互行

为和 CP-nets 的偏好评价隐式感知模式的交互式遗传

算法. 首先, 基于用户实施的简单的人-机交互行为, 构

建 CP-nets 模型, 隐式获取用户的认知和偏好; 其次,

构建基于该偏好模型的适应值估计策略, 在交互过

程中利用该策略代替用户估计进化个体适应值; 再

次, 根据估计适应值, 动态更新用户搜索信息的显示

序值, 将排序靠前的解决方案尽快呈现给用户; 最后,

在进化过程中根据用户实施的交互行为, 动态更新

CP-nets. 重复上述过程, 直至找到满意解.

本文的研究工作主要包括如下 3 个方面: 1) 提出

基于用户交互行为的偏好感知交互式遗传算法; 2) 提

出基于交互行为的 CP-nets 偏好感知模型的构建和动

态更新机制; 3) 给出基于 CP-nets 的适应值估计策略.

1 相相相关关关工工工作作作

1.1 交交交互互互式式式遗遗遗传传传算算算法法法

交互式遗传算法将传统的进化机制与用户的智

能评价相结合, 基于用户给出的进化个体适应值实施

进化操作, 代替了基于数学模型的适应值评价, 是解

决定性性能指标优化问题的可行方法. 不失一般性,

考虑如下一类待优化问题:

max 𝐹 (𝑋) = max 𝐹 {𝑥

, 𝑥

, ⋅ ⋅ ⋅ , 𝑥

𝑛

𝑥

𝑖

∈ 𝑔

𝑖

, 𝑔

𝑖

= {𝑥

𝑖1

, 𝑥

𝑖2

, ⋅ ⋅ ⋅ , 𝑥

𝑖𝑚

𝑖

𝑆 =

𝑛

∪

𝑖=1

𝑔

𝑖

. (1)

其中: 𝑥

𝑖

为第 𝑖 个决策变量, 其定义域 𝑔

𝑖

为含有 𝑚

𝑖

个

元素的集合; 𝑆 为优化问题的定义域; 𝐹 (𝑋) 为无法用

具体表达式描述的性能指标, 由用户根据其认知和偏

好确定. 如在个性化商品搜索中, 𝑥

𝑖

可为待搜索商品

的第 𝑖 个属性, 该属性的所有取值集合为 𝑔

𝑖

, 那么用户

给出最高评价值的属性值组合即为最满意解.

1.2 个个个性性性化化化推推推荐荐荐

近年来, 基于用户兴趣发现的个性化推荐在电商

中得到了广泛研究, 其核心是用户兴趣发现和建模.

Choi 等

[9]

针对个性化商品推荐问题, 考虑商品的

多个属性, 利用多属性决策和用户的隐性反馈, 获取

用户兴趣, 并利用其获得同类商品间的序关系; Chang

等

[10]

根据用户历史偏好建立 CP-nets 用户偏好模型,

再根据用户输入关键词属性, 利用偏好模型向用户提

供搜索结果; Ganesh 等

[11]

利用用户定性偏好建立的

CP-nets 模型为用户提供搜索内容, 避免了传统网络

服务中向用户提供所有满足用户请求的服务. 上述研

究的总体思路均是通过对浏览网站或者商品的特征

信息赋予一定的权值, 根据记录的用户浏览行为, 采

用简单相加或者取大形式, 确定相关的权重, 获取用

户兴趣, 并没有与进化算法结合.

Kim 等

[12]

结合交互式遗传算法和基于内容的过

滤技术, 提出了一种新的电商推荐系统, 以动态跟踪

用户的兴趣, 并将其应用于音乐推荐中; Ahn

[13]

利用

agent 根据用户的浏览和购物行为, 模拟其兴趣模型,

并利用进化算法动态优化相关参数. 上述研究仅简单

利用进化算法优化或者更新所构建的兴趣模型, 而没

有将所建立的用户兴趣模型应用于进化算法中, 通过

与用户交互的融合, 动态调整用户兴趣模型的同时,

对搜索过程进行优化, 从而尽快辅助用户找到满意的

信息.

本质上, 用户搜索满意信息的过程是一个优化

过程, 那么, 根据用户实时交互信息采用合适的方法

(如 CP-nets) 捕捉用户的偏好, 并将其代替人实现交互

式进化优化算法中的个体评价, 直接辅助用户搜索,

则有望解决现有交互式进化优化算法和个性化搜索

存在的问题. 鉴于此, 本文提出基于 CP-nets 的偏好感

知交互式遗传算法.

2 基基基于于于CP-nets的的的偏偏偏好好好感感感知知知交交交互互互式式式遗遗遗传传传算算算法法法

2.1 算算算法法法框框框架架架

本文所提算法框架如图 1 所示, 主要包括 4 部分:

1) 基于用户所输入的信息给出初始化的信息, 即交

互式遗传算法中的初始种群生成; 2) 人机交互, 即由

用户根据系统显示的进化个体表现型实施交互行

为, 如对感兴趣的内容进行的少数点击、浏览等行

为; 3) 基于交互行为的 CP-nets 偏好建模和更新, 以基

于用户的交互行为, 获取并跟踪其偏好变化; 4) 基于

剩余8页未读，继续阅读

评论收藏

内容反馈

weixin_38645198

粉丝: 5
资源: 956

基于CP-nets 的偏好感知交互式遗传算法及其个性化搜索

最新资源

基于CP-nets 的偏好感知交互式遗传算法及其个性化搜索

基于CP-nets的偏好感知交互式遗传算法及其个性化搜索 (2015年)

机器人的CP-nets优化类人轨迹规划（英文）.pdf

具有隐式不确定性评估的交互式遗传算法在个性化搜索中的应用

基于G 方检验的CP-nets学习

CP-nets上的正则化路径查询

SGM-Nets: Semi-global matching with neural networks

翻译A-fast-learning-algorithm-for-deep-belief-nets.doc编程资料

naive-surface-nets:实现一个简单易读的朴素表面网络算法

product-nets-master_ideanets_pnn_

tensorflow-nets.rar

tensorflow-nets.zip

s3tbx-c2rcc-src-main-resources-auxdata-nets-olci-rw_iop-37x37x37_596495.4.net

前端开源库-nets

dynamic-image-nets, 动作识别的动态图像网络.zip

翻译A-fast-learning-algorithm-for-deep-belief-nets.docx

翻译A-fast-learning-algorithm-for-deep-belief-nets.pdf

最新资源