孫曉燕， 朱利霞， 陳 楊

(中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221008)

基于可能性條件偏好網(wǎng)絡(luò)的交互式遺傳算法及其應(yīng)用

孫曉燕， 朱利霞， 陳 楊

(中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221008)

根據(jù)用戶實(shí)施的人機(jī)交互行為而隱式地獲取用戶偏好的交互式進(jìn)化優(yōu)化算法，可有效減輕用戶疲勞，提高個(gè)性化搜索或推薦的效率. 但是，已有研究沒(méi)有考慮用戶交互行為和偏好的不確定性，影響了對(duì)用戶偏好的擬合精度以及基于該偏好表達(dá)的進(jìn)化搜索. 針對(duì)該問(wèn)題，提出基于可能性條件偏好網(wǎng)絡(luò)的交互式遺傳算法，以刻畫(huà)用戶交互行為和偏好的不確定性，并提高算法的搜索性能. 首先，采用交互時(shí)間表示交互行為，考慮交互行為的不確定性，給出交互時(shí)間可信度的定義，并基于該定義給出了用戶不確定偏好的表達(dá)函數(shù)；其次，利用可信交互時(shí)間和偏好函數(shù)，定義了用戶對(duì)評(píng)價(jià)對(duì)象的偏好權(quán)重，并利用該權(quán)重，設(shè)計(jì)(更新)可以定量表示用戶不確定偏好的可能性條件偏好網(wǎng)絡(luò)，以更好地?cái)M合用戶偏好；然后，結(jié)合評(píng)價(jià)不確定性和可能性條件偏好網(wǎng)絡(luò)，提出了改進(jìn)的個(gè)體適應(yīng)值估計(jì)策略，以更好地引導(dǎo)搜索； 最后，將所提算法應(yīng)用于圖書(shū)個(gè)性化搜索中，結(jié)果表明了算法搜索的可靠性和高效性.

交互式遺傳算法； 不確定性； 可能性條件偏好網(wǎng)絡(luò)； 個(gè)性化搜索

0 引言

在當(dāng)前信息社會(huì)中，個(gè)性化搜索、個(gè)性化服務(wù)等已成為網(wǎng)絡(luò)發(fā)展、數(shù)據(jù)管理和挖掘的首要任務(wù). 實(shí)質(zhì)上，個(gè)性化信息獲取是優(yōu)化問(wèn)題. 但是，目前從優(yōu)化角度解決該類問(wèn)題的研究成果還較少. 在個(gè)性化信息獲取中，人-機(jī)交互貫穿整個(gè)過(guò)程，如用戶興趣建模和跟蹤等[1]. 若將用戶興趣模型與進(jìn)化優(yōu)化算法結(jié)合，則可望提高用戶搜索效率，而這恰好符合交互式進(jìn)化優(yōu)化算法應(yīng)用的范疇[2]. 交互式進(jìn)化優(yōu)化算法將人的智能與進(jìn)化優(yōu)化搜索過(guò)程進(jìn)行結(jié)合，可有效解決個(gè)性化產(chǎn)品設(shè)計(jì)、電力系統(tǒng)優(yōu)化、房屋裝修、網(wǎng)頁(yè)布局、音樂(lè)創(chuàng)作及圖像檢索等問(wèn)題[3-8].

孫曉燕等[9]借鑒個(gè)性化搜索中用戶興趣建模的研究成果，考慮用戶搜索的評(píng)價(jià)對(duì)象屬性間的相互關(guān)聯(lián)關(guān)系，提出了基于交互行為和條件偏好網(wǎng)絡(luò)的交互式進(jìn)化優(yōu)化算法，并用于解決個(gè)性化搜索問(wèn)題. 然而，在該算法框架中，沒(méi)有考慮用戶認(rèn)知或偏好評(píng)價(jià)的不確定性. 筆者在文獻(xiàn)[9]的基礎(chǔ)上，研究含認(rèn)知不確定性的隱式評(píng)價(jià)交互式進(jìn)化優(yōu)化算法.

