十進(jìn)制整數(shù)編碼的DE算法模式集定理研究

王凱光,高岳林

(北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川750021)

1.引言和預(yù)備知識(shí)

差分進(jìn)化算法(Differential Eveolution,簡(jiǎn)稱DE[1?3])是由Storn和Price于1995年提出的為解決切比雪夫不等式(Chebyshev Inequality)的一種采用浮點(diǎn)矢量編碼的在連續(xù)空間進(jìn)行搜索的全局優(yōu)化算法[4?6],是通過(guò)差分方式進(jìn)行迭代搜索的全局性進(jìn)化算法,具有簡(jiǎn)單、易實(shí)現(xiàn)、收斂性好、魯棒性強(qiáng)等優(yōu)點(diǎn)[7?13],但就算法尋優(yōu)的本質(zhì)上說(shuō),其大小如何影響種群多樣性的分布,進(jìn)而影響算法的收斂性質(zhì)[11,13],在理論機(jī)制上面尚未得到說(shuō)明.鑒于此,本文將在二進(jìn)制模式定理[14?15]研究基礎(chǔ)上,應(yīng)用十進(jìn)制編碼對(duì)DE算法的動(dòng)力學(xué)機(jī)制進(jìn)行初步研究,探索種群規(guī)模(NP)、收縮因子(F)、交叉概率(CR) 等控制參數(shù)對(duì)種群尋優(yōu)的動(dòng)力學(xué)機(jī)制,并提出相應(yīng)的編碼規(guī)則以及基本概念,給出能夠很好解釋DE算法各類參數(shù)對(duì)種群尋優(yōu)能力影響的十進(jìn)制模式集定理.

ⅠDE算法原理

一般地,極小化優(yōu)化問(wèn)題如下表示:

其中,D為決策變量的維數(shù),NP為種群規(guī)模,f(Xi)為適應(yīng)度函數(shù),Xi(i=1,2,··· ,NP) 為D維參量矢量,xij(i= 1,2,··· ,NP;j= 1,2,··· ,D)為第i個(gè)個(gè)體的第j個(gè)分量,aij,bij分別為尋優(yōu)范圍的下界和上界,差分進(jìn)化算法(Differential Eveolution,DE)基本操作原理如下描述[1,4,7].

(i)初始化種群

設(shè)置DE算法的種群為X(t),則個(gè)體可表示為:

其中t為進(jìn)化代數(shù),NP為種群規(guī)模.

初始化種群:確定所求優(yōu)化問(wèn)題的維數(shù)D,最大進(jìn)化代數(shù)T,種群規(guī)模NP,設(shè)置生成初值尋優(yōu)向量如下所示:

(ii)變異操作

DE算法的個(gè)體變異成分是父代個(gè)體的差分矢量,每次差分變異個(gè)體均來(lái)源于第t代父代個(gè)體種群中的兩個(gè)個(gè)體(Xti1,Xti2),其中i1,i2∈NP,則差分矢量定義為:Di1,2=Xti1?Xti2,那么對(duì)任意矢量個(gè)體Xti,定義變異操作為:

其中,i1,i2,i3∈{1,2,··· ,NP}且i1,i2,i3互不相同,種群規(guī)模NP≥4,F為收縮因子.在種群中隨機(jī)選取不為零的相異矢量,通過(guò)差分操作得到變異個(gè)體,變異個(gè)體將實(shí)現(xiàn)調(diào)整種群多樣性的可能.

(iii)交叉操作

對(duì)于種群目標(biāo)矢量個(gè)體(xti),與變異個(gè)體進(jìn)行交叉操作,產(chǎn)生試驗(yàn)個(gè)體Uit+1,為保持種群多樣性,引入交叉概率CR和隨機(jī)函數(shù)rand(0,1)對(duì)變異個(gè)體和目標(biāo)矢量個(gè)體(xti)進(jìn)行交叉選擇,保證試驗(yàn)個(gè)體至少有一位由變異個(gè)體貢獻(xiàn),對(duì)于其他位點(diǎn),通過(guò)交叉概率CR決定變異個(gè)體和目標(biāo)矢量個(gè)體(xti)對(duì)試驗(yàn)個(gè)體中某些位點(diǎn)的貢獻(xiàn),交叉操作的試驗(yàn)方程如下:

