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

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

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

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