基于改進(jìn)量子蟻群算法的TSP求解問題研究

王啟明，李瑋瑤

（平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467000）

基于改進(jìn)量子蟻群算法的TSP求解問題研究

王啟明，李瑋瑤

（平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467000）

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

改進(jìn)；博弈論；蟻群算法；旅行商問題

1 引 言

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

2 博弈論概念簡介

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

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

由以上理論，進(jìn)行如下定義：

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

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

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

3.1 非合作博弈模型

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

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

3.2 初始種群產(chǎn)生

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

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

qi0為｜0＞態(tài)位置，qi1為｜1＞態(tài)位置。

3.3 螞蟻位置變異處理

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

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

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

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

3.4 最優(yōu)位置更新規(guī)則

設(shè)螞蟻Pi當(dāng)前搜索到的最優(yōu)位置為：

整個種群目前搜索到的最優(yōu)位置為：

位置狀態(tài)更新規(guī)則描述為：

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

其中

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

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

4 仿真實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文算法的有效性以及可行性，本文利用3個典型的標(biāo)準(zhǔn)測試函數(shù)對GQACA算法尋優(yōu)性能進(jìn)行測試。應(yīng)用于TSP問題求解；測試函數(shù)（15）主要測試算法陷入局部最優(yōu)的問題。實(shí)驗(yàn)采用測試函數(shù)（16）Rosenbroc函數(shù)以及測試函數(shù)（17）Bohachevsky函數(shù)進(jìn)行優(yōu)化［9-11］，尋找函數(shù)極值來測試算法在時間上的優(yōu)越性。

測試函數(shù)（15）

其中x∈［－500，500］；

測試函數(shù)（16）Rosenbroc函數(shù)：

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

測試函數(shù)（17）Bohachevsky函數(shù)：首先對測試函數(shù)進(jìn)行測試，將GQACA測試結(jié)果與QACA和基準(zhǔn)的ACA的結(jié)果進(jìn)行比較。得到三種比較結(jié)果如表1所示。

表1 三種算法優(yōu)化結(jié)果比較Tab.1 Optimization results of three algorithms

5 結(jié)束語

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

［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］ 劉玉嶺，馮登國，吳麗輝，等.基于靜態(tài)貝葉斯博弈的蠕蟲攻防策略績效評估［J］.軟件學(xué)報，2012，23（3）：712-723.

Liu Yuling，F(xiàn)eng 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.基于博弈論的信息安全技術(shù)評價模型［J］.計(jì)算機(jī)學(xué)報，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］.系統(tǒng)工程理論與實(shí)踐，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-），男，河南魯山人，碩士研究生，講師，主研方向：軟件工程算法和物聯(lián)網(wǎng)。

2014-11-18