基于非合作博弈模型的量子蟻群算法

甘泉，王啟明，時合生

基于非合作博弈模型的量子蟻群算法

甘泉，王啟明，時合生

針對量子蟻群算法求解組合優(yōu)化問題時易陷入局部最優(yōu)和收斂速度慢的問題，提出一種基于非合作博弈模型的量子蟻群算法（quantum ant colony algorithm based on non-cooperative game theory，NGQACA），采用重復博弈模型，在重復博弈中產(chǎn)生一個博弈序列，使得每次博弈都能夠產(chǎn)生最大效益，并得到了相應博弈過程的納什均衡。利用三個典型的標準測試函數(shù)對此算法進行實驗測試，實驗結果表明本文基于非合作博弈模型的量子蟻群算法的收斂精度和穩(wěn)定性均要優(yōu)于量子蟻群算法（quantum ant colony algorithm，QACA）和蟻群算法(ant colony algorithm，ACA)。

非合作；博弈論；蟻群算法；位置變異；函數(shù)分析

0 引言

博弈論的最大特點是能夠為相應的博弈過程找到納什均衡點，而納什均衡點也正是策略的最優(yōu)點[1]。非合作博弈經(jīng)常用于分析解決這種問題并且納什均衡解被認為是這種博弈的解[2-3]。即使非合作博弈模型的主要目的是為了最大化所有次級用戶的收益，根據(jù)所有次級用戶采取的均衡解，主用戶的收入也同樣會被最大化[4-7]。針對量子蟻群算法求解問題的不足，根據(jù)博弈論的思想，本文提出一種基于非合作博弈模型的量子蟻群算法，采用重復博弈模型，在重復博弈中產(chǎn)生一個博弈序列，使得每次博弈都能夠產(chǎn)生最大效益，并得到了相應博弈過程的納什均衡。該算法設計擴大解的搜索空間，改善種群信息結構，避免搜索陷入局部最優(yōu)。并將該算法與目前比較常用的一些算法進行了比較，結果表明該算法具有更好的收斂速度。

1 量子蟻群算法

量子蟻群算法是基于量子計算原理的一種蟻群算法，將量子計算與蟻群算法相結合的量子蟻群算法是一種嶄新的優(yōu)化方法，具有很強的生命力和研究價值[8]。

A.Narayanan&M.Moore在“Quantum-ant algorithm”一文中提出了量子蟻群的概念，并將量子蟻群算法用于求解組合優(yōu)化問題，取得了較好的效果[9]。M．Dorigo曾給出三種不同模型，分別稱之為螞蟻循環(huán)系統(tǒng)（ant-cyclc system）、螞蟻數(shù)量系統(tǒng)（ant-quantity system）、螞蟻密度系統(tǒng)（ant-density system）[10-15]。它們的差別在于公式的不同，在螞蟻數(shù)量系統(tǒng)模型中如公式（1）：

這3種模型的區(qū)別在于后兩種模型中利用的是局部信息，而前者利用的是全局信息，經(jīng)過實驗對比，在求解問題時螞蟻循環(huán)系統(tǒng)性能較好，因而本文采用它作為基本模型。算法停止條件可以用固定循環(huán)次數(shù)或者當解的變化不明顯時便停止計算。

基本蟻群算法實現(xiàn)步驟如下：

（1）初始化

（2）迭代過程

根據(jù)公式（1）和（2），螞蟻k選擇下一個地點j，將螞蟻k移動到城市j，把城市j置入禁忌列表tabak；

計算所有螞蟻求得的回路距離，根據(jù)公式（1）、（2）更新路徑(i,j)上的信息激素；

（3）輸出結果，結束算法。

2 非合作博弈模型

2.1 非合作博弈模型

為不失一般性，本文以求函數(shù)的最小值為例，始終成立如公式（3）：

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

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

在NGQACA中，采用編碼方案如公式（4）：

qi0為|0＞態(tài)位置,qi1為|1＞態(tài)位置。

3 位置變異處理

3.1 螞蟻位置變異處理

本文基于博弈模型的改進算法使用一種通過量子非門設計的變異操作，具體步驟如下：（1）以概率Qm從量子螞蟻種群中選取若干個個體；（2）對選中的量子螞蟻個體按概率Pm確定一個或多個變異位；

（3）對選中位量子比特的幾率執(zhí)行量子非門操作。3.2最優(yōu)位置更新規(guī)則

設螞蟻Pi當前搜索到的最優(yōu)位置如公式（7）：

整個種群目前搜索到的最優(yōu)位置如公式（8）：

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

（1）螞蟻Pi上量子位幅角增量的更新如公式（9）：

（2）螞蟻上量子位概率幅的更新如公式（10）：

螞蟻Pi更新后的兩個新位置如公式（11）、（12）：

4 仿真實驗結果與分析

為驗證本文算法的有效性以及可行性，本文利用3個典型的標準測試函數(shù)對NGQACA算法尋優(yōu)性能進行測試。對每個測試函數(shù)分別進行測試；測試函數(shù)（1）主要測試算法陷入局部最優(yōu)的問題。實驗采用測試函數(shù)（2）Rosenbrock函數(shù)以及測試函數(shù)（3）Bohachevsky函數(shù)進行優(yōu)化，尋找函數(shù)極值來測試算法在時間上的優(yōu)越性[16-18]。

測試函數(shù)（1）

測試函數(shù)（2）Rosenbrock函數(shù)：