由于鼠標(biāo)滾動(dòng)信息也可反映用戶的偏好[10]，因此，可利用瀏覽時(shí)間和鼠標(biāo)滾動(dòng)次數(shù)定義交互時(shí)間和評(píng)價(jià)偏好的不確定性函數(shù). 因條件偏好網(wǎng)絡(luò)(conditional preference networks，CP-nets)無(wú)法反映節(jié)點(diǎn)以及節(jié)點(diǎn)之間存在的偏好不確定性，文獻(xiàn)[11]提出了一種新的偏好網(wǎng)絡(luò)——可能性網(wǎng)絡(luò)(probabilistic networks)，它能靈活地表達(dá)不確定偏好. 在此基礎(chǔ)上，Cornelio[12]和Bigot等[13]考慮到動(dòng)態(tài)不確定和噪音特性，進(jìn)一步構(gòu)建動(dòng)態(tài)概率CP-nets，即每個(gè)依賴關(guān)系都以一定的概率存在，從而靈活刻畫(huà)偏好關(guān)系.筆者在此基礎(chǔ)上利用PCP-nets(probabilistic conditional preference networks)可靈活表示不確定偏好.

1 基于交互行為的用戶偏好不確定性表示

在電子商務(wù)搜索系統(tǒng)中，用戶的交互行為能很好地體現(xiàn)用戶的興趣偏好. 若僅僅利用交互時(shí)間的長(zhǎng)短去刻畫(huà)用戶對(duì)某搜索對(duì)象的偏好度難以反映用戶交互行為中的所有信息. 如用戶對(duì)第i個(gè)商品Xi和第j個(gè)商品Xj的交互瀏覽時(shí)間關(guān)系為t(Xi)>t(Xj)， 并不能說(shuō)明用戶對(duì)Xi的興趣度一定比對(duì)Xj的興趣度大，有可能是Xi的頁(yè)面較長(zhǎng)，增加了用戶的瀏覽時(shí)間，那么t(Xi)和t(Xj)就有一定的可信度. 所以,筆者結(jié)合鼠標(biāo)滾動(dòng)次數(shù)，考慮具有可信度的交互行為.

1.1交互行為的可信度

考慮4類交互行為：①點(diǎn)擊瀏覽行為A1；②保存行為A2；③收藏/標(biāo)簽行為A3； ④決策/購(gòu)買(mǎi)行為A4. 偏好關(guān)系為A1

采用交互時(shí)間刻畫(huà)上述4種交互行為，并利用鼠標(biāo)滾動(dòng)次數(shù)定義交互時(shí)間的可信度. 對(duì)搜索對(duì)象Xi，設(shè)用戶交互時(shí)間為tj(Xi)， 鼠標(biāo)滾動(dòng)次數(shù)為nj(Xi)，j=1,2,3,4;i=1,2,…,Lj，其中Lj表示對(duì)象集合包含的元素個(gè)數(shù). 融合可信度的交互行為量化表達(dá)如式(1)所示：

(1)

式中,β為控制條件可信程度變化的參數(shù).

1.2含交互不確定性的偏好表示

基于上述交互行為可信度表示，進(jìn)一步給出用戶對(duì)搜索對(duì)象Xi的偏好表示. 用戶對(duì)于特別喜歡和特別不喜歡的搜索對(duì)象往往給出的評(píng)價(jià)越可信； 而對(duì)于不關(guān)心的對(duì)象, 評(píng)價(jià)的可信性則相對(duì)較小. 那么用戶偏好不確定度定義如下所示:

(2)

式中,γ為可變參數(shù)；t0為平均瀏覽時(shí)間.

(3)

(4)

式中,k為調(diào)節(jié)參數(shù).

(5)

對(duì)式(5)進(jìn)行歸一化處理:

(6)

2 基于不確定偏好權(quán)重的可能性條件偏好網(wǎng)絡(luò)的構(gòu)建

2.1可能性條件偏好網(wǎng)絡(luò)的初始化構(gòu)建

2.2可能性條件偏好網(wǎng)絡(luò)的更新

(7)

(8)

根據(jù)式(8)計(jì)算偏好權(quán)重，更改支配關(guān)系.

3 基于可能性條件偏好網(wǎng)絡(luò)的交互式遺傳算法

