指針網(wǎng)絡(luò)改進(jìn)遺傳算法求解旅行商問(wèn)題

關(guān)鍵詞：指針網(wǎng)絡(luò);遺傳算法;旅行商問(wèn)題

中圖法分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

遺傳算法作為一種最優(yōu)化算法，其主要通過(guò)模擬自然界物種的進(jìn)化過(guò)程和規(guī)律，并根據(jù)模擬物種進(jìn)化的過(guò)程實(shí)現(xiàn)基因的交叉互換和變異等過(guò)程，最終生產(chǎn)新的個(gè)體甚至種群。從理論上看，遺傳算法的持續(xù)優(yōu)化會(huì)使下一代個(gè)體或者種群的性能明顯優(yōu)于上一代。但從現(xiàn)實(shí)情況看，受種群基因質(zhì)量的影響，通過(guò)遺傳算法生成的個(gè)體或者種群在質(zhì)量上并不完全是直線上升的。換言之，遺傳算法會(huì)受其他因素的影響而出現(xiàn)性能和尋優(yōu)速度下降的情況。因此，需要根據(jù)情況對(duì)遺傳算法進(jìn)行改進(jìn)。指針網(wǎng)絡(luò)作為一種能從離散輸入序列中獲取輸出序列條件概論的神經(jīng)網(wǎng)絡(luò)，在改進(jìn)遺傳算法中的種群因素、提高預(yù)測(cè)的準(zhǔn)確度等方面具有明顯的效果。本文重點(diǎn)以求解旅行商問(wèn)題為載體，對(duì)指針網(wǎng)絡(luò)改進(jìn)遺傳算法進(jìn)行相應(yīng)的研究。

1旅行商問(wèn)題概述

旅行商問(wèn)題是涉及計(jì)算機(jī)科學(xué)、工程學(xué)、數(shù)學(xué)、運(yùn)籌學(xué)等諸多學(xué)科的一項(xiàng)基礎(chǔ)性問(wèn)題。該問(wèn)題是指一位旅行商需要到n個(gè)城市去推銷(xiāo)自己的產(chǎn)品，要求從某一城市出發(fā)，經(jīng)過(guò)n-1個(gè)城市，并且經(jīng)過(guò)這些城市的次數(shù)只能是一次，最后再回到出發(fā)城市，要求解的問(wèn)題是旅行商的最短路程。

關(guān)于求解旅行商問(wèn)題，通常情況是將旅行商的最短路徑作為目標(biāo)函數(shù)，將除出發(fā)城市外，其余n-1個(gè)城市必須經(jīng)過(guò)且只能經(jīng)過(guò)一次作為約束條件。在現(xiàn)實(shí)生活和社會(huì)發(fā)展中，類(lèi)似旅行商問(wèn)題的情況比較常見(jiàn)，這也使得關(guān)于這一典型問(wèn)題的研究成為各類(lèi)算法研究與應(yīng)用中重點(diǎn)關(guān)注和探索解決的問(wèn)題。

2遺傳算法求解旅行商問(wèn)題的方法

傳統(tǒng)基于遺傳算法求解旅行商問(wèn)題的流程如圖1所示。從原理上看，遺傳算法是在模擬達(dá)爾文的遺傳選擇和自然淘汰規(guī)則的基礎(chǔ)上產(chǎn)生的生物進(jìn)化過(guò)程計(jì)算模型，其是一種通過(guò)模擬自然進(jìn)化的過(guò)程來(lái)探索確定最優(yōu)解的方法。在一般的算法應(yīng)用中，遺傳算法的實(shí)現(xiàn)主要包括城市生成模塊、地圖選擇模塊、參數(shù)設(shè)置模塊、交叉算子選擇模塊、變異算子選擇模塊、具體輸出信息顯示模塊。其中，城市生成模塊主要是生成旅行商問(wèn)題中涉及的城市數(shù)量和城市名稱或者代碼;地圖選擇模塊是根據(jù)問(wèn)題研究的需要，選擇不同的地圖，并對(duì)各個(gè)城市在地圖上的分布情況進(jìn)行確定。目前使用得比較多的地圖是基于直角坐標(biāo)系的地圖和圓形地圖;參數(shù)設(shè)置模塊是用戶根據(jù)具體的研究情況，設(shè)置遺傳算法應(yīng)用中的相關(guān)參數(shù)，這些參數(shù)主要包括交叉率、變異率、種群大小、世代數(shù)、進(jìn)化設(shè)置等;交叉算子選擇模塊主要是用戶根據(jù)研究的需要，選擇相應(yīng)的交叉算法;變異算子選擇模塊主要是在基于次序的變異、基于位置的變異和倒位變異這三種變異實(shí)現(xiàn)方式中進(jìn)行選擇;具體輸出信息限制模塊是為了使程序運(yùn)行時(shí)具體算法和各種數(shù)據(jù)信息能夠更明晰地顯示出來(lái)而設(shè)置的輸出方式，一般顯示的信息主要有計(jì)算結(jié)果、算法運(yùn)行時(shí)間、所選遺傳算子等。

