王高飛，鄧立治，田金信，李 梅

(1.哈爾濱工業(yè)大學(xué)管理學(xué)院，黑龍江哈爾濱150001;2.黑龍江科技學(xué)院經(jīng)濟(jì)管理學(xué)院，黑龍江哈爾濱150027;3.北京科技大學(xué)經(jīng)濟(jì)管理學(xué)院，北京100083)

談判是一個(gè)動(dòng)態(tài)過(guò)程，在這個(gè)過(guò)程中，兩個(gè)或多個(gè)具有不同標(biāo)準(zhǔn)、約束和偏好的參與者針對(duì)一個(gè)交易的相關(guān)條目共同達(dá)成一個(gè)可以相互接受的協(xié)定［1］。按談判機(jī)制將談判分為:一對(duì)一談判(雙邊談判)、一對(duì)多談判和多對(duì)多談判。其中，一對(duì)多談判被看作是多個(gè)并發(fā)的雙邊談判，多對(duì)多談判可以通過(guò)一對(duì)多談判擴(kuò)展得到［2］。而多屬性談判更具實(shí)用性，因此筆者選定雙邊多屬性談判求解模型作為研究對(duì)象。目前，對(duì)于網(wǎng)上談判模型求解的代表性研究方法有:博弈論模型［3］、以效用函數(shù)為基礎(chǔ)的多屬性決策模型［4－5］、對(duì)策分析法［6］、解決沖突的圖形模型［7－8］和基于遺傳算法的解支持方法［9－10］等。這些方法在一定程度上推動(dòng)了談判理論研究的進(jìn)展，但仍沒(méi)有完全解決多屬性談判中存在的以下問(wèn)題:①多數(shù)算法采用線(xiàn)性函數(shù)，雖然簡(jiǎn)化了問(wèn)題，但存在局部交易的退化和重要屬性的作用被埋沒(méi)等副作用［11］;②在非線(xiàn)性函數(shù)的復(fù)雜合同研究中，談判存在著囚徒困境的問(wèn)題;③在談判求解過(guò)程中，忽略了屬性之間的依賴(lài)關(guān)系［12］;④由于屬性間復(fù)雜依賴(lài)關(guān)系與用戶(hù)偏好獲取的困難，使效用函數(shù)表達(dá)成為難題。

筆者針對(duì)上述問(wèn)題，構(gòu)建了BP神經(jīng)網(wǎng)絡(luò)與遺傳算法的聯(lián)合算法(BPNN－GA算法)，該算法充分利用遺傳算法全局優(yōu)化與BP神經(jīng)網(wǎng)絡(luò)非線(xiàn)性映射的優(yōu)點(diǎn)，有效克服以上不足，求解談判雙方效用最大的談判方案，實(shí)現(xiàn)雙方的共贏。

1 雙邊多屬性談判決策模型

雙邊多屬性談判問(wèn)題可以表述為:買(mǎi)方與賣(mài)方對(duì)雙方關(guān)注的N項(xiàng)屬性的各種可能方案進(jìn)行談判，直到達(dá)成一致或談判失敗。對(duì)于每種可能的方案，買(mǎi)賣(mài)雙方都有一定的效用評(píng)價(jià)，談判問(wèn)題的目標(biāo)就是尋求使雙方效用最大的方案。該問(wèn)題定義如下:

定義1 用i表示需要談判的屬性項(xiàng)，其中i=1，2，…，n。

定義2 用xij表示第i項(xiàng)屬性的第j種可能取值，j=1，2，…，mi;xij∈Di，Di為第 i項(xiàng)屬性的取值范圍。談判方案可用向量 X=［x1j，x2j，…，xnj］T表示。

定義3 在談判中，談判雙方對(duì)當(dāng)前方案的效用評(píng)價(jià)由各自事先訓(xùn)練收斂的BP神經(jīng)網(wǎng)絡(luò)進(jìn)行。網(wǎng)絡(luò)輸入向量為 X=［x1j，x2j，…，xnj］T，網(wǎng)絡(luò)輸出值可作為雙方對(duì)當(dāng)前方案的各自效用評(píng)價(jià)值，可表示為Ub和Us。則對(duì)談判問(wèn)題的目標(biāo)函數(shù)表述為:

2 雙邊多屬性談判的BPNN－GA算法

