求解圖分割問題的混合進(jìn)化算法.pdf

1、圖論中的圖可以表示各種社會(huì)主體及其之間的復(fù)雜關(guān)系。根據(jù)一定的要求，對(duì)圖進(jìn)行分割，可以廣泛用于頻譜分配、寄存器分配、RFID閱讀器沖突、電路布線、作業(yè)調(diào)度等方面。
　　本文以圖著色、塊模型、飛蜂窩網(wǎng)絡(luò)頻譜分配問題為代表，研究求解圖分割問題的混合進(jìn)化算法。論文主要進(jìn)行了以下三個(gè)方面的工作：
　?。?）提出了求解圖著色問題的混合進(jìn)化算法。算法首先采用k種顏色著色并求解其k-著色，如果該方案可行，用k?1代替k，重復(fù)該過程直到無法找

2、到更小的k-著色。算法采用多父代免沖突交叉算子，結(jié)合禁忌搜索，并且通過實(shí)驗(yàn)證明了算法的有效性。
　?。?）提出了求解塊模型問題的進(jìn)化算法。算法首先采用完全子圖的思想進(jìn)行種群初始化，然后通過交叉、修復(fù)，不斷增加塊的規(guī)模，最后通過反復(fù)迭代，得到最大的目標(biāo)函數(shù)值，并保證算法收斂。實(shí)驗(yàn)結(jié)果證明了本算法的可行性以及優(yōu)越性。
　　（3）提出了基于禁忌搜索的飛蜂窩網(wǎng)絡(luò)頻譜分配方法。根據(jù)網(wǎng)絡(luò)中飛蜂窩基站之間的干擾情況繪制出飛蜂窩網(wǎng)絡(luò)干擾圖，