環(huán)路的平均固定時間研究

張培愛

(暨南大學(xué)數(shù)學(xué)系,廣東 廣州 510632)

環(huán)路的平均固定時間研究

張培愛

(暨南大學(xué)數(shù)學(xué)系,廣東 廣州 510632)

進化圖可以動態(tài)刻畫一個種群的動態(tài)演化,定置概率描述進入種群的新突變體占據(jù)整個種群的概率,而平均固定時間反映了該種群的平均進化速度．本文研究了環(huán)路的平均固定時間．在種群個體數(shù)量很大的情況下,給出了環(huán)路上單個突變體的平均固定時間及其性質(zhì)．當(dāng)相對適應(yīng)度01時,隨著r的增加,環(huán)路的固定概率增加了,而平均固定時間卻減少了．

環(huán)路;平均固定時間;進化圖;固定概率

進化圖由Lieberman、Hauert和Nowak[1]于2005年在《Nature》上提出．用一個有向圖來刻畫一個種群的動態(tài)進化[1-9]．有向圖中的頂點表示種群中的個體,個體間的相互作用由連接頂點的邊來表示．在每個時間步,按照一定的規(guī)則,隨機挑選一個個體進行繁殖,每個個體被挑到的概率與其相對適合度、出度、入度、位置、圖的空間結(jié)構(gòu)等有關(guān)．被選出的個體取代相鄰個體的概率與連接它們的邊的權(quán)重成正比．當(dāng)一個突變體(新的個體)在這個種群中出現(xiàn),這個突變體可能占據(jù)整個種群或者從這個種群消失．這個具有一定相對適應(yīng)度的突變體占據(jù)整個種群的概率為定置概率,與種群的個體數(shù)量、空間結(jié)構(gòu)、突變體的相對適應(yīng)度等有關(guān)．突變體的相對適合度就是突變體的適應(yīng)度與種群中原有個體的適應(yīng)度比值．一個突變體在一個進化圖中的定置概率越高,表明這個種群的更新能力更強,系統(tǒng)穩(wěn)定性就越差[5-8]．固定時間被定義為突變個體最終占領(lǐng)整個種群所花費的時間;平均固定時間反映了該類種群的平均進化速度．平均固定時間越少,種群平均進化速度越快．Whigham和Dick[10], Broom等[3],Paley等[11]研究了k-星型圖和漏斗圖的平均固定時間,并給出了隨著相對適應(yīng)度的增加、平均固定時間也相應(yīng)減少的結(jié)論．Antal等[12]給出了一種在充分混合的種群中的平均固定時間的計算方法．Nie和Zhang[6]得到了在充分大的種群下,等溫圖和k-星型圖的平均固定時間的簡單表達公式等．環(huán)路是一類特殊的進化圖,對于環(huán)路中的每個頂點來講,入度等于出度．權(quán)重矩陣W=(wij)不再要求是隨機的,權(quán)重系數(shù)wij可以是任意的非負(fù)數(shù)．在每個時間步,挑選一條邊．挑選概率正比于wij與該邊首端個體(即頂點i)的相對適合度的乘積．如果邊ij被選擇,則i的子代將取代j．由于在許多不同背景下產(chǎn)生的圖都是環(huán)路,因此,環(huán)路的研究具有非常重要的意義．張京友等[13]給出了環(huán)路的定置概率,下面我們給出環(huán)路中單個突變體的平均固定時間．

1 主要結(jié)論

環(huán)路作為一種特殊的進化圖,張京友等[13]研究了其定置概率,并給出了定置概率隨著相對適應(yīng)度的增加而增加的結(jié)論,并應(yīng)用于知識型企業(yè)組織結(jié)構(gòu)．下面我們將計算環(huán)路的平均固定時間,得到以下結(jié)論．

定理(環(huán)路平均固定時間定理) 在一個有N個適應(yīng)度為1的正常個體、具有環(huán)路結(jié)構(gòu)的種群中,如果引入一個相對適應(yīng)度為r的突變個體,則該突變個體占領(lǐng)整個種群的平均固定時間為

(1)

證明 記環(huán)路中的一個個體p,即有向圖中的一個頂點p,wi(p)和wo(p)分別表示頂點p的入度和出度．因為進化圖G為一個環(huán)路,所以每個頂點的入度等于出度,即wo(p)=wi(p)[13]．記狀態(tài)i表示種群中有i個相對適應(yīng)度為r的突變體和N-i個適應(yīng)度為1的正常個體情形．狀態(tài)0表示突變體在該種群中消失,狀態(tài)N表示突變體占據(jù)了整個種群,因此我們稱狀態(tài)0和狀態(tài)N為吸收狀態(tài)．

γi=p(i→i)=1-p(i→i-1)-p(i→i+1);

i=1,2,…,N-1.

以上方程可化為如下方程:

(2)

由一維隨機游走過程[14-15]可知

pi(t)=μipi-1(t-1)+λipi+1(t-1)+(1-μi-λi)pi(t),

i=1,2,…,N-1,

