從艷芳，王祝君

（1.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350000；2.湖南工程學(xué)院 計(jì)算科學(xué)與電子學(xué)院，湘潭 411104）

0 引言

種群是指在特定時(shí)間和空間中生活和繁殖的同種個(gè)體的總和.在同一空間，兩個(gè)群體之間有競(jìng)爭(zhēng)、合作、替代等關(guān)系.兩個(gè)種群的種群功能類似，但是彼此提供能源的方式、技術(shù)以及數(shù)量不盡相同，雙方給環(huán)境帶來(lái)的影響也不同.兩個(gè)種群之間相互抑制，又互相促進(jìn)，受各種復(fù)雜關(guān)系的制約，要想獲得種群在特定時(shí)刻的準(zhǔn)確分布數(shù)量或者密度值，往往相當(dāng)困難.但是，研究與其等效的穩(wěn)定狀態(tài)的數(shù)量或密度關(guān)系，卻有著重要的理論與應(yīng)用價(jià)值.對(duì)于種群關(guān)系的研究，大多是建立在Lotka-Volterra模型［1-2］的基礎(chǔ)上，通過(guò)分析常微分方程的穩(wěn)定性，研究不同條件下種群的食餌模型達(dá)到穩(wěn)定狀態(tài)的情況.

自從Nash［3-4］對(duì)非合作博弈提出了一種被稱為Nash均衡解的概念之后，如何找到非合作博弈的Nash均衡已成為一個(gè)非常經(jīng)典的問(wèn)題.Nash均衡問(wèn)題是經(jīng)濟(jì)學(xué)和管理學(xué)等的基礎(chǔ)，在計(jì)算機(jī)工程，生物信息學(xué)等各個(gè)領(lǐng)域也有著廣泛的應(yīng)用［5-7］.本文從博弈論角度研究?jī)蓚€(gè)種群生態(tài)系統(tǒng)的最優(yōu)響應(yīng)算法及其收斂性，即將兩個(gè)種群競(jìng)爭(zhēng)模型當(dāng)作一個(gè)博弈模型，設(shè)計(jì)一個(gè)最優(yōu)響應(yīng)算法，證明算法收斂于Nash均衡解.

1 問(wèn)題描述

自然界中任何一種物種都不是孤立存在的，總是同其他物種發(fā)生這樣或那樣的關(guān)系.物種之間的相互作用關(guān)系對(duì)于整個(gè)生物界的生存和發(fā)展是極其重要的，這種作用關(guān)系將各個(gè)物種連接為一個(gè)復(fù)雜的生命之網(wǎng)，決定著群落和生態(tài)系統(tǒng)的穩(wěn)定性.不同種群之間存在著一種相互依賴、相互制約的生存方式，如種群甲靠豐富的自然資源生長(zhǎng)，而種群乙靠捕食種群甲為生，生態(tài)學(xué)上稱種群甲為食餌，種群乙是捕食者，二者共處組成捕食者-食餌系統(tǒng).由于生物的很多適應(yīng)性都可以用捕食者和食餌之間的協(xié)同進(jìn)化加以說(shuō)明，所以對(duì)于捕食者-食餌相互作用關(guān)系的研究具有非常重要的理論意義和應(yīng)用價(jià)值.在這里我們僅以文獻(xiàn)［8］中經(jīng)典的Lotka-Volterra模型為例.兩個(gè)種群競(jìng)爭(zhēng)模型為：

設(shè)θ1(x ,y )，θ2(x ,y)分別表示兩個(gè)種群的數(shù)量，則：

用博弈模型來(lái)表達(dá)同一生態(tài)系統(tǒng)中兩個(gè)具有競(jìng)爭(zhēng)關(guān)系的種群平衡問(wèn)題，我們得到

在有限資源環(huán)境下，種群數(shù)量隨著時(shí)間動(dòng)態(tài)地逼近均衡狀態(tài)，因此有

由Nash均衡的定義知，w*=(x*,y*)∈X×Y是上述博弈的一個(gè)Nash均衡解，當(dāng)且僅當(dāng)x*=

2 投影梯度法

給出一些符號(hào)說(shuō)明：對(duì)任意的x∈Rn，‖‖x定義為x的Euclidean范數(shù)，即定義為x的橢球范數(shù)，即‖x ‖=xTGx，G ∈ Sn+；在閉凸集Ω上的投影算子定義為

2.1 臨近型線性化迭代算法

因?yàn)?θ1(x ,y )，θ2(x ,y)均為未知，直接求解（2）具有一定的困難，根據(jù)種群的生態(tài)系統(tǒng)模型可知，?xθ1(x .y)=f(x ,y )，?yθ2(x .y)=g(x ,y).因此，我們可采用臨近型線性化迭代方法得到：

