自適應(yīng)記憶遺傳算法研究及在TSP問題中的應(yīng)用.pdf

1、遺傳算法是一種模仿生物自然進(jìn)化過程的、自適應(yīng)啟發(fā)式的全局優(yōu)化算法。由于在利用遺傳算法求解問題時(shí)僅需要很少的輔助信息，容易與其它領(lǐng)域的知識(shí)相結(jié)合，且具有較好的自適應(yīng)性和并行性，使得遺傳算法在組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、人工生命等領(lǐng)域得到了廣泛的應(yīng)用。雖然國(guó)內(nèi)外都很重視遺傳算法的理論和應(yīng)用研究，并取得了很多令人矚目的研究成果，但是遺傳算法的理論和方法還尚未成熟，仍然存在一些不足有待于進(jìn)一步改善。
　　首先，本文以遺傳算法在函數(shù)優(yōu)化

2、中的應(yīng)用為實(shí)例，分析了遺傳算法優(yōu)化過程中基因編碼相同的染色體重復(fù)出現(xiàn)的現(xiàn)象，且隨著進(jìn)化代數(shù)的不斷增加重復(fù)個(gè)體出現(xiàn)的機(jī)率也越來越大。針對(duì)這個(gè)問題，本文通過引入合適規(guī)模的基因庫(kù)用以存儲(chǔ)重復(fù)出現(xiàn)個(gè)體的基因編碼和對(duì)應(yīng)的適應(yīng)度值，并將基因庫(kù)中的染色體按適應(yīng)度值從大到小的順序有序排列。對(duì)于基因庫(kù)中有相同基因編碼的染色體可以直接從基因庫(kù)中獲取其適應(yīng)度值，進(jìn)而解決重復(fù)個(gè)體適應(yīng)度值的重復(fù)計(jì)算問題，降低算法的時(shí)間復(fù)雜度，提高算法的計(jì)算效率。
　　其次

3、，針對(duì)上述算法無法根據(jù)當(dāng)前種群中個(gè)體的分布情況對(duì)遺傳算子執(zhí)行的控制參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整的問題，本文按照自適應(yīng)遺傳算法的交叉概率和變異概率調(diào)節(jié)公式的設(shè)計(jì)原則，根據(jù)種群中個(gè)體的相似系數(shù)，利用Logistic曲線方程對(duì)遺傳算法的交叉概率和變異概率進(jìn)行自適應(yīng)調(diào)整，進(jìn)而提高算法的收斂性能。
　　最后本文以典型的旅行商TSP問題為應(yīng)用背景，以Malab R2009a和Microsoft Visual Studio2010作為開發(fā)環(huán)境，選取TSPL

4、IB中的城市坐標(biāo)數(shù)據(jù)為實(shí)例，實(shí)現(xiàn)了一個(gè)基于改進(jìn)后算法的TSP問題求解系統(tǒng)，并對(duì)改進(jìn)后算法的計(jì)算個(gè)體適應(yīng)度值的時(shí)間代價(jià)與算法的收斂性進(jìn)行測(cè)試和驗(yàn)證。測(cè)試結(jié)果表明:種群規(guī)模為50～150，基因庫(kù)規(guī)模選取為種群規(guī)模的0.1倍～0.2倍時(shí)，本文算法能夠有效地減少算法的時(shí)間復(fù)雜度，其加速比能夠達(dá)到49.70％左右。在算法的收斂性方面，本文改進(jìn)后的算法收斂速度快于基本遺傳算法但稍慢于Srinivas等人提出的自適應(yīng)遺傳算法，且收斂效果要好于其它兩種