式(1.7)中randj[0,1],CR∈(0,1)為交叉概率,CR取值越大,表明矢量個(gè)體在不同位點(diǎn)發(fā)生交叉而產(chǎn)生新矢量個(gè)體的概率就越大;CR = 0時(shí),表明沒(méi)有發(fā)生任何交叉操作,有利于保持種群的多樣性和全局群搜索能力;CR=1時(shí),表明一定在某些位點(diǎn)發(fā)生交叉操作,有利于保持全局搜索和加快收斂速度.CR=0或1是發(fā)生交叉操作的兩種極端情況,j=jrand為隨機(jī)選擇的位點(diǎn),這是為了試驗(yàn)個(gè)體Uti要從變異個(gè)體V ti至少獲得一個(gè)發(fā)生基因變異的位點(diǎn),確保變異個(gè)體目標(biāo)矢量個(gè)體(xti)、試驗(yàn)個(gè)體三者矢量個(gè)體之間互不相同,表明交叉操作引起種群間的交叉是有效交叉.

(iv)選擇操作

DE算法的選擇操作是一種基于貪婪算法的選擇機(jī)制,經(jīng)過(guò)變異和選擇操作之后生成的試驗(yàn)個(gè)體與目標(biāo)矢量個(gè)體(xti)進(jìn)行競(jìng)爭(zhēng)和選擇,若當(dāng)Uit+1的適應(yīng)度值好于Xit的適應(yīng)度值,那么作為最優(yōu)個(gè)體會(huì)被種群繼承到下一代,否則保留到下一代的個(gè)體將是(xti),選擇算子在種群中的選擇作用由下述方程進(jìn)行描述:

Ⅱ二進(jìn)制編碼模式定理

引理1.1[14?15](模式定理,Schema Theorem) 在遺傳算子選擇、交叉、變異作用下,那些低階、短定義距、高適應(yīng)度的模式的生存數(shù)量,將隨著迭代次數(shù)的增加而以指數(shù)級(jí)增長(zhǎng).

2.十進(jìn)制編碼DE算法的模式集定理

對(duì)于十進(jìn)制整數(shù)編碼的DE算法,采用V={0,1,2,3,4,5,6,7,8,9}10個(gè)基本字符作為基本字符串(Essential Character String),字符串中不確定位點(diǎn)(也稱為分配符)?均在10個(gè)基本字符中取值,基本字符串中若含有不確定位點(diǎn)?,則稱為普通字符串(Ordinary Character String),顯然基本字符串也屬于普通字符串(簡(jiǎn)稱字符串(Character String)),字符串中任意字符的位點(diǎn)用{di|i ∈Z+,di ∈V}來(lái)表示.

Ⅰ基本概念及定義

定義2.1(模式,Schema)H稱之為一個(gè)模式,若存在形式={?,0,1,2,3,4,5,6,7,8,9},其中?的位點(diǎn)是任意的,并記作H=V,其中分配符?∈{0,1,2,3,4,5,6,7,8,9}.例如,H=?5?7??9就是一個(gè)模式,而H=0517119就是一個(gè)確定的模式表示形式.

定義2.2(模式集,Schema Sets)?稱之為一個(gè)模式集,若存在形式?={Hi|i ∈Z+}.

定義2.3(模式集階,Schema Sets Order) 包含在模式集?中所有模式{Hi|i ∈Z+}的階的總和,稱為模式集?的模式集階,記作Θ(?).若?Hi ∈?,O(Hi) =ki,則

例1現(xiàn)有一個(gè)模式集?={Hi|i ∈{1,2,3}},其中,O(Hi) =ki,i ∈{1,2,3},那么,也即這個(gè)模式集?的階為說(shuō)明此時(shí)該模式集?中3個(gè)相異個(gè)體分別包含各自模式{Hi|i= 1,2,3}的階ki,那么這三個(gè)模式{Hi|i= 1,2,3}的階的總和為