3.1基于可能性條件偏好網(wǎng)絡(luò)的個(gè)體適應(yīng)值的估計(jì)

首先，考慮條件偏好有向圖中決策變量的層級(jí)分布貢獻(xiàn)度.xj支配的決策變量越多，class(xj)越小. 根據(jù)文獻(xiàn)[9]可知，決策變量xj的貢獻(xiàn)度為C1(xj)=2(class(xj)-1)class(xj)，若某決策變量未出現(xiàn)，則設(shè)該貢獻(xiàn)度值為C1(xj)=1. 結(jié)合偏好可能度，借鑒貝葉斯推理的鏈?zhǔn)焦?，?duì)于進(jìn)化個(gè)體Xi={x1i1,x2i2,…,xnin}的適應(yīng)值估計(jì)策略如式(9)：

(9)

3.2算法步驟

Step1：根據(jù)實(shí)際問(wèn)題進(jìn)行編碼，并設(shè)定遺傳操作的各種參數(shù)；

Step2：基于用戶輸入關(guān)鍵詞信息，歷史搜索信息和社會(huì)群體搜索結(jié)果，獲得初始化種群；

Step3：根據(jù)2.1節(jié)方法，構(gòu)建初始化可能性條件偏好網(wǎng)絡(luò)；

Step4：根據(jù)3.1節(jié)方法，估計(jì)當(dāng)前進(jìn)化種群的個(gè)體適應(yīng)值，選擇N個(gè)適應(yīng)值較大的進(jìn)化個(gè)體提交給用戶；

Step5：用戶實(shí)施交互行為，若找到滿意解，則算法終止，并輸出滿意解，否則，轉(zhuǎn)Step6；

Step6：記錄瀏覽時(shí)間和鼠標(biāo)滑動(dòng)次數(shù)，根據(jù)第1節(jié)計(jì)算用戶對(duì)評(píng)價(jià)對(duì)象的偏好權(quán)重，并根據(jù)2.2節(jié)方法更新可能性條件偏好網(wǎng)絡(luò)；

Step7：對(duì)當(dāng)前種群實(shí)施選擇，交叉和變異操作，生成新種群，轉(zhuǎn)Step4.

4 算法的應(yīng)用

4.1實(shí)驗(yàn)背景

將本文算法應(yīng)用到文獻(xiàn)[9]所構(gòu)建的圖書(shū)個(gè)性化搜索系統(tǒng)中，如圖1所示.通過(guò)算法的比較，驗(yàn)證本文算法的有效性.為了說(shuō)明本文算法IGA-PCP(probabilistic conditional preference network assisted interactive genetic algorithm)的整體性能，將其與文獻(xiàn)[9]所提算法IGA-CP(conditional preference network assisted interactive genetic algorithm)以及與傳統(tǒng)的交互式遺傳算法IGA(interactive genetic algorithm)進(jìn)行比較.

圖1 圖書(shū)搜索系統(tǒng)界面Fig.1 Interface of book search system

4.2參數(shù)設(shè)置

采用二進(jìn)制形式編碼，編碼串按照決策屬性分塊. 以當(dāng)當(dāng)網(wǎng)心理學(xué)圖書(shū)為例，將心理學(xué)圖書(shū)屬性分為7類，每一類屬性下有若干取值，本實(shí)驗(yàn)中共46個(gè)，需要19位二進(jìn)制碼. 實(shí)驗(yàn)中，β=6，k=5，γ=4，3種比較算法均采用輪盤(pán)賭選擇，單點(diǎn)交叉和變異，且交叉和變異概率分別為0.6、0.1，種群規(guī)模設(shè)為8.

4.3實(shí)驗(yàn)結(jié)果與分析

4.3.1 偏好不確定函數(shù)表示的合理性

鼠標(biāo)滾動(dòng)次數(shù)以及可信時(shí)間之間的關(guān)系如表1所示.可信時(shí)間與所定義的偏好度函數(shù)關(guān)系如圖2所示.

