基于probabilistic memetic算法的二次最小生成樹問(wèn)題的研究.pdf

1、最小生成樹問(wèn)題是一類經(jīng)典的網(wǎng)絡(luò)優(yōu)化問(wèn)題。大量研究表明，最小生成樹結(jié)構(gòu)是通信網(wǎng)絡(luò)設(shè)計(jì)的最優(yōu)拓?fù)洹Ｉ蓸湓诖蠖鄶?shù)網(wǎng)絡(luò)設(shè)計(jì)和分析問(wèn)題中扮演著重要角色，然而，實(shí)際的網(wǎng)絡(luò)優(yōu)化問(wèn)題通常需要滿足附加的約束，形成約束最小生成樹問(wèn)題。二次最小生成樹(q-MST)問(wèn)題是在最小生成樹問(wèn)題中附加了邊的交互費(fèi)用的一類約束最小生成樹問(wèn)題，是一類典型的NP完全問(wèn)題。在實(shí)際生活中的很多組合優(yōu)化問(wèn)題，例如，通信網(wǎng)絡(luò)設(shè)計(jì)、超大規(guī)模集成電路的設(shè)計(jì)等優(yōu)化問(wèn)題，都可以轉(zhuǎn)化為二次

2、最小生成樹問(wèn)題，所以對(duì)二次最小生成樹問(wèn)題的研究具有較大的理論意義和實(shí)用價(jià)值。
　　 Probabilistic Memetic Algorithm(PMA)是在memetic算法的基礎(chǔ)上，通過(guò)管理每個(gè)個(gè)體的學(xué)習(xí)強(qiáng)度來(lái)平衡進(jìn)化和個(gè)體學(xué)習(xí)。本文通過(guò)對(duì)q-MST問(wèn)題和PMA進(jìn)行分析、研究，采用基于一種新的進(jìn)化算法PMA對(duì)二次最小生成樹問(wèn)題進(jìn)行求解，將PMA首次應(yīng)用到q-MST問(wèn)題中。本文首先對(duì)采用進(jìn)化算法求解二次最小生成樹問(wèn)題的現(xiàn)有文

3、獻(xiàn)進(jìn)行學(xué)習(xí)和分析，發(fā)現(xiàn)算法中的編碼、進(jìn)化算子等關(guān)鍵技術(shù)還可以通過(guò)改進(jìn)得到更好的解；然后根據(jù)二次最小生成樹問(wèn)題設(shè)計(jì)出局部搜索算子，并借鑒Jaccard系數(shù)推導(dǎo)出在非歐幾里得空間下個(gè)體間距離的計(jì)算方法，進(jìn)而設(shè)計(jì)出基于PMA的二次最小生成樹問(wèn)題的步驟和求解過(guò)程；最后設(shè)計(jì)局部加速算子和全局優(yōu)化算子，對(duì)本文設(shè)計(jì)的PMA進(jìn)行優(yōu)化。
　　 本文參照有關(guān)文獻(xiàn)給出的按隨機(jī)方式生成二次最小生成樹問(wèn)題的方法，通過(guò)設(shè)計(jì)隨機(jī)生成器來(lái)產(chǎn)生若干個(gè)二次最小生成