2.1 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)模型是神經(jīng)網(wǎng)絡(luò)中比較成熟、應(yīng)用最廣泛的一種神經(jīng)網(wǎng)絡(luò)模型。它是基于誤差反向傳播算法的多層前饋型神經(jīng)網(wǎng)絡(luò)。BP神經(jīng)網(wǎng)絡(luò)具備任意精度的函數(shù)逼近能力，具有自組織、自適應(yīng)、自學(xué)習(xí)、高度非線(xiàn)性映射性、泛化性和容錯(cuò)性等優(yōu)點(diǎn)。假定網(wǎng)絡(luò)有m個(gè)隱含層，輸入層X(jué)=(x1，x2，…)，輸出層Y=(y1，y2，…)，第s層節(jié)點(diǎn)數(shù)為ns，ysk為s層節(jié)點(diǎn)k的輸出，Wsk是上一層與第s層節(jié)點(diǎn)k的連接權(quán)重，如式(2)和式(3)所示。一般而言，神經(jīng)元常用Sigmoid函數(shù)，如式(4)所示。

基于BP神經(jīng)網(wǎng)絡(luò)的上述特點(diǎn)，使之在具有非線(xiàn)性函數(shù)復(fù)雜合同談判中的運(yùn)用成為可能。神經(jīng)網(wǎng)絡(luò)輸出是買(mǎi)方或賣(mài)方對(duì)某談判方案的評(píng)價(jià)值，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)簡(jiǎn)化為如圖1所示的3層網(wǎng)絡(luò)的單維輸出，其中U為輸出的評(píng)價(jià)值。

2.2 遺傳算法與BPNN－GA算法求解模型

遺傳算法(genetic algorithm，GA)是模擬達(dá)爾文遺傳選擇和自然淘汰生物進(jìn)化過(guò)程的計(jì)算模型?；谶z傳算法進(jìn)行優(yōu)化求解，需要進(jìn)行編碼、確定初始群體、計(jì)算適應(yīng)度、選擇、交叉、變異以及終止等操作。遺傳算法具有簡(jiǎn)單、魯棒性強(qiáng)、全局最優(yōu)性、可并行性及高效率等優(yōu)點(diǎn)。由于它不受搜索空間限制性假設(shè)的約束，不要求諸如連續(xù)性、導(dǎo)數(shù)存在和單峰等假設(shè)，能夠從離散的、多極值的、含有噪音的高維問(wèn)題中以較大的概率找到全局最優(yōu)解，因此在解決多屬性談判中具有廣闊的應(yīng)用前景。

傳統(tǒng)的遺傳算法的適應(yīng)度函數(shù)必須是具有明確數(shù)學(xué)表達(dá)式的函數(shù)方程，但實(shí)際上，每個(gè)談判者的偏好不同，方案中各屬性間依賴(lài)關(guān)系較復(fù)雜，如何確定談判各屬性值與談判者的滿(mǎn)意度(效用)之間的顯式(可以用數(shù)學(xué)方程明確表示)函數(shù)關(guān)系是非常困難的。筆者針對(duì)多屬性談判特點(diǎn)，將BP神經(jīng)網(wǎng)絡(luò)用于談判提議方案的效用評(píng)價(jià)，以談判雙方效用評(píng)價(jià)值之積的目標(biāo)函數(shù)作為遺傳算法的適用度函數(shù)，形成求解此類(lèi)談判問(wèn)題的BPNN－GA算法。將上述的思路轉(zhuǎn)化成模型，如圖2和圖3所示。

圖1 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

圖2 目標(biāo)函數(shù)模型

圖3 基于BP－GA算法的談判問(wèn)題求解流程

2.3 BPNN－GA算法求解過(guò)程

2.3.1 BP網(wǎng)絡(luò)樣本選取與數(shù)據(jù)處理

在談判前雙方就所要談判的款項(xiàng)(屬性)i具體類(lèi)別與每項(xiàng)條款的取值范圍Di達(dá)成一致，并據(jù)此準(zhǔn)備BP網(wǎng)絡(luò)的訓(xùn)練樣本。由計(jì)算機(jī)在取值范圍內(nèi)隨機(jī)生成多組數(shù)據(jù)并遵循適度均勻原則，由專(zhuān)家給出對(duì)應(yīng)評(píng)價(jià)值。對(duì)于樣本數(shù)據(jù)的處理，輸入數(shù)據(jù)采用線(xiàn)性刻度轉(zhuǎn)換方法進(jìn)行歸一化，如式(5)所示。x*為歸一化后的樣本數(shù)據(jù)，輸出數(shù)據(jù)為百分制得分，訓(xùn)練時(shí)按分?jǐn)?shù)/100進(jìn)行歸一化處理。

2.3.2 BP神經(jīng)網(wǎng)絡(luò)創(chuàng)建與訓(xùn)練

在使用Matlab工具箱創(chuàng)建BP網(wǎng)絡(luò)時(shí)，采用newff函數(shù)設(shè)計(jì)3層BP網(wǎng)絡(luò)，神經(jīng)元的傳輸函數(shù)采用logsig函數(shù)，如式(4)所示，網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。BP網(wǎng)絡(luò)訓(xùn)練方法很多，筆者采用LM算法。LM算法是由高斯－牛頓法演變而來(lái)的，該算法極大提高了收斂的速度，彌補(bǔ)了標(biāo)準(zhǔn)BP算法收斂速度慢的不足，克服了牛頓法易振蕩發(fā)散的缺點(diǎn)。

