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

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

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

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

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