模糊非合作博弈的算法研究

李凌 袁昊劼

該文在一個(gè)求解Stackelberg-Nash均衡解的模糊模擬的二層遺傳算法基礎(chǔ)上，為模糊非合作博弈設(shè)計(jì)了一個(gè)基于模糊優(yōu)先關(guān)系求解模糊均衡的的遺傳算法，并給出了求解最優(yōu)模糊均衡的改進(jìn)遺傳算法，并用一個(gè)實(shí)例驗(yàn)證了算法的可行性。

自20世紀(jì)90年代以來，科學(xué)技術(shù)和經(jīng)濟(jì)快速發(fā)展，市場開始全球化，企業(yè)面臨的競爭日趨激烈。技術(shù)的進(jìn)步和需求的多樣化，使產(chǎn)品壽命周期不斷縮短，因而企業(yè)面臨著縮短交貨期、提高產(chǎn)品質(zhì)量、降低成本和改進(jìn)服務(wù)的壓力。如何以更高的產(chǎn)品價(jià)值、更優(yōu)的產(chǎn)品質(zhì)量、更低廉的成本、更快捷的市場反應(yīng)速度和更滿意的服務(wù)與競爭者抗衡；如何占領(lǐng)盡可能大的市場份額，成為企業(yè)經(jīng)營戰(zhàn)略的核心，也成為企業(yè)面臨的重要問題。供應(yīng)鏈的產(chǎn)生改變了現(xiàn)代企業(yè)的競爭方式，使得企業(yè)間通過加強(qiáng)合作來提高競爭力，共同將利益蛋糕做大，建立一種“共贏”的戰(zhàn)略合作伙伴關(guān)系。在建立合作伙伴關(guān)系中，由于利益的原因，雙方之間往往存在著策略的對抗和競爭，或?qū)δ骋环N局面的對策選擇，因此須對建立供應(yīng)鏈合作伙伴關(guān)系采用非合作博弈的方法去分析。

現(xiàn)在非合作博弈在經(jīng)濟(jì)管理中已得到了廣泛的應(yīng)用，Nash均衡作為非合作博弈的一個(gè)重要概念，是所有應(yīng)用領(lǐng)域中希望得到的最優(yōu)狀態(tài)。雖然理論上已經(jīng)證明了它的存在性，但是并沒有給出求解Nash均衡的一般性算法。尤其是對規(guī)模較大的問題，現(xiàn)有的方法很難給出解。隨著現(xiàn)代優(yōu)化算法的發(fā)展，人們開始把遺傳算法引入到均衡求解中來。2001年，陳士俊等[1]提出了一種求解Nash均衡解的遺傳算法。仝凌云等[2]運(yùn)用雙種群自適應(yīng)遺傳算法解決了虛擬企業(yè)伙伴選擇的問題。王成山等[3]以改進(jìn)的遺傳算法為基礎(chǔ)，提出了一種適用于輸電網(wǎng)投資博弈的均衡分析方法。以上這些算法都是對經(jīng)典的Nash均衡設(shè)計(jì)的。2004年，曾玲等[4]針對產(chǎn)品價(jià)格為模糊變量的一般遞階資源分配問題，設(shè)計(jì)了一個(gè)求解Stackelberg-Nash均衡解的基于模糊模擬的二層遺傳算法。本文將在此基礎(chǔ)上為模糊非合作博弈設(shè)計(jì)一個(gè)求解模糊均衡的基于模糊優(yōu)先關(guān)系的遺傳算法，并通過一個(gè)實(shí)例進(jìn)行驗(yàn)證。

一、模糊非合作博弈

定義1局中人的集合為，局中人的策略集為，當(dāng)每個(gè)局中人選定一個(gè)策略（）后，就形成了博弈的一個(gè)局勢；對于每一個(gè)局勢 ，局中人 有一個(gè)模糊支付函數(shù)，則為一個(gè)模糊非合作博弈。

定義2設(shè)是模糊非合作博弈的一個(gè)局勢，如果

，

則稱為的一個(gè)均衡局勢。

定義3對于模糊非合作博弈，為局中人的模糊占優(yōu)策略的隸屬度為

.

定義4對于模糊非合作博弈，局勢S為的模糊均衡的隸屬度為

.

定義5對于模糊非合作博弈，如果對隸屬函數(shù)有

，

則稱局勢為的最優(yōu)模糊均衡。

二、求解模糊均衡的遺傳算法

對于模糊非合作博弈，其最優(yōu)模糊均衡滿足。顯然這是一個(gè)組合最優(yōu)化問題，隨著局中人數(shù)量以及策略集元素的增加，求解最優(yōu)模糊均衡的計(jì)算量是指數(shù)增長的。這是一個(gè)NP-hard問題。

我們將每個(gè)局勢看作自然界中的一個(gè)生物體，每個(gè)局中人的策略看作是生物體的不同染色體。正如生物體的生存性質(zhì)與染色體組的基因關(guān)系，最優(yōu)解也將是算法過程中的最優(yōu)模糊均衡，從而獲得有限n人非合作模糊博弈的最優(yōu)模糊均衡。在此我們假設(shè)所有局中人均有m個(gè)策略。

