基于交互式进化优化的图书个性化搜索方法

摘要

本发明公布了一种用于心理学图个性化快速搜索的交互式进化优化方法，指导用户快速寻找满意图书，减轻用户搜索疲劳，具体内容包括：(1)基于用户所输入的信息，给出初始化的信息，即交互式遗传算法中的初始种群生成；(2)人机交互，即由用户根据系统显示的进化个体表现型，实施交互行为，如对感兴趣的内容进行的少数的点击、浏览等行为；(3)基于交互行为的CP-nets偏好建模和更新，以基于用户的交互行为，获取并跟踪其偏好变化；(4)基于CP-Nets的交互式进化过程，即根据CP-nets对当前的进化种群所代表的搜索信息进行适应值评价，实施选择、交叉和变异操作，以生成可能满足用户偏好的新个体信息。

说明书

技术领域

本专利属于智能计算领域，是一种基于交互式进化优化策略的图书个性化搜索方法，可用于引导用户在网络环境下进行图书的快速搜索。 

背景技术

在现实生活中，需要人参与的评价和决策优化问题广泛存在。如旅游计划的制定问题，不同人对旅行中的路线，交通方式，时间，费用等的综合评价不同，从而制定出不同的旅游路线。上述问题为优化问题，但是，由于需要人的参与，无法用精确数学模型描述，导致基于数学函数的传统优化和各种智能优化算法不再适用。融合了人智能评价的交互式进化优化算法可有效解决此类问题，该方法将人的智能评价和传统进化优化过程相结合，它能很有效的解决含个性化信息优化问题。该方法需要人根据其对优化问题的个性化偏好，主观地评价进化个体适应值，进而实现进化优化。具体而言：首先，由计算机完成传统进化优化算法的工作，包括编码、解码、解集初始化，并将各解所对应的方案呈现给用户；其次，用户通过人-机交互界面，根据个人的认知和偏好，对所见对象进行评价；最后，计算机根据评价值，对编码的进化个体执行选择、交叉、变异等进化操作，生成新的解集。用户不断重复上述过程，直至找到满意解或者算法满足终止条件，算法结束并输出最优解。本发明将交互式进化优化算法引入到网络环境下的图书个性化搜索中，可为用户提供一个高效的搜索平台，引导用户快速完成搜索。 

近年来，交互式进化优化已在诸多领域得到了成功应用。例如，刘肖健等人在2009年的机械工程学报上发表的《基于交互式遗传算法的产品配色设计》一文中，利用了交互式遗传算法挖掘最优色彩匹配方案，但是需要大量的选择评价来捕捉用户对色彩的意象，增加了用户评价负担。在计算机软件著作权登字为第0186137号的软件《基于进化个体不确定适应值交互式遗传算法的服装设计软件》中，将进化计算用于服装款式的设计，寻找最符合用户偏好的颜色搭配及款式。现有成果虽然取得了一定的成功，但是由于所采用的评价方式，进化策略等较为单一、灵活性差，对用户的个性化支持不足，因此普遍存在着进化效率不高，易用性差等问题。Jimmy Secretan等人在2008年的CHI会议上发表的《Picbreeder:Evolving Pictures Collaboratively Online》一文中，介绍了由其团队开发的在线图片进化系统，该系统采用了基于权值网络的进化方式，能够从一幅简单的图片进化出满足用户要求的复杂图片，大大改善了进化的效果。但是在这套系统中，由于无法生成具有特定属性的起始种群以及进 化策略上存在的缺陷，导致无法在种群的多样性和收敛性之间达到较好的平衡，增加种群多样性的同时会大大减缓种群的收敛速度，反之亦然。在专利号为201110094666.4的《用于窗帘设计的交互式进化优化方法》发明专利中，允许用户设定模糊偏好信息生成初始种群，同时提供了多种个体评价方式和个体的编码方式，确定了搜索的范围及形式，减小搜索区域。但是需要用户多次评价，极易产生用户疲劳，导致评价不真实。现有的这些研究成果尽管存在着各种各样的问题，但是仍对本发明提供了多方面的有益指导。 

交互式进化优化算法在诸多理论研究方面取得的辉煌成就不断推动着其在生产生活中的应用，体现了巨大的实践价值。经查阅相关文献，目前尚无将该项技术应用到图书个性化搜索的先例，如能针对图书个性化搜索问题，设计出一套高效的搜索方法，将大大减轻用户的搜索量，提高搜索效率，同时也可考虑将其推广到其它领域的个性化搜索中，实现更大的社会效益。 

发明内容

