陳福林

（贛州師范高等?？茖W(xué)校，江西 贛州 341000）

0 引 言

目前，社會(huì)各領(lǐng)域中，存在大量的優(yōu)化問(wèn)題。對(duì)于這些問(wèn)題，如何進(jìn)行優(yōu)化，有不少研究人員進(jìn)行了相關(guān)的研究，并提出了很多研究算法。本文在分析現(xiàn)有優(yōu)化算法的基礎(chǔ)上，進(jìn)行了基于貝葉斯網(wǎng)絡(luò)的進(jìn)化計(jì)算優(yōu)化研究?；谪惾~斯網(wǎng)絡(luò)的進(jìn)化估計(jì)計(jì)算研究首先是找好變量及各變量間的因果關(guān)系，根據(jù)變量間的因果關(guān)系構(gòu)建網(wǎng)絡(luò)模型，然后根據(jù)網(wǎng)絡(luò)模型事件的因果關(guān)系的先驗(yàn)概率、條件概率來(lái)推導(dǎo)、優(yōu)化問(wèn)題解集的聯(lián)合概率分布，用優(yōu)解得到的聯(lián)合概率分布優(yōu)化下一代種群?；谪惾~斯網(wǎng)絡(luò)的進(jìn)化計(jì)算算法對(duì)解決高階、多層次化的問(wèn)題優(yōu)化有很好的優(yōu)勢(shì)。在不確定性問(wèn)題處理中得到較好應(yīng)用。

1 進(jìn)化計(jì)算

進(jìn)化計(jì)算是一種以達(dá)爾文進(jìn)化論為依據(jù)，對(duì)人工系統(tǒng)進(jìn)行設(shè)計(jì)、優(yōu)化和控制的技術(shù)和方法的總稱。進(jìn)化計(jì)算自從20世紀(jì)60年代提出到現(xiàn)在已經(jīng)發(fā)展了4 個(gè)分支：一是由美國(guó)密歇根大學(xué)的J.Holland 提出的遺傳算法，遺傳算法在機(jī)器學(xué)習(xí)及系統(tǒng)優(yōu)化等方面得到廣泛應(yīng)用；二是由美國(guó)科學(xué)家L.J.Fogel 提出的進(jìn)化規(guī)劃，該方法最初是用來(lái)預(yù)測(cè)符號(hào)系列輸入的有限狀態(tài)，后來(lái)用于優(yōu)化問(wèn)題的參數(shù)；三是由德國(guó)科學(xué)家RecHechenber 和Schwefe 提出的進(jìn)化策略，該策略主要用來(lái)解決彎管形狀優(yōu)化問(wèn)題；四是科學(xué)家Koza 提出的遺傳程序設(shè)計(jì)，主要用于機(jī)器學(xué)習(xí)等，目前正嘗試用于對(duì)C 計(jì)算機(jī)結(jié)構(gòu)化程序設(shè)計(jì)言，C++程序設(shè)計(jì)語(yǔ)言、java 程序設(shè)計(jì)語(yǔ)言及Python 程序設(shè)計(jì)語(yǔ)言等面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言進(jìn)行優(yōu)化學(xué)習(xí)，并對(duì)這些語(yǔ)言的算法優(yōu)化取得了不錯(cuò)效果，在實(shí)際程序編寫(xiě)及項(xiàng)目開(kāi)發(fā)中取得了應(yīng)用。

2 遺傳算法分析

遺傳算法是一種隨機(jī)優(yōu)化算法，是通過(guò)對(duì)染色體的評(píng)價(jià)和染色體中基因的作用，有效地利用原有的信息來(lái)指導(dǎo)搜索，用搜索的信息改善優(yōu)化質(zhì)量狀態(tài)，通過(guò)種群不斷優(yōu)化，得到最優(yōu)后代。

遺傳算法是一種依賴人工選擇和重組操作的優(yōu)化算法。在用遺傳算法進(jìn)行種群優(yōu)化過(guò)程中要用到積木假設(shè)及模式定理，但積木假設(shè)及模式定理往往是相互矛盾的，因此在優(yōu)化過(guò)程中經(jīng)常達(dá)不到要求。

3 貝葉斯網(wǎng)絡(luò)概述

