基于增強型差分進化算法求解廣義Nash均衡問題

Solving generalized Nash equilibrium problem based on enhanced differential evolutionary algorithm

Wang Kaia，b，Jia Wenshenga，bt （a.Collgeoftsamp;istis，rocalybotofeecisioaingamp;tolSeuzUesit 550025，China）

Abstract：Addressng theproblems thatclassicalmathematical methods forsolvingthegeneralizedNashequilibriumproblem face，suchasrelianceoninitialpointseletion，highdiferentiabilityrequirements，informationlossduringproblemtrasfor mation，andinsuffcientperformanceofmeta-heuristicalgorithms，thispaperproposedanenhanceddiferentialevolutionalg rithmtodirectlysolvethegeneralizedNashequilibriumproblemusingtheNikaido-Isoda function.Firstly，toimprovethediversityandconvergence speedofthediferentialevolutionalgorithm，itintroducedtheideasof tent chaotic mapping，adaptive coeficients，andtheslme mouldalgorithmtodesignanimprovedversionofthediferentialevolutionalgorithm.Italsoprovied atheoretical proofofthealgorithm’sconvergence.Secondly，itdefinedadominancestrategyandarelativefitnessfunction using the Nikaido-Isoda function toenhancepopulationvariationand selectioninthediferentialevolutionalgorithm.Finaly， theresultsofarithmeticcases indiferentdimensionsdemonstratethatthealgorithmsuccessullyresolves thegeneralized Nash equilibrium problem.Therefore，theproposedmethodforsolvingthegeneralizedNashequilibriumproblemdoesnotrelyoninitialpointslectinorfereiabilityanditvidsiformationlossduringprblmtansforatineringcrtaindvntges and effectiveness.

Keywords：generalized Nashequilibrium；Nikaido-Isoda function；bimodal variants；dominance strategies；meta-heuristic algorithms

0 引言

Nash均衡是非合作博弈中非常重要的概念，它在經(jīng)濟學(xué)、管理學(xué)、人工智能等[1＼～3]領(lǐng)域都有廣泛的應(yīng)用。隨著實際問題的不斷交互使問題變得復(fù)雜，廣義Nash均衡問題（GNEP）應(yīng)運而生，Debreu[4]首次為市場均衡的存在性提供了嚴(yán)格的證明，為市場均衡理論奠定了堅實基礎(chǔ)，但沒有給出有效的求解方法。因此，如何求解GNEP成為近年博弈論的研究熱點之一，引起了學(xué)者們的廣泛關(guān)注。