首先對測試函數(shù)進行測試，將GQACA測試結果與文獻[5]中報道的NQACA和基準的ACA的結果進行比較。進化曲線如圖1，圖2所示：

圖1 函數(shù)f(1)的尋優(yōu)曲線（迭代200）

圖2 函數(shù)f(1)的尋優(yōu)曲線（迭代500）

從圖表中列出結果可以看出，本文NGQACA算法的收斂精度和穩(wěn)定性均要優(yōu)于QACA算法和ACA算法,并且能較好的避免陷入局部最優(yōu)。

Rosenbrock函數(shù)存在2個極大值點3897.7342和3905.9262，Bohachevsky函數(shù)有多個局部極大值，全局極大值為0.24003441。兩種算法個體數(shù)量均為40，最大迭代次數(shù)200，實驗次數(shù)50，優(yōu)化結果如表1所示：

表1 三種算法優(yōu)化結果比較

由此可見GQACA明顯優(yōu)于QACA以及ACA。

5 總結

提出一種新的基于博弈論的量子蟻群算法。采用重復博弈模型，在重復博弈中存在一個博弈序列，每次博弈都能夠產(chǎn)生最大效益。并得到了相應博弈過程的納什均衡。利用典型的標準測試函數(shù)對NGQACA算法尋優(yōu)性能進行測試。實驗結果表明本文NGQACA算法的收斂精度和穩(wěn)定性均要優(yōu)于QACA算法和ACA算法。

[1]P.Li and S.Li,"Quantum ant colony algorithm for continuous space optimization,"[J].Control Theory and Applications,2008,25(2):237-241.

[2]P.C.Li and H.Y.Wang,"Quantum Ant Colony Optimization Algorithm Based on Bloch Spherical Search,"[J].Neural Network World,2012,22(4):325-341.

[3]袁浩.基于量子蟻群算法的粗糙集屬性約簡方法[J].計算機工程與科學,2010,32(5):82-84.

[4]P.Li,K.Song,and E.Yang,"Quantum ant colony optimization with application,"2010 Sixth International Conference on Natural Computation[C].(ICNC),2010:2989-2993.

[5]W.Honggang,M.Liang,Z.Huizhen,etal. Quantum-inspired ant algorithm for knapsack problems [J].Journal of Systems Engineering and Electronics,2009,20(5):1012-1016.

[6]許波.彭志平,余建平,等.基于蛙跳思想的量子編碼遺傳算法[J].中國工程科學,2014,16(3):113-117.

[7]沈鵬.物流配送路徑優(yōu)化問題求解的量子蟻群算法[J].計算機工程與應用,2013,49(21):56-59.

[8]賈瑞玉,李亞龍,管玉勇.求解旅行商問題的混合量子蟻群算法[J].計算機工程與應用,2013,49(22):36-39.

[9]何小鋒,馬良.求解0-1背包問題的量子蟻群算法[J].計算機工程與應用,2011,47(16):29-31.

[10]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.

[11]田有亮,馬建峰,彭長根,等.秘密共享體制的博弈論分析[J].電子學報,2011,39(12):2790-2795

[12]曾曉麗,胡偉,曹海,等.基于博弈論的多媒體傳感器網(wǎng)絡MAC協(xié)議[J].計算機工程,2013,39(6):103-106.

[13]劉玉嶺,馮登國,吳麗輝,等.基于靜態(tài)貝葉斯博弈的蠕蟲攻防策略績效評估[J].軟件學報,2012,23(3):712-723.

[14]Dorigo.M．Optimization,learning and natural algorithms [D].Ph.D.Thesis,Department of Electronics,Politecnico di Milano,Italy,1992.

[15]Maniezzo V,Dorigo M,Colorni A.．The ant system：optimization by a colony of cooperating agents[J]．IEEE Transactions on Systems，Man，and Cybernetics-Part B.1996,26(1):29-41.

[16]Diosan L,Oltean M..What Else is the Evolution of PSO Telling Us[J].Journal of Artificial Evolution and Applications,2008,8(2):1-12.

Quantum Ant Colony Algorithm Based on Non-cooperative Game Theory

Gan Quan,Wang Qiming,Shi Hesheng
(School of Computer Science and Technology Department,Pingdingshan University,Pingdingshan 467002,China)

Quantum ant colony algorithm is easy to fall into the situation of local optimum and slow convergence rate when solving combinatorial optimization problem.This paper puts forward a quantum ant colony algorithm based on non-cooperative game theory(NGQACA).Adopted in this algorithm,the repeated game model can produce a game sequence to make every game produce maximum benefit,and then it can get the corresponding game process of Nash equilibrium.The there typical test functions are used for testing the performance of NGQACA algorithm optimization.The experimental results show that the convergence precision and stability of NGQACA are better than QACA and ACA algorithm.

Non-cooperative;Game Theory;Ant ColonyAlgorithm;Position Variation FunctionAnalysis

TP393

A

1007-757X(2015)06-0026-03

2015.03.04）

甘 泉（1980-），男，安徽省靈璧縣，平頂山學院，計算機科學與技術學院，講師，碩士，研究方向：算法分析，平頂山，467000

王啟明（1980-），男，魯山人，平頂山學院，計算機科學與技術學院，講師，碩士，研究方向：軟件工程算法，平頂山，467000

時合生（1977-），男，郾城縣人，平頂山學院，計算機科學與技術學院，講師，碩士，研究方向：計算機軟件與理論，平頂山，467000