基于模糊粒子群優(yōu)化算法的雙邊多議題協(xié)商模型

周松華

?

基于模糊粒子群優(yōu)化算法的雙邊多議題協(xié)商模型

周松華

（井岡山大學(xué)電子與信息工程學(xué)院，江西，吉安 343009 ）

針對電子商務(wù)應(yīng)用，提出了一種基于模糊粒子群優(yōu)化算法的雙邊多議題協(xié)商模型。該模型以追求協(xié)商雙方聯(lián)合效用最大化為前提，通過粒子群在對手提議和自身議題理想值域之間進(jìn)行快速有效搜索出最優(yōu)解或近似最優(yōu)解生成反提議；從而促使協(xié)商實(shí)現(xiàn)“雙贏”。實(shí)驗(yàn)分析表明，該模型能有效提高協(xié)商效率。

多Agent系統(tǒng)；自動(dòng)協(xié)商；粒子群算法

基于Agent的自動(dòng)協(xié)商是多Agent系統(tǒng)（MAS，Multi-Agent System）領(lǐng)域的一個(gè)研究熱點(diǎn)，近年來已經(jīng)取得了許多成果。其中有關(guān)電子商務(wù)環(huán)境下的自動(dòng)協(xié)商研究中，具有代表性研究有：（1）基于經(jīng)驗(yàn)學(xué)習(xí)的自動(dòng)化協(xié)商模型[1-2]，使用基于實(shí)例的推理技術(shù)將以前的經(jīng)驗(yàn)和策略應(yīng)用于當(dāng)前的協(xié)商決策中，提供了可調(diào)整的協(xié)商策略來對協(xié)商過程進(jìn)行動(dòng)態(tài)控制；（2）面向目標(biāo)的自動(dòng)化協(xié)商模型[3]，Agent以自己的信息狀態(tài)和接收到的提議，利用自己的學(xué)習(xí)系統(tǒng)來產(chǎn)生下一刻的反提議，通過不斷的學(xué)習(xí)使自身的行為更加理性，提高協(xié)商效率。（3）側(cè)重消解協(xié)商僵局的協(xié)商模型[4-6]，通過動(dòng)態(tài)放寬引起協(xié)商僵局的相關(guān)議題的保留值，進(jìn)行協(xié)商議題保留值的等效置換以保證不降低協(xié)商效用并達(dá)到協(xié)商一致。

本文的研究是在基于協(xié)商歷史資源的自治協(xié)商前期研究基礎(chǔ)上，引入粒子群優(yōu)化算法(PSO, Particle swarm optimization)作為協(xié)商指導(dǎo)策略，提出一種基于模糊粒子群優(yōu)化算法[10]的雙邊多議題協(xié)商模型FPSONEC(fuzzy particle swarm optimization negotiation E-commerce)。PSO算法[7-9]是Kennedy等人于1995年提出的一種模擬鳥群覓食行為發(fā)展起來的智能進(jìn)化算法，粒子群的每次迭代能產(chǎn)生一組非劣解，及其適合擴(kuò)展來求解目標(biāo)優(yōu)化問題。而協(xié)商以獲取自身最大利益為目標(biāo)，通過對相關(guān)議題反復(fù)協(xié)商以達(dá)到“雙贏”的局面，即雙方在一個(gè)共同的協(xié)商數(shù)學(xué)模型中尋找使雙方利益最大化的最優(yōu)解。本文提出的協(xié)商模型將協(xié)商過程轉(zhuǎn)化為一個(gè)多目標(biāo)優(yōu)化問題，通過粒子群在指定域范圍內(nèi)搜索，獲得pareto最優(yōu)解集，生成反提議；促使協(xié)商Agent能最大限度地達(dá)到協(xié)商的滿意解甚至最優(yōu)解,并且提高協(xié)商的效率。

1 自動(dòng)協(xié)商模型

1.1 FPSONEC模型定義

