基于遺傳算法求解TSP問(wèn)題

文/靳博文

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

1.概述

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

2.遺傳算法

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

圖1 遺傳算法流程

3.算例仿真

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

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

4.結(jié)論

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