對(duì)于非合作博弈的Nash均衡問(wèn)題，常見(jiàn)的求解算法包括正則化Gauss-Seidel算法、信賴域算法等［9］.Zhang等［10］借助預(yù)測(cè)-校正的思想，提出了通過(guò)投影算法獲得博弈的廣義Nash平衡點(diǎn)，Peng等［11］將兩人輪流博弈問(wèn)題轉(zhuǎn)變成求解變分不等式問(wèn)題，在預(yù)測(cè)-校正過(guò)程中利用非精確的臨近點(diǎn)交替方向法求得Nash平衡點(diǎn).對(duì)于運(yùn)用預(yù)測(cè)和校正兩個(gè)步驟來(lái)求解博弈問(wèn)題，相當(dāng)于對(duì)于博弈的策略進(jìn)行了外界因素的調(diào)整，在自然環(huán)境下食物鏈適應(yīng)于“物競(jìng)天擇，適者生存”法則，排除人為因素的影響.針對(duì)這種不允許校正的非合作博弈Nash均衡來(lái)說(shuō)，本文提出一種投影梯度算法，并在一定條件下證明算法全局收斂到Nash平衡點(diǎn).

全文通篇做如下假設(shè)：

假設(shè)1兩種群的數(shù)量函數(shù)θ1(x ,y )，θ2(x ,y)都是自身控制的可微凹函數(shù)，即：對(duì)于任意固定y，θ1(x ,y)是x∈X(y)?Rn的可微凹函數(shù)；對(duì)于任一固定的x，θ2(x ,y)是y∈Y(x)?Rm的可微凹函數(shù).

由 模 型（1）知 ，?xθ1(x .y)=f(x ,y )，?yθ2(x .y)=g(x ,y).根據(jù)假設(shè)1，任意給定y，f(x ,y)關(guān)于x∈X(y)單調(diào).同樣，任意給定x，g(x ,y)關(guān)于y∈Y(x)單調(diào).故：

假設(shè)2決策集X、Y是簡(jiǎn)單的有界閉凸集，以保證其在閉集上的投影比較容易計(jì)算.在上述假設(shè)條件下，兩種群博弈的Nash均衡解等價(jià)于下列變分不等式組的解：

這種等價(jià)性提示，可以借助變分不等式的求解方法來(lái)計(jì)算博弈的Nash均衡解，本文用投影梯度的方法求解變分不等式問(wèn)題.迭代（3）和（4）等價(jià)于：

2.2 算法描述及收斂性分析

本節(jié)先給出一種求解兩個(gè)種群的生態(tài)系統(tǒng)博弈Nash均衡問(wèn)題的最優(yōu)響應(yīng)算法，然后對(duì)算法的全局收斂性進(jìn)行分析.

算法1最優(yōu)響應(yīng)算法

步驟1初始化，令ε＞0，對(duì)任意給定的初始點(diǎn)x0∈X，X ?Rn，Y ?Rm，通過(guò)求解問(wèn)題得到y(tǒng)1∈Y：y-y1,g(x0,y1)-β0(y1-y0) ≤ 0,?y∈ Y(x0).

步驟2對(duì)于給定的(xk,yk)，分別求解如下的變分不等式，得到當(dāng)前情況下的最優(yōu)策略：xk+1∈X(yk)和yk+1∈Y(xk+1)：

步驟3計(jì)算εk=max{‖ xk+1-xk‖,‖yk+1-yk‖}，如果εk＜ ε，則停止.否則，令k:=k+1，返回步驟1.

則迭代（7）和（8）可以寫(xiě)成下列的緊湊形式：求wk+1∈W，使得

假設(shè)3若w*=(x*,y*)∈W是博弈的一個(gè)Nash均衡點(diǎn)，則

引理1對(duì)于給定的wk，設(shè)wk+1是由算法1產(chǎn)生新迭代點(diǎn)，若

w*=(x*,y*)∈W是種群博弈問(wèn)題的一個(gè)Nash均衡點(diǎn)，則

證明.由f(x ,y)，g(x ,y)的單調(diào)性，將(x ′,y′)=(xk+1,yk+1)代入式（5）

將(x ,y)=(xk+1,yk)和(x ,y)=(x*,y*)分別代入（12），將兩式相加求和，得到：

把(x ,y)=(xk+1,yk)和(x ,y)=(xk+1,yk+1)分別代入式（10）的第一個(gè)和第二個(gè)不等式并結(jié)合式（6），（12）和（13），直接得到式（11）.證畢.

定理1設(shè){wk}是算法1產(chǎn)生的迭代序列，w*是所考慮的種群博弈模型的一個(gè)Nash均衡點(diǎn)，則

證明將w=w*，代入（9）可得

展開(kāi)得到 w*-wk+1,D(wk,wk+1) ≤

(w*-wk+1,G(wk+1-wk))，所以

再結(jié)合上式和引理1可以直接得到（14），定理得證.

定理2算法1產(chǎn)生的迭代序列{ }wk收斂于Nash均衡點(diǎn).

證明.由定理1可得

3 結(jié)論

本文研究種群動(dòng)力學(xué)中捕食者-食餌模型的Nash均衡問(wèn)題，即在有限資源環(huán)境下，種群數(shù)量隨著時(shí)間動(dòng)態(tài)逼近均衡狀態(tài).建立了兩個(gè)種群競(jìng)爭(zhēng)博弈的Nash均衡模型，采用交替投影梯度算法求解所得的博弈模型，證明了所提出的算法收斂到該博弈的Nash均衡點(diǎn)，即兩種群競(jìng)爭(zhēng)生態(tài)系統(tǒng)的均衡點(diǎn).