限時(shí)條件下，F(xiàn)PSONEC模型整體形式化描述為一個(gè)六元組：FPSONEC = <，，，，，>，各元組分別定義為：

協(xié)商參與者集合={1，2}；1為買方2為賣方。

1.2 基于FPSO的協(xié)商策略

理想的協(xié)商“雙贏”局面要求協(xié)商雙方在追求自身效用最大化同時(shí)還能達(dá)到協(xié)商雙方聯(lián)合效用最大。在信息保密和先驗(yàn)知識未知的環(huán)境下，本模型中僅買方Agent采用FPSO算法，在基于事例推理技術(shù)，從協(xié)商歷史案例中學(xué)習(xí)獲得對手的近似協(xié)商偏好，以預(yù)測對方效用。

1.2.1 FPSO算法

針對協(xié)商過程的不確定性，結(jié)合模糊理論對基本粒子群優(yōu)化算法（PSO）進(jìn)行改進(jìn)，對慣性權(quán)值和粒子的位置更新進(jìn)行模糊處理，將全局最優(yōu)值用所有粒子的個(gè)體最優(yōu)的加權(quán)平均值取代，使得粒子能夠通過更多的信息來調(diào)整自己的飛行方向和速度，算法的改進(jìn)能有效解決陷入局部最優(yōu)的缺點(diǎn)，提高算法在協(xié)商議題值域內(nèi)的搜索精度。

改進(jìn)的模糊粒子群優(yōu)化算法（FPSO）中每個(gè)粒子根據(jù)以下公式（1），（2）調(diào)整自己的飛行速度和方向：

1.2.2 協(xié)商優(yōu)化數(shù)學(xué)模型描述

編碼方案：種群中的每一個(gè)粒子代表要協(xié)商的議題值向量，

Nash提出兩個(gè)Agent協(xié)商的最優(yōu)結(jié)果是雙方效用的乘積取最大化，協(xié)商過程買方Agent啟動(dòng)FPSO算法，粒子群在對方提議值和自身理想議題值間范圍內(nèi)搜索出能滿足聯(lián)合效用（公式3）最大化目標(biāo)的最優(yōu)解或近似最優(yōu)解；作為本輪反提議。公式（4），（5）為協(xié)商雙方Agent所采用的多議題整合效用函數(shù)進(jìn)行提議評價(jià)。

1.2.3 模型協(xié)商算法

協(xié)商開始，雙方以協(xié)商議題值提議的方式進(jìn)行協(xié)商交互，買方Agent接收到賣方Agent初始提議后，整個(gè)協(xié)商過程如圖1所示：

圖1 協(xié)商流程圖

2 仿真實(shí)驗(yàn)及分析

表1 協(xié)商參數(shù)

在協(xié)商過程中啟動(dòng)FPSO算法作為協(xié)商策略產(chǎn)生反提議，粒子群規(guī)模選擇20，每個(gè)子群的慣性權(quán)重都為1.49，最大進(jìn)化代數(shù)為100，粒子群的c1,c2均取為2。對協(xié)商策略進(jìn)行matlab編程，并對其有效性進(jìn)行驗(yàn)證。

本文所采用的實(shí)驗(yàn)指標(biāo)包括協(xié)商過程中信息交換輪數(shù)（nego-rounds），協(xié)商過程雙方聯(lián)合效用，實(shí)驗(yàn)結(jié)果如圖2。

圖2 協(xié)商聯(lián)合效用分析

本次實(shí)驗(yàn)案例協(xié)商在基于FPSONEC模型上經(jīng)過4輪即協(xié)商成功，聯(lián)合效用為0.45，買方和賣方的效用分別為0.68，0.66，基本達(dá)到各自的理想效用。

在基于資源的協(xié)商和FPSONEC兩個(gè)模型上分別選取其他12個(gè)實(shí)驗(yàn)案例的仿真驗(yàn)證統(tǒng)計(jì)結(jié)果如表2所示。