本发明提出了一套完整的基于交互式进化优化的个性化高效搜索算法，包括基于编码的初始搜索对象的(进化个体)的生成、人机交互、基于交互行为的用户评价模型、模型更新以及进化方法。首先根据用户的浏览行为、对某图书的关注程度以及相关操作等，获取用户的兴趣模型；然后，利用条件偏好网络(Conditional Preference Nets,CP-nets)推导出用户对于待搜索图书不同属性值组合的偏好关系，实现对当前所见不同图书的评价；最后，基于评价值，进行选择、交叉和变异的操作，得到一组新的图书属性值的优化组合，为用户提供更满足其偏好的图书信息。重复上述过程，直到用户找到满意图书。基于此，我们开发出了相应的系统，其根本目的是为用户在图书个性化搜索过程中，快速找到满意图书，减轻自身疲劳。 

本发明的特点在于：一是根据用户输入的图书搜索属性值和已存在的历史偏好属性信息，为用户提供满足其偏好的图书，同时保证搜索的多样性；二是本发明中为解决用户频繁评价导致的用户疲劳问题，利用用户的浏览行为，间接获得用户的偏好，建立用户偏好模型CP-nets，以此来获得用户对搜索对象的评价；三是在整个进化过程中，采用符合图书属性描述的二进制编码方式进行进化操作。每一特点由相对应的功能模块实现。本发明的三大模块及所使用的方法如下： 

1、搜索对象的初始化生成(进化种群的初始化)模块 

在网络环境中，用户根据个人需求，进行个性化信息的搜索时，我们希望呈现给用户的信息尽可能贴近用户需求，让用户快速搜索到满意解，同时确保提供给用户的信息尽可能保 持其多样性，以便给用户提供更大的搜索空间，激发用户的浏览兴趣。我们利用三个方面信息进行对用户搜索偏好初始化建模，包括：用户当前输入的搜索信息、用户的历史搜索信息以及社会群体信息。 

2、用户偏好提取与更新模块 

本发明是在图书搜索过程中，通过分析用户搜索行为，提炼出用户对各图书关键属性值的偏好关系，建立用户偏好模型CP-nets。同时将CP-nets与交互式遗传算法相结合，以动态反映并跟踪用户的兴趣。此方法可以防止用户反复评价，减少用户评价的主观性、模糊性，进而为下面的交互式工作，提供满足用户兴趣的评价结果，减少用户搜索的时间，防止用户疲劳。 

2.1、偏好模型：CP-nets是一种表示定性条件的偏好语言，能够精确表示用户偏好，同时可以利用CP-nets偏好表中的规则，推断出用户对各属性值的偏好，这有利于挖掘用户在搜索满意解过程中的偏好。 

2.2、评价方式：根据用户的浏览行为，包括点击次数、浏览时间、保存、收藏等，获得用户对优化对象各组成部分的偏好评价，该方法可避免由于频繁的人机交互而导致的用户厌烦和疲劳，提高图书个性化搜索的效率。 

2.3、偏好模型更新：通过比较用户的实时浏览行为，动态更新当前图书信息的显示序值，将排序靠前的商品尽快地呈现给用户。 

本发明根据用户浏览行为，实时获取用户偏好，在最大限度减轻用户评价负担的同时，也能够保障对个体做出有效评价，提高了实用性。 

3、进化模块 

用户在搜索满意解的过程中，偏好会随时改变，这就要求我们能够实时跟踪用户偏好，所以我们利用交互式遗传算法中人为主观评价的特点，随时跟踪用户偏好。本模块利用偏好模型CP-nets，将用户对图书的偏好信息，转化为用户对相应图书的评价值，再在图书的编码空间中，利用交互式遗传算法实施进化优化，不断产生越来越接近用户需求的新图书。该模块具体内容包括： 

3.1、基于行为的图书评价：基于用户行为，不断跟踪其偏好，并更新偏好模型，从而获取用户对当前所见图书信息的评价值。 

3.2、编码方式：对于图书的编码空间，根据其所具有的属性值，采用二进制编码方式，1代表该属性值存在于当前的图书信息中，0代表不存在，利用该策略可减少进化计算的复杂性。 

本发明中所采用的进化方法，充分结合了不同进化算法的优点，使得对图书个体的进化更加高效、精细，更具实用价值。 

总之，本发明所提出的图书个性化搜索设计方法，能够在保证进化效率、进化效果的前提下，最大限度地减小用户评价工作量，减轻用户负担，满足了用户对图书快速搜索的要求。该项发明亦可应用到其它的个性化搜索中，尤其是电子商务的智能化、个性化和高效化搜索中，因此具有极高的实用价值和广阔的应用前景。 

附图说明

图1是本发明中所提出的用于心理学图书个性化搜索的交互式进化优化方法流程图； 

图2是本发明中所提出的用于心理学图书个性化搜索的算法框架示意图； 

图3是依据本发明所提方法开发的心理学图书个性化搜索设计系统界面图； 

