混沌優化算法在TSP問題的應用

桂傳志

摘 要：混沌是非線性系統所產生的類似隨機的運動，研究表明混沌序列具有隨機性、遍歷性等特點。由于混沌序列的隨機性、遍歷性等特點，可將其應用在TSP問題的應用上。多數文章產生混沌序列采用Logistic映射，由于Logistic映射所產生的混沌序列很不均勻，該文采用邏輯自映射來產生混沌序列，大大提高了優化運算的時間。

關鍵詞：混沌 優化算法 TSP問題 Logistic映射

中圖分類號：TP18 文獻標識碼：A 文章編號：1674-098X（2016）07（c）-0074-02

TSP問題即旅行商問題，它求解的是旅行者經過N個城市且僅一次并回到原處總的最小行程。該文章通過邏輯自映射所產生的混沌序列來編程求解20個城市的TSP問題，得到了TSP問題的最優解。

自李兵等將混沌序列引入優化算法，成功地解決了優化算法收斂于局部極值的問題，優化算法取得了較大的進展。近年來，利用混沌序列進行優化搜索的研究也取得了一定的成就。為提高搜索效率，張彤等提出變尺度混沌優化算法，通過變尺度不斷地縮小搜索范圍，提高了搜索精度，加快了搜索速度。高鷹等把混沌優化算法思想引入粒子群算法，通過對粒子群進行尋優，從而使粒子群的進化速度加快。文章在前人的研究基礎上，將混沌優化算法應用于解決TSP問題。

1 混沌序列

混沌序列具有遍歷性、隨機性、“規律性”等特點，是對初始值敏感的一種復雜序列。由于混沌序列的遍歷性，使得混沌搜索可以跳出局部最優點，從而達到全局最優點。混沌序列的產生方法有Logestic映射、立方映射、邏輯自映射等方法。其表達式分別如下：

2 不同映射產生的混沌序列比較

對于Logestic映射，對隨機取一初值，，Logestic映射所產生的混沌序列具有很好的遍歷性，但是在用Logestic映射尋優的過程中，因為Logestic映射所產生的混沌序列具有遍歷性不均勻的特點，使得尋優速度比較緩慢。

而立方映射和邏輯自映射所產生的混沌序列也具有很好的遍歷性，立方映射、邏輯自映射所產生的混沌序列的遍歷性要更加均勻，從而使得尋優的速度加快。各種映射所產生的混沌序列如圖1所示。

衡量混沌性質的一個重要指標是李亞普諾夫指數，從李亞普諾夫指數也可以看出Logestic映射的混沌特性較其他映射更不明顯。通過實驗的方法得到各種映射所產生的混沌序列的均勻性是不一樣的，其分布情況見表1。

3 TSP問題概述

TSP問題，即Travelling Salesman Problem，又被稱為推銷員問題，是數學領域中著名的N-P問題之一。假設有一個旅行商要去拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能經過一次而且必須經過一次，并且最后要回到原來出發的城市。路徑的選擇目標是要求得到的路徑路程為所有路徑之中的最小值。

建立TSP問題解決模型的方法很多，文中采用矩陣的方法。在表2的方陣中，ABCDE表示城市名稱，矩陣的值為0表示在旅行時，兩個城市沒有直接經過；矩陣的值為1表示在旅行時，兩個城市直接經過。為保證旅行過程中，每個城市僅經過一次，則要求矩陣的每行每列有且僅有一個1，其余均為0。表示經過的城市路徑為A-E-D-C-B-A。

第二步：選擇兩個混沌序列初值（不相等），即和，其值不相等，且在（-1，1）范圍之內。

第三步：將表示TSP問題的矩陣轉化為單位陣，求出此時的TSP問題的解，將其設為最優解。

第四步：利用邏輯自映射函數產生兩個混沌序列。并將其乘以城市數，然后取整，得到i和j。若i和j相等，重復第四步。

第五步：將表示TSP問題的矩陣的i和j行進行交換操作。

第六步：計算此時的解，如果則。

第七步：達到循環次數，結束；否則，返回第四步。

4 仿真結果

文章采用電腦隨機產生20城市坐標，然后對這20城市進行TSP問題求解。這20城市的其坐標值為：16，65；11，100；68，2；58，10；10，80；28，5；30，38；30，95；98，40；28，16；41，41；71，33；63，21；19，58；8，46；91，26；79，38；29，92；63，63；43，10。

通過仿真，求得結果如圖2，其最短路徑的距離為561.37。

參考文獻

[1] 李兵，蔣慰孫.混沌優化方法及其應用[J].控制理論與應用，1997，14（4）：613-615.

[2] 張彤，王宏偉，王子才.變尺度混沌優化方法及其應用[J].控制與決策，1999，14（3）：285-288.

[3] 高鷹，謝勝利.混沌粒子群優化算法[J].計算機科學，2004， 31（8）：13-15.

[4] 洪蕾.粒子群及人工魚群算法優化研究[J].軟件，2014（8）：83-86.