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

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

中圖法分類號：TP301 文獻標識碼：A

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

1旅行商問題概述

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

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

2遺傳算法求解旅行商問題的方法

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

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

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

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

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

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

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

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

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

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

5結(jié)語

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

作者簡介：

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