文/靳博文

TSP問題是一個備受研究者們關(guān)注的NP難題，遺傳算法作為應(yīng)用較為普遍的智能優(yōu)化算法，是求解TSP問題的有效方法。本論文通過改變種群數(shù)量、交叉概率、變異概率、城市數(shù)量等參數(shù)，對比運(yùn)行結(jié)果后分析得出這些參數(shù)設(shè)置的最優(yōu)區(qū)間，為遺傳算法解決TSP問題提供參考。

1.概述

在數(shù)學(xué)領(lǐng)域中，TSP問題被學(xué)者們視作是一個典型的組合優(yōu)化問題[1]。該問題在生活中非常常見，很多發(fā)生在我們身邊問題就是TSP問題模型在現(xiàn)實生活中的應(yīng)用[2-4]。因此，研究TSP問題不僅具有很大的理論意義，也具有相當(dāng)高的實際價值。當(dāng)城市數(shù)量較少時，TSP問題很容易得到解決，然而在現(xiàn)實的問題中，“城市數(shù)量”往往很多，這使得該問題的解決難度大大增加。目前，在求解大規(guī)模TSP問題時，通常使用智能優(yōu)化算法。本文主要聚焦遺傳算法，分析不同參數(shù)設(shè)置對求解TSP問題的影響。

2.遺傳算法

遺傳算法起源于人類對生物系統(tǒng)的觀察，用計算機(jī)來模擬生物遺傳進(jìn)化的規(guī)律進(jìn)行迭代，是由Michigan大學(xué)的約翰·霍蘭德(J·Holland)教授于1975年首先提出來的。按照自然界適者生存的法則，種群越優(yōu)秀的個體越有更高的概率遺傳自己的基因。每個個體的染色體通過選擇、交叉和變異等過程產(chǎn)生新的更優(yōu)的染色體，從而使得種群得到優(yōu)化，這也意味著得到的解越來越優(yōu)，種群通過這樣的規(guī)則進(jìn)行迭代優(yōu)化，直到最終得到目標(biāo)問題的最優(yōu)解。遺傳算法是一種全局搜索算法，當(dāng)遺傳算法對構(gòu)建模型進(jìn)行求解時，根據(jù)實際問題的初始解進(jìn)行編碼形成基因串，基因串即染色體經(jīng)過選擇、交叉、變異后形成新的染色體，新形成的染色體比之前的染色體更接近最優(yōu)解。再經(jīng)過不斷的迭代，一直得到最優(yōu)解，遺傳算法的主要步驟是編碼解碼、確定初始種群、確定適應(yīng)度函數(shù)、選擇、交叉和變異。

圖1 遺傳算法流程

3.算例仿真

為了研究只改變種群參數(shù)、交叉概率、變異概率、城市數(shù)量時，遺傳算法的不同表現(xiàn)，做算例仿真如下。在城市數(shù)為25，迭代次數(shù)為2000，種群個數(shù)為100，交叉概率為0.8，變異概率為0.05條件下，結(jié)果如下圖所示。結(jié)果圖從左到右，從上到下依次為城市位置分布、初始種群分布、最終路線圖、最小種群路徑隨迭代次數(shù)的變化圖。按照上面的方法，本著控制變量的實驗原則，分別運(yùn)行以上述實驗為基準(zhǔn)其他參數(shù)不變，種群數(shù)量、交叉概率、變異概率、城市數(shù)量由大到小的算例仿真，并對運(yùn)行結(jié)果進(jìn)行比較。

圖2 運(yùn)行結(jié)果圖

4.結(jié)論

通過上述算例分析，可得出結(jié)論如下：（1）在種群數(shù)量改變時，隨著種群數(shù)量的增加，路徑總長度達(dá)到收斂的迭代次數(shù)，即達(dá)到最優(yōu)解的迭代次數(shù)和最短距離，即最優(yōu)解的值，變化趨勢均是先下降后上升。這也意味著種群數(shù)量大小與收斂速度相關(guān)，當(dāng)種群數(shù)量過大時，收斂速度會相應(yīng)減緩。（2）在交叉概率改變時，隨著交叉概率的增大，達(dá)到最優(yōu)解的迭代次數(shù)和最優(yōu)解的值變動較為頻繁。（3）在變異概率改變時，隨著變異概率的增大，達(dá)到最優(yōu)解的迭代次數(shù)變化趨勢為先增加后減少；最優(yōu)解的值則隨著變異概率的增加而不斷增加。（4）在城市數(shù)量改變時，隨著城市數(shù)量增加達(dá)到最優(yōu)解的迭代次數(shù)不斷增加，并且逐步趨近2000次；最優(yōu)解的值也相應(yīng)增加。當(dāng)城市數(shù)量過大時，遺傳算法在求解TSP問題方面處于劣勢。