隨著時代的發(fā)展，廣大學(xué)者不斷探索GNEP的求解方法。Facchinei等人[5]提出了一種具有良好性質(zhì)的全局收斂懲罰方法，將GNEP簡化為非光滑Nash均衡問題進行求解。陳盼華[分別將GNEP轉(zhuǎn)換為擬變分不等式問題、最優(yōu)化問題，并提出新的下降算法進行求解。Wang等人[7]研究了模糊區(qū)域上的GNEP，在變分不等式方法的基礎(chǔ)上提出一個求解GNEP的算法，并進行穩(wěn)定性分析。Nie等人[8]使用拉格朗日乘子計算廣義Nash均衡的有效多項式，利用半定松弛的矩-平方和層次結(jié)構(gòu)求解GNEP。Krilasevic等人[9]提出一種新穎的無投影連續(xù)半分散求解算法，求解單調(diào)的GNEP。 Wang^[10] 研究了一類動態(tài)GNEP，提出一種利用微分變分不等式求解GNEP的算法，并對算法進行收斂性分析。后來，一些學(xué)者在經(jīng)典方法的基礎(chǔ)上，結(jié)合分布式和分解的思想求解GNEP。Migot等人[11]提出一類GNEP的分解方法，在完全凸性的假設(shè)下證明了算法的收斂性。Franci等人[1]提出了第一個分布式搜索算法，求解了帶有隨機因素的GNEP。侯劍等人[13]利用Nikaido-Isoda函數(shù)將GNEP轉(zhuǎn)換為等價的光滑約束優(yōu)化問題進行求解，在支付函數(shù)的梯度具有強單調(diào)性的假設(shè)條件下給出求解該問題的Nikaido-Isoda算法。

Roughgarden[14]提出Nash均衡的求解是一個NP難問題。近年，元啟發(fā)式算法在解決NP難問題上體現(xiàn)出優(yōu)越性，因此，學(xué)者們試圖通過元啟發(fā)式算法求解Nash均衡。賈文生等人[15]利用KKT條件和FB互補函數(shù)將GNEP轉(zhuǎn)換為線性方程組問題，并設(shè)計一種免疫粒子群算法進行求解。Mohtadi等人[16]提出一種叫做博弈求解器算法的啟發(fā)式算法求解一般Nash均衡問題。Liu等人[1]提出協(xié)同量子免疫粒子群算法求解GNEP，并給出算法收斂的充要條件。Li等人[18]提出一種基于文化算法的自適應(yīng)差分進化算法求解一般 Ω_n 人非合作博弈問題的Nash均衡。張國強等人[19]運用改進的微分進化算法求解Nash均衡問題，其通過差分進化算法在解空間中隨機游走搜索尋找最優(yōu)解。

綜上，求解GNEP經(jīng)典的方法大致分為兩類：一是將GNEP轉(zhuǎn)換為擬變分不等式，借助投影算法、牛頓法等進行求解；二是利用gap函數(shù)、懲罰函數(shù)等將GNEP轉(zhuǎn)換為約束優(yōu)化問題進行求解。但經(jīng)典方法存在以下不足：a）對初始點依賴程度較大，相對容易陷人局部最優(yōu)；b）在求解問題時可微性條件較高，求解之前往往作出較多的假設(shè);c）將GNEP轉(zhuǎn)換為其他問題進行求解的過程中，會受到二次可微性的限制且會損耗問題的原始信息；d）隨著問題規(guī)模不斷增大，可能會導(dǎo)致計算復(fù)雜度和時間代價增長。智能算法按照特定規(guī)則在解空間內(nèi)進行尋優(yōu)，不受初始點選取和模型可微性條件的限制，并在NP難問題上展現(xiàn)出強大的性能，已有利用啟發(fā)式算法求解GNEP的研究較少，且多數(shù)也存在問題轉(zhuǎn)換損耗信息、收斂性理論研究、收斂性能不足等問題。差分進化算法擁有結(jié)構(gòu)簡單、勘探性能強、種群多樣性豐富等優(yōu)點，能夠比對父代和子代進行尋優(yōu)，但作為一種元啟發(fā)式算法也存在不足：a）隨機生成初始點，種群多樣性不足；b）開發(fā)性能不足；c）算法收斂性缺乏理論證明。

受上述研究啟發(fā)，本文針對經(jīng)典方法和元啟發(fā)式算法求解GNEP存在的不足進行探索，貢獻如下：

a）針對GNEP轉(zhuǎn)換過程中損耗原信息的問題，引人NikaidoIsoda函數(shù)對GNEP進行直接求解，而不進行轉(zhuǎn)換求解；

b）針對經(jīng)典方法依賴初始點選擇和可微性條件的問題，實現(xiàn)兩代協(xié)同進化，采用差分進化算法進行求解，擺脫初始點和可微性條件的限制；

c）針對元啟發(fā)式算法的迭代圍繞適應(yīng)度函數(shù)進行而利用Nikaido-Isoda函數(shù)直接求解GNEP不存在直接的適應(yīng)度函數(shù)的問題，利用Nikaido-Isoda函數(shù)定義一種相對占優(yōu)策略以及相對適應(yīng)度函數(shù)引入到EDE中來實現(xiàn)GNEP的求解；

d）針對差分進化算法初始種群多樣性不足和開發(fā)性能不足，引入Tent混沌映射、自適應(yīng)系數(shù)和黏菌算法思想進行改進，提高算法多樣性和收斂性能，平衡算法勘探能力和開發(fā)能力，得到增強型差分進化算法并給出算法收斂性證明和算例分析結(jié)果。

簡言之，利用EDE產(chǎn)生GNEP的策略組合，即種群，進一步通過Nikaido-Isoda函數(shù)以及給出的相關(guān)定義判斷得到最佳策略，從而探索GNEP的求解方法。結(jié)果顯示，將Nikaido-Isoda函數(shù)引入到GNEP的求解中，利用改進的差分進化算法求解實際GNEP問題存在一定的優(yōu)勢與有效性。

1問題描述

1.1廣義Nash均衡問題

設(shè)有 N 個局中人，每個局中人 v∈{1，2，…，N} ，使得 x= （20號 （x¹，x²，…，x^N）^T∈Rⁿ 表示所有局中人的決策變量， x^v=（x^v，1 表示每個局中人 v 的控制變量，其中 n= 表示除局中人 v 外所有局中人的決策變量，記 x= （x^v，x^-v） 。假設(shè)局中人 v 的策略集為 x^v∈X_v（x^-v） ，它依賴于所有其他局中人的策略。 X_v（x^-v） 被稱為局中人 σ_v 的可行集，它由等式約束或不等式約束明確定義。每個局中人 v 都有一個支付函數(shù) θ_v（x^v，x^-v） ： Rⁿ?R ，其中 θ_v 與局中人的決策變量x^v 和其他局中人的決策變量 x^-v 都相關(guān)。通常，對于每個局中人 σ_v ，?v=1，2，…，N ，約束函數(shù)形如

其中： h_v（x^v） 是所有局中人的自我約束，它只依賴于局中人的決策變量。 g_v（x^v，x^-v） 表示所有局中人的共同約束，它依賴于所有局中人的決策變量。 h_v 和 g_v 的維數(shù)分別記為 m_v 和 m₀ 。

若

x^*=（x^*，1，x^*，2，…，x^*，N）∈

X₁（x^-1）×X₂（x^-2）×…×X_N（x^-N）

是GNEP的 Nash 均衡，那么對于任意的 v∈N x^*，v∈X_v （x^*，-v） ，該方程滿足優(yōu)化問題：

θ_v（x^*，v，x^*，-v）=min_x^v，x^-vθ_v（x^v，x^-v）

s.t.x^v∈X_v（x^?，-v）

特別地，如果 ?x^-v∈X（x^-v） ，有 X_ν（x^-ν）=X（x^ν），?ν= 1，2，…，N ，GNEP等價的優(yōu)化問題式（3）就退化為一般 N 人非合作博弈Nash均衡問題。

1.2 Nikaido-lsoda函數(shù)

Nikaido-Isoda函數(shù)是研究 Nash 均衡問題和廣義Nash均衡問題的重要工具，1955年，由Nikaido等人在文獻[20]中提出。

設(shè)局中人集合 X={1，…，N} θ_i 為第 i 個局中人的支付函數(shù)， X_i 為供其選擇的策略集。記 ，那么Nikaido-Isoda函數(shù)為 ψ：X×X?R ，

其中： ：x，y∈X

定義1設(shè)局中人集合為 X={1，…，N} ， ?i∈X，X_i 是第 i 個局中人的策略集， G_i：X_i?P₀（X_i） 是第 i 個局中人在共享約束下的可行策略映射，約束下聯(lián)合策略集 。如果存在 x^?=（x^?，υ，x^?，-υ）∈X 使得

ψ（x^?，y）?0，?y∈X

則稱 x^* 是廣義 Nash 均衡問題的解。反之，若

ψ（x^*，y）gt;0，?y∈X，y≠x^*

那么 x^* 一定不是廣義 Nash 均衡問題的解。

注1：定義1反映了 Nash 均衡解與Nikaido-Isoda函數(shù)之間的關(guān)系，能夠直接比較GNEP中兩個不同策略值的優(yōu)劣，從而為對GNEP直接進行求解而不是轉(zhuǎn)換后再求解提供了工具。

2算法EDE設(shè)計

2.1 差分進化算法（DE）

Storn等人在文獻[21]中首次提出差分進化算法。DE是一種基于種群的智能算法，具有結(jié)構(gòu)簡單和魯棒強的優(yōu)點，通過種群個體之間的差異信息對個體形成擾動，進而探求整個種群。DE有三個主要控制參數(shù)，即變異因子 F 、交叉概率CR以及種群規(guī)模 NP ，四個操作即初始化、變異、交叉和選擇。

2.1.1初始化

假設(shè)種群中有 N 個個體，記為

其中： _;N 代表種群規(guī)模大??； D 代表種群空間的維數(shù)。在DE的研究中，一般假設(shè)初始總體服從均勻分布，個體 x_ij 由

x_ij=rand?（x_j^U-x_j^L）+x_j^L

i=1，2，…，N;j=1，2，…，D

得到，其中rand代表 （0，1） 的隨機數(shù)， Δ_?Δ_?^U 和 x_j^L 分別表示變量的上界和下界。

2.1.2 變異

在 DE 中，變異操作類似于其他進化算法，個體 V=（v_i1 U，…，in）的變異公式為

其中： r₁?r₂ 和 r₃ 是取值在 [0，NP] 上與 i 不等的不同隨機整數(shù)； F 表示收縮因子，它能夠控制變異過程中兩個個體的差異大?。??_t 代表當(dāng)前迭代數(shù)。

2.1.3 交叉

根據(jù)具有給定概率的親本和后代之間的交叉來產(chǎn)生新的個體U=（ui，u，…，uiD）

其中： rand（j） 是 （0，1） 內(nèi)的隨機值； CR 是指在 [0，1] 內(nèi)執(zhí)行交叉操作的概率； rn（i）∈{1，2，…，D} 表示一個隨機選擇的序列，它確保一個新的個體從變異向量中至少得到一個分量值。

2.1.4 選擇

根據(jù)以下公式選擇個體和親代，生成子代 X_i^t+1 C

其中 ?f（?） 為適應(yīng)度函數(shù)值。

由于元啟發(fā)式算法的迭代依賴于適應(yīng)度函數(shù)的計算與更新，而利用Nikaido-Isoda函數(shù)對GNEP進行直接求解的過程中只存在不同策略值的比較，而不存在實際的目標(biāo)函數(shù)（適應(yīng)度函數(shù)），所以本文結(jié)合Nikaido-Isoda函數(shù)和差分進化算法思想給出如下兩個定義，以便進一步保證算法的正常進行。

定義2基于Nikaido-Isoda函數(shù)定義一種示性函數(shù) τ （20

定義3基于Nikaido-Isoda函數(shù)定義一種相對適應(yīng)度函數(shù) f_i：R?R ，

注2：由式（3）可知，廣義Nash均衡問題能夠被等價于一個極小化的優(yōu)化問題來求解。那么，存在一個目標(biāo)函數(shù) F ，當(dāng) x_t^*∈X，f（x_t^*）=maxf（x_tⁱ） 時，使得 F（x_t^*）=min F（x_tⁱ） . i=1，2，…，N，t 表示種群的第 χ_t 代。即等價于給出一個抽象的適應(yīng)度函數(shù)，為后文進行算法收斂性分析提供工具。

2.2增強型差分進化算法（EDE）設(shè)計

2.2.1 Tent混沌映射

通常，混沌映射產(chǎn)生的序列的主要特征有非線性、遍歷性、隨機性等，普通隨機方法產(chǎn)生的種群遍歷性較弱， Tent 是常見混沌映射中最均勻的映射之一。針對大多數(shù)智能算法種群多樣性的不足，本文將Tent混沌映射引進種群的初始化，以增強

EDE算法的遍歷性和多樣性。

其中： 0lt;αlt;1 。

因此，種群初始化由式（14）實現(xiàn)。

2.2.2 雙模式變異

針對DE在迭代過程中隨機更新個體時收斂能力較弱，本文引入雙模式變異。在黏菌算法中，個體適應(yīng)度值的不同，位置更新時個體的權(quán)重也會不同，權(quán)重計算如下[22]：

其中：case表示排名前1/2的個體； r 表示在 （0，1） 上的隨機值； bf 表示在當(dāng)前迭代過程最佳適應(yīng)值； wf 表示在當(dāng)前迭代過程中最差適應(yīng)值； s 表示適應(yīng)度值已排序的序列（在最小值問題中遞增）。

受黏菌算法思想的啟發(fā)，將DE的變異操作轉(zhuǎn)換為一種雙模式變異：

X_r1^t，X_r2^t，X_r3^t，X_r4^t，X_r5^t∈X;i=1，2，…，N

其中：case表示排名前1/3的個體； r₁，r₂，r₃，r₄，r₅ 分別表示1和 N 之間的不同整數(shù)； F 為收縮因子； X_best^t 表示第 χ_t 代中最好的個體。

2.2.3 自適應(yīng)更新

通常，收縮因子 F∈[0，1] ，取值大能夠增強種群多樣性，探索能力強，但后期收斂速度變慢；取值小有利于分析個體各維可分離問題，收斂越快，開發(fā)能力越強。將自適應(yīng)收縮因子引入到DE中，實現(xiàn)EDE算法探索和開發(fā)能力之間的平衡。

其中： F₀ 表示設(shè)定的初始收縮因子； iter 表示迭代數(shù)； Max_-T 表示最大迭代次數(shù)。

2.2.4占優(yōu)策略與存檔集

根據(jù)Nikaido-Isoda函數(shù)的定義與性質(zhì)，定義兩個占有策略用于選擇操作。

定義4相對占優(yōu)策略?？紤]兩個策略 x，y∈X ，稱 y 是 x 的相對占優(yōu)策略，如果滿足