首先我們對問題進(jìn)行編碼。根據(jù)非合作模糊博弈的特點(diǎn)，本文采用常規(guī)碼，對于局中人，其策略集為，向量是局中人的決策向量，其中表示局中人沒有選取第個(gè)策略，表示局中人選擇了第個(gè)策略。所有局中人的選擇構(gòu)成了博弈的一個(gè)局勢，則局勢可以用向量表示。

隨機(jī)選擇個(gè)局勢作為初始群體，

由定義4，可知衡量最優(yōu)模糊均衡的指標(biāo)函數(shù)為：

又由定義2，3，局勢為模糊均衡的隸屬度是：

現(xiàn)在問題轉(zhuǎn)化為求的最大值。作適應(yīng)函數(shù)：

計(jì)算概率

并以此概率分布從中隨機(jī)選一些染色體構(gòu)成一個(gè)種群（集中可能重復(fù)選中的一個(gè)元素）。

因?yàn)榍懊娌捎昧顺Ｒ?guī)編碼，而局勢的變化隨每一個(gè)局中人策略選擇的變化而變化，所以選擇交配規(guī)則時(shí)，我們采用單親遺傳法。

從1到中隨機(jī)選取個(gè)數(shù)，對于每一個(gè)，將第個(gè)分量與第個(gè)分量交換當(dāng)時(shí)，；得到新的，組成新的局勢。將中所有染色體進(jìn)行上述交配，得到。

以某個(gè)較小的概率p發(fā)生變異，得到，令，，形成新的群體，循環(huán)計(jì)算。

當(dāng)或者迭代次數(shù)達(dá)到某個(gè)次數(shù)時(shí)，終止程序。

簡單遺傳算法有可能不收斂到全局最優(yōu)解，因此需要簡單遺傳算法作一點(diǎn)改動(dòng)，每次記下當(dāng)前最優(yōu)解并在群體狀態(tài)最前增加一維存放當(dāng)前最優(yōu)解，則遺傳算法收斂到最優(yōu)解。

改進(jìn)后的遺傳算法其主要特征是：進(jìn)化的每一代，記錄前面各代遺傳的最優(yōu)解并存放在群體的第一位，這個(gè)染色體只起到一個(gè)記錄的功能不參加遺傳運(yùn)算。

現(xiàn)將模糊均衡的改進(jìn)遺傳算法敘述如下：

步驟一：給定群體規(guī)模，初始群體；

步驟二：對群體中的每一個(gè)染色體計(jì)算它的適應(yīng)函數(shù)

，；

步驟三：若停止規(guī)則滿足，則算法停止；否則，計(jì)算概率

，

以此概率分布從中隨機(jī)選一些染色體構(gòu)成一個(gè)種群；

步驟四：通過單親遺傳法進(jìn)行交配，交配概率為，得到；

步驟五：以一個(gè)較小的概率p，使得一個(gè)染色體的一個(gè)基因發(fā)生變異，形成；在中記錄當(dāng)前最優(yōu)解，，形成一個(gè)新的群體；

返回步驟二。

三、實(shí)際應(yīng)用

下面通過一個(gè)具體的實(shí)例來驗(yàn)證一下算法的有效性。

假設(shè)現(xiàn)有同行業(yè)的兩個(gè)制造商甲和乙，他們希望建立供應(yīng)鏈的方式來提高自身的競爭力，在建立合作伙伴關(guān)系的過程中，各自有3個(gè)可供選擇的供應(yīng)商，他們的選擇結(jié)果是互相影響的，根據(jù)不同的情況，甲和乙的收益矩陣如下：

遺傳算法的參數(shù)選擇：群體規(guī)模=3；交配概率為0.5；變異概率為0.2；算法終止條件為：迭代次數(shù)達(dá)到100或者當(dāng)均衡隸屬度高于0.5算法停止。通過計(jì)算，我們得到上述問題的最優(yōu)均衡局勢為甲選擇策略3，乙選擇策略3，即局勢（3，3）為模糊均衡的隸屬度為0.214。

四、小結(jié)

本文先給出了具有模糊支付的非合作博弈的定義，以及求解模糊均衡的定義，但是發(fā)現(xiàn)當(dāng)局中人數(shù)量較多，或策略較多時(shí)，依靠枚舉法進(jìn)行求解是非常繁瑣的，這是一個(gè)NP-hard問題。為了求得最優(yōu)模糊均衡，在一個(gè)求解Stackelberg-Nash均衡解的基于模糊模擬的二層遺傳算法的基礎(chǔ)上，為模糊非合作博弈設(shè)計(jì)了一個(gè)求解模糊均衡的基于模糊優(yōu)先關(guān)系的遺傳算法，并給出了求解最優(yōu)模糊均衡的改進(jìn)遺傳算法，最后通過一個(gè)實(shí)例進(jìn)行了驗(yàn)證。

[1]陳士俊，孫永廣，吳宗鑫.一種求解Nash均衡解的遺傳算法[J].系統(tǒng)工程，2001.19

[2]仝凌云，陳增強(qiáng)，袁著祉，安利平.虛擬企業(yè)伙伴選擇的雙種群自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程，2006.32

[3]王成山，吉興全.輸電網(wǎng)投資規(guī)劃的Nash均衡分析（二）[J].電力系統(tǒng)自動(dòng)化，2002.26

[4]曾玲，高金伍.帶模糊參數(shù)的遞階資源分配問題[J].系統(tǒng)工程理論與實(shí)踐，2004.11