基于改進量子蟻群算法的TSP求解問題研究

王啟明，李瑋瑤

（平頂山學院計算機科學與技術學院，平頂山467000）

基于改進量子蟻群算法的TSP求解問題研究

王啟明，李瑋瑤

（平頂山學院計算機科學與技術學院，平頂山467000）

TSP問題是一個組合優化問題，該問題具有NP計算復雜性，運用量子蟻群算法求解該問題時易陷入局部最優和收斂速度慢的問題。因此提出一種基于博弈論的量子蟻群算法（GQACA），該算法采用重復博弈模型，在重復博弈中產生一個博弈序列，使得每次博弈都能夠產生最大效益，并得到相應博弈過程的納什均衡。把該算法應用于TSP求解，實驗結果表明本文中GQACA算法的收斂精度和穩定性均要優于其他量子蟻群算法。

改進；博弈論；蟻群算法；旅行商問題

1 引 言

旅行商問題，即TSP問題（Travelling Salesman Problem），又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一［1-2］。可以描述為：已知n個城市之間的相互距離，現有一推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發的城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？解決旅行商問題的各種優化算法，都是通過犧牲解的精確性來換取較少的耗時［3］。其他一些啟發式的搜索算法則依賴于特定的問題域，缺乏通用性。相比較而言，遺傳算法是一種通用性很好的全局搜索算法，因此遺傳算法是解決旅行商問題的一種不錯的算法。賈瑞玉等分析了量子蟻群算法的優缺點，提出一種新的求解旅行商問題（Traveling Salesman Problem，TSP）的混合量子蟻群算法［4-5］。博弈論的最大特點是能夠為相應的博弈過程找到納什均衡點，而納什均衡點也正是策略的最優點［6］。該算法設計擴大解的搜索空間，改善種群信息結構，避免搜索陷入局部最優。并將該算法與目前比較常用的一些算法進行了比較，結果表明該算法具有更好的收斂速度［7-8］。

2 博弈論概念簡介

博弈論是研究決策主體在給定信息結構下如何決策以最大化自己的效用［8］。博弈由3個基本要素組成，即局中人、策略集、效用。一般的，非合作策略式博弈由三種要素組成：博弈的參與者集合，i∈N，N＝1，2，...，n；參與者的策略空間，pi，i＝1，2，...，n；每個參與者的支付函數，ui（p1，p2，...，pn），i＝1，2，...，n。博弈的策略可以表述為：

納什均衡是指在某一策略組合中，所有的參與者面臨這樣一種情況，當其他人不改變策略時，他此時的策略是最優的。即在策略式博弈G＝｛p1，p2，...，pn；u1，u2，...，un｝中，如果對任何其他參與人的策略組合p－i，參與人i的策略是嚴格最優選擇，即：

由以上理論，進行如下定義：

εi被稱為參與者i的占優策略。這里公式（3）中的εi（p－i）＝εi（p）。定義E（p）＝［εi（p－1），εi（p－2），...，εn（p－n）］T為整個博弈的最優策略集合。最優策略集合與納什均衡是一致的。所以策略E（p）是一個純策略納什均衡。此時對每個參與者都滿足：

每一個理性的參與者都不會有單獨改變策略的沖動。

3 基于博弈論的量子編碼蟻群算法（GQACA）

3.1 非合作博弈模型

為不失一般性，本文以求函數的最小值為例，下式始終成立。

其中t為迭代次數，F為最優值函數。非合作博弈理論中，參與者只根據他們可察覺的自我利益（perceived self-interest）來決策。參與者之間的威脅、協議、許諾之類，是無法實施的，即便參與者在博弈中可以相互溝通。除了那些博弈規則確實允許的協議外，參與者無法達成有約束力的協議。對于一個兩只螞蟻博弈模型而言，分別用“1”和“2”代替兩個博弈方，當“1”首先進行策略選擇時，它會選擇使自己的收益盡可能大的策略，然后“2”可根據自身收益來考慮是接受還是拒絕由“1”提出的策略，如果“2”不受益，就不接受，如果“2”受益，就接受，并且自動獲得下一輪的優先選擇權。

3.2 初始種群產生

在GQACA中，采用如下編碼方案

其中θij＝2π×rnd；（i，j＝1，2，...，m），m是種群規模，n是空間維數，rnd為（0，1）之間的隨機數，這兩個位置分別對應量子態｜0＞和｜1＞的概率幅。

qi0為｜0＞態位置，qi1為｜1＞態位置。

3.3 螞蟻位置變異處理

基于博弈模型的改進算法使用一種通過量子非門設計的變異操作，具體步驟如下：

（1）以概率Qm從量子螞蟻種群中選取若干個個體；

（2）對選中的量子螞蟻個體按概率Pm確定一個或多個變異位；

（3）對選中位量子比特的幾率執行量子非門操作。

3.4 最優位置更新規則

設螞蟻Pi當前搜索到的最優位置為：

整個種群目前搜索到的最優位置為：

位置狀態更新規則描述為：

