協(xié)同進(jìn)化算法及其應(yīng)用研究.pdf

1、進(jìn)化計算已在各個領(lǐng)域得到了廣泛的成功應(yīng)用,但其理論和應(yīng)用都還存在一些瓶頸問題.本文對其前沿方向之一——協(xié)同進(jìn)化計算模型進(jìn)行了深入地分析.針對海量數(shù)據(jù)分類問題、SAT問題、有約束和無約束數(shù)值優(yōu)化、多目標(biāo)優(yōu)化、超大規(guī)模集成電路布圖規(guī)劃等五個具有挑戰(zhàn)性的問題進(jìn)行了系統(tǒng)深入地研究.針對不同問題提出了多種新的算法和實(shí)現(xiàn)策略,主要工作概括如下:(1)針對海量數(shù)據(jù)的分類問題,提出了組織協(xié)同進(jìn)化分類算法.它與現(xiàn)有進(jìn)化分類方法的不同之處在于采用了一種自下

2、而上的搜索機(jī)制,即先使若干樣本的集合得到進(jìn)化,再從進(jìn)化結(jié)果中提取規(guī)則.這樣有利于避免在進(jìn)化過程中產(chǎn)生無意義的規(guī)則.(2)針對SAT問題,提出了求解SAT問題的組織進(jìn)化算法.它將原問題分解成若干子問題,用每個子問題形成一個組織.逐個解決子問題后再通過一定方式協(xié)調(diào)不同子問題間相沖突的變量,以達(dá)到求解原問題的目的.實(shí)驗(yàn)中用3700個不同規(guī)模的標(biāo)準(zhǔn)SAT問題對算法性能作了全面測試,驗(yàn)證了其有效性和通用性.(3)針對數(shù)值優(yōu)化問題,提出了組織進(jìn)化數(shù)

3、值優(yōu)化算法.該算法與傳統(tǒng)遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略求解數(shù)值優(yōu)化問題的運(yùn)行機(jī)制不同.它先由個體構(gòu)成組織,再由組織構(gòu)成種群.進(jìn)化操作不直接作用于個體上,而作用于組織上.從理論上證明了其具有全局收斂性.用15個無約束標(biāo)準(zhǔn)優(yōu)化問題和13個有約束標(biāo)準(zhǔn)優(yōu)化問題驗(yàn)證了算法性能.并對算法中的各個參數(shù)變化機(jī)理進(jìn)行了分析,確定了其取值范圍,便于讀者應(yīng)用.(4)提出了一種新的、適用于進(jìn)化算法求解VLSI布圖規(guī)劃問題的布圖表示方法——移動模式序列.設(shè)計了移動

4、模式序列到布局的轉(zhuǎn)換算法,對其正確性和復(fù)雜度進(jìn)行了理論分析.(5)基于移動模式序列,提出了求解布圖規(guī)劃問題的組織進(jìn)化算法.它能同時處理多種類型模塊混合的布圖問題.對300個硬矩形模塊問題、100個軟矩形模塊問題、100個軟矩形模塊和非矩形模塊的混合問題均求得了高質(zhì)量的解,表明這一方法適于求解大規(guī)模布圖規(guī)劃問題,具有很高的實(shí)用價值.(6)提出了協(xié)同進(jìn)化多目標(biāo)優(yōu)化算法,并根據(jù)其框架提出了求解布圖規(guī)劃問題的多目標(biāo)優(yōu)化方法.它一次運(yùn)行就可求出各