注 由于一個(gè)種群規(guī)模為NP的種群,假設(shè)其中存在有限個(gè)模式的個(gè)體,相異模式個(gè)體所攜帶的表示其特征量的模式是相異的,采用{Hi|i ∈Z+}作為模式集階的基本量是基于以下考慮:假設(shè)這里有兩個(gè)相異模式的個(gè)體(此時(shí)模式和個(gè)體是相當(dāng)?shù)?H1、H2,O(H1)=k1,O(H2)=k2,即這兩個(gè)模式個(gè)體所攜帶的染色體(確定字符串)上的不同位點(diǎn)上基因(確定字符)的個(gè)數(shù)分別為k1,k2,經(jīng)過(guò)選擇、交叉、變異后所得新個(gè)體中染色體(新確定字符)上的位點(diǎn)會(huì)增加或者說(shuō)新的確定子字符個(gè)數(shù)會(huì)增加,按照遺傳算法模式定理,新增加的確定字符個(gè)數(shù)將介于min{k1,k2}和ki之間,或者說(shuō)新個(gè)體的多樣性特征會(huì)增加與兩父代個(gè)體不同的某些特征,鑒于種群進(jìn)化的不確定性,采用{Hi|i ∈Z+}作為模式集階的基本量,具有概率上的廣義特征.

定義2.4(模式集串長(zhǎng),String Length of Schema Sets Order) 模式集?中所有模式{Hi|i ∈Z+}包含的所有字符的數(shù)量為l,則稱該模式集?的串長(zhǎng)為l,并記作L(?)=l.

例2若?={Hi|i= 1,2},L(H1) =l1,L(H2) =l2,則L(?) =L(H1)+L(H2) =l1+l2,也即這個(gè)模式集?的串長(zhǎng)為L(zhǎng)(?) =L(H1)+L(H2) =l1+l2,說(shuō)明此時(shí)該模式集?中2個(gè)相異個(gè)體分別包含各自模式{Hi|i= 1,2,3}的串長(zhǎng)li,那么兩個(gè)模式{Hi|i= 1,2,3}的串長(zhǎng)總和為L(zhǎng)(?)=l1+l2,模式集?的串長(zhǎng)對(duì)相異模式個(gè)體的變異強(qiáng)度有概率上被分割或替換的可能性,串長(zhǎng)越長(zhǎng),這樣的可能性就越大,反之越小.

定義2.5(模式集距,Schema Sets Order Range) 模式集?中所有模式{Hi|i ∈Z+}進(jìn)行降序或升序排列,模式{Hi|i ∈Z+}按次序排列的第一個(gè)模式的第一個(gè)位點(diǎn)上的確定字符(按次序方向)與按次序排列的最后一個(gè)模式的最后一個(gè)位點(diǎn)上的確定字符(按次序方向)的距離,稱為模式集距,記作δ(?).

例3現(xiàn)有模式集?={Hi|i= 1,2},其中H1=?2??4,H2=?2?5?,將該模式集的基本量按順序排列,對(duì)于模式集的第一個(gè)基本量H1,按順次序排列的第一個(gè)確定字符為2,其確定為點(diǎn)為第2位點(diǎn),同樣模式集的第二個(gè)基本量H2,按順次序排列的最后一個(gè)確定字符為5,其確定位點(diǎn)為第9位點(diǎn),那么該模式集?距為δ(?)=9?2=7,同模式集串長(zhǎng)的概率意義類似,不同的是模式集距中若有位點(diǎn)被分割或替換,發(fā)生變異的可能性強(qiáng)于模式集串長(zhǎng).

定義2.6(平均適應(yīng)度函數(shù),Function of Average Fitness) 設(shè)X(t)={Xt1,Xt2··· ,XtNP}為第t代種群,Ev(Xti)為Xti的適應(yīng)度,則稱

為模式集?的平均適應(yīng)度函數(shù).

其中,Ev(Xti)是種群規(guī)模為NP的種群中,任意個(gè)體(既包含同一模式的個(gè)體,也包含相異模式的個(gè)體,總之是所有種群個(gè)體)的平均適應(yīng)度,f(?,t) 是種群規(guī)模為NP的種群所包含的相異模式個(gè)體的平均適應(yīng)度,二者具有檢索個(gè)體數(shù)量上的不同,但其數(shù)學(xué)性質(zhì)完全類似.