貝葉斯網(wǎng)絡(luò)又稱為信念網(wǎng)絡(luò)、概率網(wǎng)路、因果網(wǎng)絡(luò)或知識(shí)圖，從這些稱呼可知，貝葉斯網(wǎng)絡(luò)是用于描述變量間概率關(guān)于的圖形模式，圖中的節(jié)點(diǎn)即為變量，節(jié)點(diǎn)間的有向邊表示變量間的因果關(guān)系，如圖1所示，圖1不僅能體現(xiàn)高度相互影響的變量集的直觀界面，還能體現(xiàn)導(dǎo)致有效算法的數(shù)據(jù)結(jié)構(gòu)，為復(fù)雜性和不確定性問(wèn)題的解決提供了很直觀自然的方法，用貝葉斯網(wǎng)絡(luò)進(jìn)行不確定性問(wèn)題推理時(shí)用到事件即變量的先驗(yàn)概率及條件概率，推導(dǎo)出事件后驗(yàn)概率，從而找出問(wèn)題的最優(yōu)解，用的推理法為概率推理法，在給定一定的證據(jù)節(jié)點(diǎn)條件下計(jì)算查詢節(jié)點(diǎn)的后驗(yàn)概率分布。

圖1 貝葉斯網(wǎng)絡(luò)模型圖

4 基于貝葉斯網(wǎng)絡(luò)進(jìn)化計(jì)算優(yōu)化研究

4.1 基于貝葉斯網(wǎng)絡(luò)進(jìn)化計(jì)算優(yōu)化算法的實(shí)現(xiàn)思想

遺傳算法可以理解為是在沒(méi)有先驗(yàn)知識(shí)的情況下，從個(gè)體中學(xué)習(xí)基因之間的關(guān)系及個(gè)體的適應(yīng)度信息，利用學(xué)習(xí)得到的信息產(chǎn)生更好的下一代群體的算法。前面分析了遺傳算法中的積木假設(shè)及模式定理往往是相互矛盾的，且積木塊往往又是分布在所有的染色體中，有時(shí)用遺傳算法進(jìn)行問(wèn)題的研究時(shí)找不到最優(yōu)解，在基于遺傳算法研究的基礎(chǔ)上引發(fā)了對(duì)分布估計(jì)算法的研究，分布估計(jì)算法又稱為遺傳算法的概率圖模型方法，而貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法是概率圖模型中典型的一種模型優(yōu)化算法。

貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法的實(shí)現(xiàn)思想是使用圖形作為工具描述因子間的因果關(guān)系，概率表述每一代群體的相互關(guān)系緊密程度，算法的基礎(chǔ)是利用每一代的個(gè)體，從中學(xué)習(xí)隨機(jī)變量的分布，在學(xué)習(xí)得到的分布基礎(chǔ)上，生成下一代新個(gè)體，如此反復(fù)直到產(chǎn)生最佳群體，即最優(yōu)解。

當(dāng)我們用貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法對(duì)問(wèn)題進(jìn)行優(yōu)化時(shí)考慮的主要問(wèn)題有兩個(gè)方面：一是如何利用可選解進(jìn)行估計(jì)，即如何確定先驗(yàn)概率；二是如何利用分布函數(shù)確定新解，即確定后驗(yàn)概率。這兩問(wèn)題互相關(guān)聯(lián)，在優(yōu)化問(wèn)題的過(guò)剩中，如果能對(duì)初始分布進(jìn)行正確估計(jì)，則能產(chǎn)生更好的優(yōu)化解，對(duì)問(wèn)題進(jìn)行更好的優(yōu)化。根據(jù)算法在實(shí)現(xiàn)時(shí)設(shè)計(jì)的不同，貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法分為連續(xù)的貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法和離散的貝葉斯網(wǎng)絡(luò)進(jìn)化優(yōu)化算法。

4.2 貝葉斯網(wǎng)絡(luò)優(yōu)化算法流程

在BOA 算法中，首先通過(guò)均勻分布隨機(jī)產(chǎn)生方式得到第一代群體。然后利用貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)中用到的評(píng)價(jià)函數(shù)探索空間網(wǎng)，構(gòu)造一個(gè)與當(dāng)前群體優(yōu)秀個(gè)體相匹配貝葉斯網(wǎng)絡(luò)，新的個(gè)體可從貝葉斯分布網(wǎng)絡(luò)優(yōu)化、推導(dǎo)產(chǎn)生，然后再用網(wǎng)絡(luò)優(yōu)化、推導(dǎo)產(chǎn)生新個(gè)體替代前一代中存在問(wèn)題的個(gè)體加入種群。具體的算法流程如圖2所示。

圖2 概率圖模型進(jìn)化分布算法實(shí)現(xiàn)圖

BOA 算法是貝葉斯網(wǎng)絡(luò)作為變量的概率模型。用BOA算法進(jìn)行問(wèn)題優(yōu)化時(shí)，要解決兩個(gè)問(wèn)題：一是評(píng)價(jià)函數(shù)的選擇；二是如何對(duì)構(gòu)建的網(wǎng)絡(luò)進(jìn)行采樣。

4.3 BOA 算法的評(píng)價(jià)函數(shù)