2.3.3 遺傳算法的步驟

(1)編碼與解碼。針對(duì)談判問(wèn)題的實(shí)際情況，采用二進(jìn)制編碼的方法，但需考慮精度。對(duì)于給定區(qū)間［p，q］，設(shè)二進(jìn)制編碼長(zhǎng)度為l，則任何一個(gè)變量可表示為:

對(duì)應(yīng)二進(jìn)制編碼p1，p2，…，pl，二進(jìn)制編碼與實(shí)際變量的最大誤差為(q－p)/2l。解碼是編碼的逆過(guò)程。由于定義2中談判方案可用向量X=［x1j，x2j，…，xnj］T表示，則每個(gè)染色體對(duì)應(yīng)一個(gè)談判方案，染色體編碼可以用n組二進(jìn)制編碼表示。

(2)確定適應(yīng)度函數(shù)。適應(yīng)度是評(píng)價(jià)群體中個(gè)體優(yōu)劣的函數(shù)，其值越大，個(gè)體越有可能被選中進(jìn)行交叉、變異操作，個(gè)體特性便越有可能遺傳到下一代。由式(1)可直接轉(zhuǎn)化為適應(yīng)度函數(shù)如式(7)所示，顯然是要求使適應(yīng)度函數(shù)值最大的方案，如圖2所示。

Ub是買(mǎi)方對(duì)談判方案向量X輸入買(mǎi)方BP神經(jīng)網(wǎng)絡(luò)NetB的輸出評(píng)價(jià)值;Us是賣(mài)方對(duì)談判方案向量X輸入賣(mài)方BP神經(jīng)網(wǎng)絡(luò)NetS的輸出評(píng)價(jià)值。具體映射關(guān)系見(jiàn)式(4)和圖1。

(3)確定選擇、交叉和變異算子。選擇算子是遺傳算法用來(lái)對(duì)群體中個(gè)體進(jìn)行優(yōu)勝劣汰的操作，并不生成新的個(gè)體，選擇算子采用輪盤(pán)選擇與最佳保留策略。交叉算子是指兩個(gè)相互配對(duì)的染色體按某種方法相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力，這里采用離散重組交叉算子。為避免陷入局部最大值，變異算子采用離散變異算子。

(4)終止規(guī)則。由于適應(yīng)度目標(biāo)值無(wú)法事先確定，并且多次迭代容易影響計(jì)算時(shí)間。因此筆者采用設(shè)定未改善當(dāng)前解的最大代數(shù)，如設(shè)未改善當(dāng)前最優(yōu)解100代后終止運(yùn)算。

3 談判實(shí)例

企業(yè)A與企業(yè)B就企業(yè)B銷(xiāo)售的某種商品進(jìn)行網(wǎng)上談判。雙方選定的談判商品屬性與取值范圍為:商品的單價(jià)(4～5萬(wàn)元)，商品的質(zhì)量(100%～90%優(yōu)良率)以及商品交付時(shí)間(12～72 h);企業(yè)A與企業(yè)B的歸一化后樣本數(shù)據(jù)如表1所示。為簡(jiǎn)化算法說(shuō)明，表1中輸入數(shù)據(jù)由計(jì)算機(jī)系統(tǒng)隨機(jī)生成并按式(5)進(jìn)行歸一化處理，當(dāng)然在實(shí)際應(yīng)用中可由各企業(yè)自行準(zhǔn)備訓(xùn)練數(shù)據(jù)。輸出數(shù)據(jù)為企業(yè)A與企業(yè)B的專(zhuān)家組針對(duì)系統(tǒng)生成的不同方案的百分制打分值，并除以100進(jìn)行歸一化。該處選擇了35組訓(xùn)練樣本和5組檢驗(yàn)樣本。如訓(xùn)練精度未達(dá)到要求則增加訓(xùn)練樣本數(shù)量。經(jīng)訓(xùn)練后，企業(yè)A的BP神經(jīng)網(wǎng)絡(luò)NetB訓(xùn)練結(jié)果如圖4所示，企業(yè)B的NetS訓(xùn)練結(jié)果如圖5所示。由檢驗(yàn)樣本得到的仿真結(jié)果與實(shí)際評(píng)價(jià)結(jié)果的平均誤差分別為3.2%和2.8%，小于預(yù)期可接受誤差5%，訓(xùn)練達(dá)到預(yù)定要求，可以用于談判運(yùn)算。BPNN－GA算法的適應(yīng)度值與種群均值經(jīng)128代進(jìn)化后終止運(yùn)算，結(jié)果如圖6所示。最終計(jì)算結(jié)果如表2所示。