图4是用户初始偏好模型CP-nets举例； 

图5是偏好模型更新示意图。 

具体实施方式

该部分结合具体附图，对本发明的实施方式做详细说明。本发明中所提出的方法流程图和框架示意图分别如图1和如图2所示，具体实施步骤亦根据其拟定。 

为充分体现本发明所提出的交互式进化优化方法的价值，在提出本方法的同时亦开发了相应的软件系统。在图书搜索系统中，主要使用的软件是SQL Server2005和Microsoft Visual C++6.0。Microsoft Visual C++6.0用来搭建图书搜索系统平台，该平台向用户提供直观的交互界面，通过模拟浏览过程，可以得到实时数据，并传到数据库中处理。数据库SQL Server2005软件用来建立一个相应的数据库，该数据库可以存储图书信息，并能根据所采集的用户浏览行为，调整数据库中用户对图书属性偏好。系统界面如图3所示。 

步骤1：初始搜索对象的生成。该步骤内容为：根据用户输入的具体属性值、其历史搜索内容，以及当前社会群体的相关搜索内容，生成初始的图书搜索信息，并确定用户对图书各属性值的初始偏好模型。具体由以下两个子步骤完成： 

步骤101：确定用户初始偏好模型。 

我们知道，每一个商品均可以用商品属性描述，因此商品属性的组合即可以表示一个或一类商品。假设，商品具有如下属性特征： 

$>\left(\begin{array}{c}f\left(x\right)=f\{x_1,x_2,...,x_n\}\\ x_i\in g_i\\ g_i=\{x_{i1},x_{i2},...,x_{{\mathrm{im}}_i}\}\\ S=\underset{i=1}{\overset{n}{\Pi }}{g}_i\end{array}\right)---\left(1\right)$>

其中，x₁,x₂,…,x_n为n类商品属性，即n个决策属性变量；每一个决策属性变量x_i具有m_i个商品属性值；f(x)表示x_i(i＝1,2,…,m_i)的不同属性取值组合可以确定一类商品。 

初始偏好模型构建的目的是基于初始搜索时的信息，确定当前商品决策属性变量之间粗糙的偏好支配关系，以体现当前用户的个性化需求。因此我们利用用户当前输入信息、用户历史搜索记录和群体共性搜索信息，这三种信息来确定初始用户偏好模型。 

首先，根据用户当前输入信息确定决策属性变量间的偏好支配关系，构建偏好网络；然后，再根据用户历史搜索记录和群体共性搜索信息，确定决策属性变量取值间的部分偏好支配关系，获得偏好支配表。记用户初始化搜索时输入的属性集合对应的决策属性变量集为B₁，则认为B₁中的决策属性变量具有相同的偏好关系，互不支配；除B₁外的其余决策属性变量均被B₁中的决策属性变量偏好支配，但彼此互不支配。根据B₁中各决策属性变量，从用户历史搜索记录中，搜索出与之相关的各决策属性变量的取值，则这些取值支配其余取值；对于被支配的决策属性变量，以及被支配的取值，则进一步根据与B₁相关的群体历史信息，进一步确定这些决策属性变量之间的偏好支配关系，以及相应取值间的偏好支配关系。至此，完成对CP-nets的初始化构建。 

例：设商品决策属性变量集为U＝{x₁,x₂,x₃,x₄,x₅}，各决策属性变量有2个商品属性值，简记为x_i＝{x_i1,x_i2}。设用户输入决策属性变量为B₁＝{x₁}，用户历史搜索对应的决策变量值为x₁＝{x₁₁},x₂＝{x₂₁}，相应的群体搜索信息为x₁＞x₂＞x₅,x₃＞x₄，且有x₁₁：x₃₁＞x₃₂，那么，此时所构建的CP-nets如图4所示。其中图4(1)确定的是CP-nets中各决策属性变量之间的连接关系，图4(2)表示，在各决策属性变量连接关系确定下，各决策属性变量属性值之间的偏好关系，即条件偏好表。 

步骤102：生成初始种群。 

根据初始偏好模型，选择偏好模型中top-n的商品属性组合，从数据库中随机选择具有这些商品属性组合的图书呈现给用户，即生成初始种群。 

步骤2：设置进化参数，完成交互式进化准备。本发明根据图书属性34种分类，进行二进制字符串分层编码，需要设置的进化参数包括交叉概率、变异概率和最大进化代数。 

步骤3：通过人机交互模块,间接获得用户对图书的评价。本发明采用基于用户进行的简单的人-机交互行为，如浏览、点击等，简介获取其认知和偏好，进而，将该偏好模型应用于 交互式遗传算法中。在整个图书个性化搜索过程中，为了模拟用户的实时浏览行为，减少工作量，我们在图书个性化搜索界面中，利用图书图片表示用户浏览的图书，用户对每一本图书的浏览行为，使用每一副图片下的“浏览时间”滑动条和“收藏”、“加入购物车”、“购买”三个单选按钮进行模拟。 