ⅡDE算法的模式集定理

文[16-18]介紹了標(biāo)準(zhǔn)的遺傳算法的基本模式定理,Whitley教授[19?20]將二進(jìn)制編碼的字符串推廣到任意進(jìn)制字符串編碼上,我們將在前人已有的研究基礎(chǔ)上對(duì)DE算法的模式集定理進(jìn)行探討.我們知道,控制DE算法的各類參數(shù)主要有種群規(guī)模NP、收縮因子F、交叉概率CR.下面介紹十進(jìn)制整數(shù)編碼DE算法的模式集定理,它將從動(dòng)力學(xué)角度較為詳細(xì)地闡述DE算法的進(jìn)化機(jī)理.

定理2.1設(shè)DE算法的交叉概率和收縮因子分別為CR和F,模式集?的距為δ(?),模式集?的階為Θ(?),第t+1代種群X(t+1)中含有?中元素個(gè)數(shù)的期望值記為E(?∩X(t+1)),則有

其中,l為X(t)所包含模式集?的串長(zhǎng).(t)=∑x∈?∩X(t)Ev(Xti)/|X(t)|,|?∩X(t)|為X(t)中含于模式集?的元素個(gè)數(shù).

證 (i) 選擇操作對(duì)模式集?的生存數(shù)量的影響

假設(shè)種群規(guī)模為X={X1,X2,··· ,XNP},給定相應(yīng)進(jìn)化代數(shù)t,模式集?包含個(gè)數(shù)不大于種群規(guī)模為NP個(gè)相異的模式{Hi|i ∈NP},其適應(yīng)度函數(shù)(或稱之為種群演化初始時(shí)模式集的平均適應(yīng)度函數(shù))記為f(?,t).按照進(jìn)化算法演化次序,一個(gè)確定種群規(guī)模NP的種群,模式集?中任一個(gè)體按照選擇操作被選擇的次數(shù)與其適應(yīng)度函數(shù)成正比例關(guān)系,種群每演化一次,|?∩X(t)|中相異模式的每一個(gè)體被選擇的平均次數(shù)占種群規(guī)模中所有個(gè)體被選擇的平均比例數(shù)量為:

其中,

為證明方便,假設(shè)種群規(guī)模為NP的種群X={X1,X2,··· ,XNP},NP個(gè)數(shù)量的個(gè)體所攜帶的模式{Hi|i ∈NP}兩兩相異,?∩X(t) 中的個(gè)體數(shù)目|?∩X(t)|經(jīng)過(guò)N次選擇,T為最大迭代次數(shù),理論上期望在經(jīng)過(guò){t,t ≤T}次迭代后,模式集?在這樣的種群規(guī)模?∩X(t)內(nèi)元素被選擇的次數(shù)的期望為:

上式(2.5)說(shuō)明下一代種群中模式集?的生存數(shù)量與模式集?的適應(yīng)度函數(shù)值成正比,與群體X(t)平均適應(yīng)度函數(shù)值成反比.可以分為兩種情況,一種是:當(dāng)f(?,t)>ˉF(t)時(shí),模式集?的生存數(shù)量增加.另一種是:當(dāng)f(?,t)<ˉF(t)時(shí),模式集?的生存數(shù)量衰減.由此可見(jiàn),群體中任意模式集的生存數(shù)量都會(huì)在選擇操作中呈現(xiàn)如此變化規(guī)律.

那么當(dāng)群體從初始迭代值t= 0開(kāi)始進(jìn)行DE算法演化操作,假設(shè)λ這一常數(shù)不變,則上式(2.6)可改寫(xiě)為:

這表明,在選擇操作作用下,模式集?的生存數(shù)量是以指數(shù)形式進(jìn)行演化的.分為兩種情況,一種情況是:當(dāng)λ >0時(shí),模式集?的生存數(shù)量以指數(shù)形式增加.另一種情況是:當(dāng)λ <0時(shí),模式集?的生存數(shù)量以指數(shù)形式衰減.但這樣的變化僅是描述了已有模式集?的生存數(shù)量的變化,并未在原有基礎(chǔ)上產(chǎn)生新的模式.

