孫思雨　孫良旭　蘇曉磊　趙環(huán)宇

摘要：論文重點(diǎn)討論了分布估計(jì)算法的理論研究。首先，抽取出分布估計(jì)算法的核心思想，然后旨在使用EDA算法解決復(fù)雜優(yōu)化問題，提出基于近似動(dòng)態(tài)規(guī)劃的分布估計(jì)算法。通過Agent與環(huán)境的交互，將近似動(dòng)態(tài)規(guī)劃引入到進(jìn)化計(jì)算中，獲得概率模型并進(jìn)行適應(yīng)性的更新。測(cè)試函數(shù)使用六個(gè)經(jīng)典的對(duì)比實(shí)驗(yàn)，結(jié)果表明本算法的魯棒性，運(yùn)行時(shí)間短并具有較強(qiáng)的全局搜索能力，可以作為解決函數(shù)優(yōu)化問題的有效解決算法。

關(guān)鍵詞：分布估計(jì)算法；近似動(dòng)態(tài)規(guī)劃；進(jìn)化搜索

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）30-7173-04

1 分布估計(jì)算法

為克服遺傳算法由于染色體重新排列導(dǎo)致的鏈?zhǔn)絾栴}，分布估計(jì)算法（estimation of Distribution Algorithm， EDA）不使用交叉和變異操作，而是通過從發(fā)現(xiàn)的信息來優(yōu)化解集，并使用這些信息生成新的概率分布模型和解。概率模型使用全新的進(jìn)化計(jì)算的思路，成為EDA算法的理論基礎(chǔ)。EDA算法[1]的概念最初在1996年提出并得到了快速發(fā)展，近年來成為智能進(jìn)化領(lǐng)域的研究熱點(diǎn)。EDA算法[2-4]提出了一種全新的進(jìn)化模式，通過概率模型描述候選解的空間分布，并利用概率模型隨機(jī)采樣生產(chǎn)新種群，實(shí)現(xiàn)種群的進(jìn)化過程。避免盲目地重組和混合染色體的基因，能有效的增強(qiáng)搜索效率，快速生成高可靠性的解，這是傳統(tǒng)的遺傳算法無(wú)法解決的問題。

2 基于近似動(dòng)態(tài)規(guī)劃的EDA算法

2.1 問題描述

分析發(fā)現(xiàn)現(xiàn)存的分布估計(jì)算法沒有較好的執(zhí)行效果大多是因?yàn)楦怕氏蛄客ǔ６疾捎靡环N固定的策略來進(jìn)行更新，這種方式不僅無(wú)法保證整個(gè)進(jìn)化過程的策略的有效性，同時(shí)沒有考慮到進(jìn)化基因位的差異。如果每個(gè)基因位概率的相應(yīng)值在進(jìn)化更新過程中能夠被自適應(yīng)更新，將有助于改進(jìn)進(jìn)化搜索的執(zhí)行效率。為了獲取自適應(yīng)更新的概率向量，將每個(gè)基因位與Agent相關(guān)聯(lián)，并根據(jù)動(dòng)作選擇概率更新規(guī)則。這樣，每一次更新的概率值轉(zhuǎn)換為agent執(zhí)行一個(gè)動(dòng)作。如果群組隨著環(huán)境進(jìn)一步的進(jìn)化，每個(gè)agent都能夠使用強(qiáng)化學(xué)習(xí)的方法，與環(huán)境交互來尋找最優(yōu)的動(dòng)作策略。

Q學(xué)習(xí)作為經(jīng)典的強(qiáng)化學(xué)習(xí)算法不需要估計(jì)環(huán)境模型，只需要通過Q函數(shù)的迭代計(jì)算來獲得最優(yōu)的動(dòng)作策略，動(dòng)作策略將會(huì)隨著agent的不斷學(xué)習(xí)而更新。該文提出的基于Q學(xué)習(xí)的分布估計(jì)算法（QEDA）就是基于這個(gè)概念。

2.2 算法設(shè)計(jì)