雖然遺傳算法能夠達(dá)到取得最優(yōu)值或者次優(yōu)質(zhì)的預(yù)期目的，但由于該算法容易受種群等情況的影響而出現(xiàn)陷入局部最優(yōu)和收斂速度慢等問(wèn)題，最終可能會(huì)影響旅行商問(wèn)題求解的效果。

3指針網(wǎng)絡(luò)改進(jìn)遺傳算法求解旅行商問(wèn)題的方法

基于指針網(wǎng)絡(luò)改進(jìn)遺傳算法求解旅行商問(wèn)題，是將指針網(wǎng)絡(luò)引入遺傳算法中的初始種群的改造，使遺傳算法能夠更準(zhǔn)確地學(xué)習(xí)組織優(yōu)化問(wèn)題的組合規(guī)則。在此次研究中，主要將指針網(wǎng)絡(luò)應(yīng)用到遺傳算法的初始化方案中，以此改善遺傳算法的初始種群構(gòu)造，提高整個(gè)算法的性能。

4基于指針網(wǎng)絡(luò)改進(jìn)遺傳算法應(yīng)用的流程

圖2展示的是基于指針網(wǎng)絡(luò)改進(jìn)遺傳算法的具體應(yīng)用流程。通過(guò)該圖可以看出，改進(jìn)后的遺傳算法主要包括四個(gè)重要的步驟———即生成高質(zhì)量初始種群、形成新初始種群、改進(jìn)初始種群構(gòu)造結(jié)構(gòu)和進(jìn)行自適應(yīng)處理。其中，改進(jìn)初始種群構(gòu)造結(jié)構(gòu)是指針網(wǎng)絡(luò)應(yīng)用的關(guān)鍵，在該環(huán)節(jié)，主要包括最優(yōu)子代融合和基于漢明距離輪盤(pán)賭進(jìn)行初始種群結(jié)構(gòu)優(yōu)化。

在最優(yōu)子代融合中，通過(guò)圖2可以看出，需要首先生成初始種群S和指針網(wǎng)絡(luò)解集T，然后對(duì)S和T分別進(jìn)行個(gè)體適應(yīng)度的計(jì)算，保留優(yōu)良的個(gè)體，最后對(duì)S和T分別取適應(yīng)度最高的子集加入新解集中。

在將適應(yīng)度最高的子集加入新解集中時(shí)，可以按照特定的權(quán)重進(jìn)行處理，以保證最大程度保留指針網(wǎng)絡(luò)解集T中的個(gè)體的優(yōu)勢(shì)。

在基于漢明距離輪盤(pán)賭的過(guò)程中，主要使用漢明距離來(lái)測(cè)量個(gè)體之間的差異，其根據(jù)兩個(gè)長(zhǎng)度相等的字符串中，對(duì)應(yīng)位置不相同的個(gè)數(shù)來(lái)確定距離值。在此次求解旅行商問(wèn)題中，假設(shè)兩個(gè)個(gè)體X₁和X₂之間的韓明距離為rH（X₁，X₂）。需要注意的是，為掌握種群之間的多樣性，需要對(duì)種群中每個(gè)個(gè)體之間的漢明距離進(jìn)行計(jì)算，最后計(jì)算中種群的平均漢明距離，其計(jì)算公式如下。

在按照上述公式計(jì)算出漢明距離后，即可將剩余個(gè)體中距離最短的個(gè)體加入初始解集中。

5結(jié)語(yǔ)

旅行商問(wèn)題作為一項(xiàng)經(jīng)典的算法問(wèn)題，其在現(xiàn)實(shí)生活中的行為決策方面具有普遍的代表性。由于基于傳統(tǒng)遺傳算法在求解旅行商問(wèn)題方面存在缺陷和不足，本次研究提出了基于指針網(wǎng)絡(luò)改進(jìn)遺傳算法的思路，并以求解旅行商問(wèn)題為案例進(jìn)行了研究。最終的研究結(jié)果表明，在求解旅行商問(wèn)題中，指針網(wǎng)絡(luò)能夠在中低規(guī)模的旅行商模擬數(shù)據(jù)中獲得高準(zhǔn)確度的結(jié)果。并且，基于指針網(wǎng)絡(luò)改進(jìn)的遺傳算法可以顯著提高求解的質(zhì)量和收率速度，這較同類(lèi)型的初始化方法具有更明顯的特點(diǎn)和優(yōu)勢(shì)。因此，可以確定的是基于指針網(wǎng)絡(luò)改進(jìn)的遺傳算法在求解旅行商問(wèn)題方面的效果突出。

作者簡(jiǎn)介：

沈滌（1973—），碩士，工程師，研究方向：人工智能、多媒體、GIS。