在Cooper 及Buntine 等人研究的基礎(chǔ)上，Heckerman 提出了貝葉斯網(wǎng)絡(luò)的BDe 函數(shù)評(píng)價(jià)方法。利用BDe 進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，就是尋找后驗(yàn)分布最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。即：

從公式可以看知，要計(jì)算一個(gè)X的Dbe 測(cè)度，必須計(jì)算實(shí)例數(shù)據(jù)的似然分布（X |）和結(jié)構(gòu)的似然分布（X ）。如果實(shí)例數(shù)據(jù)完整，實(shí)例變量互相獨(dú)立以及參數(shù)變量為Dirichlet 分布的假設(shè)情況下，BOA 算法的Bde 度量公式為：

式中：為背景信息；（|）為構(gòu)建網(wǎng)絡(luò)的先驗(yàn)概率；π為x的父親節(jié)點(diǎn)集合；m′（ π）與m′（x，π）分別為優(yōu)化問(wèn)題的先驗(yàn)信息。在對(duì)問(wèn)題進(jìn)行優(yōu)化時(shí)，把m′（x，π）與（|）融入到問(wèn)題的優(yōu)化中，先驗(yàn)概率反映出了被測(cè)量網(wǎng)絡(luò)與先前網(wǎng)絡(luò)的相似程度。

4.4 BOA 的采樣算法

在給定了BOA 算法的評(píng)價(jià)函數(shù)后，接下來(lái)是事情就是根據(jù)現(xiàn)有的網(wǎng)絡(luò)結(jié)構(gòu)產(chǎn)生新的后選解，后選解要通過(guò)對(duì)構(gòu)建的網(wǎng)絡(luò)采樣取得。BOA 算法的采樣分兩個(gè)步驟完成：一是確定節(jié)點(diǎn)間的關(guān)系，主要是確定網(wǎng)絡(luò)結(jié)構(gòu)中所有節(jié)點(diǎn)的祖孫關(guān)系，一般是通過(guò)排序算法來(lái)實(shí)現(xiàn)；二是根據(jù)步驟一確定的節(jié)點(diǎn)關(guān)系，產(chǎn)生一個(gè)新的后選解。因此具體算法為：

(1)根據(jù)給定的網(wǎng)絡(luò)和群體，計(jì)算網(wǎng)絡(luò)中每一節(jié)點(diǎn)對(duì)于父節(jié)點(diǎn)的條件概率。

(2)對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行排序，確定相應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)，置父節(jié)點(diǎn)到該節(jié)點(diǎn)的前面。

(3)按照先前的排序和計(jì)算得到的條件概率，依次采樣每個(gè)節(jié)點(diǎn)。

(4)把所有采樣得到的節(jié)點(diǎn)值合在一起，構(gòu)成一個(gè)新的個(gè)體。

4.5 BOA 算法進(jìn)化優(yōu)化仿真過(guò)程

基于貝葉斯網(wǎng)絡(luò)的進(jìn)化計(jì)算優(yōu)化仿真過(guò)程如圖3所示。

圖3 基于貝葉斯網(wǎng)絡(luò)的進(jìn)化優(yōu)化仿真過(guò)程圖

從基于貝葉斯網(wǎng)絡(luò)的進(jìn)化優(yōu)化仿真過(guò)程圖可知，用BOA 算法進(jìn)行進(jìn)化計(jì)算優(yōu)化的關(guān)鍵是尋找度量值最大的網(wǎng)絡(luò)來(lái)估計(jì)聯(lián)合概率分布（）,首先選擇種群D（）中構(gòu)建貝葉斯網(wǎng)絡(luò)模型，接著是對(duì)模型進(jìn)行學(xué)習(xí)，模型的學(xué)習(xí)包含兩個(gè)方面：一是結(jié)構(gòu)的學(xué)習(xí)；另一方面是條件概率表的更新學(xué)習(xí)。新模型的學(xué)習(xí)在進(jìn)化過(guò)程中是一個(gè)反復(fù)的過(guò)程，新的網(wǎng)絡(luò)模型構(gòu)建完后，新的個(gè)體可以對(duì)網(wǎng)絡(luò)抽樣得到。

5 結(jié) 論

利用貝葉斯算法進(jìn)行進(jìn)化優(yōu)化時(shí)，是利用變量的聯(lián)合概率分布來(lái)生成新的候選解，用貝葉斯網(wǎng)絡(luò)構(gòu)造數(shù)據(jù)模型，生產(chǎn)子代指導(dǎo)對(duì)解空間的搜索。BOA 通過(guò)對(duì)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)和采樣取代了傳統(tǒng)遺傳算法的交叉和變異操作，實(shí)現(xiàn)了對(duì)種群的學(xué)習(xí)并產(chǎn)生了優(yōu)良的子代群體，同時(shí)避免了大量人工參數(shù)的設(shè)置、重要構(gòu)造塊的破壞。