遺傳算法在TSP上的應(yīng)用及改進(jìn).pdf

1、旅行商問題(TSP)是著名的NP完全難題，也是組合優(yōu)化、計(jì)算機(jī)科學(xué)界經(jīng)典的問題之一。因此對(duì)TSP尋找出實(shí)際而又有效的算法，就具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。而遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，具有簡(jiǎn)單、通用、穩(wěn)健等特性，能依概率收斂到問題的全局最優(yōu)解。這就是本文提出的改進(jìn)遺傳算法求解TSP的目的和意義。 本文從旅行商問題的概述出發(fā)，介紹了TSP的數(shù)學(xué)描述與分類，在原有的基礎(chǔ)上，對(duì)TSP作了更細(xì)致的

2、分類；介紹了遺傳算法的基本概念、原理、步驟及意義，將遺傳算法的一些主要的操作過程用數(shù)學(xué)形式表示，使其變得簡(jiǎn)單而又公式化；通過依賴于遺傳操作的基本遺傳機(jī)理的敘述，為以后算法的改進(jìn)打下理論基礎(chǔ)。本文主要工作如下： (1)分析了影響遺傳算法性能的一些重要參數(shù)，通過基本遺傳算法(SGA)對(duì)不同種群規(guī)模的TSP問題分別進(jìn)行計(jì)算機(jī)模擬仿真，討論了基本遺傳算法在求解TSP中存在的不足。 (2)針對(duì)現(xiàn)有的遺傳算法的不足和TSP本身的特點(diǎn)

3、，提出了三種改進(jìn)的混合遺傳算法(HGA)。 首先提出了混合遺傳算法Ⅰ(HGAⅠ)，在HGAⅠ中采用了依概率近鄰法，用其生成的初始種群優(yōu)于隨機(jī)產(chǎn)生初始種群，較近鄰法略差，但個(gè)體多樣性水平優(yōu)于近鄰法，而且生成的初始種群的隨機(jī)路徑的總長(zhǎng)度服從正態(tài)分布。將依概率的近鄰法和邊重組交叉算子與啟發(fā)式變異算子結(jié)合起來(lái)得到HGAⅠ。 其次為了進(jìn)一步改進(jìn)其性能，保證算法的全局收斂性，混合遺傳算法Ⅱ(HGAⅡ)應(yīng)用改良圈算法及最大容許停滯代數(shù)

4、，不僅避免了HGAⅠ中終止進(jìn)化代數(shù)的選取問題，而且大大加快了算法的收斂速度，使算法具有很好的魯棒性。同時(shí)在HGAⅡ中采取杰出者記錄與“父子混合”選擇策略以及隨機(jī)因素控制參數(shù)α，從理論上保證了算法的全局收斂性。 最后在混合遺傳算法Ⅲ(HGAⅢ)中引入多元回歸分析中的三均值的概念對(duì)遺傳算法的控制參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整，從而克服用不變的控制參數(shù)來(lái)控制遺傳進(jìn)化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。 (3)