表1 歸一化后的樣本數(shù)據(jù)

圖4 NetB訓(xùn)練過(guò)程

圖5 NetS訓(xùn)練過(guò)程

圖6 經(jīng)過(guò)128次迭代后的優(yōu)化解性能跟蹤

表2 運(yùn)算結(jié)果

從表2的運(yùn)算結(jié)果可以看出，算法在28代達(dá)到最大值，迭代100代后無(wú)改善，程序終止。最終的談判方案為:商品價(jià)格4.519 1萬(wàn)元，商品質(zhì)量為92.752%的優(yōu)良率，交貨時(shí)間為50.676 h。企業(yè)A的滿(mǎn)意度為50.57%，企業(yè)B的滿(mǎn)意度為54.57%，談判的目標(biāo)函數(shù)最大值(適應(yīng)度函數(shù)最大值)為0.276 0。

4 結(jié)論

針對(duì)原有線(xiàn)性效用函數(shù)假設(shè)的局限性，筆者提出了BPNN－GA雙邊多屬性談判求解算法，通過(guò)基于樣本數(shù)據(jù)的BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練，逼近具有復(fù)雜屬性依賴(lài)關(guān)系的非線(xiàn)性效用函數(shù)映射，合理避免了對(duì)非線(xiàn)性效用函數(shù)方程的結(jié)構(gòu)設(shè)計(jì)與參數(shù)求解難題。放松了原有方法的約束條件，為雙邊多屬性談判提供了更具一般性的求解方法，為該類(lèi)問(wèn)題研究提供了新的思路。同時(shí)，將雙邊優(yōu)化模型進(jìn)行適當(dāng)拓展可以用于一對(duì)多談判和多對(duì)多談判，具有廣闊的應(yīng)用前景。當(dāng)然，由于該問(wèn)題的復(fù)雜性以及算法的初次引入，新算法還有較大的改進(jìn)空間。例如，進(jìn)一步提高BP神經(jīng)網(wǎng)絡(luò)逼近精度，合理選擇樣本數(shù)據(jù)，特別是為降低談判雙方的評(píng)價(jià)工作量，如何在小樣本數(shù)據(jù)情況下實(shí)現(xiàn)較高精度求解等將是下一步研究的重點(diǎn)。

［1］JENNINGSN R，F(xiàn)ARATIN P，LOMUSCIO A R，et al.Automated negotiation:prospectsmethods and challenges［J］.International Journal of Group Decision and Negotiation，2001，10(2):199－215.

［2］RAHWAN I，KOWALCZYK R，PHAM H H.Intelligent agents for automated one－to－many e－commerce negotiation［C］//Twenty－Fifth Australian Computer Science Conference.Melbourne:［s.n.］，2002:197－204.

［3］CHE Y K.Design competition throughmultidimensional auctions［J］.RAND Journal of Economics，1993，24(4):668－680.

［4］MARTIN B.An experimental analysis ofmulti－attribute auctions［J］.Decision Support Systems，2000，29(3):249－268.

［5］FARATIN P，SIERRA C，JENNINGSN R.Using similarity criteria to make negotiation trade－offs in automated negotiations［J］.Artificial Intelligence，2002，142(2):205－237.

［6］TEICH JE，WALLENIUSH，WALLENIUS J.Advances in negotiation science［J］.Transactions in Operational Research，1994(6):55－94.

［7］LIK W，HIPELKW，KILGOUR D M，et al.Preference uncertainty in the graph model for conflict resolution［J］.IEEE Transaction Systems，Man and Cybernetics，2004，34(4):507－520.

［8］孫華梅，李一軍，曹榮增，等.基于約束放松的電子商務(wù)協(xié)同談判模型［J］.運(yùn)籌與管理，2008，17(4):132－137.

［9］李玥，馮玉強(qiáng)，王衍華，等.遺傳算法在網(wǎng)上談判支持系統(tǒng)中的應(yīng)用研究［J］.系統(tǒng)工程理論與實(shí)踐，2002(6):87－92.

［10］董婷婷，馮玉強(qiáng).基于辯論的談判解支持研究［J］.預(yù)測(cè)，2009(2):76－80.

［11］DE PAULA G E，RAMOS F S，RAMALHO G L.Bilateral negotiation model for agent－mediated electronic commerce［C］//AMEC 2000.Berlin:Springer，2001:1－14.

［12］FUJITA K，ITO T，KLEINM.Finding nash bargaining solutions for multi－issue negotiations:a preliminary result［C］//Proceedings of the 1st International Working Conference on Human Factors and Computational Models in Negotiation.New York:ACM，2009:63－70.