基于Q學(xué)習(xí)的分布估計(jì)算法能夠解決二進(jìn)制編碼，種群規(guī)模位N，編碼長(zhǎng)度為m，初始的概率向量表示為p（t）=（p1（t）， p2（t）……pm（t）），其中pi（t）表示第i個(gè)基因位取1的概率。每次迭代包括選擇、更新概率模型和采樣以及其他操作。

采樣操作與PBIL、UMDA等相似的算法使用蒙特卡羅方法，根據(jù)概率向量隨機(jī)產(chǎn)生N個(gè)個(gè)體的種群。根據(jù)每一代的最優(yōu)子群的適應(yīng)度來選擇參數(shù)，同時(shí)根據(jù)選擇比r（0

Q學(xué)習(xí)算法更新pi（t），需要每個(gè)基因位都與一個(gè)agent相關(guān)聯(lián)，而且與相應(yīng)的每一代的組群位作為環(huán)境同步進(jìn)化。環(huán)境狀態(tài)的定義是能夠識(shí)別基因位在在進(jìn)化過程的不同階段，因此，根據(jù)gi（t）和bi（t）來定義狀態(tài)之間的關(guān)系。

定義一個(gè)較大的頻閾集[θhigh]，較小的頻閾定義為[θlow]，[θdiff]被定義為頻率差，Agenti前t代的狀態(tài)被劃分為：

1）[gi（t）>θhigh]且[bi（t）>θhigh]，或者[gi（t）<θlow]且[bi（t）<θlow]；

2） [gi（t）-bi（t）>θdiff]；

3） 不滿足上述條件的其他情況

Agenti，第一代種群的動(dòng)作t集合包括如下概率更新規(guī)則：

1）動(dòng)作1：概率降低[Pi（t+1）=βpi（t）] （0）

2） 動(dòng)作2：概率增加[Pi（t+1）=1-β[1-pi（t）]] （1）

3） 動(dòng)作3：概率值不變[Pi（t+1）=pi（t）] （2）

式（0）～（2）中i=1，2……m， [β（0<β<1）]是學(xué)習(xí)速率。Agenti與環(huán)境進(jìn)行交換，可以選擇合適的動(dòng)作來獲得并產(chǎn)生下一點(diǎn)的概率pi（t+1）。為了將Agenti存儲(chǔ)到Q表中，定義Q矩陣：[Qi=[Qi（sj，ak）]3×3] （3）

每次迭代算法，每個(gè)Agenti使用[ε]貪婪策略選擇動(dòng)作，跟轉(zhuǎn)換后的回報(bào)和狀態(tài)更新Q表的值。第一代t-1時(shí)刻Agenti的狀態(tài)為s，選擇執(zhí)行動(dòng)作a，狀態(tài)轉(zhuǎn)換為s。使用式（4）、（5）更新[Qi（s，a）]：

[Qi（s，a）←Qi（s，a）+α[ri（t-1）+γmaxQi（s'，a'）-Qi（s，a）]] （4）

其中[ri（t-1）=1 |pi（t）-gi（t）|<|pi（t-1）-gi（t-1）|-1 otherwise] （5）

[ri（t-1）]表示Agenti在t-1時(shí)刻獲得的直接回報(bào)。

基于Q學(xué)習(xí)的分布估計(jì)算法可以描述為以下步驟。算法代替精英策略群組，保證最優(yōu)解搜索而不發(fā)生退化。

算法1：基于Q學(xué)習(xí)的分布估計(jì)算法

步驟2：初始化Qi=0，i=1，2……m；設(shè)置P（1）=（0.5，0.5……0.5），t=1。

步驟3： While（終止條件不滿足）do

步驟4：根據(jù)P（t）采樣第N-1代的種群，并使用最優(yōu)的個(gè)體代表當(dāng)前群組。新個(gè)體確定第i位值：生成一個(gè)隨機(jī)數(shù)[ξ∈[0，1]]，如果[ξ≤pi（t）]第i位選擇1，否則第i為選擇0；

