長模式遺傳算法及其應(yīng)用.pdf

1、遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，它提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，目前已廣泛應(yīng)用于許多學(xué)科。在對遺傳算法進(jìn)行深入研究的基礎(chǔ)上，針對傳統(tǒng)遺傳算法在求解一類容易用0-1表示的問題時存在的不足，提出了一種改進(jìn)的遺傳算法——長模式遺傳算法。
　　針對定義距較長的模式提出了三個具體的再生算子，并以再生算子代替交叉算子，采用簡單位變異算子，從而獲得長模式遺傳算法，它在一類容易用0

2、-1來表示的問題中比采用交叉算子的傳統(tǒng)遺傳算法具有更好的反映問題特性的特點。長模式遺傳算法的編碼方式主要有二進(jìn)制編碼、格雷編碼和符號編碼，而選擇方式、運(yùn)行過程、適應(yīng)度計算等與傳統(tǒng)遺傳算法基本相同；并且針對問題的需要提出了三種終止條件以滿足不同需求。
　　為了研究編碼方式、選擇方式、再生算子、再生概率和變異概率等因素對長模式遺傳算法性能的影響，采用多個通用的測試函數(shù)，提出了成功比例、平均世代數(shù)、平均運(yùn)行時間等具有平均思想的性能評價指

3、標(biāo)，通過大量的數(shù)值仿真實驗，獲得了長模式遺傳算法在測試函數(shù)的仿真實驗中具有較好性能指標(biāo)的一些策略和參數(shù)選擇。
　　為了研究高階、長定義距以及平均適應(yīng)度高的模式的遺傳，將長模式遺傳算法應(yīng)用于One-Max函數(shù)和皇家大道問題，仿真結(jié)果證實了再生算子的有效性以及再生算子和變異算子在模式的重組和遺傳過程中的良好作用。
　　我們將長模式遺傳算法，基本遺傳算法，模擬退火算法，遺傳模擬退火算法，基于價值密度的貪婪算法，回溯法，分支定界法和

4、動態(tài)規(guī)劃法應(yīng)用于0-1背包問題，實驗結(jié)果表明：長模式遺傳算法同其它算法相比，它所獲得的最優(yōu)解的質(zhì)量和回溯法、動態(tài)規(guī)劃法等精確算法獲得的結(jié)果相同，比基本遺傳算法、模擬退火算法、遺傳模擬退火算法、基于價值密度的貪婪算法等算法獲得的最優(yōu)解更好，而且長模式遺傳算法獲得最優(yōu)解時的評價指標(biāo)比基本遺傳算法、遺傳模擬退火算法等算法的相應(yīng)指標(biāo)更好，證明了長模式遺傳算法的有效性。
　　在分析多選擇背包問題和多約束背包問題的基礎(chǔ)上，分別提出了基于物品的