定義5強相對占優(yōu)。考慮策略 y^*∈X，y^* 被稱為在第 χ_t 代種群中的個體 x 的強相對占優(yōu)策略，如果 ?x∈X_t 滿足

f（y^*）=maxf（x）

其中 X _ 代表第 χ_t 代個體所處的種群空間。

那么，基于上述兩種占優(yōu)策略，DE的選擇操作實現(xiàn)公式為

命題1考慮策略 x^*∈X ，若 x^* 是一個廣義Nash均衡解，那么 x^* 是強相對占優(yōu)策略，并且 X 中不存在策略 x∈X 是 x^* 的相對占優(yōu)策略。

存檔集在利用占優(yōu)策略進行個體更新的過程中，EDE算法是通過比較父代和親代來實現(xiàn)的，于是需要定義一個存檔集 Y 對父代進行記錄。同時，也將存檔集 Y 作為相對占優(yōu)個體組成的集合來進行更新。

2.3算法步驟及偽代碼

a）設(shè)置EDE算法的參數(shù)，如 N，D，CR，F(xiàn)₀，X^U，X^L ，并設(shè)置最大迭代次數(shù) 和精度 ε ：

b）利用式（14）的Tent混沌映射隨機生成 N 個初始種群 P

c）使用式（13）計算種群空間中個體的相對適應(yīng)度函數(shù)值f（X_i） 并排序，確定當(dāng)前種群 P（t） 中的最優(yōu)位置 X_best^t= max f（X_i） ：