從表1可知，鼠標(biāo)滾動(dòng)次數(shù)與用戶實(shí)際交互時(shí)間的相互關(guān)系與本文所提可信時(shí)間相符，表明筆者所提時(shí)間可信度的合理性. 由圖2可知，式(4)所定義的偏好度函數(shù)隨著可信時(shí)間的增加而非線性增加，符合實(shí)際情況，表明了偏好度函數(shù)定義的合理性.

表1 IGA-PCP用戶瀏覽行為

圖2 偏好度函數(shù)fj(Xi)與可信時(shí)間的關(guān)系Fig.2 Relation between preference function fj(Xi) and credible time

4.3.2 對(duì)比實(shí)驗(yàn)

3種比較算法，實(shí)驗(yàn)結(jié)果如圖3所示.實(shí)驗(yàn)針對(duì)84類圖書(shū)共4 420本，在所有的圖書(shū)中找到“特殊兒童的問(wèn)題行為干預(yù)”，記錄實(shí)驗(yàn)數(shù)據(jù)如圖3所示：①I(mǎi)GA-PCP平均互異個(gè)體的比率最高，這說(shuō)明了本文算法IGA-PCP能有效提高搜索的多樣性.②本文算法的搜索時(shí)間比傳統(tǒng)IGA大約少一半，并且明顯小于IGA-CP算法搜索時(shí)間.③IGA-PCP用戶實(shí)施交互操作行為的次數(shù)平均為4.0，IGA-CP平均為7.6，傳統(tǒng)的IGA平均為7.7，由此可以看出，本文算法IGA-PCP可有效減輕用戶疲勞.

為了說(shuō)明所提算法的整體性能，現(xiàn)對(duì)勵(lì)志類圖書(shū)進(jìn)行搜索，實(shí)驗(yàn)針對(duì)24類圖書(shū)共1 159本，實(shí)驗(yàn)結(jié)果如表2所示.從表2可以看出，本文算法不僅有效減輕用戶疲勞，而且可有效提高算法多樣性. 總體來(lái)說(shuō)，本文算法明顯優(yōu)于其他兩種算法.

圖3 84類心理學(xué)圖書(shū)搜索實(shí)驗(yàn)結(jié)果Fig.3 The results of the experiment of eighty four kinds of psychology books表2 24類勵(lì)志圖書(shū)搜索實(shí)驗(yàn)結(jié)果Tab.2 The results of the experiment of twenty-fourkinds of inspirtional books

算法平均進(jìn)化代數(shù)平均搜索時(shí)間/s用戶交互次數(shù)互異個(gè)體比率IGA-PCP5.393.45.90.848IGA-CP7.8112.67.80.689IGA9.6126.07.20.669

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

用戶在搜索過(guò)程中，用戶的交互行為能夠有效地反映用戶偏好信息，但由于用戶認(rèn)知的不確定性， 反映到交互行為上也具有不確定性. 針對(duì)此情況，筆者考慮了交互行為的不確定性刻畫(huà)，以及基于該不確定性刻畫(huà)的用戶不確定偏好的描述,在用戶偏好建模方面，基于所考慮的不確定性偏好，提出了一種可能性條件偏好網(wǎng)絡(luò)擬合用戶評(píng)價(jià)偏好的方法，給出了適應(yīng)值估計(jì)策略，并將算法應(yīng)用到圖書(shū)搜索系統(tǒng)中，實(shí)驗(yàn)結(jié)果表明了該算法的可行性與有效性.

如何利用其他用戶的信息構(gòu)建多用戶偏好模型， 并進(jìn)行有效集成和更新，以實(shí)現(xiàn)網(wǎng)絡(luò)環(huán)境下的信息動(dòng)態(tài)更新并提高搜索效率，將是下一步要研究的問(wèn)題.

[1] QIAN X M, FENG H, ZHAO G S, et al. Personalized recommendation combining user interest and social circle[J]. IEEE transactions on knowledge data engineering,2013, 26(7):1763-1777.

[2] 孫曉燕.高級(jí)交互式遺傳算法理論與應(yīng)用[M]. 北京:科學(xué)出版社,2010:7-18.

[3] SORM D, RIMCHAROEN S. Web page template design using interactive genetic algorithm[C]//International Computer Science and Engineering Conference (ICSEC). Nakorn Pathom, Thailand: IEEE, 2013:201-206.

