論文關(guān)鍵詞：旅行商問題 遺傳算法 基因庫 多重搜索策略
論文摘要：TSP是組合優(yōu)化問題的典型代表,該文在分析了遺傳算法的特點(diǎn)后,提出了一種新的遺傳算法(GB—MGA),該算法將基因庫和多重搜索策略結(jié)合起來,利用基因庫指導(dǎo)單親遺傳演化的進(jìn)化方向,在多重搜索策略的基礎(chǔ)上利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通過對(duì)國際TSP庫中多個(gè)實(shí)例的測(cè)試,結(jié)果表明:算法(GB—MGA)加快了遺傳算法的收斂速度,也加強(qiáng)了算法的尋優(yōu)能力。
TSP(traveling salesman problem)可以簡述為:有n個(gè)城市1,2,…,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時(shí)間不受限制的話,在理論上這種問題終會(huì)找到最優(yōu)解,但對(duì)于稍大規(guī)模的TSP,時(shí)間上的代價(jià)往往是無法接受的。這是一個(gè)典型的組合最優(yōu)化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項(xiàng)式時(shí)間內(nèi)求到問題的解[1]。由于TSP在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運(yùn)輸、加工調(diào)度、網(wǎng)絡(luò)通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對(duì)它進(jìn)行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法、螞蟻算法、模擬退火算法、遺傳算法等。
遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)化搜索算法,其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換,搜索不依賴于梯度信息。遺傳算法主要包括選擇、交叉和變異3個(gè)操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。遺傳算法雖然不能保證在有限的時(shí)間內(nèi)獲得最優(yōu)解,但隨機(jī)地選擇充分多個(gè)解驗(yàn)證后,錯(cuò)誤的概率會(huì)降到可以接受的程度。
用遺傳算法求解TSP能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會(huì)陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時(shí)間內(nèi)計(jì)算出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文中楊輝提出的基因庫的想法,并結(jié)合文中Cheng-Fa Tsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來求解TSP問題。該文根據(jù)文中最小生成樹MST(minimum cost spanning tree)的應(yīng)用,由MST建立TSP的基因庫,保存有希望成為最優(yōu)解的邊,利用基因庫提高初始群體的質(zhì)量進(jìn)行單親演化,然后利用改進(jìn)后的交叉算子和的多重搜