d）使用式（16）變異生成種群 P₁（t） ：

e）使用式（10）交叉生成種群 P^′（t） ：

f對變異和交叉生成的種群中的個體是否在解空間內(nèi)作判斷，進行修補操作；

g）根據(jù)式（20），選擇種群 P（χ_t） 和 P^′（t） 生成后代種群P（t+1） ;

h）抽取種群 P（t+1） 中相對適應(yīng)度函數(shù)前1/3的個體，計算它們的方差 var

小于 ε 或達(dá)

i）若相對適應(yīng)度函數(shù)前 1/3 的個體的方差 var 到最大迭代次數(shù)，則輸出迭代次數(shù)、最優(yōu)個體的位置以及方差。則，轉(zhuǎn)到步驟e）。算法1 EDE算法輸人：參數(shù) （204號輸出 ：t，X_best^t ，var。a） N ， D ， C R ， F _" X{ U } ， X ^ { L } ，"http://設(shè)置參數(shù)b） //初始化種群F=F₀?2^λ/∣ 計算自適應(yīng)系數(shù) Inde x=sort（f（x） ） 計算相對適應(yīng)度函數(shù)，并排序 ? /（204號 Y=X //記錄父代d） if case else（20 （20end if 分別對情況（a）和（b）進行變異操作 ? /e）if r else（24號 U_ij^t+1=X_ij^t+1 end if 對個體進行交叉操作 * /f） X=Inspect（X） //對個體進行修補操作g）if ψ（X_ij^t+1，U_i^t+1）gt;0 （20X_ij^t+1=U_i^t+1 else（20號 X_ij^t+1=X_i^t （20end if 對個體進行選擇操作 * /h） var=var（Index（，N/3））/N/? 計算相對適應(yīng)度函1/3前的個體方差 /i） if var lt;ε or _t?MaxT break ;elset=t+1 （204號end if／*判斷是否滿足終止條件，若不滿足則返回c） ? ／