[4] 楊胡萍，李威仁，左士偉，等. 基于改進(jìn)遺傳算法的電力系統(tǒng)無(wú)功優(yōu)化[J]. 鄭州大學(xué)學(xué)報(bào)(工學(xué)版), 2015, 36(6):66-69.

[5] LIU X. Color mapping design from image to 3D product model[J]. Journal of mechanical engineering, 2009, 45(10):222-227.

[6] GARCIA-HERNANDEZ L, ARAUZO-AZOFRA A, SALAS-MORERA L, et al. Recycling plants layout design by means of an interactive genetic algorithm[J]. Intelligent automation and soft computing, 2013, 19(3):457-468.

[7] KOGA S, INOUE T, FUKUMOTO M. A proposal for intervention by user in interactive genetic algorithm for creation of music melody[C]//International Conference on Biometrics and Kansei Engineering. Tokyo, Japan: IEEE, 2013:129-132.

[8] DASS M V, ALI M M, ALI M R. Image retrieval using interactive genetic algorithm[C]//International Conference on Computational Science and Computational Intelligence. Las Vegas, USA:IEEE, 2014:215-220.

[9] 孫曉燕,陸宜娜,鞏敦衛(wèi),等. 基于CP-nets的偏好感知交互式遺傳算法及其個(gè)性化搜索[J]. 控制與決策, 2015,30(7):1153-1161.

[10] CLAYPOOL M, LE P, WASED M, et al. Implicit interest indicators[C]//Proceedings of the 6th International Conference on Intelligent User Interfaces. New York, USA:IEEE, 2001:33-40.

[11] BENAMOR N, DUBOIS D, GOUIDER H, et al. Possibilistic networks: a new setting for modeling preferences[M]. Berlin, Germany: Springer, 2014:1-7.

[12] CORNELIO C, GOLDSMITH J, MATTEI N, et al. Dynamic probabilistic CP-nets[C]//Multidisciplinary Workshop on Advances in Preference Handling. Chicago, USA:IEEE, 2013:1-7.

[13] BIGOT D, FAGIER H, MENGIN J, et al. Probabilistic conditional preference networks[J]. Computer science, 2013,19:72-81.

ProbabilisticConditionalPreferenceNetworkAssistedInteractiveGeneticAlgorithmandItsApplication

SUN Xiaoyan, ZHU Lixia, CHEN Yang

(School of Information and Control Engineering, China University of Mining & Technology, Xuzhou 221008, China)

Interactive evolutionary algorithms with user preference implicitly extracted from interactions of user were more powerful in alleviating user fatigue and improving the exploration in personalized search or recommendation. However, the uncertainties in user interactions and preferences have not been considered in the previous research, which might greatly impact the reliability of the extracted preference model, as well as the effective exploration of the evolution with that model. Therefore, an interactive genetic algorithm with probabilistic conditional preference networks (PCP-nets) was proposed, in which, the uncertainties were further figured out according to the interactions, and a PCP-net was designed to depict user preference model with higher accuracy by involving those uncertainties. First, the interaction time was adopted to mathematically describe the relationship between the interactions and user preference, and the reliability of the interaction time was further defined to reflect the interactive uncertainty. The preference function with evaluation uncertainty was established with the reliability of interaction time. Second, the preference weights on each interacted object were assigned on the basis of preference function and reliability. With these weights, the PCP-nets were designed and updated by involving the uncertainties into the preference model to improve the approximation. Third, a more accurate fitness function was delivered to assign fitness for the individuals. Last, the proposed algorithm was applied to a personalized book search and its superiority in exploration and feasibility was experimentally demonstrated.

interactive genetic algorithm; uncertainty; possibilitic conditional preference networks; personalized search

2017-05-18；

2017-08-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61473298)

孫曉燕(1978— )，女，江蘇徐州人，中國(guó)礦業(yè)大學(xué)教授，博士，主要從事智能優(yōu)化研究，E-mail:xysun78@126.com.

1671-6833(2017)06-0001-05

TP181

A

10.13705/j.issn.1671-6833.2017.06.001