雙編碼改進遺傳算法求解旅行商問題

王 玉，譚代倫

(西華師范大學數學與信息學院，四川 南充 637009)

0 引言

旅行商問題(Traveling Salesman Problem，TSP)是一個經典的組合優化問題，其求解難度被證明是NP難問題[1]。在現實生活中，TSP問題廣泛應用于貨物零件加工順序[2]、汽配件噴涂順序[3]、倉儲系統揀貨路徑規劃[4]、光伏板清潔[5]等領域。

TSP問題于1959年被Dantzing等人提出[6]，被國內外眾多專家學者研究，并用于測試算法效率[7]，目前已有大量研究成果。早期，求解TSP問題主要是精確型算法，如P.M.E.Shutler[8]基于分支定界算法思想，提出新的分支規則，將次梯度優化計算的最小生成樹的標準下界作為算法下界，再從另一個角度去考慮最后幾棵樹的大部分邊，使決策樹的節點數增長冪為2，減少了解決TSP問題所需要的決策節點總數，降低了問題的復雜度。G.Carpaneto[9]基于子路徑巡回消除方法，從三個方面對分支定界算法進行了改進，提出了一種廣度優先分支定界算法，促進了成本矩陣的更新，加快了運算速度。精確算法的研究具有很強的理論意義，但只適用于求解小規模TSP問題。

自20世紀80年代以來，基于啟發式規則的智能優化算法[10]興起并被快速應用于求解TSP問題，如遺傳算法[11-12]、模擬退火算法[13]、蜂群算法[14]、蟻群算法[15]、螢火蟲算法[16]、粒子群算法[17]等，它們普遍具有快速搜索和求解能力，對規模更大的TSP問題也有明顯效果。其中，以達爾文進化論、孟德爾遺傳變異理論、模式理論為基礎的遺傳算法[18]逐漸受到重視，它是一種自適應全局優化的概率搜索算法，具有較強的魯棒性、并行性，容易與其他算法結合等優點，但也存在交叉算子不易操作、容易過早收斂而陷入局部最優、收斂速度慢等缺點。……