(ii) 交叉操作對(duì)模式集?的生存數(shù)量的影響

由于選擇操作不能檢索新的種群區(qū)域,為此增加交叉操作.這里采用單點(diǎn)交叉(這并不影響定理的證明).由于單點(diǎn)交叉時(shí)隨機(jī)選擇1到l ?1位點(diǎn)中某一位點(diǎn)作為交叉點(diǎn),交換交叉位點(diǎn)之后的所有對(duì)應(yīng)字符子串,當(dāng)交叉操作作用在模式集?所包含所有模式{Hi|i ∈NP}的定義距{li|i ∈NP}之內(nèi),模式集?有被破壞的可能,應(yīng)該明確注意到,即使交叉操作作用在模式的定義距內(nèi)部,模式集同樣存在不被破壞的可能.

由上式(2.8)可以看出,定義距δ(Hi)越大,模式被破壞的概率越大.一般地,對(duì)任意模式{Hi|i ∈NP}可以計(jì)算出經(jīng)交叉操作后生存概率的下界為Psurvival,在單點(diǎn)操作作用下,任一長(zhǎng)度為{li|i ∈NP}的模式的生存概率為那么,在交叉作用下模式集?存活概率(?存活估計(jì)值)為:

現(xiàn)考慮模式集?在選擇和交叉兩種操作用下的生存數(shù)量有如下估計(jì)式:

這表明,模式集?增加或衰減依賴于平均適應(yīng)度函數(shù)值以及定義距δ(Hi).當(dāng)f(?,t)>(t)且δ(Hi)較小時(shí),模式集?的生存數(shù)量呈現(xiàn)指數(shù)級(jí)增長(zhǎng).反之,呈現(xiàn)指數(shù)級(jí)衰減.

(iii) 收縮因子F對(duì)模式集?的生存數(shù)量的影響

DE算法是以差分形式V t+1i=Xti3+F ·(Xti1?Xti2)進(jìn)行變異的,其中F類似于進(jìn)化算法中的變異概率,則對(duì)任一模式{Hi|i ∈NP}的每一位點(diǎn)發(fā)生變異的概率為F,那么該位點(diǎn)不發(fā)生變異的概率為1?F,若每一模式Hi在變異操作作用下能夠生存下來(lái)(即Hi不受破壞),也就意味著該模式Hi確定位點(diǎn)上的字符在變異時(shí)不能發(fā)生任何變化,又因?yàn)槟Ｊ紿i的階為O(Hi),則在變異操作作用下模式Hi不被破壞的概率為(1?F)O(Hi),從而模式集?在變異操作作用下不被破壞的概率為或者寫(xiě)成(1?F)Θ(?),它們之間是等價(jià)的關(guān)系.

綜上所述,經(jīng)過(guò)選擇,交叉,變異操作后,X(t+1)含有模式集?中元素的個(gè)數(shù)期望值如下式所示:

同時(shí),由于收縮因子與變異概率在種群中個(gè)體的作用上是相當(dāng)?shù)?假設(shè)種群規(guī)模為NP的種群X(t) ={Xi(t)|i ∈{1,2,··· ,NP}}中每一個(gè)體的變異概率為{Pi|i ∈{1,2,··· ,NP};Pi ∈(0,1)},在種群規(guī)模為NP的種群X(t)中,任取三個(gè)相異個(gè)體{Xij|j=1,2,3},于是將(1.6) 式可改寫(xiě)為如下式子:

由于相異個(gè)體{Xij|j= 1,2,3}所屬模式{Hij|j= 1,2,3}也是相異的,同樣地,三個(gè)相異個(gè)體的變異概率{Pi|i ∈{1,2,3};Pi ∈(0,1)}是隨機(jī)相異的,因而模式{Hij|j= 1,2,3}關(guān)于下一代模式和變異概率分別滿足下式:

同樣地,