3 EDE算法收斂性分析

本章對EDE算法的收斂性能進行分析，無限狀態(tài)的連續(xù)解空間可以離散化以方便進行算法的理論分析[23]，假定離散空間中EDE 算法的種群個體 i 在時刻 χ_t 有 X_i（t）=x_i（t） ， 為狀態(tài)空間， x_i（t） 為個體 χ_i 在時刻 Φ_t 的狀態(tài)。狀態(tài) X_i（t） 所構(gòu)成的序列 {X_i（t）} ， t?1 在離散空間中為取值離散的隨機變量。首先，給出兩個定義和假設(shè)。

定義6對目標(biāo)函數(shù) F：Rⁿ?R，S 為 Rⁿ 的子集，那么一定能夠在 s 中存在一點 z ，使函 F 的函數(shù)值最小，或至少存在下確界 ?

使得 F 在 s 上能接受它，其中 v[A] 為在集合 A 上的Lebesgue測度。

定義7EDE 算法[24]中交叉變異以概率CR 對種群個體及其分量進行重組變換，在完備概率空間 中可定義該過程為一個隨機映射 φ：Ω×SS²

φ（ω，X）=?X，V?

其中 是一個非空抽象集合，集合 A 是一個 σ -代數(shù)，它由集合 中的子集生成 ，μ 表示集合 A 上的概率測度， ω 表示一個基本事件，并且有

μ（ω|φ（ω，X）=?X，V?）=μ（V=X_i+F?（X_j-X_k））

假設(shè)1對 ，若 ξ∈S ，那么 F（ξ） 。

假設(shè)1中 H 表示在問題空間能夠產(chǎn)生一個解的函數(shù)，它能保證 H 產(chǎn)生的新個體比當(dāng)前的個體更優(yōu)。 z 是子集 s 中的一個最小值個體， ξ 是根據(jù)算法對應(yīng)位置更新公式在子集 s 中得到的一列可行解。

假設(shè)2考慮 s 的任意Borel子集 A ，如果它的勒貝格測度v（A）gt;0 ，那么

其中 表示通過測度 μ_t 生成 A 的概率。

假設(shè)2表示對測度為 v 的一個 A 的任意子集，若采取隨機取樣方法，則它每次都錯過集合 A 的概率一定為零。算法的 ε 可接受區(qū)域 ，則所有在可接受區(qū)域取得點的概率一定是非零的。

引理1全局收斂充要條件[25]。假設(shè)目標(biāo)函數(shù) F 是可測的， s 為R\"的可測子集，滿足假設(shè)1和2。

設(shè) {z_k}_k=1^∞ 是算法生成的解序列，那么

lim_t∞B[z_t∈R_ε]=1

其中： B[z_t∈R_ε] 表示算法在第 χ_t 步生成的解 z_t∈R_s 的概率。

命題2EDE算法滿足假設(shè)1。

由注1和占優(yōu)策略可定義函數(shù) H：RⁿRⁿ

