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

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

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

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

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