步驟5：計(jì)算N個(gè)個(gè)體的適應(yīng)度函數(shù)并排序；

步驟6：根據(jù)頻率gi（t）和bi（t），i=1，2…m，選擇M個(gè)最優(yōu)個(gè)體和最差個(gè)體；

步驟7：對(duì)每個(gè)基因位i，記錄t-1時(shí)刻的狀態(tài)s和采取的動(dòng)作a，通過gi（t）和bi（t）確定當(dāng)前狀態(tài)s；使用式（5）計(jì)算直接回報(bào)，根據(jù)式（3） 、（4） 更新Q表值[Qi（s，a）]。

步驟8：生成隨機(jī)數(shù)[ξi∈[0，1]]，如果[ξi≤pi（t）τ0=50]，則隨即選擇一個(gè)動(dòng)作a，否則使用[a'=argmax Qi（s'，a'）]選擇動(dòng)作。

步驟9：根據(jù)式（0）～（2）以及動(dòng)作a，根據(jù)相應(yīng)的公式計(jì)算pi（t+1）的新概率值。

步驟10：結(jié)束。

2.3 改進(jìn)策略

算法每次更新概率pi（t），Agenti使用[ε]貪婪策略隨機(jī)選擇動(dòng)作，使用1-[ε]概率按照當(dāng)前狀態(tài)最大Q值選擇動(dòng)作。由于[ε]貪婪策略不會(huì)總能選擇到最佳的動(dòng)作，所有總是以較小的概率進(jìn)行隨機(jī)選擇動(dòng)作。通過增加隨機(jī)選擇的概率，能夠讓Agent探索新知識(shí)，比[ε]貪婪策略獲得更好的結(jié)果。

然而，使用固定的[ε]值具有一定的局限性，尤其是當(dāng)Agent經(jīng)過足夠多次學(xué)習(xí)以后，當(dāng)前的策略已經(jīng)接近于最有策略，如果仍然以[ε]概率隨機(jī)選擇動(dòng)作的話，將會(huì)影響算法的收斂速度。如果可以逐漸的減少探索概率的影響，能很大程度上提高基于Q學(xué)習(xí)的分布估計(jì)算法的執(zhí)行效率。使用模擬退火法算法的MetroPolis規(guī)則能夠解決這個(gè)問題，它通過隨著溫度的降低逐步降低發(fā)生劣質(zhì)解得概率。

下面給出使用改進(jìn)的MetroPlis規(guī)則的基于Q學(xué)習(xí)的分布估計(jì)算法的設(shè)計(jì)規(guī)則。

算法2：改進(jìn)的基于Q學(xué)習(xí)的分布估計(jì)算法

步驟1：初始化Qi=0，i=1，2……m；初始溫度[temperatureτ=τ0]；設(shè)置P（1）=（0.5，0.5……0.5），t=1。

步驟2： While（終止條件不滿足）do

步驟3：根據(jù)P（t）采樣第N-1代的種群，在t-1時(shí)刻使用最優(yōu)的個(gè)體代表當(dāng)前群組。

步驟4：計(jì)算N個(gè)個(gè)體的適應(yīng)度函數(shù)并排序；

步驟5：根據(jù)頻率gi（t）和bi（t），i=1，2…m，選擇M個(gè)最優(yōu)個(gè)體和最差個(gè)體；

步驟6：對(duì)每個(gè)基因位i，記錄t-1時(shí)刻的狀態(tài)s和采取的動(dòng)作a，通過gi（t）和bi（t）確定當(dāng)前狀態(tài)s；使用式（5）計(jì)算直接回報(bào)，根據(jù)式（4）更新Q表值[Qi（s，a）]。

步驟7：使用[a'=argmax Qi（s'，a''）]選擇動(dòng)作[ar]，根據(jù)如下概率確定動(dòng)作[a']。

[P{a'=ar}=eQ（s，a'）-Q（s，a*）τ] （6）

[P{a'=a*}=1-P{a'=ar}] （7）

步驟8：根據(jù)式（0）～（2）以及動(dòng)作a重新計(jì)算pi（t+1）的概率值；

步驟9：結(jié)束。

冷卻：[τ←λτ；]

[t←t+1].

幾何冷卻策略算法使[τ←λτ]，其中[λ∈（0，1）]是溫度系數(shù)。隨著溫度的降低，Agenti隨機(jī)選擇動(dòng)作的概率越來越小，當(dāng)溫度趨于0時(shí)，策略相當(dāng)于貪婪策略。

3 對(duì)比實(shí)驗(yàn)

3.1 測(cè)試函數(shù)

為了評(píng)價(jià)基于Q學(xué)習(xí)的分布估計(jì)算法的執(zhí)行效率，用本算法與經(jīng)典的UMDA、PBIL、MIMIC算法、遺傳算法進(jìn)行比較。選擇6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試。Sphere函數(shù)、Quadric函數(shù)、Schaffer函數(shù)、griewank函數(shù)、Rosenbrock函數(shù)和Rastrigin函數(shù)。不同形式的標(biāo)準(zhǔn)測(cè)試函數(shù)具有較好額運(yùn)行效果。Schaffer函數(shù)、Griewank函數(shù)和Rastrigin函數(shù)是多峰函數(shù)，具有多個(gè)局部最小值，通常更難以找到全局最小解。算法用于測(cè)試其跳過局部最小進(jìn)行全局尋優(yōu)的能力。Rosenbrock函數(shù)式單峰、非凸病態(tài)函數(shù)值域上具有單調(diào)特性。全局最優(yōu)點(diǎn)的收斂于遠(yuǎn)方，可以使用有效算法來對(duì)其進(jìn)行估計(jì)。Sphere函數(shù)和Quadric函數(shù)式單峰函數(shù)，能夠測(cè)量?jī)?yōu)化算法的準(zhǔn)確性，檢驗(yàn)算法的實(shí)現(xiàn)程度。

3.2 實(shí)驗(yàn)結(jié)果分析

經(jīng)過測(cè)試，基于Q學(xué)習(xí)的分布估計(jì)算法參數(shù)如下：頻閾[θhigh]=0.75，[θlow]=0.25，[θdiff]=0.35，選擇[γ]=0.2，調(diào)節(jié)率[β]=0.9，學(xué)習(xí)因子[α]=0.2，折扣因子為0.9。比較UMDA算法選擇率設(shè)置為0.2，PBIL算法學(xué)習(xí)率設(shè)置為0.1，MIMIC算法選擇率設(shè)置為0.4，遺傳算法使用單點(diǎn)交叉，交叉率為0.7，變異率為0.1。所有算法的種群規(guī)模設(shè)置為50，終止條件設(shè)置為找到全局最有接或者進(jìn)化代數(shù)為T，T設(shè)置為200。

考慮的上述算法都具有一定的隨機(jī)性，使用函數(shù)f1～f6分別獨(dú)立測(cè)試50次，實(shí)驗(yàn)結(jié)果如表所示。表1顯示了每個(gè)算法獲得全局最優(yōu)解的個(gè)數(shù)。表2顯示了50次測(cè)試的平均值、標(biāo)準(zhǔn)差和最差值。表3顯示了每種方法的平均運(yùn)行時(shí)間（單位：秒）。其中QEDA表示基于Q學(xué)習(xí)的分布估計(jì)算法，MEDA表示使用MetroPolis和[ε]貪婪策略的基于Q學(xué)習(xí)的分布估計(jì)算法。QEDA選擇[ξ]=0.5，MEDA的初始溫度設(shè)為[τ0=50]，溫度系數(shù)[λ=0.9]。

可以看出，無(wú)論是傳統(tǒng)的遺傳算法還是UMDA、PBIL、MIMIC算法，在解決復(fù)雜問題的函數(shù)優(yōu)化中，都不容易找到全局最優(yōu)解。而PBIL搜索成功率高68%，其他三種算法低50%左右。基于Q學(xué)習(xí)的分布估計(jì)算法運(yùn)行效率最高，尤其是使用了MetroPolis規(guī)則的基于Q學(xué)習(xí)的分布估計(jì)算法，對(duì)于6個(gè)標(biāo)準(zhǔn)函數(shù)都能夠找到全局的最優(yōu)解。在算法的執(zhí)行時(shí)間上，雙變量相關(guān)的MIMIC算法執(zhí)行效率最差。而使用了MetroPolis規(guī)則的基于Q學(xué)習(xí)的分布估計(jì)算法與PBIL算法都求解了Rosenbrock函數(shù)，而且在執(zhí)行時(shí)間上也是最好的。endprint

參考文獻(xiàn)：

[1] Larranaga P， Lozano J A， Estimation of Distribution Algorithms： a New Tool for Evolutionary Computation [M]. Boston： Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning： A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163， Pittsburgh， PA ，1994.

[3] Mühlenbein H，Paa G.From recombination of genes to the estimation of distributions I. Binary parameters， in： Parallel Problem Solving from Nature，1996：178-187.

[4] Pelikan M，Goldberg D E，Lobo F.A survey of optimization by building and using probabilistic models， Computational Optimization and Applications，2002（21）：5-20.

[5] Sergios T， Konstantinos K.Pattern Recognition， Second Edition[M]. San Diego： Academic Press，2003.

[6] Dasgupta D，F(xiàn)orrest S.Artificial immune systems and their applications[M].Berlin：Spring-Verlag，1998.

[7] Slowinski R， Hapke M. Scheduling under fuzziness[M]. New York： Physica-Verlag，2000.

[8] Seber G A R Linear regression analysis[M]. New York： John Wiley，1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System，1989，I（1）.endprint

參考文獻(xiàn)：

[1] Larranaga P， Lozano J A， Estimation of Distribution Algorithms： a New Tool for Evolutionary Computation [M]. Boston： Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning： A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163， Pittsburgh， PA ，1994.

[3] Mühlenbein H，Paa G.From recombination of genes to the estimation of distributions I. Binary parameters， in： Parallel Problem Solving from Nature，1996：178-187.

[4] Pelikan M，Goldberg D E，Lobo F.A survey of optimization by building and using probabilistic models， Computational Optimization and Applications，2002（21）：5-20.

[5] Sergios T， Konstantinos K.Pattern Recognition， Second Edition[M]. San Diego： Academic Press，2003.

[6] Dasgupta D，F(xiàn)orrest S.Artificial immune systems and their applications[M].Berlin：Spring-Verlag，1998.

[7] Slowinski R， Hapke M. Scheduling under fuzziness[M]. New York： Physica-Verlag，2000.

[8] Seber G A R Linear regression analysis[M]. New York： John Wiley，1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System，1989，I（1）.endprint

參考文獻(xiàn)：

[1] Larranaga P， Lozano J A， Estimation of Distribution Algorithms： a New Tool for Evolutionary Computation [M]. Boston： Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning： A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163， Pittsburgh， PA ，1994.

[3] Mühlenbein H，Paa G.From recombination of genes to the estimation of distributions I. Binary parameters， in： Parallel Problem Solving from Nature，1996：178-187.

[4] Pelikan M，Goldberg D E，Lobo F.A survey of optimization by building and using probabilistic models， Computational Optimization and Applications，2002（21）：5-20.

[5] Sergios T， Konstantinos K.Pattern Recognition， Second Edition[M]. San Diego： Academic Press，2003.

[6] Dasgupta D，F(xiàn)orrest S.Artificial immune systems and their applications[M].Berlin：Spring-Verlag，1998.

[7] Slowinski R， Hapke M. Scheduling under fuzziness[M]. New York： Physica-Verlag，2000.

[8] Seber G A R Linear regression analysis[M]. New York： John Wiley，1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System，1989，I（1）.endprint