其中： ?h（x_i，t） 表示EDE算法更新位置過程中具體使用的函數(shù)，形如 x_i，t+1=h（x_i，t） 。 X_best^t 表示第 Φ_t 代中最好的個體，有 f（X_best^t）= maxf（x_j^t），j=1，2，…，N

以上描述體現(xiàn)了粒子位置對迭代次數(shù) χ_t 的依賴關(guān)系。序列 {X_best^j}_j=1^t 表示所有粒子從開始迭代到第 χ_t 次迭代時得到的最優(yōu)位置序列，那么序列 {F（X_best^j）}_j=1^t 是單調(diào)不增的。

因此， H 的定義符合假設(shè)1。

命題3EDE 算法滿足假設(shè)2。

對任意迭代數(shù) Φ_t 、粒子 X_i ，定義 μ_i，t 表示對應(yīng) D 維的概率測度，那么若任意 s 的 Borel 子集 A 滿足 v（A）gt;0 ，則由定義7得

令 M_i，t=R^D?S，M_i，t 表示 μ_i，t 在樣本空間上的支撐， M_i，t? A ，則

0lt;μ_i，t[A]lt;1

那么，種群中個體的支撐聯(lián)合為

M_t=?_i=1^NM_i，t=R^D?S

并且 M_t 表示分布 μ_ι 的支撐。那么，由 μ_t 生成 A 的概率為

又由式（28）得

0lt;μ_t[A]lt;1

因此有

即EDE算法滿足假設(shè)2。

定理1 EDE 算法是一個全局收斂算法。

命題2和3表示，EDE算法滿足假設(shè)1和2，由引理1，對 生成的解序列 {X_k}_k=1^∞ ，滿足

因此，EDE算法全局收斂。

4數(shù)值實驗

為了驗證Nikaido-Isoda函數(shù)結(jié)合EDE算法求解廣義Nash均衡問題的有效性，本章給出五個不同維度的數(shù)值例子。例1和例2為二維的廣義Nash均衡問題，例3是五維的廣義Nash均衡問題，例4嘗試求解一個十維的廣義Nash均衡問題，設(shè)置參數(shù)如表1所示。

需要注意的是，本文提出的EDE算法以最大迭代次數(shù)和相對適應(yīng)度函數(shù)排名在前1/3的個體的方差var為迭代終止條件。var越小，說明種群中表現(xiàn)好的個體差異越小，即這1/3的個體都迭代達(dá)到最優(yōu)。同時，由EDE算法雙模式更新的較強勘探性和開發(fā)性使得個體不會陷入局部最優(yōu)，并通過策略值收斂圖直觀體現(xiàn)EDE算法能否成功收斂到近似廣義Nash均衡解，并記該Nash均衡近似解為 x^* ，每個算例運行3次。

例 1^[19] 考慮一個二維的廣義博弈問題，目標(biāo)函數(shù)和約束條件如下：

其中： θ_i（i=1，2） 為支付函數(shù)； x_i（i=1，2） 為決策變量。

在給定的參數(shù)條件下，EDE算法的計算結(jié)果如表2、圖1所示。求得該GNEP的近似解為 x^*=（1.6，1.8） ，收斂較快。通過相對占優(yōu)策略對 x^*=（1.6，1.8） 進行驗證，得 ψ（1.6 1.9），（1.6，1.8）） gt;0 ，意味著EDE算法求出的近似解（1.6，1.8）比文獻[19]中求得的解 x^*=（1.6，1.9） 好，并且EDE算法求解的平均迭代次數(shù)52比文獻[19]中的平均迭代94次更少，EDE算法的表現(xiàn)更好。

例2考慮文獻[26]中的博弈問題，該問題是一個二維廣義Nash均衡問題，模型如下：

其中： θ_i（i=1，2） 為支付函數(shù)； x_i（i=1，2） 為決策變量。

計算結(jié)果如表3所示，策略值收斂圖如圖2所示。結(jié)果顯示，EDE算法成功收斂到該廣義 Nash 均衡問題的近似解 x^*= （5，9），由于算法探索性能較強，導(dǎo)致在問題模型的數(shù)學(xué)性質(zhì)較差時，前期的收斂性較弱，從而在求解本例時前中期算法收斂較慢。EDE算法求解結(jié)果與文獻[26]中的兩個求解算法所得近似解（5，9）相同，但EDE算法收斂更快，且不依賴于初始點選擇和可微性條件。

例 3^[19] 考慮一個寡頭壟斷市場問題。5家公司以非合作的方式提供同質(zhì)產(chǎn)品，設(shè) p 將消費者購買此數(shù)量產(chǎn)品的單價分配給市場上產(chǎn)品的總量 Q ，這個函數(shù) p 被稱為逆需求曲線。生產(chǎn)成本用一個成本函數(shù) f_i（i=1，2，…，5） 來表示。函數(shù) f_i（i= 1，2，…，5） 和 p 的形式如下：