表2 兩種模型的協(xié)商效率比較

Table.2 The comparison of Two models ' negotiation efficiency

FPSONEC模型在產(chǎn)生反提議中充分考慮了對方提議和自身最優(yōu)提議值，以積極的協(xié)商態(tài)度追求“雙贏”為目標(biāo)。實(shí)驗(yàn)表明FPSONEC協(xié)商模型相對基于資源的電子商務(wù)協(xié)商系統(tǒng)有效的提高了協(xié)商效率。

3 結(jié)論

FPSONEC模型在基于案例資源推理的基礎(chǔ)上引入粒子群優(yōu)化算法進(jìn)行協(xié)商過程控制。并通過實(shí)驗(yàn)驗(yàn)證了其相對于單一的依賴協(xié)商歷史案例資源指導(dǎo)協(xié)商在效率上有所提高。但本模型在粒子群搜索域空間限制在對方提議值和自身理想提議值區(qū)間進(jìn)行，當(dāng)對方提議值超出自身最大值時(shí)搜索最優(yōu)值存在溢出現(xiàn)象，導(dǎo)致協(xié)商失敗。故模型的后期優(yōu)化中如何規(guī)避協(xié)商陷入僵局及消解僵局工作有待于做更多的深入研究。

[1] 楊清平. 蒲國林. 基于交互歷史的多Agent自動(dòng)協(xié)商研究[J].計(jì)算機(jī)科學(xué),2008,35(9):226-229.

[2] 李健利. 使用案例推理的協(xié)商策略研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(8):119-121.

[3] 王黎明.黃厚寬.一個(gè)基于多階段的多Agent多問題協(xié)商框架[J].計(jì)算機(jī)研究與發(fā)展，2005,42（11）：1849-1855.

[4] 彭志平,陳珂. 一種消解協(xié)商僵局的多目標(biāo)粒子群優(yōu)化算法[J].電子學(xué)報(bào),2007,35(8):1452-1457.

[5] 王黎明,沈揚(yáng). 協(xié)商僵局的策略研究[J].計(jì)算機(jī)應(yīng)用，2010,30(6):1519-1522.

[6] 張慧 .基于PSO的協(xié)商僵局消解機(jī)制的研究[D]，太原:太原理工大學(xué), 2008.

[7] 周松華.歐陽春娟,自適應(yīng)模糊的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(33):46-48.

[8] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]. Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya，1995:39-43.

[9] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proceedings IEEE International Conference on Neural Net-works[C].Piscataway:IEEE Press,1995:1942-1948.

[10] Kennedy J, Eberhart R C. Swarm Intelligence[M]. SiliconValley:Morgan Kaufmann Publishers,2001.

[11] 周松華. 基于資源的電子商務(wù)自動(dòng)協(xié)商模型研究[D].廣州:華南師范大學(xué),2005.

RESEARCH ON BILATERAL MULTI-ISSUE NEGOTIATION MODEL BASED ON FPSO

ZHOU Song-hua

(School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China)

An autonomous negotiation model based on fuzzy particle swarm optimization (FPSO) is proposed in the application of E-commerce. The model is used to pursue negotiations joint utility maximization. The win-win negotiation is achieved and the counter proposal is generated based on the optimal solution or approximate optimal solution, which is provided by the quickly and efficiently search of particle swarm optimization between rival proposal and its’ issues ideal. The experimental analysis shows that the model can effectively improves the efficiency of negotiation.

multi-agent system; autonomous negotiation; particle swarm optimization

1674-8085(2014)01-0051-04

TP393.08

A

10.3969/j.issn.1674-8085.2014.01.011

2013-10-23；

2013-12-09

江西省教育廳科學(xué)技術(shù)研究項(xiàng)目(GJJ13553)

周松華(1977-)，女，江西吉安人，副教授，碩士，主要從事智能算法及應(yīng)用，電子商務(wù)研究(E-mail:zhousonghua@jgsu.edu.cn).