其中,這里的P是一個(gè)理論上的具有概率特征的數(shù)學(xué)量,在算子操作作用下起到改變個(gè)體編碼數(shù)值的作用,但僅僅是一種改變具體數(shù)值編碼的可能性,在尋優(yōu)過(guò)程中,由于自然環(huán)境或是其它影響因素,這種概率上的改變會(huì)更加明顯,最終使得個(gè)體的數(shù)值編碼發(fā)生改變,從而產(chǎn)生個(gè)體變異,實(shí)現(xiàn)進(jìn)一步交叉和選擇的可能,為產(chǎn)生新的尋優(yōu)個(gè)體提供客觀條件.在實(shí)際操作中應(yīng)該對(duì)于不同模式{Hij|j=1,2,3}的變異概率,也即如下式子:

其中上面兩式在理論說(shuō)明上是等價(jià)的,由此可得,

當(dāng)F <1,CR<1時(shí),(1?F)Θ(?)≈1?F ·Θ(?),且

注意到(2.17)式以及選擇、變異、交叉三種算子對(duì)模式集?中所有模式{Hi(t)|i ∈{1,2,··· ,NP}}的生存數(shù)量的分析,可以得出以下結(jié)論:

結(jié)論成立.

定理2.2(模式集定理) 對(duì)DE算法進(jìn)行十進(jìn)制整數(shù)編碼,在DE選擇、交叉、變異操作作用下,具有較低模式集階、較短模式集距、較高適應(yīng)度函數(shù)值的模式集的生存數(shù)量,隨種群迭代次數(shù)的增加呈現(xiàn)指數(shù)級(jí)增長(zhǎng).

推論2.1在DE算法中,低階、短距且適應(yīng)度函數(shù)值高于平均適應(yīng)度函數(shù)值的模式集?,在子代種群中的數(shù)量期望值以指數(shù)形式增加.

推論2.2在定理2.1證明過(guò)程中,有效地縮減了收縮因子的變化范圍,將F的變化范圍在理論上縮小到(0,1)區(qū)間,同時(shí)也體現(xiàn)了收縮因子與變異概率在種群演化過(guò)程中具有概率上的相當(dāng)性特征,和Storn教授與Price教授在文[1]中對(duì)F的取值為0.5左右吻合,與文[21-26]將F均取值為(0,1)區(qū)間高度吻合.

推論2.3在種群規(guī)模為NP的種群中,適應(yīng)度函數(shù)值高于平均適應(yīng)度函數(shù)值的模式集?中任意模式{Hi|i ∈{1,2,··· ,NP}}將會(huì)按照指數(shù)級(jí)增長(zhǎng)方式被選擇.

3.結(jié)語(yǔ)

本文基于十進(jìn)制整數(shù)編碼基礎(chǔ)上嘗試在理論層面推導(dǎo)出選擇、交叉、變異等操作算子在推動(dòng)種群演化、種群尋優(yōu)的模式集定理(即DE算法推動(dòng)種群演化的動(dòng)力學(xué)機(jī)制),研究結(jié)論表明,在DE選擇、交叉、變異等操作算子作用下,具有較低模式集階、較短模式集距、較高適應(yīng)度函數(shù)值的模式集的生存數(shù)量,將隨種群迭代次數(shù)的增加呈現(xiàn)指數(shù)級(jí)增長(zhǎng).該定理從根本上說(shuō)明了差分進(jìn)化算法(Differential Eveolution,簡(jiǎn)稱DE)在推動(dòng)種群尋優(yōu)的動(dòng)力學(xué)機(jī)制,有效解決了離散種群個(gè)體在全局尋優(yōu)方面的動(dòng)力學(xué)演化機(jī)制,為后續(xù)研究連續(xù)型種群個(gè)體的動(dòng)力學(xué)演化機(jī)制提供了研究基礎(chǔ).在研究之余,我們隱約感覺(jué)到在生物學(xué)意義上的閉生態(tài)種群中的個(gè)體具有量子特征,至于這樣的量子特征在尋優(yōu)過(guò)程是如何體現(xiàn)的,以及體現(xiàn)出來(lái)的是何種量子特征,還有待于進(jìn)一步研究和討論.同時(shí)還研究了收縮因子F與變異概率的相當(dāng)性特征,將收縮因子F的范圍縮小至(0,1)區(qū)間.本文提出的十進(jìn)制整數(shù)編碼DE算法的模式定理在理論層面較好解釋了種群演化的內(nèi)部動(dòng)力學(xué)機(jī)制.