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

李凌 袁昊劼

該文在一個求解Stackelberg-Nash均衡解的模糊模擬的二層遺傳算法基礎上，為模糊非合作博弈設計了一個基于模糊優先關系求解模糊均衡的的遺傳算法，并給出了求解最優模糊均衡的改進遺傳算法，并用一個實例驗證了算法的可行性。

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

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

一、模糊非合作博弈

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

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

，

則稱為的一個均衡局勢。

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

.

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

.

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

，

則稱局勢為的最優模糊均衡。

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

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

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

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

隨機選擇個局勢作為初始群體，

由定義4，可知衡量最優模糊均衡的指標函數為：

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

現在問題轉化為求的最大值。作適應函數：

計算概率

并以此概率分布從中隨機選一些染色體構成一個種群（集中可能重復選中的一個元素）。

因為前面采用了常規編碼，而局勢的變化隨每一個局中人策略選擇的變化而變化，所以選擇交配規則時，我們采用單親遺傳法。

從1到中隨機選取個數，對于每一個，將第個分量與第個分量交換當時，；得到新的，組成新的局勢。將中所有染色體進行上述交配，得到。

以某個較小的概率p發生變異，得到，令，，形成新的群體，循環計算。

當或者迭代次數達到某個次數時，終止程序。

簡單遺傳算法有可能不收斂到全局最優解，因此需要簡單遺傳算法作一點改動，每次記下當前最優解并在群體狀態最前增加一維存放當前最優解，則遺傳算法收斂到最優解。

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

現將模糊均衡的改進遺傳算法敘述如下：

步驟一：給定群體規模，初始群體；

步驟二：對群體中的每一個染色體計算它的適應函數

，；

步驟三：若停止規則滿足，則算法停止；否則，計算概率

，

以此概率分布從中隨機選一些染色體構成一個種群；

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

步驟五：以一個較小的概率p，使得一個染色體的一個基因發生變異，形成；在中記錄當前最優解，，形成一個新的群體；

返回步驟二。

三、實際應用

下面通過一個具體的實例來驗證一下算法的有效性。

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

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

四、小結

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

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

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

[3]王成山，吉興全.輸電網投資規劃的Nash均衡分析（二）[J].電力系統自動化，2002.26

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