步骤4：偏好模型CP-nets的更新。根据用户实时交互信息，不断提取用户对各决策属性变量即其取值的偏好关系，更新CP-nets模型，以跟踪用户偏好的变化，尽快找到符合用户偏好的信息。 

步骤401：用户实时浏览行为评价权重转换。 

浏览时间可直接反应用户的偏好，因此，因此我们根据浏览行为确定如下5种浏览时间。定义如下，用户浏览第i页第j(j＝1,2,3…8)本图书的时间t_ij：(1)用户对此图书无任何点击浏览时间，则t_ij＝0；(2)用户浏览此图书但无收藏、加入购物车，或者购买行为，若浏览时间在t_ij≤29(s)，则规定浏览时间为：t_ij＝t_实际,否则，若浏览时间t_ij＞29(s)则记作t_ij＝29(s)；(3)用户仅有收藏行为，记用户对图书的评价为t_ij＝30(s)；(4)用户有加入购物车行为，则用户对图书的评价为g_ij＝50(s)；(5)用户产生购买行为，则记作b_ij＝100(s)。基于浏览时间，定义用户对第i页第j(j＝1,2,3…8)本图书的偏好权重为W_ij＝max(t_ij,s_ij,g_ij,b_ij)。我们将第i页第j(j＝1,2,3…8)本图书的浏览时同时分配给此图书包含的属性，作为图书属性值的权值。 

步骤402：偏好模型更新。 

如图5所示，根据心理学图书属性特点，用户偏好的CP-nets模型分为父属性顶点U＝(U₁,U₂,…,U_m)和子属性节点集V＝(V₁,V₂,…,V_m)。每一个子属性节点均包含L_i(i＝1,2,…m)个属性，父属性U的每一个取值确定一个子属性的选择，即确定CP-nets中各节点间的的固定偏好连接关系。如父属性取值为U₁＝儿童心理学可以确定子属性节点V₁＝{学前儿童，小学儿童，特殊儿童}，如图5所示中U₁→V₁,U₂→V₂,…U_m→V_m。 

CP-net的更新分两种情况： 

第一种：在只有一个父属性U₁→V₁的情况下，首先确定父属性U所有取值的排序 然后根据用户评价，确定用户对第i页 所浏览图书中子属性$>V_1=(V_{11},V_{12},...,V_{{1L}_1})$>各属性值的权值为$>w\left(V_{1h}\right)=\frac{\underset{j=1}{\overset{8}{\Sigma }}{W}_{\mathrm{ij}}\left(V_{1h}\right)}{8}(h=\mathrm{1,2},...L_1),$>对该权重按照从大到小顺序排序后，确定中属性值的序值，并赋予 值,对于权重值相同的属性值赋予同一序值，并依次降序赋值。及确定了CP-nets中的各决策变量属性值偏好关系。 

第二种：在用户浏览行为中，发现有其他属性值出现，如图中红色矩形框所示Z…＞U₃，首先要确定父属性取值间的偏好关系，其次分别比较子属性取值间的偏好关系。首先通过比较和确定父属性U₁、U₃的偏好序值，若w(U₁)＞w(U₃),则sequ:U₁＝m,U₃＝m-1，其他父属性的序值为sequ:U₂＝U₄＝…＝U_m＝m-2。然后再根据用户浏览行为，确定U₁→V₁₁和U₃→V₁₃子属性取值排序，排序方法同CP-nets跟新第一种方法。 

步骤5：个体适应值获取。 

根据更新之后的偏好模型，我们通过基于软约束的支配占优策略，确定CP-nets的定量化，从而获得用户对所有图书的适应值评价。具体步骤如下，如图5所示，在偏好模型CP-nets中父属性U的class(U)＝1，即class(U₁)＝class(U₂)＝…＝class(U_m)＝1，子属性V的class(V)＝0,即class(X)＝class(Y)＝…＝class(S)＝0。对于一本图书所具有的属性o＝(U_i,V_ij)，从而获得个体适应值为$>F\left(o\right)=\mathrm{sequ}\left(U_i\right)·2^{\mathrm{class}\left(U_i\right)}+\mathrm{sequ}\left(V_{\mathrm{ij}}\right)·2^{\mathrm{class}\left(V_i\right)}.$>然后根据图1进行进化操作。 

步骤6：保存最优方案，完成心理学图书个性化搜索。通过以上过程，用户可最终完成图书的进化。此时用户可将找到的最佳搜索结果进行保存。在整个进化过程中，用户若始终对当前的心理学图书搜索结果不够满意，可选择重新搜索，开始新的进化。