基于遺傳算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化研究.pdf

1、復(fù)雜網(wǎng)絡(luò)現(xiàn)象在日常生活中非常普遍，可以說人們就是生活在一個網(wǎng)絡(luò)化的社會中。近年來，隨著網(wǎng)絡(luò)理論和計算機技術(shù)的飛速發(fā)展，復(fù)雜網(wǎng)絡(luò)受到越來越多的研究者的關(guān)注，已成為研究的一個熱點。特別是小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的提出，開創(chuàng)了復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元。 最小生成樹(MST)是通信網(wǎng)絡(luò)的最優(yōu)拓?fù)浣Y(jié)構(gòu)，在現(xiàn)實世界中，許多網(wǎng)絡(luò)優(yōu)化問題可以描述為各種帶約束的最小生成樹問題?？紤]到從具體的模型出發(fā)研究復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是一種較好的方法，因此，借助數(shù)學(xué)

2、模型的思想，可以將各種約束MST問題抽象為相應(yīng)的模型。此時，復(fù)雜網(wǎng)路的優(yōu)化設(shè)計問題就轉(zhuǎn)化為對具體數(shù)學(xué)模型的求解。如何求解這個模型是本文工作的重心。由于這類問題一般是NP-完全問題，至今未有十分有效的最優(yōu)算法。作為一種被廣泛應(yīng)用的優(yōu)化方法，遺傳算法(GA)具有傳統(tǒng)搜索算法無法比擬的優(yōu)勢，它為復(fù)雜網(wǎng)絡(luò)系統(tǒng)的優(yōu)化提供了一個有效的途徑。 以度約束最小生成樹(DCMST)問題為例，本文詳細(xì)討論了如何將遺傳算法應(yīng)用于該問題，并通過C語言和M

3、ATLAB的混合編程實現(xiàn)了這個算法。一方面，結(jié)合具體的遺傳編碼、遺傳操作及對運行階段的劃分，分別采用基于prüfer數(shù)編碼的遺傳算法(PGA)、兩階段遺傳算法(TSGA)和基于度的排列的遺傳算法(DGA)來求解該問題，實現(xiàn)了對具體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化問題的求解；另一方面，為了驗證算法的可行性和有效性，編寫邊邊交換的啟發(fā)式算法的程序來求解該問題，作為與遺傳算法求解結(jié)果的比較對象，對不同規(guī)模數(shù)值例子的實驗都說明了遺傳算法效果顯著。因此，在許多的