指針網絡改進遺傳算法求解旅行商問題

關鍵詞：指針網絡;遺傳算法;旅行商問題

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

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

1旅行商問題概述

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

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

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

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

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

3指針網絡改進遺傳算法求解旅行商問題的方法

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

4基于指針網絡改進遺傳算法應用的流程

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

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

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

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

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

5結語

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

作者簡介：

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