即

i=1,2,…,N-1.

從而,

由上式可得

該式可化為

i=1,2,…,N-1.

經(jīng)過多次迭代得到

其中:qk=r-k．令i=1,2,…,N-1,則

定理證畢．

在上述定理中,我們給出了進入環(huán)路中的單個突變體最后占領(lǐng)種群的平均固定時間,下面給出環(huán)路的平均固定時間的一個性質(zhì)．

證明 當(dāng)r∈(0,1),N非常大時,

可直接計算得

下面討論當(dāng)r>1時的情況．

直接結(jié)算可得

2 結(jié) 論

本文給出了環(huán)路上單突變體的平均固定時間,并討論了當(dāng)種群個體數(shù)目非常大,突變個體的相對適應(yīng)度小于種群中原有個體的適應(yīng)度,即該突變體是一個劣勢突變體時,環(huán)路的平均固定時間隨著相對適應(yīng)度的增加而增加,由文獻[9]可知,該環(huán)路的定制概率是隨著相對適應(yīng)度的增加而增加．而對于種群中相對適應(yīng)度大于種群中原有個體的平均適應(yīng)度,即該突變體是一個優(yōu)勢突變體時,環(huán)路的平均固定時間隨著適應(yīng)度的增加而減少,而環(huán)路的定置概率是隨著相對適應(yīng)度的增大而增大的．

[1] Lieberman E,Hauert C,Nowak M A. Evolutionary dynamics on graphs[J]. Nature,2005,433(20):312-316.

[2] Shakarian P,Roos P,Johnson A. A review of evolutionary graph theory with applications to game theory[J]. BioSystems,2012,107(2):66-80.

[3] Broom M,RychtT. Evolutionary dynamics on graphs—the effect of graph structure and initial placement on mutant spread[J]. The Journal of Statistical Theory and Practice,2011,5(3):369-381.

[4] Ohtsuki H, Hauert C, Lieberman E,et al. A simple rule for the evolution of cooperation on graphs and social networks[J].Nature, 2006,441(7092):502-505.

[5] Nie Puyan, Zhang Peiai. Evolutionary graphs with frequency dependent fitness[J]. Internal Journal of Modern Physics B,2009,23(4):537-543.

[6] Nie Puyan, Zhang Peiai. Fixation time for evolutionary graphs[J]. International Journal of Modern Physics B,2010, 24(27): 5285-5293.

[7] Zhang Peiai, Nie Puyan, Hu Daiqiang. Bi-level evolutionary graphs with multi-fitness[J]. IET Systems Biology,2010,4(1):33-38.

[8] Zhang Peiai.Fixation probabilities of evolutionary graphs bassed on the positions of new appearing mutants[DB/OL]. http://www.hindawi.com/journals/jam/2014/901363/2014-04-17.

[9] Nie Puyan. Evolutionary graphs on two levels[J]. Ars Combinatoria,2008, 86:115-120.

[10] Whigham P A, Dick G. Evolutionary dynamics for the spatial Moran process[J]. Genetic Programming and Evolvable Machines,2008, 9(2):157-170.

[11] Paley C, Taraskin S,Elliott S.Temporal and dimensional effects in evolutionary graph theory[J]. Physical Review Letters,2007,98(9):1-13.

[12] Antal T, Scheuring I. Fixation of strategies for an evolutionary game in finite populations[J]. Mathematical Biology,2006,68(2):1923-1944.

[13] 張京友,張培愛,鐘海萍.進化圖論在知識型企業(yè)組織結(jié)構(gòu)中的應(yīng)用[J].山東大學(xué)學(xué)報:理學(xué)版,2013,48(1): 107-110.

[14] Liang Dongfang, Wu Xuefei. A random walk simulation of scalar mixing in flows through submerged vegetations[J]. Journal of Hydrodynamics,2014, 26(3):343-350.

[15] 劉恒,寇月,申德榮,等.基于隨機游走路徑的分布式SimRank算法[J].計算機科學(xué)與探索,2014,8(12):1422-1431.

(責(zé)任編輯 李春梅)

Average Fixation Time on a Circulation

ZHANG Pei-ai

(Department of Mathematics, Jinan University, Guangzhou 510632, China)

Evolutionary graph can be used to describe the evolution of a population dynamically. The fixation probability of an evolutionary graph is the probability that a new emerging mutant occupies the whole population, while its average fixation time reflectes the average evolutinary velocity of the population. The average fixation time of a new mutant on a circulation with large population is studied and its property is discussed. When the relative fitness 01, the fixation probability of a circulation increases, but the average fitness time decreases with the increase of the relative fitnessr.

circulation; average fixation time; evolution graph; fixation probability

1004-8820(2015)04-0246-03

10.13951/j.cnki.37-1213/n.2015.04.003

2015-05-13

教育部人文社科資助項目(11YJAZH118)．

張培愛(1973- ),女,山東濰坊人,副教授,博士,研究方向為最優(yōu)化理論及其應(yīng)用．

O224

A