其中： ω_i，θ_iA_i 是給定的非負(fù)參數(shù)，在表6中給出， 1?x_i?150

其中： 被稱為彈性需求，本文取為 η=1.1 ，利潤函數(shù)

因此，得到一個五維的寡頭市場廣義Nash均衡問題

EDE算法的計算結(jié)果如表5所示，策略值收斂圖如圖3所示。EDE算法成功求解了該五維的寡頭市場GNEP，在50次后就達(dá)到基本收斂，大約在100次時收斂到近似解 x^*=（37 ，42，44，43，39），與文獻[19]方法相比，結(jié)果相同，但EDE算法迭代次數(shù)更少，體現(xiàn)出EDE算法求解GNEP的可行性與優(yōu)越性。

例 4^[27] 考慮 Kesselman 提出的網(wǎng)絡(luò)交換模型，本文考慮10個參與方。

假設(shè)有 N 個用戶，緩沖器容量為 B ，每個用戶 v 決定了其在緩沖器上的數(shù)據(jù)包數(shù)量 x^v ，用戶 v 的效用函數(shù)如下：

表示每個用戶 v 的傳輸率； 表示緩沖器的擁堵 水平。問題要達(dá)到效用函數(shù)最大化，取 B=1，N=10 得到一個10維的廣義 Nash 均衡問題如下：

在給定的參數(shù)條件下，結(jié)果如表6、圖4所示。EDE算法迭代到75次時就能夠達(dá)到收斂，算法成功求得該10維的網(wǎng)絡(luò)交換GNEP的近似解 x^*=（0.09，0.09，…，0.09） ，這與文獻[27]中使用光滑化方法求得的結(jié)果（ 0.090 041 95 ，0.09004193，…） 相同，但相比之下，EDE算法不依賴于初始點的選擇，并且不要求支付函數(shù)或約束函數(shù)的可微性，求解過程更簡單、穩(wěn)定。

5結(jié)束語

本文考慮從Nikaido-Isoda函數(shù)的角度研究廣義Nash均衡問題的求解方法。近年來，大多數(shù)的相關(guān)研究都是利用NikaidoIsoda函數(shù)在一定條件下將問題轉(zhuǎn)換為優(yōu)化問題之后，再利用牛頓法、投影法、松弛懲罰法等經(jīng)典方法進行求解。因此，本文嘗試根據(jù)Nikaido-Isoda函數(shù)本身的性質(zhì)來直接求解廣義Nash均衡問題。

通過引人Tent混沌映射、自適應(yīng)系數(shù)以及黏菌算法的思想設(shè)計一種增強型差分進化算法，并給出收斂性分析。其次，根據(jù)Nikaido-Isoda函數(shù)能夠直接比較不同策略優(yōu)劣的特性給出幾個相關(guān)定義，以實現(xiàn)GNEP的直接求解。不同維度的GNEP數(shù)值結(jié)果顯示，EDE在求解廣義Nash均衡問題上體現(xiàn)出較好的收斂性與可行性。相較于以往的部分算法，EDE具有對問題模型的可微性不敏感、不依賴于初始點選擇、不存在問題轉(zhuǎn)換損耗信息、收斂速度較快等優(yōu)勢，體現(xiàn)出EDE算法在求解廣義Nash均衡問題的優(yōu)勢和廣泛適用性。

在未來，廣義Nash均衡在現(xiàn)實中的應(yīng)用將會越來越廣泛，求解GNEP仍然是一個NP難問題。下一步的研究重點有：a）將GNEP的求解應(yīng)用到一個更貼近實際的大算例中，而不僅僅是當(dāng)前文中的實例；b）與更多具有代表的方法進行對比研究，進一步提高所提出方法的實用性與優(yōu)越性，擴大其適用范圍。

參考文獻：

[1]Myerson R B. Nash equilibrium and the history of economic theory [J].Journal of Economic Literature，1999，37（3）：1067-1082.

[2]DreuD，CarstenKW，Giacomantonio M，et al.Psychological constraints on aggressive predation in economic contests[J].Journal of ExperimentalPsychologyGeneral，2019，148（10）：1767-1781.

[3]FragkosG，Tsiropoulou EE，Papavassiliou S.Artificial intelligence enabled distributed edge computing for Internet of Things applications [C]//Proc of the 16th International Conferenceon Distributed Computing in Sensor Systems.Piscataway，NJ：IEEE Press，2O2O：450-457.

[4]Debreu G．A social equilibrium existence theorem[J].Proceedings of the National Academy of Sciences，1952，38（10）： 886-893.

[5]Facchinei F，Kanzow C. Penalty methods for the solution of generalized Nash equilibrium problems[J].SlAM Journal on Optimization，2010，20（5）：2228-2253.

