第五章-分布估計(jì)算法研究

第五章分布估計(jì)算法研究遺傳算法是廣泛應(yīng)用的智能優(yōu)化算法，通過選擇、交叉和變異三種基本操作實(shí)現(xiàn)全局最優(yōu)解的搜索。遺傳算法獲得巨大成功的理論基礎(chǔ)是建筑塊理論[1]，該理論指出遺傳算法具有通過組合個(gè)體的建筑塊獲得最優(yōu)解的能力。建筑塊理論能夠有效使用的重要條件是在數(shù)據(jù)編碼中能夠明確表示建筑塊的位置[2,3]，否則遺傳算法中的交叉和變異操作就有可能破壞建筑塊，特別是那些較長(zhǎng)的或距離較遠(yuǎn)的塊，從而導(dǎo)致算法的收斂速度下降或找不到最優(yōu)解[4]。分布估計(jì)算法（EstimationofDistributionAlgorithm,EDA）源于遺傳算法，是為解決遺傳算法中存在的因交叉、變異操作而導(dǎo)致的建筑塊破壞問題而提出的[5,6]。在分布估計(jì)算法中沒有交叉和變異操作，取而代之的是對(duì)于選擇出來的優(yōu)勢(shì)群體的概率分布模型進(jìn)行估計(jì)，并根據(jù)估計(jì)的模型進(jìn)行采樣。由于分布估計(jì)算法具有更強(qiáng)的理論基礎(chǔ)，因此受到廣大學(xué)者的重視，成為當(dāng)前進(jìn)化計(jì)算領(lǐng)域的研究熱點(diǎn)[7~10]。5.1引言與遺傳算法類似，分布估計(jì)算法也是基于群體的一種進(jìn)化算法，算法由一個(gè)初始群體開始，在每代循環(huán)中，首先根據(jù)每個(gè)個(gè)體的適應(yīng)值選擇出具有代表性的適應(yīng)值較好的一些個(gè)體組成優(yōu)勢(shì)群體。然后根據(jù)優(yōu)勢(shì)群體估計(jì)其中的個(gè)體所服從的概率分布模型，比如聯(lián)合正態(tài)分布。第三步便是根據(jù)估計(jì)的概率分布模型采樣產(chǎn)生一些新個(gè)體，并用來替換原有群體中的部分個(gè)體，從而組成新一代的群體。當(dāng)滿足循環(huán)終止條件時(shí)，算法結(jié)束，當(dāng)前群體中的適應(yīng)值最好的個(gè)體就是算法優(yōu)化的結(jié)果。與遺傳算法相比，分布估計(jì)算法中沒有了交叉和變異兩個(gè)操作，而是對(duì)選擇群體的概率分布模型進(jìn)行估計(jì)和采樣。由于建筑塊中的變量相關(guān)性要比其他變量之間的相關(guān)性強(qiáng)。分布估計(jì)算法更注重變量的相關(guān)結(jié)構(gòu)，對(duì)建筑塊的分布情況進(jìn)行整體估計(jì)，這樣不僅可以避免交叉變異所帶來的建筑塊破壞問題，反而有助于建筑塊的增長(zhǎng)。分布估計(jì)算法的基本步驟如下：Step1：初始化群體。在搜索空間內(nèi)按均勻分布隨機(jī)產(chǎn)生PS個(gè)點(diǎn)，組成初始群體，記進(jìn)化代數(shù)g為1。Step2：計(jì)算適應(yīng)值。根據(jù)適應(yīng)值評(píng)價(jià)函數(shù)計(jì)算第g代群體中的各點(diǎn)的適應(yīng)值。Step3：選擇優(yōu)勢(shì)群體。根據(jù)適應(yīng)值，運(yùn)用一定的選擇策略（如截?cái)噙x擇，輪賭選擇等）選出適應(yīng)值較好的s個(gè)個(gè)體組成優(yōu)勢(shì)群體。Step4：估計(jì)優(yōu)勢(shì)群體的概率分布模型。一般假設(shè)優(yōu)勢(shì)群體服從某一類概率分布模型，然后以優(yōu)勢(shì)群體為樣本，對(duì)具體的概率分布F進(jìn)行估計(jì)。Step5：根據(jù)估計(jì)的概率模型進(jìn)行采樣，產(chǎn)生一些新個(gè)體。在搜索空間內(nèi)按概率分布F隨機(jī)產(chǎn)生l個(gè)點(diǎn)，作為新生代中的部分個(gè)體。Step6：更新群體。由第g代群體中m個(gè)適應(yīng)值較好的個(gè)體，新生的l個(gè)個(gè)體，以及隨機(jī)產(chǎn)生（或者以較好個(gè)體為初始點(diǎn)搜索等方式產(chǎn)生）的PS-m-l個(gè)個(gè)體組成新一代群體，并將進(jìn)化代數(shù)g←g+1。Step7：若滿足某種停止準(zhǔn)則，則算法結(jié)束，g代群體中的最好個(gè)體就是優(yōu)化的結(jié)果；否則算法轉(zhuǎn)到Step2繼續(xù)執(zhí)行。根據(jù)變量相關(guān)性的情況，一般認(rèn)為分布估計(jì)算法可分為以下三類：各變量相互獨(dú)立的分布估計(jì)算法，變量?jī)蓛上嚓P(guān)的分布估計(jì)算法和多變量相關(guān)的分布估計(jì)算法。前兩類分布估計(jì)算法在運(yùn)算復(fù)雜度方面優(yōu)于第三類算法，但由于其不能充分考慮變量的相關(guān)性，因此在復(fù)雜問題的優(yōu)化效果方面要次于第三類算法。下面對(duì)這三類算法中的代表性算法進(jìn)行簡(jiǎn)單的介紹和分析。5.1.1變量相互獨(dú)立的分布估計(jì)算法PBIL（Population-BasedIncrementalLearning）[11]和UMDA（UnivariateMarginalDistributionAlgorithm）[12]都是典型的變量相互獨(dú)立的分布估計(jì)算法，它們僅考慮離散變量。對(duì)于選擇出來的優(yōu)勢(shì)群體，根據(jù)每個(gè)變量的取值情況估計(jì)其一維邊緣分布，由于在這類算法中所考慮的變量是相互獨(dú)立的，因此反映群體分布情況的聯(lián)合分布為各邊緣分布之積。兩種方法的不同之處在于它們更新概率模型的方式不同。PBIL采用線性調(diào)整概率模型的方式，在原有概率模型的基礎(chǔ)上，根據(jù)優(yōu)勢(shì)群體的分布情況，各邊緣分布按一定的學(xué)習(xí)速率進(jìn)行線性調(diào)整，即pk(X)=∏ipk(xi)=∏i[α×pk-1(xi)+(1-α)×ni/N]。當(dāng)α=0時(shí)，PBIL等價(jià)于UMDA。UMDA則根據(jù)優(yōu)勢(shì)群體的分布情況直接確定概率模型，即pk(X)=∏ip(xi|Dk-1s)。cGA（compactGeneticAlgorithm）[13]也是變量獨(dú)立的分布估計(jì)算法，它需要較小空間，因?yàn)槠淙后w規(guī)模僅為2，在每代運(yùn)行時(shí)比較兩個(gè)個(gè)體的適應(yīng)值，并將較好的個(gè)體作為概率模型。在連續(xù)域內(nèi)的變量獨(dú)立的分布估計(jì)算法有PBILc[14,15]和UMDAcG[16],它們分別是PBIL和UMDA在連續(xù)域內(nèi)的擴(kuò)展，邊緣分布使用的是一元正態(tài)分布。這類算法在解決優(yōu)化變量之間獨(dú)立的問題時(shí)表現(xiàn)非常好，并能有效解決遺傳算法帶來的建筑塊破壞問題，但是在優(yōu)化變量之間存在相關(guān)性的問題時(shí)則表現(xiàn)的非常差，其原因是算法中沒有考慮到優(yōu)化變量的相關(guān)性。5.1.2變量?jī)蓛上嚓P(guān)的分布估計(jì)算法最初考慮變量相關(guān)性的分布估計(jì)算法將變量關(guān)系簡(jiǎn)化為兩兩相關(guān)，典型的算法有MIMIC（MutualInformationMaximizationforInputClustering）[17]、COMIT（CombiningOptimizerwithMutualInformationTree）[18]和BMDA（BivariateMarginalDistributionAlgorithm）[19]。它們分別采用鏈狀結(jié)構(gòu)、樹結(jié)構(gòu)和森林來表示兩兩相關(guān)的變量關(guān)系。在MIMIC中概率模型表示為pkπ(X)=pk(xi1|xi2)…pk(xin-1|xin)pk(xin)，為了找到變量(x1,x2,…,xn)的最佳排列π=(i1,i2,…,in)，MIMIC算法使用貪婪算法最小化兩個(gè)概率分布之間的K-L距離。COMIT采用樹結(jié)構(gòu)表示變量的兩兩相關(guān)性，通過反復(fù)最小化相互信息指標(biāo)來向樹結(jié)構(gòu)中不斷加入最大的枝。BMDA使用Pearson的χ2測(cè)試決定變量連接到哪棵樹中以及樹中變量的依賴關(guān)系。連續(xù)域的此類算法如MIMIC在連續(xù)域中的擴(kuò)展MIMICcG[16]，其中使用了二元正態(tài)分布表示邊緣分布。為找到最優(yōu)排列，MIMICcG最小化的條件熵為。兩兩相關(guān)的分布估計(jì)算法考慮了優(yōu)化變量的部分關(guān)系并且其結(jié)構(gòu)學(xué)習(xí)也比較容易，在解決一些變量不獨(dú)立的優(yōu)化問題時(shí)表現(xiàn)也較好，比如算法COMIT和BMDA能夠有效的優(yōu)化二維spin-glass問題。但對(duì)于變量關(guān)系更為復(fù)雜的優(yōu)化問題，這類算法則表現(xiàn)得較差。5.1.3多變量相關(guān)的分布估計(jì)算法多變量相關(guān)的分布估計(jì)算法能夠全面考慮優(yōu)化問題的結(jié)構(gòu)，但其模型學(xué)習(xí)的復(fù)雜度也相對(duì)較高。根據(jù)表示變量關(guān)系的網(wǎng)絡(luò)結(jié)構(gòu)可以分為有向網(wǎng)絡(luò)的分布估計(jì)算法、基于無向網(wǎng)絡(luò)的分布估計(jì)算法和基于一般網(wǎng)絡(luò)結(jié)構(gòu)的分布估計(jì)算法。Bayesian網(wǎng)絡(luò)是有向無環(huán)圖，典型的基于Bayesian網(wǎng)絡(luò)的分布估計(jì)算法有BOA（BayesianOptimizationAlgorithm）[20,21]、EBNA（EstimationofBayesianNetworkAlgorithm）[22,23]和EGNA（EstimationofGaussianNetworkAlgorithm）[24]。此類算法中使用Bayesian網(wǎng)絡(luò)表示變量關(guān)系，根據(jù)選擇出的群體估計(jì)網(wǎng)絡(luò)的結(jié)構(gòu)和參數(shù)，并根據(jù)估計(jì)的Bayesian網(wǎng)絡(luò)模型進(jìn)行采樣生成下一代群體。BOA使用BD量（Bayesian-Dirichletmetric）和貪婪算法學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)。EBNA使用BIC量（BayesianInformationCriteriametric）來衡量網(wǎng)絡(luò)結(jié)構(gòu)。此類算法在優(yōu)化復(fù)雜的變量相關(guān)問題時(shí)效果很好，但是Bayesian網(wǎng)絡(luò)的學(xué)習(xí)本身是NP難問題，因此算法的時(shí)間復(fù)雜度較高，多數(shù)時(shí)間花費(fèi)在模型的估計(jì)上。EGNA是連續(xù)域分布估計(jì)算法，使用高斯網(wǎng)絡(luò)表示變量的關(guān)系，該網(wǎng)絡(luò)由貝葉斯得數(shù)、懲罰極大似然得數(shù)和邊排除測(cè)試決定，變量的概率密度由高斯分布表示。Markov網(wǎng)絡(luò)是無向圖，基于Markov網(wǎng)絡(luò)的分布估計(jì)算法有FDA（FactorizedDistributionAlgorithm）[25]、DEUM（DistributionEstimationUsingMarkovnetworkalgorithm）[26-28]、MN-FDA（MarkovNetworkFactorizedDistributionAlgorithm）[29]、MN-EDA（MarkovNetworkEstimationofDistributionAlgorithm）[30]、MOA（MarkovianitybasedOptimizationAlgorithm）[31]和MARLEDA（MarkovianLearningEstimationofDistributionAlgorithm）[32]。FDA用固定的概率圖模型表示變量關(guān)系，但需要有關(guān)于變量關(guān)系的專家知識(shí)來完成概率分布函數(shù)的分解。DEUM根據(jù)無向圖中的集群建立適應(yīng)函數(shù)的模型，并將聯(lián)合分布分解成Gibbs分布，模型參數(shù)通過解群體進(jìn)行估計(jì)，采樣時(shí)使用了Markov鏈蒙特卡洛方法（包括Gibbs采樣和Metropolis采樣）。MN-FDA用無向圖近似表示聯(lián)合分布，并從中構(gòu)造出連接圖，然后根據(jù)連接圖采樣。MN-EDA用聯(lián)合分布的Kukichi近似來構(gòu)建概率模型并用Gibbs采樣產(chǎn)生新群體。MOA和MARLEDA是依賴于局部Markov性的分布估計(jì)算法，它們通過無向網(wǎng)絡(luò)估計(jì)條件概率并由此采樣。MARLEDA根據(jù)χ2測(cè)試估計(jì)結(jié)構(gòu)，MOA采用基于交互信息的方式采樣并利用退火溫度表來控制探索與開采。這類算法同樣適用于優(yōu)化變量強(qiáng)耦合的問題，但其中的FDA對(duì)于黑箱問題或形式復(fù)雜的優(yōu)化問題則無能為力。ECGA（ExtendedCompactGeneticAlgorithm）[33]是cGA的擴(kuò)展，該算法將變量分成若干個(gè)相互獨(dú)立的組，在每一組中變量之間有相關(guān)性，而與其它組中的任何變量都不相關(guān)。所有變量的聯(lián)合分布為各組變量的分布函數(shù)之積。EMNA（EstimationofMultivariateNormalAlgorithm）[34]用所有變量的聯(lián)合正態(tài)分布表示解分布模型，根據(jù)選擇的群體估計(jì)均值向量和協(xié)方差矩陣作為模型參數(shù)，并從聯(lián)合正態(tài)分布中采樣得到新一代群體。鐘偉才等在文獻(xiàn)[35]中提出一種建立在一般Gauss網(wǎng)絡(luò)上的算法，并采用Cholesky分解的方式產(chǎn)生新個(gè)體。這類算法全面考慮了變量之間的相關(guān)性，并且省去了復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)，但是估計(jì)協(xié)方差矩陣的運(yùn)算量是優(yōu)化空間維數(shù)的平方，其時(shí)間復(fù)雜度仍然較高。目前已有的分布估計(jì)算法中要么不能充分考慮變量之間的相關(guān)性，對(duì)變量強(qiáng)相關(guān)的問題優(yōu)化效果較差，要么模型估計(jì)的時(shí)間開銷很大。最近的研究表明分布估計(jì)算法中90%的運(yùn)算時(shí)間花費(fèi)在模型估計(jì)階段[36]，為減少算法的時(shí)間開銷，學(xué)者們采用了不同的方法對(duì)其進(jìn)行改進(jìn)，如并行方式[37,38]、與其他算法融合的方式[39-41]、混合局部搜索的方式[42]，使用迭代的[43]或偶然的模型建立方式[44]以及初始信息優(yōu)化的方式[45,46]等。如果基礎(chǔ)算法中能夠用較小的時(shí)間開銷實(shí)現(xiàn)模型估計(jì)是最好的。所有變量的聯(lián)合分布無疑是反映變量關(guān)系的準(zhǔn)確且簡(jiǎn)捷的方式。5.2copula分布估計(jì)算法基于copula理論的分布估計(jì)算法是近幾年來提出的一種新型的分布估計(jì)算法，據(jù)我們所有的中英文資料顯示，我們?cè)?009年IEEECEC會(huì)議中發(fā)表的論文[47]是這方面最早的論文。后來也有文獻(xiàn)顯示在2007年就有西班牙文的論文將高斯copula函數(shù)用于分布估計(jì)算法的研究中[48]。美國(guó)密蘇里州分布估計(jì)算法實(shí)驗(yàn)室對(duì)分布估計(jì)算法的綜述中特別指出，基于copula理論的分布估計(jì)算法是一種利用連續(xù)型概率模型對(duì)群體結(jié)構(gòu)進(jìn)行估計(jì)的解決連續(xù)型優(yōu)化問題的分布估計(jì)算法[49]，并引用了我們的論文作為這方面研究的原始代表性成果。2009年之后，許多國(guó)內(nèi)外學(xué)者在基于copula理論的分布估計(jì)算法方面進(jìn)行了研究，這里先簡(jiǎn)單介紹幾個(gè)代表性的成果。文獻(xiàn)[50]中提出了copula分布估計(jì)算法的基本框架，將概率模型的估計(jì)操作分成了兩部分：copula函數(shù)的估計(jì)和各邊緣分布函數(shù)的估計(jì)；在采樣操作中首先根據(jù)copula函數(shù)采樣得到概率向量（即該向量的每一維都代表一個(gè)概率，其值在(0,1)區(qū)間內(nèi)），然后根據(jù)概率向量和各邊緣分布函數(shù)計(jì)算得到搜索空間中的點(diǎn)作為新一代中的個(gè)體。文獻(xiàn)[51~60]在此基礎(chǔ)上對(duì)copula分布估計(jì)算法做了進(jìn)一步的研究。文獻(xiàn)[61]利用copula函數(shù)和一種稱為D-vine的規(guī)則藤結(jié)構(gòu)在分布估計(jì)算法中建立概率圖模型，并從理論上分析了三維copula函數(shù)的熵和條件交互信息之間的關(guān)系。文獻(xiàn)[62]利用阿基米德copula函數(shù)建立變量之間的兩兩相關(guān)的關(guān)系，并提出了一種估計(jì)copula函數(shù)參數(shù)的方法。文獻(xiàn)[52]和文獻(xiàn)[63]分別利用阿基米德copula函數(shù)和經(jīng)驗(yàn)copula函數(shù)反映變量之間的相關(guān)結(jié)構(gòu)，提出了相應(yīng)的基于copula理論的分布估計(jì)算法。文獻(xiàn)[53]在阿基米德copula分布估計(jì)算法中用偽極大似然估計(jì)的方式估計(jì)copula函數(shù)的參數(shù)，得到比固定參數(shù)的copula分布估計(jì)算法更好的優(yōu)化效果。文獻(xiàn)[64]提出了選擇copula函數(shù)的方法，利用依賴樹和二維copula函數(shù)表示概率圖模型，建立了靈活的聯(lián)合分布函數(shù)。5.2.1copula分布估計(jì)算法的統(tǒng)一框架在copula理論中，多變量的聯(lián)合分布可以分解成兩部分：（1）各個(gè)變量的邊緣分布，（2）一個(gè)copula函數(shù)。copula函數(shù)是多元函數(shù)，其中每個(gè)自變量取值范圍為[0,1]。顯然對(duì)單變量的邊緣分布進(jìn)行估計(jì)和采樣要比聯(lián)合分布簡(jiǎn)單的多。通過copula函數(shù)“連接”各邊緣分布可以獲得所有變量的聯(lián)合分布。對(duì)此聯(lián)合分布進(jìn)行采樣時(shí)，可以首先對(duì)copula函數(shù)進(jìn)行采樣，產(chǎn)生[0,1]D空間中的點(diǎn)，然后根據(jù)各邊緣分布函數(shù)的反函數(shù)求得采樣點(diǎn)的位置。根據(jù)Sklar定理，隨機(jī)向量的聯(lián)合分布可以分成兩部分表示，一是各個(gè)隨機(jī)變量的一維邊緣分布，另一是反映隨機(jī)向量相關(guān)結(jié)構(gòu)的copula函數(shù)。那么在copula分布估計(jì)算法中就可以用此定理來完成估計(jì)群體分布模型的操作，其分布模型為優(yōu)化變量的聯(lián)合分布。事實(shí)上，在copula分布估計(jì)算法中聯(lián)合分布不需要顯式表示，只需要估計(jì)出各個(gè)邊緣分布Fi(i=1,..,n)并構(gòu)造出copula函數(shù)C即可。在分布模型估計(jì)操作完成之后，下一步需要對(duì)此模型進(jìn)行采樣。根據(jù)copula理論，為產(chǎn)生服從聯(lián)合分布H(x1,x2,…,xn)=C(F1(x1),F2(x2),…,Fn(xn))的個(gè)體，首先需要產(chǎn)生服從聯(lián)合分布C的[0,1]n空間中的點(diǎn)(u1,u2,…,un)，然后根據(jù)邊緣分布函數(shù)Fi(i=1,..,n)的反函數(shù)Fi-1計(jì)算得到值xi=Fi-1(ui)，這樣得到的向量(x1,x2,…,xn)服從分布H，即(x1,x2,…,xn)為根據(jù)估計(jì)的概率模型H采樣得到的新個(gè)體。根據(jù)x根據(jù)xi(k)=Fi-1(ui(k)),i=1,..,n,k=1,…,l計(jì)算得到新的個(gè)體當(dāng)前代群體優(yōu)勢(shì)群體選擇估計(jì)copula函數(shù)C(u1(1),u2(1),…,un(1))(u1(2),u2(2),…,un(2))……(u1(l),u2(l),…,un(l))采樣F1F2…Fn估計(jì)邊緣分布是否終止最優(yōu)個(gè)體為優(yōu)化結(jié)果否是圖5.1copula分布估計(jì)算法的算法原理圖綜上所述，copula分布估計(jì)算法如圖7.1所示，首先在搜索空間中按均勻分布產(chǎn)生規(guī)模為PS的初始群體，然后循環(huán)執(zhí)行下列4個(gè)步驟直至滿足終止條件：Step1：選擇。在當(dāng)前群體中按基于適應(yīng)值的某種選擇策略選擇s個(gè)個(gè)體組成優(yōu)勢(shì)群體，記為x={xi=(xi1,xi2,…,xin),i=1,2,…,s}。Step2：估計(jì)邊緣分布。優(yōu)勢(shì)群體中的s個(gè)體是n維隨機(jī)向量(X1,X2,…,Xn)的s個(gè)樣本，那么{xij,i=1,2,…,s}就是隨機(jī)變量Xj的樣本，據(jù)此可估計(jì)其邊緣分布函數(shù)Fj(j=1,..,n)。Step3：從copula函數(shù)C中采樣。產(chǎn)生l個(gè)服從聯(lián)合分布函數(shù)C的向量(u1(k),u2(k),…,un(k)),k=1,…,lStep4：產(chǎn)生新一代群體。由以下三部分構(gòu)成新一代群體：①保留當(dāng)前代群體中的適應(yīng)值最好的m個(gè)個(gè)體至新一代；②通過計(jì)算xi(k)=Fi-1(ui(k))(i=1,..,n,k=1,…,l)得到l個(gè)新的個(gè)體(x1(k),x2(k),…,xn(k)),k=1,…,l；③在搜索空間中按均勻分布隨機(jī)產(chǎn)生其余的PS-m-l個(gè)個(gè)體。copula分布估計(jì)算法考慮的是所有變量的聯(lián)合分布，其聯(lián)合分布用copula函數(shù)和各變量的邊緣分布表示，采用一般的copula函數(shù)可以表示所有變量全部相關(guān)的情況。特別地，對(duì)于copula函數(shù)C=∏，那么變量之間就是相互獨(dú)立的。采用不同的邊緣分布就可以表示變量不相關(guān)的一些典型算法。如UMDAc可以認(rèn)為是copula分布估計(jì)算法的一種特殊情況，其copula函數(shù)為∏，邊緣分布為正態(tài)分布。對(duì)于變量可分為若干相互獨(dú)立的組,且每組內(nèi)變量相關(guān)的分布估計(jì)算法，則可以用嵌套式的copula分布估計(jì)算法表示，其copula函數(shù)C=∏(C1,..,Cs)，s表示變量的分組數(shù)。copula理論將復(fù)雜的聯(lián)合分布中的邊緣分布分離出來，而把注意力集中在了反映變量之間關(guān)系的骨架結(jié)構(gòu)上。在copula理論中起重要作用的關(guān)鍵定理是Sklar定理[46]。該定理表明：在連續(xù)的情況下，一個(gè)聯(lián)合分布函數(shù)可以唯一的表示為一個(gè)copula函數(shù)和各變量邊緣分布函數(shù)的復(fù)合函數(shù)；且對(duì)于給定的copula函數(shù)及邊緣分布函數(shù)，由它們確定的聯(lián)合分布也是唯一的。5.2.2copula分布估計(jì)算法的收斂性不失一般性，設(shè)優(yōu)化問題是maxf(x),x∈D，其中x=(x1,x2,…xn)∈Rn，D是Rn中的一個(gè)非空有界閉集，而且f(x):D→R是一個(gè)正的連續(xù)的目標(biāo)函數(shù)。那么存在一個(gè)點(diǎn)x*∈D，對(duì)任意x∈D，有f(x*)≥f(x)，即x*是優(yōu)化問題maxf(x)的全局最優(yōu)解，在此點(diǎn)處目標(biāo)函數(shù)達(dá)到最大值G*=f(x*)。設(shè)對(duì)于任意實(shí)數(shù)Q<G*，集合B={x|x∈D,f(x)>Q}的Borel測(cè)度均為正。設(shè)Pop(t)和Pops(t)分別表示第t代的群體和選擇群體，它們分別服從聯(lián)合分布函數(shù)H(x,t)和Hs(x,t)。在copula分布估計(jì)算法中，選擇操作就是從Pop(t)中按一定的策略選出Pops(t)，即：H(x,t)→Hs(x,t)。在估計(jì)操作中，對(duì)Pops(t)的概率分布模型進(jìn)行估計(jì)，首先估計(jì)每一維的邊緣分布Fis(xi,t),i=1,2,…,n。由Glivenko-Canteli定理[92]可知，在群體規(guī)模無窮大的情況下，第t代選擇群體的第i維經(jīng)驗(yàn)分布函數(shù)收斂于Fis(xi,t)，因此Pops(t)的各一維邊緣分布函數(shù)Fis(xi,t)可以被準(zhǔn)確地估計(jì)。然后根據(jù)Pops(t)估計(jì)copula函數(shù)Cs(u,t)。根據(jù)Sklar定理可知，在D上存在唯一的copula函數(shù)Cs(u,t)，使得Hs(x,t)=Cs(F1s(x1,t),F2s(x2,t),…,Fns(xn,t),t)；對(duì)于給定的copula函數(shù)Cs(u,t)和邊緣分布函數(shù)Fis(xi,t)，其組合Cs(F1s(x1,t),F2s(x2,t),…,Fns(xn,t),t)一定是分布函數(shù)。也就是，在Fis(xi,t),i=1,2,…,n確定的條件下，Hs(x,t)和Cs(u,t)是一一對(duì)應(yīng)的。那么copula分布估計(jì)算法的估計(jì)操作就可以表示為：根據(jù)Pops(t)估計(jì)一維邊緣分布函數(shù)Fis(xi,t),i=1,2,…,n和copula函數(shù)Cs(u,t)，設(shè)估計(jì)值為和，由Glivenko-Canteli定理，。因此，估計(jì)操作實(shí)際上是根據(jù)Pops(t)估計(jì)Fis(xi,t),i=1,2,…,n和。在采樣操作中，首先根據(jù)copula函數(shù)采樣得到[0,1]n空間中服從分布函數(shù)的隨機(jī)向量(U1,U2,…,Un)的取值，然后根據(jù)邊緣分布函數(shù)的反函數(shù)(Fis)-1計(jì)算Xi=(Fis)-1(Ui,t)，從而得到新群體(X1,X2,…,Xn)。在copula函數(shù)采樣無誤差的情況下，(X1,X2,…,Xn)服從分布。(X1,X2,…,Xn)構(gòu)成了第t+1代群體，前面已經(jīng)說明其分布為H(x,t+1)，其copula函數(shù)表示形式為Cs(F1s(x1,t+1),F2s(x2,t+1),…,Fns(xn,t+1),t+1)。由采樣操作可知，F(xiàn)i(xi,t+1)=Fis(xi,t),i=1,2,…,n，根據(jù)Sklar定理，。綜上所述，copula分布估計(jì)算法可以為表示反復(fù)執(zhí)行下面的兩個(gè)操作：選擇：H(x,t)→Hs(x,t)變異：Cs(u,t)→C(u,t+1)設(shè)聯(lián)合分布函數(shù)H(x,t)和Hs(x,t)對(duì)應(yīng)的聯(lián)合密度函數(shù)分別為h(x,t)和hs(x,t)，邊緣分布函數(shù)Fis(xi,t)對(duì)應(yīng)的密度函數(shù)為fis(xi,t)，copula函數(shù)C(u,t)和Cs(u,t)本身是分布函數(shù)，它們對(duì)應(yīng)的密度函數(shù)分別是c(u,t)和cs(u,t)。則，其中(5.1)，其中(5.2)定義5.1：設(shè)用分布估計(jì)算法優(yōu)化maxf(x)，其最優(yōu)值為G*，算法中第t代群體服從密度函數(shù)h(x,t)，令(5.3)即E(t)表示第t代群體的平均適應(yīng)值，如果，則稱分布估計(jì)算法全局收斂。引理5.1：如果選擇算子為比例選擇，那么一個(gè)個(gè)體被選中的概率和它的適應(yīng)值成正比，選擇群體的密度函數(shù)可表示為(5.4)引理5.2：如果選擇算子為截?cái)噙x擇，其選擇率為α(t)，那么第t代群體中適應(yīng)值最好的百分之(100α(t))個(gè)體被選中，組成選擇群體。從而選擇群體的密度函數(shù)可表示為(5.5)其中，實(shí)數(shù)β(t)滿足條件(5.6)即第t代群體中適應(yīng)值不小于β(t)的個(gè)體被選中。引理5.3：如果選擇算子為二個(gè)體錦標(biāo)賽選擇，那么在第t代群體中隨機(jī)選擇兩個(gè)個(gè)體，將其中適應(yīng)值較大的一個(gè)加入到選擇群體中。此時(shí)選擇群體的密度函數(shù)可表示為。(7.7)Fatou引理：設(shè){fn(x)}是可測(cè)集E上的一系列負(fù)可測(cè)函數(shù)，則(5.8)定理5.1：在群體規(guī)模無窮大的情況下，如果copula分布估計(jì)算法中的初始群體密度函數(shù)h(x,0)為正的連續(xù)函數(shù)，且copula函數(shù)滿足C(u,t+1)=Cs(u,t)，那么：（1）采用比例選擇算子的copula分布估計(jì)算法收斂；（2）如果截?cái)噙x擇算子的選擇率α(t)滿足：在任意代t，都有α(t)≤θ(0<θ<1)，那么采用此截?cái)噙x擇算子的copula分布估計(jì)算法收斂；（3）采用二個(gè)體錦標(biāo)賽選擇算子的copula分布估計(jì)算法收斂。證明：由于C(u,t+1)=Cs(u,t)，(5.9)故c(u,t+1)=cs(u,t)。(5.10)又在copula分布估計(jì)算法中fi(xi,t+1)=fis(xi,t),i=1,2,…,n。(5.11)根據(jù)公式(5.1)、(5.2)、(5.10)和(5.11)有(5.12)（1）如果使用比例選擇，根據(jù)公式(5.4)和(5.12)有(5.13)已知f(x)和h(x,0)在D上是正的連續(xù)函數(shù)，故h(x,t)也是正的連續(xù)函數(shù)，且對(duì)任意t≥0，有0≤E(t)<G*。因?yàn)椋?5.14)所以(5.15)從而(5.16)由于h(x,t)在D上是正的連續(xù)函數(shù)且E(t)≥0，故對(duì)任意t>0，有E(t+1)≥E(t)。{E(t)}構(gòu)成了D上的單調(diào)有界序列，故極限存在，記為。下面證明G=G*。用反證法，假設(shè)G<G*。由公式(7.13)有(5.17)當(dāng)f(x)>G時(shí)，有(7.18)又因?yàn)閷?duì)任意x∈D，h(x,0)>0，所以對(duì)任意滿足f(x)>G的x，有。令S={x|x∈D,f(x)>G}，則S的Borel測(cè)度非零。從而根據(jù)Fatou引理有(5.19)這與h(x,t)是密度函數(shù)相矛盾。因此G=G*，copula分布估計(jì)算法全局收斂。（2）如果使用截?cái)噙x擇，由公式(5.5)和(5.12)有(5.20)那么對(duì)任意f(x)<β(t)有h(x,t+1)=0。從而(5.21)根據(jù)公式(5.6)(5.22)比較公式(5.21)和(5.22)可知?jiǎng)t極限存在，記為。下面證明β=G*。同樣用反證法，假設(shè)β<G*。那么對(duì)于任意f(x)>β，有(5.23)又因?yàn)閷?duì)任意x∈D，h(x,0)>0，所以對(duì)任意滿足f(x)>β的x，有。令S={x|x∈D,f(x)>β}，則S的Borel測(cè)度非零。從而根據(jù)Fatou引理有(5.24)這與h(x,t)是密度函數(shù)相矛盾，故。因?yàn)镋(t)≥β(t)，所以。（3）如果采用二個(gè)體錦標(biāo)賽選擇，那么由公式(5.7)和(5.12)有(5.25)對(duì)任意ε>0，令，(5.26)，(5.27)，(5.28)由公式(5.25)可得(5.29)顯然，對(duì)任意x∈Nε，有(5.30)由公式(5.29)和(5.30)可得，(5.31)其中(5.32)由的對(duì)稱性可知(5.33)那么(5.34)從而(5.35)因?yàn)椋?，即。因?yàn)?，所以，，即?.3阿基米德copula分布估計(jì)算法下面對(duì)copulaEDA進(jìn)行具體分析。設(shè)優(yōu)化問題為。(5.36)記規(guī)模為s的優(yōu)勢(shì)群體為，則是隨機(jī)向量的s組觀測(cè)值。各隨機(jī)變量的邊緣分布可以采用正態(tài)分布或者經(jīng)驗(yàn)分布函數(shù)構(gòu)造。在本節(jié)中介紹copula函數(shù)為阿基米德copula函數(shù)的copulaEDA。根據(jù)Sklar定理，由各隨機(jī)變量的邊緣分布函數(shù)及copula函數(shù)可以確定一個(gè)聯(lián)合分布。此時(shí)，解空間的概率模型構(gòu)建成功。接下來需要對(duì)估計(jì)的模型進(jìn)行隨機(jī)采樣產(chǎn)生新種群。在采樣中關(guān)鍵的步驟是對(duì)copula函數(shù)進(jìn)行采樣。5.3.1阿基米德copula函數(shù)采樣算法設(shè)阿基米德copula函數(shù)為C，其生成元為φ，(U1,U2,…,Un)是服從聯(lián)合分布C的隨機(jī)向量，根據(jù)Marshall和Olkin提出的算法[65]，如果存在一個(gè)分布函數(shù)F，滿足F(0)=0，且其拉氏變換與生成元的反函數(shù)相等，即，則產(chǎn)生(U1,U2,…,Un)的取值(u1,u2,…,un)可采用如下方法。算法5.1：從阿基米德copula函數(shù)中采樣的算法Step1：采樣,其中是生成元的反拉氏變換；Step2：產(chǎn)生相互獨(dú)立的值xi~U[0,1],i=1,…,n；Step3：令，則(u1,u2,…,un)為所需要的向量。常見的阿基米德copula函數(shù)及其反拉氏變換如表5.1所示，在本節(jié)中以Gumbelcopula為例介紹阿基米德copula分布估計(jì)算法及其參數(shù)估計(jì)。表5.1阿基米德copula函數(shù)的生成元及對(duì)應(yīng)的的反拉氏變換函數(shù)名稱生成元反拉氏變換對(duì)應(yīng)的分布函數(shù)GumbelClaytonFrank參數(shù)為的正整數(shù)域內(nèi)的對(duì)數(shù)級(jí)數(shù)5.3.2Gumbelcopula分布估計(jì)算法Gumbelcopula函數(shù)的生成元是，由表5.1可知，根據(jù)Marshall等提出的采樣算法，從Gumbelcopula函數(shù)和邊緣經(jīng)驗(yàn)分布函數(shù)采樣新個(gè)體的算法如下：算法5.2:(x1(k),x2(k),…,xn(k))=sample_Gumbel(k)Step1：產(chǎn)生服從均勻分布的隨機(jī)變量取值；Step2：產(chǎn)生與獨(dú)立的、服從指數(shù)分布exp(1)的隨機(jī)變量取值W；Step3：令,,,,；Step4：通過如下計(jì)算得到服從分布的隨機(jī)變量取值Z：(5.37)Step5：通過如下計(jì)算得到服從分布的隨機(jī)變量取值v：(5.38)Step6：產(chǎn)生相互獨(dú)立的服從均勻分布U[0,1]的隨機(jī)變量取值vi,i=1,…,n,令(5.39)Step7：通過如下計(jì)算得到新個(gè)體(x1(k),x2(k),…,xn(k))(5.40)在上述算法中，(u1,u2,…,un)是服從分布函數(shù)為Gumbelcopula函數(shù)的In空間中的向量。(x1(k),x2(k),…,xn(k))是搜索空間中服從聯(lián)合分布C(F1,F2,…,Fn)的向量。在copula分布估計(jì)算法框架下，基于Gumbelcopula函數(shù)和邊緣經(jīng)驗(yàn)分布函數(shù)的copula分布估計(jì)算法如下：算法5.3:具有經(jīng)驗(yàn)邊緣分布函數(shù)的GumbelcopulaEDAStep1：隨機(jī)產(chǎn)生規(guī)模為PS的初始群體Pg，令當(dāng)前進(jìn)化代數(shù)g←0；Step2：根據(jù)一定的選擇策略從當(dāng)前群體Pg中選擇出規(guī)模為s的優(yōu)勢(shì)群體Sg；Step3：根據(jù)Sg估計(jì)每一維變量的邊緣經(jīng)驗(yàn)分布函數(shù)Fi；Step4：Fork=1tol執(zhí)行(x1(k),x2(k),…,xn(k))=sample_Gumbel(k)；Step5：由以下三部分構(gòu)成新群體：Pg中的m個(gè)最優(yōu)個(gè)體，l個(gè)新產(chǎn)生的個(gè)體，在搜索空間中隨機(jī)產(chǎn)生其余的PS-m-l個(gè)個(gè)體；令g←g+1；Step6：如果滿足終止條件，則算法結(jié)束，Pg中適應(yīng)值最好的個(gè)體為優(yōu)化的結(jié)果；否則轉(zhuǎn)到Step2繼續(xù)執(zhí)行。實(shí)驗(yàn)結(jié)果表明了copula分布估計(jì)算法的有效性和可行性，并且在優(yōu)化效果方面有很好的表現(xiàn)。同時(shí)在研究過程中發(fā)現(xiàn)需要進(jìn)一步研究的內(nèi)容：阿基米德copula分布估計(jì)算法中關(guān)于copula函數(shù)的參數(shù)對(duì)算法的影響，以及如何根據(jù)優(yōu)勢(shì)群體確定適當(dāng)?shù)膮?shù)。因?yàn)閏opula函數(shù)的參數(shù)也影響著變量的相關(guān)結(jié)構(gòu)，從而影響了所估計(jì)的概率分布模型與優(yōu)勢(shì)群體實(shí)際的概率分布模型之間的吻合度，進(jìn)一步對(duì)copula分布估計(jì)算法的性能有所影響。5.3.3基于PMLE的阿基米德copula分布估計(jì)算法參數(shù)估計(jì)法不同的copula函數(shù)體現(xiàn)的變量之間的相關(guān)結(jié)構(gòu)不同，copula函數(shù)的參數(shù)不同，所對(duì)應(yīng)的變量之間的相關(guān)程度也不同，在copula函數(shù)選定的情況下，如何選取參數(shù)是一個(gè)很重要的問題。不同的參數(shù)θ對(duì)應(yīng)的分布函數(shù)不同，因此需要根據(jù)優(yōu)勢(shì)群體確定相應(yīng)copula函數(shù)的參數(shù)值，使得該函數(shù)能夠更準(zhǔn)確的模擬優(yōu)勢(shì)群體中變量的相關(guān)性。在本節(jié)中參數(shù)估計(jì)方法采用PMLE，具體操作如下：Step1：根據(jù)樣本x={xi=(xi1,xi2,…,xin),i=1,2,…,s}估計(jì)邊緣經(jīng)驗(yàn)分布,j=1,2,…,n，即(5.41)其中，x(i)j為第j維向量的s個(gè)樣本按升序排列后的第i個(gè)值。Step2：根據(jù)公式(5.41)中的分布函數(shù)確定樣本x對(duì)應(yīng)的分布函數(shù)值u={ui=(ui1,ui2,…,uin),i=1,2,…,s}。Step3：根據(jù)u中的值及表7.1中具體的copula函數(shù)求得θ的極大似然估計(jì)值。Gumbelcopula函數(shù)的邊緣分布函數(shù)仍然是Gumbelcopula函數(shù)，其參數(shù)θ的值保持不變。因此，當(dāng)Gumbelcopula函數(shù)的維數(shù)較高時(shí)，可以隨機(jī)選擇兩個(gè)變量，估計(jì)其二維邊緣Gumbelcopula函數(shù)的參數(shù)值θ作為所有變量的聯(lián)合分布的參數(shù)值。對(duì)于Gumbelcopula函數(shù)，令，,，，則Gumbelcopula函數(shù)的密度函數(shù)為。在實(shí)驗(yàn)中，隨機(jī)選擇兩個(gè)變量ui和uj，其對(duì)數(shù)似然函數(shù)為，其中。由于θ≥1，可令θ0=1，并取步長(zhǎng)為t，θp+1=θp+t。根據(jù)樣本依次計(jì)算，直至，則為極大似然估計(jì)的近似值。實(shí)驗(yàn)表明這種具有參數(shù)估計(jì)的copula分布估計(jì)算法優(yōu)于固定參數(shù)的copula分布估計(jì)算法5.4經(jīng)驗(yàn)copula分布估計(jì)算法經(jīng)驗(yàn)copula分布估計(jì)算法中根據(jù)選擇群體構(gòu)造經(jīng)驗(yàn)copula函數(shù)，其原理與一維經(jīng)驗(yàn)分布函數(shù)相同，然后根據(jù)其構(gòu)造原理推導(dǎo)出從經(jīng)驗(yàn)copula函數(shù)中采樣的算法。在實(shí)現(xiàn)經(jīng)驗(yàn)copula分布估計(jì)算法時(shí)，不需要明確構(gòu)造出經(jīng)驗(yàn)copula函數(shù)，而只需要直接實(shí)現(xiàn)從copula函數(shù)采樣即可。5.4.1多維經(jīng)驗(yàn)copula函數(shù)的構(gòu)造方式設(shè)n維隨機(jī)向量X，其聯(lián)合分布為F(x)，copula函數(shù)為C(u)，各變量的一維邊緣分布為Fi(x)，i=1,…,n。則根據(jù)Sklar定理有。產(chǎn)生一組服從分布F(x)的隨機(jī)數(shù)(x1,…,xn)的方法是首先產(chǎn)生服從分布C(u)的一組隨機(jī)數(shù)u1,…,un，然后再由各邊緣分布函數(shù)的反函數(shù)產(chǎn)生（x1,…,xn），其中。設(shè)copula函數(shù)C(u)相應(yīng)的密度函數(shù)為c(u)，則邊緣密度函數(shù)(5.42)顯然c(u)=cn(u)。為了產(chǎn)生非獨(dú)立的隨機(jī)數(shù)u1,…,un，需要知道條件分布函數(shù)(5.43)設(shè)n維隨機(jī)向量Z，已知其規(guī)模為s的樣本z=zi=(zi1,zi2,…zin)，i=1,2,..s，首先對(duì)隨機(jī)向量的每一維構(gòu)造其經(jīng)驗(yàn)分布函數(shù)，然后根據(jù)所得的經(jīng)驗(yàn)分布函數(shù)將樣本zi對(duì)應(yīng)到其經(jīng)驗(yàn)分布函數(shù)值，這樣就得到向量ui，ui的每維取值在區(qū)間[0,1]內(nèi)。從而由隨機(jī)向量Z的樣本得到了隨機(jī)向量U的樣本，其中，向量u∈[0,1]n就是copula函數(shù)的自變量。由copula理論，copula函數(shù)C(u)實(shí)際上是隨機(jī)向量U的聯(lián)合分布函數(shù)。那么根據(jù)概率論的基本理論，產(chǎn)生向量u的方式就是根據(jù)U的邊緣分布計(jì)算出相應(yīng)的條件分布，然后由條件分布產(chǎn)生向量u。因此首先需要估計(jì)U的邊緣分布cd(u)，U的樣本已知，邊緣分布易于估計(jì)。具體做法如下：對(duì)于隨機(jī)向量Z的s個(gè)樣本，分別按維由小到大進(jìn)行排序，設(shè)第d∈{1,2,..n}維排序后的結(jié)果是，那么第d維的經(jīng)驗(yàn)分布函數(shù)就是(5.44)由公式(5.44)可以將s個(gè)樣本映射為s個(gè)向量，作為空間[0,1]n中的s個(gè)點(diǎn)。將區(qū)間[0,1]分成K等份，記為，即。這樣，n維單位空間[0,1]n就分解成為Kn個(gè)小空間，。統(tǒng)計(jì)每個(gè)小空間中點(diǎn)的個(gè)數(shù)，記為。那么密度函數(shù)(5.45)令，則。由公式(5.42)，有(5.46)其中，(5.47)則條件分布函數(shù)(5.43)就是(5.48)(5.49)其中,。計(jì)算公式(5.47)中定義的的方法在[94]中給出，具體如下：算法5.4：計(jì)算Step1：根據(jù)公式(5.44)將樣本點(diǎn)映射為[0,1]n空間上的點(diǎn)；Step2：令數(shù)組f(d),d=1,2,…,n中的元素為0；Step3：for(i=1:s)for(d=1:n);endfor(d=2:n) end end產(chǎn)生相互依賴的一組隨機(jī)數(shù)u1,…,un的過程generation(f)如下：算法5.5：generation(f)Step1：在[0,1]區(qū)間內(nèi)按均勻分布產(chǎn)生隨機(jī)數(shù)u1和uStep2：根據(jù)公式(7.48)有，其中是滿足條件的{0,…,K-1}內(nèi)的最小整數(shù)。Step3：for（d=3：n） Step3.1在[0,1]區(qū)間內(nèi)按均勻分布產(chǎn)生隨機(jī)數(shù)u; Step3.2根據(jù)公式(7.49)有，其中是滿足條件的{0,…,K-1}內(nèi)的最小整數(shù)。5.4.2經(jīng)驗(yàn)copulaEDA算法步驟及復(fù)雜性分析設(shè)優(yōu)化問題為?；谏鲜龇治?，經(jīng)驗(yàn)copulaEDA的算法步驟如下：Step1:在搜索空間中按均勻分布隨機(jī)產(chǎn)生PS個(gè)個(gè)體，確定選擇率ss和變異率tt；Step2：根據(jù)適應(yīng)值選擇其中的s=ss×PS個(gè)主體作為優(yōu)勢(shì)群體(z1,…,zs)；Step3：根據(jù)(z1,…,zs)計(jì)算，即執(zhí)行算法7.4；Step4：重復(fù)下列步驟l=(1-ss-tt)×PS次，產(chǎn)生l個(gè)個(gè)體加入到群體中；Step4.1:(u1,…un)=generation(f);Step4.2:for（i=1：n） end（x1,…,xn）為產(chǎn)生的新個(gè)體。Step5：在搜索空間中按均勻分布隨機(jī)產(chǎn)生tt×PS個(gè)個(gè)體加入到群體中；Step6：若滿足算法終止條件，則結(jié)束，群體中具有最優(yōu)適應(yīng)值的個(gè)體即優(yōu)化結(jié)果。否則轉(zhuǎn)Step2繼續(xù)執(zhí)行。在文獻(xiàn)[66]中已證明當(dāng)s能被K整除時(shí)，上述方法構(gòu)造的函數(shù)C(u)是一個(gè)copula函數(shù)。構(gòu)造copula函數(shù)的時(shí)間復(fù)雜度是。根據(jù)C(u)產(chǎn)生服從該分布的隨機(jī)向量的時(shí)間復(fù)雜度是。對(duì)于經(jīng)驗(yàn)copulaEDA，設(shè)優(yōu)化問題的維數(shù)為n，群體規(guī)模為PS，選擇率為ss，則根據(jù)選擇的群體估計(jì)概率模型并采樣生成下一代群體的時(shí)間復(fù)雜度為(5.50)實(shí)驗(yàn)表明，經(jīng)驗(yàn)copulaEDA能夠收斂到全局最優(yōu)解，但算法的局部開采能力較弱，在進(jìn)化后期收斂的速度較慢。因此可以在經(jīng)驗(yàn)copulaEDA中引入其他的進(jìn)化算法以增強(qiáng)其局部開采能力，或者在算法后期采用爬山法等局部搜索法進(jìn)行改進(jìn)。5.5基于離散Quasi-Copula的分布估計(jì)算法Copula方法是利用隨機(jī)變量的邊緣分布來近似確定其聯(lián)合分布的數(shù)學(xué)方法，是在構(gòu)造多元聯(lián)合分布以及隨機(jī)變量間相關(guān)結(jié)構(gòu)分析中常用的工具。目前copula理論主要被應(yīng)用于金融市場(chǎng)的相關(guān)性分析、資產(chǎn)定價(jià)和風(fēng)險(xiǎn)管理等金融領(lǐng)域。國(guó)內(nèi)對(duì)copula理論更深入的研究還不多，且很少利用copula理論研究復(fù)雜的組和優(yōu)化問題。Copula的種類很多，不同的問題應(yīng)用不同的copula方法，離散Quasi-Copula方法是求解離散變量間相關(guān)性的一個(gè)有效工具[67-69]。本節(jié)根據(jù)Quasi-Copula函數(shù)在構(gòu)建反映離散隨機(jī)變量相關(guān)性問題上具有的優(yōu)勢(shì)，將其引入分布估計(jì)算法中構(gòu)造反映離散隨機(jī)數(shù)據(jù)分布的多變量相關(guān)的概率模型，并從中采樣產(chǎn)生新個(gè)體，從而提高分布估計(jì)算法求解復(fù)雜的離散優(yōu)化問題的能力。5.5.1離散Quasi-Copula基本概念Copula是連接、交換的意思,它是把多個(gè)隨機(jī)變量的聯(lián)合分布與它們的邊緣分布相連接的連接函數(shù)。Quasi-Copula是copula的一個(gè)擴(kuò)展，它是描述在隨機(jī)變量的邊緣分布函數(shù)不可導(dǎo)的條件下，刻畫變量間相關(guān)性的連接函數(shù)。離散Quasi-Copula是描述離散變量條件下的連接函數(shù)。n維離散Quasi-Copula可描述如下：設(shè)是定義在n維空間In的一個(gè)集合，，,…為大于1的自然數(shù)。則一個(gè)離散Quasi-Copula是一個(gè)n元函數(shù)C:In→I,I=[0，1]，且滿足下列條件：（1），，若中至少有一個(gè)為0，則=0.（2）若中除了外全為1，則=.（3），，.5.5.2基于離散Quasi-Copula的概率模型從文獻(xiàn)[70,71]中可知，對(duì)于給定的n維樣本，對(duì)應(yīng)的經(jīng)驗(yàn)copula為：，其中，…為樣本對(duì)應(yīng)的順序統(tǒng)計(jì)量。離散Quasi-Copula的種類很多，很明顯，一個(gè)經(jīng)驗(yàn)copula就是一個(gè)典型的離散Quasi-Copula。因此，本節(jié)以經(jīng)驗(yàn)copula為例描述個(gè)體的相關(guān)性，求解聯(lián)合概率分布，建立概率模型，進(jìn)而求解問題。確定各變量的邊緣分布函數(shù)在離散優(yōu)化問題中，隨機(jī)獲得的樣本（個(gè)體）的分布函數(shù)及其類型都是未知的，因此這里通過順序統(tǒng)計(jì)量獲得樣本的經(jīng)驗(yàn)分布函數(shù)[72]，再利用經(jīng)驗(yàn)分布函數(shù)估計(jì)個(gè)體的邊緣分布函數(shù)。具體過程如下：設(shè)優(yōu)勢(shì)群體中的個(gè)體為Xi=(x1i,x2i,…xDi),i=1,2,…n。按照維數(shù)，對(duì)所有個(gè)體相同維數(shù)上的元素按大小遞增的順序重新排列，獲得每一維上的順序統(tǒng)計(jì)量，即xd(1),xd(2),…xd(n),d=1,2,…D。針對(duì)所有個(gè)體的每一維，計(jì)算其經(jīng)驗(yàn)分布函數(shù)，獲得個(gè)體的邊緣分布函數(shù)，即（5.51）xd.表示第d維上的變量,d=1,2,…D。Fd(xd.)為第d維上的邊緣分布函數(shù)，是單調(diào)非降左連續(xù)的跳躍函數(shù)（階梯函數(shù)），在每個(gè)點(diǎn)上跳躍量都是1/n，0≤Fd(xd.)≤1，F(xiàn)d(xd.)的可能取值為0,1/n,…n-1/n,1。令ud,i=Fd(xd,i)，即第d維上第i個(gè)變量的概率值，ui=(u1i,…uDi),ui為第i個(gè)個(gè)體Xi的映射點(diǎn)([0,1]D→[0,1])。確定離散Quasi-Copula函數(shù)首先對(duì)n維空間In進(jìn)行分割[73]，把空間分成k個(gè)子空間，Ω1,Ω2,…,Ωk，Ωj=[((j-1)δ,jδ]，j=1,2,…k,k是一個(gè)能被n整除的正整數(shù)。則第j個(gè)子空間可以表示為，即每個(gè)子空間是D維的。分割的細(xì)密程度由k決定。令其密度函數(shù)為相應(yīng)點(diǎn)落在對(duì)應(yīng)子空間中的個(gè)數(shù)的函數(shù)，即，，其中，，Nj表示落在第j個(gè)子空間上的點(diǎn)的個(gè)數(shù)。令，，=-1(5.52)則定義各變量的邊緣密度為：，d=1,2,…D，(5.53)(5.54)通過邊緣密度函數(shù)，得到條件分布函數(shù)為：(5.55)由上面建立的條件分布函數(shù)，獲得變量的聯(lián)合概率分布：(5.56)此即建立的基于離散Quasi-Copula的概率模型，從中抽樣產(chǎn)生新個(gè)體。5.5.3群體的產(chǎn)生新個(gè)體產(chǎn)生分兩步[73]，第一步，先從概率模型中抽樣產(chǎn)生相關(guān)的隨機(jī)數(shù)，然后以此隨機(jī)數(shù)為基礎(chǔ)產(chǎn)生新個(gè)體，組成新群體。Step1在每一維上，產(chǎn)生相關(guān)的隨機(jī)數(shù)（v1,v2,…,vn）首先，在[0,1]之間產(chǎn)生一個(gè)隨機(jī)數(shù)，然后按下列公式產(chǎn)生后面的數(shù)，(5.57)↓jd是滿足式(5.9)的最小整數(shù)，↓jd∈{0,1,…k-1}(5.58)Step2產(chǎn)生新個(gè)體新一代個(gè)體的產(chǎn)生如下：，，，，t為進(jìn)化代數(shù)。5.5.4算法流程算法采用經(jīng)驗(yàn)分布函數(shù)確定各變量的邊緣分布函數(shù)，然后通過經(jīng)驗(yàn)Copula方法，通過從樣本中估計(jì)變量的聯(lián)合分布函數(shù)，獲得多變量相關(guān)的概率分布模型，并從中抽樣產(chǎn)生新群體。具體步驟如下：Step1編碼。采用自然數(shù)編碼方式對(duì)問題進(jìn)行編碼.Step2產(chǎn)生初始群體。設(shè)群體規(guī)模為N。以均勻分布隨機(jī)產(chǎn)生N個(gè)自然數(shù)排列作為初始群體。Step3適應(yīng)度計(jì)算和優(yōu)勢(shì)群體的選擇。Step4建立概率模型。Step5產(chǎn)生新群體。Step6更新概率模型。從新產(chǎn)生的群體中，選擇新的優(yōu)勢(shì)群體，重新計(jì)算個(gè)體的聯(lián)合分布，獲得新的概率模型。判斷收斂條件，如果收斂或滿足終止條件，結(jié)束。否則返回Step3。重復(fù)上述步驟，直到滿足收斂條件。整個(gè)過程采用精英保留策略。5.5.5實(shí)例仿真為了驗(yàn)證本節(jié)提出的基于離散QuasiCopula的分布估計(jì)算法（CEDA）的優(yōu)化性能，針對(duì)TSP問題進(jìn)行仿真實(shí)驗(yàn)，測(cè)試實(shí)例來自TSPLIB數(shù)據(jù)庫(kù)。實(shí)驗(yàn)結(jié)果與算法GA、PBIL和OPBIL[74]的實(shí)驗(yàn)結(jié)果進(jìn)行了比較。實(shí)驗(yàn)環(huán)境為：種群規(guī)模等于城市個(gè)數(shù)，eil51和berlin52問題最大運(yùn)行2000，eil76最大運(yùn)行2500代，其余例子最大運(yùn)行3500代，參數(shù)=0.15（PBIL與OPBIL參數(shù)設(shè)置相同）。優(yōu)勢(shì)群體選擇比例為0.5。每個(gè)例子運(yùn)行30次，為運(yùn)行30次所得解的平均值，為均方差。仿真結(jié)果如表5.2所示。表5.2CEDA算法與其它算法計(jì)算結(jié)果的比較例子算法GAμσPBILμσOPBILμσCEDAμσeil51687.9340.87590.1730.6546.0320.94521.1119.91berlin5212294.14859.1810676.56812.609792.80548.739670.42534.88eil76986.9974.75846.9457.71754.2344.49738.8342.90kroA10055285.645290.8245871.623769.3238726.172880.9338160.552531.76kroB10056804.895324.8845775.774352.5838300.592782.2938177.562790.95kroC10055560.714637.7245758.083216.8537351.602653.4937141.022346.81kroD10056120.534833.3644964.253324.7637229.582327.2237219.462077.36kroE10055657.734583.1646057.643396.0938876.372637.2638705.052577.17eil1011323.5277.861112.9760.10960.9959.91940.2756.78ch13016566.871573.2214400.64933.6711638.47922.8911397.02687.25從表5.2中可以看出，算法CEDA得到的均值與方差都大大優(yōu)于GA與基本PBIL算法的結(jié)果。OPBIL算法是一種改進(jìn)的PBIL算法，改進(jìn)變異算子提高種群的多樣性，從而提高算法的求解能力，而算法CEDA的結(jié)果優(yōu)于OPBIL算法的結(jié)果，說明算法CEDA有較好的搜索能力。5.6優(yōu)良模式連接的分布估計(jì)算法5.6.1優(yōu)良模式連接的思想模式在遺傳算法中占有很重要的地位，在基于二進(jìn)制編碼的基本遺傳算法中，個(gè)體是以二進(jìn)制字符串形式表示的，遺傳算法中串的運(yùn)算實(shí)際上是模式的運(yùn)算[75]。模式定理可描述如下:引理5.6.1模式定理.設(shè)遺傳算法采用比例選擇策略，其中交叉概率和變異概率分別為pc和pm，且取值較小，模式H的階為o(H)，長(zhǎng)度為δ(H)，第t+1代種群P(t+1)中含有H中元素個(gè)數(shù)的期望為E[|H∩P(t)|],則以下不等式成立：（5.59）它說明了包含適應(yīng)度值高、長(zhǎng)度短、低階的建筑塊的個(gè)體在后代中至少以指數(shù)級(jí)增長(zhǎng)。模式定理在一定程度上解釋了基本遺傳算法的有效性。說明了階次低、定義長(zhǎng)度短且其適應(yīng)度值超過種群平均適應(yīng)度值的模式在種群中的數(shù)目的期望值以指數(shù)級(jí)遞增。模式定理是遺傳算法的基本理論，保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，是解釋遺傳算法機(jī)理的有效工具。模式定理為積木塊假設(shè)理論提供了有力的理論支持。引理5.6.2積木塊假設(shè)（buildingblockhypothesis）.遺傳算法通過低階、短定義距以及平均適應(yīng)度值高于種群平均適應(yīng)度的模式（積木塊），在遺傳操作的作用下相互結(jié)合，最終接近全局最優(yōu)解。目前，大量的實(shí)踐支持積木塊假設(shè)理論，并在許多領(lǐng)域內(nèi)取得了成功。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的樣本數(shù)呈指數(shù)增長(zhǎng)，即遺傳算法存在找到最優(yōu)解的可能性，而積木塊假設(shè)指出，積木塊在遺傳算子的作用下，能生成低階、短距和高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。在進(jìn)化領(lǐng)域中，基本遺傳算法是基于人工選擇和交叉、變異等遺傳操作構(gòu)成的一種優(yōu)化方法。由于遺傳操作的隨機(jī)性，在對(duì)大量的構(gòu)造塊（積木塊）進(jìn)行選擇和重組過程中易導(dǎo)致構(gòu)造塊破壞和連鎖問題的發(fā)生，從而導(dǎo)致算法早熟或陷入局部最優(yōu)解。因此，研究能更好地識(shí)別構(gòu)造塊，從而解決連鎖問題的算法成為研究的一個(gè)熱點(diǎn)問題。在求解問題的過程中，如果只是獨(dú)立的考慮種群中的各個(gè)串，則不能充分考慮變量間的相關(guān)性，當(dāng)通過概率把各個(gè)串結(jié)合起來考慮，發(fā)掘串群體的相似點(diǎn)，我們就會(huì)得到大量的串信息來幫助指導(dǎo)搜索。因此，借鑒模式定理與積木塊假設(shè)的思想與結(jié)論，我們提出了一種優(yōu)良模式連接的思想。主要內(nèi)容可描述如下，采用自然數(shù)編碼方式，并令最初的模式只包含兩個(gè)相鄰的確定值，在進(jìn)化過程中，通過在規(guī)模不大的優(yōu)勢(shì)群體中考慮相似點(diǎn)的大量信息，對(duì)以較高頻率出現(xiàn)在后代中的相鄰值以概率為基礎(chǔ)進(jìn)行連接，組成包含多個(gè)相鄰確定值的模式，這些模式中的確定值組成了一個(gè)連接塊，令其為優(yōu)良模式連接塊，并在進(jìn)化過程中以塊為整體參與進(jìn)化，使得那些適應(yīng)度值高于種群平均適應(yīng)度值的模式在下一代中將會(huì)有更多的代表串，而對(duì)那些適應(yīng)度值低于種群平均適應(yīng)度值的模式，它們?cè)谙乱淮械拇泶畬?huì)減少，充分體現(xiàn)了“優(yōu)勝劣汰”的思想。本節(jié)將優(yōu)良模式連接的思想引入分布估計(jì)算法中，改進(jìn)算法中概率模型的建立方式，為提高算法的優(yōu)化性能提供了可能。5.6.2模式矩陣的建立模式矩陣是根據(jù)個(gè)體中兩兩相鄰變量在優(yōu)勢(shì)群體中出現(xiàn)頻率的大小建立的。為表述方便，以模式中的變量（確定值）表示相應(yīng)的模式。記初始群體為，初始優(yōu)勢(shì)群體為，優(yōu)勢(shì)群體規(guī)模為n。其中第k個(gè)個(gè)體表示為，。以為模板建立模式矩陣。由于初始群體以均勻分布產(chǎn)生，因此，令所有變量產(chǎn)生的初始概率為，通過統(tǒng)計(jì)中兩兩相鄰變量出現(xiàn)的頻率，建立模式矩陣如下：t為進(jìn)化代數(shù),這里t=1。且，（5.60）（5.61）其中，，為1表示中的第k個(gè)個(gè)體中存在相鄰變量，否則為0。為優(yōu)勢(shì)群體中相鄰變量出現(xiàn)的頻率。公式（5.60）中，越大，上一代對(duì)下一代影響越大，反之越小。在建立模式矩陣時(shí)，只考慮此相鄰變量是否出現(xiàn)在相應(yīng)的個(gè)體結(jié)構(gòu)中，這種方法能增大出現(xiàn)頻率高的模式被保留的機(jī)會(huì)。5.6.3分塊優(yōu)化過程建立分塊模型設(shè)進(jìn)化到第s代，對(duì)應(yīng)的模式矩陣為，根據(jù)對(duì)最優(yōu)個(gè)體結(jié)構(gòu)進(jìn)行分塊，建立分塊結(jié)構(gòu)模型如下[76]：最優(yōu)個(gè)體中的模式信息代表優(yōu)良模式信息。若某相鄰變量的模式出現(xiàn)的頻率高，則其出現(xiàn)在下一代中的幾率大。若存在若干相鄰變量，出現(xiàn)的頻率均很高，為避免在進(jìn)化過程中優(yōu)良連接模式被破壞，同時(shí)避免在同一區(qū)域的重復(fù)搜索，則使其連接成一個(gè)塊，以塊為單位參與進(jìn)化。這時(shí)可設(shè)定一個(gè)參數(shù)，若多個(gè)相鄰模式出現(xiàn)的頻率大于，令其連接成一個(gè)塊。越大，表示被連接成塊的模式出現(xiàn)的頻率越高，反之越小。具體分塊步驟如下：設(shè)最優(yōu)個(gè)體為，且∧考慮相鄰變量組成的模式的特征，若對(duì)應(yīng)模式矩陣，的值大于參數(shù)，則認(rèn)為模式與相關(guān)，屬于同一個(gè)塊，否則，相互獨(dú)立。越小，連接條件越易滿足，變量越易被連接成子塊，反之，變量越難被連接成子塊。在優(yōu)化過程中，每個(gè)子塊被作為一個(gè)整體參與進(jìn)化。若太小，很容易滿足連接條件，多個(gè)變量很快被連接成子塊，使得算法易陷入局部最優(yōu)。太大，連接條件不容易滿足，算法總在整個(gè)模式中搜索，降低搜索速度，不利于搜索到最優(yōu)解。一般來說選擇。產(chǎn)生初始子塊群體設(shè)最優(yōu)個(gè)體最大分塊數(shù)為R，R為正整數(shù)。隨機(jī)產(chǎn)生M個(gè)1到R的排列作為子塊初始群體，根據(jù)子塊排序計(jì)算個(gè)體得分，選擇最優(yōu)個(gè)體和優(yōu)勢(shì)群體，令子塊優(yōu)勢(shì)群體規(guī)模為m。分塊概率模型的建立和更新令第t代子塊優(yōu)勢(shì)群體為，第k個(gè)個(gè)體表示為，。t=0表示初始子塊群體，初始子塊優(yōu)勢(shì)群體記為。由于各子塊間相互獨(dú)立，且可任意交換位置，因此，在子塊優(yōu)勢(shì)群體中，針對(duì)每一個(gè)位置，計(jì)算各子塊排在該位置的概率，建立分塊概率模型如下：其中，為第個(gè)子塊排在第個(gè)位置上的概率，t為進(jìn)化代數(shù)，。由于初始子塊群體以均勻分布產(chǎn)生，因此令子塊的初始產(chǎn)生概率為。通過計(jì)算初始子塊優(yōu)勢(shì)群體中各子塊排列位置的概率，得到為：（5.62）在進(jìn)化過程中，通過計(jì)算新的優(yōu)勢(shì)群體中各子塊排列位置的概率，對(duì)概率模型進(jìn)行更新，概率的更新如下：（5.63）（5.64），越大，上一代個(gè)體，對(duì)下一代影響越大，反之越小。與意義相同，取值可相等也可不等，文中取二者相等。產(chǎn)生新子塊群體從新的概率模型中重新抽樣。抽樣方式為以的每一列為基礎(chǔ)，采用輪盤法反復(fù)抽樣，給每個(gè)位置選擇取值，產(chǎn)生新子塊群體。計(jì)算子塊個(gè)體得分，判斷收斂性。若收斂則結(jié)束；否則，調(diào)整子塊內(nèi)部變量間的排序。調(diào)整子塊內(nèi)部各變量的排序?yàn)楸苊庀萑刖植孔顑?yōu)，針對(duì)每一個(gè)子塊，隨機(jī)或以條件概率為基礎(chǔ)產(chǎn)生新排列，重新調(diào)整子塊內(nèi)部各變量的排列順序，進(jìn)一步進(jìn)行局部搜索。重復(fù)執(zhí)行上述步驟，得到子塊的若干新排列。計(jì)算得分，若得分有改進(jìn)，保留新排列，否則原排列不變，執(zhí)行下一個(gè)子塊操作。直到所有子塊操作完成。判斷收斂性，若滿足收斂條件，結(jié)束。否則，選擇新的子塊優(yōu)勢(shì)群體，返回步驟，更新子塊概率模型。重復(fù)步驟至，當(dāng)最優(yōu)子塊個(gè)體在若干代內(nèi)得分不變時(shí)，分塊優(yōu)化過程結(jié)束。5.6.4算法流程基于優(yōu)良模式連接的EDA算法的主要內(nèi)容包括，首先，從種群中選擇優(yōu)勢(shì)群體，統(tǒng)計(jì)所有兩兩相鄰模式出現(xiàn)的頻率，構(gòu)建模式矩陣描述個(gè)體結(jié)構(gòu)的特征，出現(xiàn)頻率越高的模式，在模式矩陣中所占比例也越大。然后，從模式矩陣中反復(fù)抽樣，產(chǎn)生新的優(yōu)勢(shì)群體，根據(jù)相應(yīng)的模式矩陣對(duì)優(yōu)勝個(gè)體結(jié)構(gòu)進(jìn)行分塊，構(gòu)建優(yōu)良模式的連接塊。令各個(gè)塊之間相互獨(dú)立，采用變量無關(guān)的分布估計(jì)算法PBIL優(yōu)化連接塊的排序，針對(duì)每個(gè)塊內(nèi)部的模式，有條件的進(jìn)行局部調(diào)整，增強(qiáng)局部搜索能力，最終獲得問題的滿意解。算法基本流程如下：Step1產(chǎn)生初始群體.Step2計(jì)算個(gè)體的適應(yīng)度.Step3整個(gè)群體按照適應(yīng)度值從大到小排序，以一定的比例選擇若干適應(yīng)度好的個(gè)體作為優(yōu)勢(shì)群體.Step4根據(jù)優(yōu)勢(shì)群體信息，建立模式矩陣.Step5從模式矩陣中抽樣產(chǎn)生新群體。計(jì)算個(gè)體適應(yīng)度，判斷終止條件。若滿足終止條件則結(jié)束，否則選擇新的優(yōu)勢(shì)群體，執(zhí)行Step6.Step6更新模式矩陣.重復(fù)執(zhí)行步驟Step5與Step6，當(dāng)最優(yōu)個(gè)體在若干代內(nèi)得分不變時(shí)，執(zhí)行下一步。Step7分塊優(yōu)化過程.當(dāng)最優(yōu)子塊個(gè)體在若干代內(nèi)得分不變時(shí)，當(dāng)前代分塊優(yōu)化過程結(jié)束。令產(chǎn)生的新的子塊優(yōu)勢(shì)群體與執(zhí)行分塊優(yōu)化過程前的優(yōu)勢(shì)群體中的所有個(gè)體，按照適應(yīng)度的大小重新排序，選擇新的優(yōu)勢(shì)群體，返回Step4.重復(fù)執(zhí)行上述過程，直到滿足終止條件。為保證算法的收斂性，整個(gè)過程采用最優(yōu)保留策略。5.6.5實(shí)例仿真為了驗(yàn)證算法的有效性，采用幾個(gè)著名的JobShop問題和柔性JobShop問題的測(cè)試算例作為測(cè)試集進(jìn)行仿真實(shí)驗(yàn)。JobShop問題仿真測(cè)試本實(shí)驗(yàn)采用幾個(gè)著名的JobShop問題的測(cè)試算例作為測(cè)試集進(jìn)行仿真實(shí)驗(yàn)。這些算例來自FisherandThompson設(shè)計(jì)的三個(gè)算例Ft06，F(xiàn)t10與Ft20和其它幾類典型算例中的第一個(gè)算例。由于本節(jié)提出的EDA算法[77]是一種沒有混合其它優(yōu)化算法的單純EDA算法，因此仿真結(jié)果與單純PSO算法[78]中的結(jié)果進(jìn)行了比較。仿真結(jié)果如表5.3所示。表5.3EDA算法與PSO算法結(jié)果比較例子問題規(guī)模最優(yōu)解算法PSOEDAMinMaxAverageMinMaxaverageFT066655555956.1555555.0FT10101093098510841035.6937937937.0FT202051165120813521266.9118411841184.0LA01105666666688668.6666666666.0LA06155926926926926.0926926926.0LA112051222122212221222122212221222.0LA1610109459459561035945946945.5LA2115101046110211471128.4107110731071.6LA2620101218126313511312.6125712611257.8LA3130101784178918971830.4178917891789.0LA3615151268137314361409.2129213151312.7從表5.3中可以看出，EDA算法得到的最小值、均值與最大值均小于單純PSO算法中的值，說明單純EDA的優(yōu)化性能優(yōu)于單純PSO算法。同時(shí)EDA中得到的最大值、均值與最小值之間的差值非常小，說明提出的EDA算法具有很好的穩(wěn)定性。柔性JobShop問題仿真測(cè)試本實(shí)驗(yàn)選擇了3個(gè)有代表性的柔性JobShop例子進(jìn)行仿真測(cè)試。這3個(gè)例子均來自文獻(xiàn)[79,80]，文中參數(shù)與PSO+TS算法[81]參數(shù)設(shè)置相同。本節(jié)所提EDA算法[82]獲得的結(jié)果與AL+CGA算法,PSO+SA算法[83],PVNS算法[84]和PSO+TS算法進(jìn)行了比較，具體結(jié)果如下。實(shí)驗(yàn)1針對(duì)問題45的仿真計(jì)算問題45是一個(gè)完全柔性問題，每個(gè)工件的第一個(gè)工序的最早開工時(shí)間為0，EDA算法所獲得的最優(yōu)解的Gantt圖如圖5.1所示，EDA算法的仿真結(jié)果與其它幾類算法仿真計(jì)算結(jié)果的比較如表5.4所示。圖5.1問題45的最優(yōu)解Gantt圖表5.4問題45的計(jì)算結(jié)果比較AL+CGAPSO+TSEDAMakespan161111Wk101010Wt343232從表5.4中的結(jié)果可以看出，EDA算法獲得的結(jié)果優(yōu)于混合算法AL+CGA的結(jié)果，與PSO+TS算法的結(jié)果相同，但是，這里提出的EDA算法是一種單純算法，算法中沒有混合其它啟發(fā)式算法，而其它兩種算法都是混合算法，EDA算法獲得的結(jié)果優(yōu)于或等于這兩種混合算法的結(jié)果，說明提出的EDA算法具有較好的尋優(yōu)能力。實(shí)驗(yàn)2針對(duì)問題88的仿真計(jì)算問題88是一個(gè)部分柔性問題，只能選擇某些加工機(jī)器，我們令工件的不可選擇機(jī)器上的加工時(shí)間為一個(gè)很大的值，例如9999，遠(yuǎn)遠(yuǎn)大于其它機(jī)器上的加工時(shí)間，因此，當(dāng)選擇加工機(jī)器時(shí)，一般不可能選中這臺(tái)機(jī)器，從而使得問題由部分柔性問題轉(zhuǎn)變?yōu)橥耆嵝詥栴}。問題88的每個(gè)工件的第一道工序的最早開工時(shí)間為0，EDA算法所獲得的最優(yōu)解Gantt圖如圖5.2所示，算法的仿真結(jié)果與其它算法仿真結(jié)果的比較如表5.5所示。圖5.2問題88的最優(yōu)解Gantt圖從表5.5中的結(jié)果可以看出，EDA算法獲得的結(jié)果優(yōu)于混合算法AL+CGA和PSO+SA的結(jié)果，與PSO+TS算法和PVNS算法的結(jié)果相同，EDA算法是一種單純算法，算法中沒有混合其它啟發(fā)式算法，仿真結(jié)果說明單純EDA算法有較好的尋優(yōu)能力。表5.5問題88的計(jì)算結(jié)果比較算法參數(shù)AL+CGAPSO+SAPVNSPSO+TSEDAsMakespan1516151614141514Wk1313121313121212Wt7975757377777579實(shí)驗(yàn)3針對(duì)問題1010的仿真計(jì)算問題1010是一個(gè)完全柔性問題，每個(gè)工件的第一個(gè)工序的最早開工時(shí)間為0，EDA算法所獲得的最優(yōu)解Gantt圖如圖5.3所示，EDA算法的仿真結(jié)果與其它算法仿真結(jié)果的比較如表5.6所示。圖5.3問題1010的最優(yōu)解Gantt圖表5.6問題1010的計(jì)算結(jié)果比較算法參數(shù)AL+CGAPSO+SAPVNSPSO+TSEDAsMakespan77777Wk56-66Wt4544-4343從表5.6中可以看出，這幾類算法獲得的最優(yōu)完工時(shí)間相同，其它兩個(gè)參數(shù)的結(jié)果基本相似，但是本文提出的EDA算法是一種單純算法，而其它幾種算法都是混合算法，從表中的結(jié)果看以看出，EDA算法具有較好的尋優(yōu)能力。5.7基于Bayesian統(tǒng)計(jì)推理的分布估計(jì)算法Bayesian統(tǒng)計(jì)推斷理論是數(shù)理統(tǒng)計(jì)中的一個(gè)重要分支。Bayesian統(tǒng)計(jì)推斷方法與貝葉斯網(wǎng)絡(luò)優(yōu)化方法不同，它不需要優(yōu)化復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，而是直接利用樣本提供的信息，通過建立一個(gè)后驗(yàn)概率分布對(duì)樣本進(jìn)行推斷，由于這個(gè)后驗(yàn)分布中包含了先驗(yàn)分布信息和樣本信息，因而對(duì)大樣本和小樣本均有較好的統(tǒng)計(jì)推斷效果。因此，本節(jié)針對(duì)離散優(yōu)化問題，把Bayesian統(tǒng)計(jì)推斷方法引入分布估計(jì)算法中建立概率模型，提出了一種基于Bayesian統(tǒng)計(jì)推理的分布估計(jì)算法。5.7.1Bayesian統(tǒng)計(jì)推斷理論Bayesian統(tǒng)計(jì)推斷理論是數(shù)理統(tǒng)計(jì)中的一個(gè)重要分支，它有鮮明的特點(diǎn)和獨(dú)到的處理問題的方法[85]。Bayesian統(tǒng)計(jì)推斷的主要特點(diǎn)是使用先驗(yàn)分布，在得到樣本觀測(cè)值之后，由x與先驗(yàn)分布提供的信息，得到后驗(yàn)分布。后驗(yàn)分布包含了先驗(yàn)信息與樣本提供的信息，是Bayesian統(tǒng)計(jì)推斷的基礎(chǔ)。由于利用了先驗(yàn)知識(shí)，Bayesian統(tǒng)計(jì)推斷對(duì)大樣本和小樣本均有較好的統(tǒng)計(jì)推斷效果。Bayesian公式為：（5.65）其中，事件構(gòu)成互不相容的事件完備組，，為先驗(yàn)分布概率，構(gòu)成先驗(yàn)分布。由于事件B的發(fā)生可以對(duì)事件發(fā)生的概率重新估計(jì)，以后驗(yàn)分布體現(xiàn)出來，因此Bayesian公式綜合了先驗(yàn)信息與實(shí)驗(yàn)提供的樣本信息，獲得后驗(yàn)信息，并實(shí)現(xiàn)了先驗(yàn)分布向后驗(yàn)分布的轉(zhuǎn)化，是Bayesian統(tǒng)計(jì)推斷的數(shù)學(xué)模型。5.7.2概率模型的建立很多離散優(yōu)化問題，尤其是排序優(yōu)化問題，個(gè)體中各個(gè)變量的排列位置直接影響個(gè)體適應(yīng)度的大小，因此，建立能反映各變量排列位置信息的概率模型，是分布估計(jì)算法求解這類問題的關(guān)鍵。Bayesian統(tǒng)計(jì)推斷理論為我們提供了一個(gè)利用個(gè)體中的排列位置信息建立概率模型的有力工具。Bayesian統(tǒng)計(jì)推斷方法主要是通過建立一個(gè)后驗(yàn)分布對(duì)樣本進(jìn)行推斷，而這個(gè)后驗(yàn)分布是利用了先驗(yàn)分布信息與樣本提供的條件概率信息，并通過Bayesian公式的轉(zhuǎn)化獲得的。因此，在建立后驗(yàn)分布概率模型以前，首先需要建立相應(yīng)的先驗(yàn)分布概率模型和條件分布概率模型。先驗(yàn)分布概率模型的建立算法采用自然數(shù)的排列作為編碼方式對(duì)離散問題進(jìn)行編碼。充分利用個(gè)體中變量的排列位置信息建立先驗(yàn)分布概率模型。設(shè)個(gè)體長(zhǎng)度為L(zhǎng)，x=(π(1),π(2),…π(L))為1,2,…L的一個(gè)排序，表示一個(gè)個(gè)體，π(j)為排在第j個(gè)位置上的變量。個(gè)體中每個(gè)變量的排列位置直接影響個(gè)體適應(yīng)度的大小，因此為描述變量排在各個(gè)位置上的信息，令個(gè)體中的L個(gè)變量分別對(duì)應(yīng)L個(gè)位置。針對(duì)每一個(gè)位置上的變量建立一個(gè)先驗(yàn)分布概率向量，則所有變量對(duì)應(yīng)的先驗(yàn)概率向量組成一個(gè)先驗(yàn)分布概率模型，第j個(gè)位置上對(duì)應(yīng)的個(gè)體取值與先驗(yàn)分布概率向量的對(duì)應(yīng)關(guān)系如下：，概率向量pj=(p1j,p2j,…pLj)T描述了所有變量出現(xiàn)在第j個(gè)位置上的先驗(yàn)概率，j=1,2,…L。則所有位置上的概率向量組成一個(gè)概率矩陣，即P=(p1,p2,…,pL),稱P為所建立的先驗(yàn)概率分布模型。在Bayesian統(tǒng)計(jì)推斷理論中，先驗(yàn)分布是Bayesian統(tǒng)計(jì)模型中的重要組成部分。因此，先驗(yàn)分布的選取是一個(gè)很重要的問題。選取先驗(yàn)分布的方法很多，由于本算法是針對(duì)復(fù)雜優(yōu)化問題的求解，其解的概率分布都是未知的，需要在求解過程中不斷地搜索、更新、重新估計(jì)，從而獲得一個(gè)近似的分布概率模型，從中抽樣產(chǎn)生新群體，求得問題的滿意解。因此，在此算法中初始的先驗(yàn)分布概率采用均勻分布，這符合先驗(yàn)分布選取中的最大熵原則。熵是信息論中的一個(gè)基本概念，是隨機(jī)變量不確定性的度量，不確定性越大，則熵越大。在“無信息”的情況下，應(yīng)取熵最大的分布為先驗(yàn)分布，而均勻分布的熵最大，數(shù)據(jù)隨機(jī)性最大，包含的信息量也最大。因此，算法中選取初始的先驗(yàn)分布為均勻分布，然后在進(jìn)化過程中，通過提取優(yōu)勢(shì)群體中的優(yōu)良信息，不斷地更新先驗(yàn)分布，從而獲得越來越接近最優(yōu)解的先驗(yàn)分布概率模型。條件分布概率模型的建立若個(gè)體中的所有變量之間無先后約束，則每個(gè)變量可在所有位置的任意一個(gè)位置排列。若對(duì)應(yīng)第j個(gè)位置上出現(xiàn)符號(hào)（變量）π(j)，而每個(gè)變量都有可能出現(xiàn)在該位置上，所以可用一個(gè)條件概率向量表示變量π(j)出現(xiàn)在對(duì)應(yīng)位置上的信息，該條件概率向量可表示為qj=(q(π(j)／1),q(π(j)／2),…,q(π(j)／L))T。這個(gè)概率向量的值來自優(yōu)勢(shì)群體中的樣本信息，它描述了當(dāng)其它變量可能出現(xiàn)在該位置的條件下，變量π(j)出現(xiàn)的條件概率。這時(shí)，L個(gè)位置對(duì)應(yīng)L個(gè)條件概率向量，組成一個(gè)條件概率矩陣。設(shè)在第t代，第k個(gè)個(gè)體表示為xkt=(πkt(1),πkt(2),…πkt(L))，第t代優(yōu)勝個(gè)體為xt*=(πt*(1),πt*(2),…πt*(L))。根據(jù)優(yōu)勝個(gè)體與優(yōu)勢(shì)群體，建立第t代條件矩陣為：其中，qt(πt*(j)／i)表示在符號(hào)i出現(xiàn)的條件下，符號(hào)πt*(j)出現(xiàn)的條件概率。根據(jù)條件概率公式，qt(πt*(j)／i)=qt(πt*(j)·i)／qt(i)成立，其中，q