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

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

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

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