基于蟻群遺傳算法的最小圖著色數(shù)研究.pdf

1、聲明本人鄭重聲明：所呈交的學(xué)位論文，是本人在指導(dǎo)教師的指導(dǎo)下，獨(dú)立進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含其他個人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本聲明的法律責(zé)任由本人承擔(dān)。論文作者簽名：丕墊疊墮i圣日期：／_otub1旨關(guān)于學(xué)位論文使用權(quán)的說明本人完全了解太原理工大學(xué)有關(guān)保管、使用學(xué)位論文的規(guī)定，其中包括：①學(xué)校有權(quán)保管、并向有關(guān)部門送交學(xué)位論文的

2、原件與復(fù)印件；②學(xué)校可以采用影印、縮印或其它復(fù)制手段復(fù)制并保存學(xué)位論文；⑧學(xué)校可允許學(xué)位論文被查閱或借閱；④學(xué)?？梢詫W(xué)術(shù)交流為目的，復(fù)制贈送和交換學(xué)位論文：⑤學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi)容(保密學(xué)位論文在解密后遵守此規(guī)定)。簽名：日期：≯嬸6f孑導(dǎo)師簽名：≥乏q秀日期：秒IV易咿太原理工大學(xué)碩士研究生學(xué)位論文更多可能。在使用改進(jìn)的遺傳算法求解圖著色問題時，雖然比傳統(tǒng)的遺傳算法的收斂速度更快，但是其初始群體比較單一，為了減少初始種群

3、的個數(shù)從而達(dá)到求解更優(yōu)解的目的，提出用一種算法的搜索結(jié)果作為改進(jìn)遺傳算法的初始解。由于貪心算法實(shí)現(xiàn)簡單，尋優(yōu)度不高；禁忌搜索算法本身也是對初始群體依賴性較大，也不適于解決改進(jìn)遺傳算法所要解決的問題；模擬退火算法雖避免了對初值的依賴性，但是求解結(jié)果并不能方便的轉(zhuǎn)換為傳統(tǒng)遺傳算法的初始解結(jié)構(gòu)。蟻群算法具有局部收斂性，能準(zhǔn)確的描述圖著色問題的約束條件，并且所求解的結(jié)果能很方便的轉(zhuǎn)換為傳統(tǒng)遺傳算法的初始解結(jié)構(gòu)，因此更適合于進(jìn)行初始化搜索。本文首

4、先介紹了傳統(tǒng)遺傳算法的設(shè)計(jì)及其用于求解圖著色問題時存在的缺陷，針對圖著色問題的特殊性，根據(jù)遺傳算法的編碼方式和特殊算子，提出了改進(jìn)的遺傳算法模型，即編碼方式采用符號編碼，而遺傳算子的設(shè)計(jì)則采用基因換位算子、拼接算子、切斷算子來取代原來的交叉算子，使求解過程始終朝著更優(yōu)的方向發(fā)展，加快了收斂速度。然后針對改進(jìn)遺傳算法的求解模型存在的初始群體單一性問題，提出了用蟻群搜索算法為其提供初始解的思想。最后總體介紹了融合算法的求解過程，并用Matl