求解TSP問(wèn)題的混合演化算法研究.pdf

1、TSP問(wèn)題(TravelingSalesmanProblem)是一個(gè)組合優(yōu)化方面的問(wèn)題，已經(jīng)成為并將繼續(xù)成為測(cè)試組合優(yōu)化混合演化算法的標(biāo)準(zhǔn)問(wèn)題。從理論上講，使用窮舉法不但可以求解TSP問(wèn)題，而且還可以求出該問(wèn)題的最優(yōu)解。但是對(duì)現(xiàn)有的計(jì)算機(jī)來(lái)說(shuō)，使用常規(guī)的窮舉法在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求TSP問(wèn)題近似解的優(yōu)化算法應(yīng)運(yùn)而生了，本文所用到的混合演化算法也在其中。 演化算法是一種模擬自然界自適應(yīng)演化過(guò)

2、程而發(fā)展起來(lái)的通用問(wèn)題求解方法。它采用簡(jiǎn)單的編碼技術(shù)來(lái)表示各種復(fù)雜的結(jié)構(gòu)，并通過(guò)對(duì)編碼進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選擇來(lái)指導(dǎo)學(xué)習(xí)和確定搜索的方向。簡(jiǎn)單的遺產(chǎn)操作和優(yōu)勝劣汰的自然選擇機(jī)制使演化算法具有不受搜索條件的限制、不需要其它輔助信息的特點(diǎn)。它采用的種群搜索模式，有利于搜索到全局最優(yōu)解，能較好的解決解的局部性問(wèn)題。因此，演化算法被廣泛的用來(lái)求解具有挑戰(zhàn)性的問(wèn)題。 這里本文為解決TSP的演化算法提出了一種新的雙近鄰表示法，

3、因?yàn)閭鹘y(tǒng)的路徑表示方法是不適合演化過(guò)程處理的。這種能夠?qū)⒚總€(gè)路徑唯一表示的新的方法提高了演化算子的繼承能力。這種表示法的性質(zhì)和操作，構(gòu)成了新的混合演化算法的參數(shù)和演化算子。然后為了提高收斂速度，演化算法混合了局部?jī)?yōu)化算法。 局部?jī)?yōu)化算法是常用的解決TSP問(wèn)題的算法，也常是其它方法的一個(gè)部分。它具有非常高的運(yùn)行效率。不同的局部?jī)?yōu)化算子的性能也在文中做了分析。本文提出的混合局部?jī)?yōu)化算法，雖然是混合演化算法的一個(gè)部分，但它也能獨(dú)立的解