[6］陳盼華．廣義納什均衡的一類優(yōu)化方法［D]．鄭州：鄭州大學(xué)， 2015.（Chen Panhua. A class of optimization methods for generalized Nash equilibria[D].Zhengzhou：Zhengzhou University，2015.）

[7]Wang Xing，Teo K L. Generalized Nash equilibrium problem over a fuzzy strategy set [J]. Fuzzy Sets and Systems，2022，434： 172-184.

[8]Nie Jiawang，Tang Xindong.Convex generalized Nash equilibrium problems and polynomial optimization[J].Mathematical Programming，2023，198（2）：1485-1518.

[9]Krilasevic S，Grammatico S. Learning generalized Nash equilibria in monotone games： a hybrid adaptive extremum seeking control approach[J]．Automatica，2023，151：110931.

[10]Wang Xing.A computational approach to dynamic generalized Nash equilibrium problem with time delay[J]. Communications in NonlinearScienceandNumerical Simulation，2023，117：106954.

[11]Migot T，Cojocaru MG.A decomposition method fora class of convex generalized Nash equilibrium problems [J]. Optimization and Engineering，2021，22（3）：1653-1679.

[12]Franci B，Grammatico S.Stochastic generalized Nash equilibriumseeking in merely monotone games[J]. IEEE Trans on Automatic Control，2022，67（8）：3905-3919.

[13]侯劍，萌萌，文竹．一類納什均衡問題的求解算法［J]．運籌學(xué) 學(xué)報，2023，27（3）：129-136.（Hou Jian，Meng Meng，Wen Zhu. An algorithm for solving a class of Nash equilibrium problems [J]. Journal of Operations Research，2023，27（3）：129-136.）

[14]Roughgarden T.Computing equilibria：a computational complexity perspective[J].Economic Theory，2010，42（1）：193-236.

[15]賈文生，向淑文，楊劍鋒，等．基于免疫粒子群算法的廣義Nash 均衡問題求解［J]．計算機應(yīng)用研究，2013，30（9）：2637-2640. （JiaWensheng，XiangShuwen，YangJianfeng，etal.Generalized Nash equilibrium problem solving based on immune particle swarm algorithm[J].Application Research of Computers，2013，30 （9）：2637-2640.）

[16]Mohtadi M M，Nogondarian K.Presenting an algorithm to find Nash equilibrium in two-person static games with many strategies[J].Applied Mathematics and Computation，2015，251： 442-452.

[17]Liu Luping，Jia Wensheng.A new algorithm to solve the generalized Nash equilibrium problem[J].Mathematical Problems in Engineering，2020，2020：1-9.

[18]Li Huimin，Xiang Shuwen，Xia Shunyou，et al.Finding the Nash equilibria of n -person noncooperative games via solving the system of equations [J].AIMS Mathematics，2023，8（6）：13984-14007.

[19］張國強，趙國黨.一種改進的微分進化算法求解納什均衡問題與 廣義納什均衡問題[J].運籌與管理，2023，32（3）：36-42. （Zhang Guoqiang，Zhao Guodang. An improved differential evolutionary algorithm for solving Nash equilibrium problems and generalized Nash equilibriumproblems[J].Operations Research and Management，2023，32（3）：36-42.）

[20]Nikaido H， Isoda K. Note on non-cooperative convex game[J].Pacific Journal of Mathematics，1955，5（1）：807-815.

[21]StornR，PriceK.Differential evolution-a simpleand efficient adaptive scheme for global optimization over continuous spaces[M]. Berkeley：ICSI，1995.

[22]Li Shimin，Chen Huiling，Wang Mingjing，et al. Slime mould algorithm：anew method for stochastic optimization[J].Future GenerationComputerSystems，2020，111：300-323.

[23］胡中波．依概率收斂差分演化算法的理論與算法設(shè)計［D]．武 漢：武漢理工大學(xué)，2014.（Hu Zhongbo.Theory and algorithm designof differential evolutionary algorithms with probabilistic convergence[D].Wuhan：Wuhan University of Technology，2014.）

[24]Li Huimin，Xiang Shuwen，Yang Yanlong，et al.Differential evolution particle swarm optimization algorithm based on good point set for computing Nash equilibrium of finite noncooperative game[J]. AIMS Mathematics，2021，6（2）：1309-1323.

[25］曾建潮，介靖，崔志華．微粒群算法［M]．北京：科學(xué)出版社， 2004.（Zeng Jianchao，Jie Jing，Cui Zhihua.Particle swarm algorithms[M].Beijing：Science Press，2004.）

[26]Zhang Jianzhong，Qu Biao，Xiu Naihua.Some projection-like methods for the generalized Nash equilibria[J].Computational Optimizationand Applications，2010，45（1）：89-109.

[27]Von Heusinger A，Kanzow C. Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions [J].Computational Optimization and Applications，2009，43： 353-377.