（1）螞蟻Pi上量子位角增量的更新

其中

（2）螞蟻Pi上量子位概率幅的更新

螞蟻Pi更新后的兩個新位置為：

4 仿真實驗結果與分析

為驗證本文算法的有效性以及可行性，本文利用3個典型的標準測試函數對GQACA算法尋優性能進行測試。應用于TSP問題求解；測試函數（15）主要測試算法陷入局部最優的問題。實驗采用測試函數（16）Rosenbroc函數以及測試函數（17）Bohachevsky函數進行優化［9-11］，尋找函數極值來測試算法在時間上的優越性。

測試函數（15）

其中x∈［－500，500］；

測試函數（16）Rosenbroc函數：

其中（－2.048≤xi≤2.048，i＝1，2）

測試函數（17）Bohachevsky函數：首先對測試函數進行測試，將GQACA測試結果與QACA和基準的ACA的結果進行比較。得到三種比較結果如表1所示。

表1 三種算法優化結果比較Tab.1 Optimization results of three algorithms

5 結束語

主要從解決TSP問題的收斂精度和穩定性角度出發，分別介紹了博弈論的概念和基于博弈論的量子蟻群算法的實現方法，并利用三個典型函數對GQACA算法進行性能測試。結果表明，該模型不僅能夠模擬生物種群的自然進化，而且能夠模擬生物種群進化過程中的文化進化，從而體現文化進化對自然進化的指導作用及其加速自然進化的重要意義，算法的收斂精度和穩定性均要優于其他算法。

［1］ Colorni A，Dorigo M，Maniezzo V.Distributed optimization byant colonies［C］.Proceedings of 1st European Conference of Ar-tificial Life.Paris：Elsevier Publisher，1991：134-142.

［2］ Dorigo M.Optimization，learning and nature algorithms［D］.Italy：Politecnico diMilano，1992.

［3］ P C Li，H Y Wang，Quantum Ant Colony Optimization Algorithm Based on Bloch Spherical Search［J］.Neural Network World，2012，22（4）：325-341.

［4］ P Li，K Song，E Yang.Quantum ant colony optimization with application［J］.2010 Sixth International Conference on Natural Computation（ICNC），2010：2989-2993.

［5］ W Honggang，M Liang，Z Huizhen，et al.Quantuminspired ant algorithm for knapsack problems［J］.Journal of Systems Engineering and Electronics，2009，20（5）：1012-1016.

［6］ Chandra Mohan B，Baskaran R.A survey：Ant Colony Optimization based recent research and implementation on several engineering domain［J］.Expert Systems with Applications，2012，39（4）：4618-4627.

［7］ Dorigo M，Gambardella LM.Ant colonies for the traveling sales-man problem［J］.BioSystems，1997，43：73-81.

［8］ Stützle T，Hoos H H.Max-min ant system［J］.Future GenerationComputer Systems，2000，16（8）：889-914.

［9］ 劉玉嶺，馮登國，吳麗輝，等.基于靜態貝葉斯博弈的蠕蟲攻防策略績效評估［J］.軟件學報，2012，23（3）：712-723.

Liu Yuling，Feng Dengguo，Wu Lihui，et al.Bayesian game based on static performance evaluation worm attack and defense strategies［J］.Journal of Software，2012，23（3）：712-723.

［10］ 朱建明，Srinivasan Raghunathan.基于博弈論的信息安全技術評價模型［J］.計算機學報，2009，32（4）：828-834.

Zhu Jianming，Srinivasan Raghunathan.Information security technology evaluationmodel based on game theory［J］.Journal of Computers，2009，32（4）：828-834.

［11］ 高尚.解決旅行商問題的混沌蟻群算法［J］.系統工程理論與實踐，2005，25（9）：100-104.

GAO Shang.Solving Traveling Salesman Problem by Chaos Ant Colony Optimization Algorithm［J］.Systems Engineering-theory＆Practice，2005，25（9）：100-104.

Study of TSP Problem Solving Based on Im proved Quantum Ant Colony Algorithm

Wang Qiming，LiWeiyao
（School of Computer Science and Technology，Pingdingshan University，Pingdingshan 467002，China）

TST，as a combinatorial optimization problem，is solved by Quantum ant colony algorithm which is easy to fall into the local optimum and slow convergence.The quantum ant colony algorithm，based on game theory（GQACA），is put forward in this paper.It uses the repeated game to create the repeated game sequence formaximum benefit in each game，and get the corresponding game process of Nash equilibrium.The typical test functions are used for GQACA algorithm optimization performance experiment testing.The experimental results show that the GQACA convergence precision and stability of the algorithm are better than QACA algorithm and ACA one.

Improved；Game theory；Ant colony optimization；Travelling Salesman Problem

10.3969/j.issn.1002-2279.2015.03.010

TN393

A

1002-2279（2015）03-0031-03

王啟明（1980-），男，河南魯山人，碩士研究生，講師，主研方向：軟件工程算法和物聯網。

2014-11-18