量子競爭決策算法及其在旅行商問題中的應用

摘 要:提出一種新型優化算法——量子競爭決策算法，在競爭決策的基礎上，將進化博弈論中博弈者不斷學習和調整來提高競爭力的思想引入到優化中，使競爭者具有自進化能力，同時充分利用量子進化計算中量子比特、疊加態等理論，增加競爭群體的多樣性，縮小群體規模。通過對典型的TSP實驗計算和與其他算法比較，均取得了較好的效果，算法具有較強的全局優化能力。

關鍵詞:競爭決策; 進化博弈; 量子進化; 旅行商問題

中圖分類號:TP301.6

文獻標志碼:A

文章編號:1001-3695(2010)02-0586-04

doi:10.3969/j.issn.1001-3695.2010.02.051

Quantum competitive decision algorithm and its application in TSP

LIU Yong1，2，MA Liang1，NING Ai-bing1

(1.School of Management， University of Shanghai for Science Technology， Shanghai 200093， China; 2.Dept. of Fundamental Science Teaching， Yancheng Institute of Technology，Yancheng Jiangsu 224051， China)

Abstract: This paper proposed a novel optimization algorithm—quantum competitive decision algorithm. Based on competition and decision， the algorithm introduced the theory of continuous learning and adjustment to improve the competitiveness in evolutionary game theory into optimization， making competitors possess the ability of self-optimizing. The algorithm made full use of quantum bit， superposition state and other concepts in quantum evolutionary algorithm to increase the diversity of competitors and reduce the population size. Experiments on typical TSP and comparisons with other methods show the new algorithm is more efficient and the algorithm has strong capability of global optimization.

Key words:competition and decision; evolutionary game; quantum evolutionary; TSP

0引言

最優化方法在工程技術、科學研究和經濟管理等諸多領域中有著廣泛的應用，隨著目標問題的復雜性越來越強，對高效的優化技術的需求日益迫切，探尋適合復雜計算的具有智能特征的算法已成為研究熱點。

競爭決策算法是近年來提出的一種新型優化算法，是在分析大自然生物世界特別是人類的各種競爭機制和決策原理的基礎上，利用競爭造就優化和決策左右結果的特性而得出的一種尋優算法，能廣泛用于求解組合優化問題[1~4]。但在優化過程中，競爭者缺少學習和自進化能力，無法實現進化過程中的動態調整更新，同時定義的競爭力函數個數較多，影響算法的求解速度和求解問題的規模。

進化博弈論是博弈論的新發展，是一種博弈學習的動態演化理論，已成功用于生物、經濟等領域。其思想來源于生物進化理論，按照生物在進化過程中生物性狀和行為特征的復制動態的思想，進化博弈論中競爭者在博弈過程中不斷學習和調整策略，提高自身的競爭能力[5]。

基于進化博弈論的思想，將競爭決策和量子進化算法相結合，提出一種新型優化算法——量子競爭決策算法。定義每個競爭者攜帶一組表示當前解信息的量子比特，采用量子旋轉門更新競爭者攜帶的量子比特，實現每個競爭者的學習和策略調整過程，在競爭的同時完成自身的進化;同時將量子計算中量子比特、疊加態等理論與競爭者相結合，增加競爭者的多樣性，縮小競爭群體的規模，

加快算法的收斂速度。

1 算法分析

1.1競爭決策算法

競爭決策算法通過構造一個或多個競爭者參與到對一個或多個資源的競爭過程中，通過優勝劣汰的決策原則使一部分競爭者獲得資源而增加實力，另一部分競爭者失去資源而減弱實力甚至死亡。對競爭決策算法的結果有較大影響的因素有以下幾種:

a)競爭規則。

它是競爭決策算法中競爭者必須要滿足的條件，它包括以下三種條件:

(a) 初始條件，在開始進行競爭時必須滿足的條件。

(b) 競爭條件，在競爭過程中始終必須滿足的條件。

(c) 終止條件，在競爭過程中若滿足該條件就可終止當前的一次競爭決策，此時競爭者各方達到一個競爭平衡狀態，即此時每個競爭者都不能憑自己的實力從競爭對手手中搶占資源。

b)競爭力函數。

該函數代表競爭者對某種資源具有的競爭力，一般來說，競爭力函數大的競爭者占有該資源的可能性要大。

c)決策函數。

該函數起到裁判的作用，它根據每個競爭者競爭力函數值的大小來決定把資源分配給哪一個競爭者，如可將決策函數定義成把某資源分配給對該資源具有最大競爭力的競爭者。

d)初始格局。

它是指在某一輪競爭開始前各個競爭者對資源的占有情況和競爭者的實力情況。

這些因素中的某一個單獨發生變化或者組合發生變化都會對競爭和決策的結果產生較大的影響，對同一個問題來說競爭規則一般只有一個。為了取得較好的效果，可能對同一個問題采用多個競爭力函數、多個決策函數和多個初始格局的組合來實現多輪競爭，最后取競爭和決策效果最好的值作為優化值[1~4]。

1.2量子進化算法

量子進化算法是一種基于量子計算思想的概率進化算法，吸取了量子計算中的量子比特、疊加態等概念，有更好的群體多樣性和優化能力。基本的量子進化計算概念如下:

a)量子位。比特是經典計算和經典信息的基本概念，量子計算與量子信息建立在類似的概念量子比特或量子位的基礎上[6]。量子位或量子比特是量子計算中保存信息的最小單元，一個量子位可能處于|1〉也可能處于|0〉，或者兩種狀態的線性疊加。因此一個量子位可以表示為

|φ〉=α|0〉+β|1〉

其中:α和β分別表示|0〉和|1〉的概率幅，|α|2表示量子位處于|0〉概率，|β|2表示量子位處于|1〉的概率。量子比特的狀態是二維復向量空間中的向量，特殊的|0〉和|1〉狀態稱為計算基態，是構成這個向量空間的一組正交基。|α|2+|β|2=1，因為概率和一定是1，同時從幾何意義上看，是要求量子比特的狀態歸一化到長度1[6]。

b)量子個體。在量子進化算法中，量子個體定義為由量子比特組成的串:

α1β1α2β2……αmβm

m為個體長度，[αi，βi]T為第i個量子位的概率幅(i=1，2，…，m) ，一個長度為m的個體能表示2m個狀態的疊加。如一個三個量子位編碼的量子個體

121212-121232

則表示的個體狀態為

14|000〉+34|001〉-14|010〉-34|011〉+14|100〉+34|101〉-14|110〉-34|111〉

表明狀態|000〉，|001〉，|010〉，|011〉，|100〉，|101〉，|110〉和|111〉 的概率分別為1/16，3/16，1/16，3/16，1/16，3/16，1/16和3/16。這種特性使量子進化計算能以較小的群體規模獲得較好的優化結果。

c)量子門。該量子門的設計有多種形式，但由于概率歸一化的要求，變換矩陣必須滿足酉正矩陣，酉性限制是對量子門的惟一限制。常用的有非門、受控非門、Hadamard門、量子旋轉門等。量子門是實現算法進化操作的執行機構，通過量子門算子使量子比特的概率幅發生變化，推動量子個體向最優解方向演化。

d)測量。它是指根據量子比特的概率幅|β|2來生成二進制解。具體做法為:隨機產生一個[0，1]上的數r，若r<|β|2 ，則對應二進制位取1，否則取0。測量改變量子個體的狀態，從|1〉和|0〉 疊加態坍縮到與測量結果相容的特定狀態。

e)基本流程。量子進化算法采用量子比特編碼，通過測量來生成二進制解，通過量子門更新概率幅。隨著量子位|α|2和|β|2趨向0或1，量子個體收斂到單一狀態，多樣性消失[7~9]。

1.3進化博弈論

進化博弈論是一種博弈學習理論，改變了傳統博弈論中參與者完全理性的假設，認為博弈者只具有有限理性適應性學習能力，是一個學習機制所支持的策略行動的動態演化理論。其基本思想來源于生物進化論中的“適者生存，優勝劣汰”。生物進化中生物性狀動態變化過程中所體現出的復制動態，在有限理性博弈分析中，采用的策略收益低的博弈方會改變自己的策略，轉向(模仿)有較高收益的策略[5，10]。進化博弈分析最核心的概念是進化穩定策略，是指種群中大部分成員所采用的策略，而這種策略的好處是其他策略所比不上的。也就是說，個體的行為應該遵守群體的約定，一種進化穩定策略一旦確立，就會穩定下來，任何偏離進化穩定策略的行為將要受到自然選擇的懲罰[5，10~13]。

1.4量子競爭決策算法

這些方法固有的特點使這些算法的核心思想能改造和結合，本文在競爭決策算法和進化博弈論及量子進化算法的基礎上提出一種新型的優化算法——量子競爭決策算法。將量子個體作為競爭者參與到競爭決策中，從而使一個競爭者可以表達多個態的疊加，增加競爭者的多樣性，縮小競爭者的規模，同時有利于減少競爭力函數的個數，增強求解大規模問題的能力。根據每個競爭者的競爭力函數作出決策，利用決策函數進一步優化每個競爭者的競爭力。基于進化博弈論中的學習博弈和調整策略的重要思想，達到競爭者學習和自進化的目的。進化穩定策略定義為最優保持，即當前最優量子競爭者優于已知最優個體，則用當前最優量子競爭者替換該最優個體，否則保持不變。在整個優化過程中，競爭決策和進化穩定策略等方法可防止群體的退化。

2 旅行商問題的求解

旅行商問題是一個典型的優化難題，已被證明是NP-Hard問題，有著重要理論和實際應用價值[14]，但至今尚未找到有效的求解方法。因此，尋求有效求解TSP的算法有著重要的意義，而且許多算法驗證和算法效率測試都以TSP為基礎[15]。旅行商問題可描述為要求找到經過所有城市，且每個城市僅經過一次的路徑最短的Hamilton回路。

以旅行商問題為例，給出量子競爭決策算法具體的數學描述。

2.1基本符號

T:對稱性TSP。

n:TSP節點總個數。

W[i，j]:權值矩陣，表明節點i與節點j連線的權值。

dot_num[i]:第i個節點當前的度數。

arrive_w[i，j]:鄰接矩陣，表明節點i與j是否直接相鄰。

t_arrive_w[i，j]:arrive_w[ ]的傳遞對稱閉包，表明節點i與j是否能夠到達(包含通過其他節點中轉到達)。

All_line[i]:這是一個邊的集合，其包含的邊為圖中與結點i關聯的所有邊。

Line[i]:這是All_line[i]的子集，邊的一個端點為i，若設邊的另一個節點編號為k，則Line[i]包含的邊在All_line[i]中并滿足以下兩個條件:節點k的度小于2; t_arrive_w[i，k]=0，即節點k在當前圖中不能到達(含傳遞到達)節點i。

dmin[i， k]:Line[i]中權值第k小邊的權值(其中1≤k≤5)。

dmin_j[i， k]:Line[i]中權值第k小邊的另一個節點的編號(其中一個節點編號為i，1≤k≤5)。

power[i]:競爭者對邊資源(i， dmin_j[i， 1])的競爭力函數，即競爭者占用邊(i， dmin_j[i， 1])所需耗費的代價。

max_power_id:當前決策函數選中邊的一個端點的編號，即按照當前代價函數和決策函數，競爭者下一次占用的邊為(max_power_id， dmin_j[max_power_id， 1])。

有關符號的具體使用可參考文獻[3]。

2.2基本概念

1)初始狀態

n×(n-1)/2條邊視為被競爭的資源，初始狀態只有一個，即競爭者沒有占有任何邊資源，競爭結束是占有n×(n-1)/2條邊中的n條邊且滿足TSP回路條件[3]。

2)競爭力函數

競爭力函數可視為邊長的代價函數，采用可選的最好資源與候選最好資源的代價差距作為競爭力函數。所采用的競爭力函數的思想具體可描述如下:由于TSP回路中與每一節點關聯的邊中有且僅有兩條在回路中，當dot_num[i]=0時，把權值為dmin[i，1]、dmin[i，2]的兩條邊稱為基本邊，即可選的最好資源，而把權值為dmin[i，3]、dmin[i，4]、dmin[i，5]的三條邊稱為候補邊，即候選最好資源; 當dot_num[i]=1時，把權值為dmin[i，1] 的邊稱為基本邊，而把權值為dmin[i，2] 的邊稱為候補邊。為了取得好的效果，應該把候補邊與基本邊差距最大的邊優先分配給競爭者以減少因為基本邊不能加入到圖中而造成較大的損失，同時還要考慮權值為dmin[i，1]的邊(i， dmin_j[i，1])加入到圖中對節點dmin_j[i，1]的基本邊造成的損失。當不考慮邊(i， dmin_j[i，1])加入到圖中對節點dmin_j[i，1]的基本邊造成的損失，采用下式來計算power[i]:

power[i]=dmin[i，3]- dmin[i，1]+b1( dmin[i，4]- dmin[i，2])+ b1×0.1( dmin[i，5]- dmin[i，3])

當dot_num[i]=0-∞當dot_num[i]=2dmin[i，2]- dmin[i，1]+b1× (dmin[i，3]- dmin[i， 2])當dot_num[i]=1 

其中:dmin[i，3]- dmin[i，1]表示當權值為dmin[i，1]的邊不出現在TSP回路中時對整個TSP回路的權值至少造成的損失為dmin[i，3]- dmin[i，1]，其他各項的含義與此類似;b1為一個大于等于0且小于等于1的權重數，表明其對應項對競爭力函數power[i]的影響程度。該式表明:邊(i， dmin_j[i1，1])不分配到TSP回路中可能要比把邊(i， dmin_j[i，1])分配到TSP回路要多耗費power [i]的代價，即把邊(i， dmin_j[i，1])分配到TSP回路可避免權值為power [i]的損失。

令k=dmin_j[i，1]，當考慮邊(i， k)加入到圖中對節點k的基本邊造成的損失，采用來power [i]=power [i] - (dmin[i， 1]-dmin[k，1]) 計算。

該式在計算的結果上減去(dmin[i， 1]-dmin[k，1])，減去部分為由于邊(i， k)加入到TSP回路而使節點k要損失的權值，即邊(i， k)的加入使得節點k不能取與其關聯的短邊而造成TSP回路權值增加[3]。

3)競爭者

本算法定義m個競爭者，競爭者的類型由權重數b1確定，每輪競爭時b1在區間[0，1]上隨機生成。

4)決策函數

決策函數只有一個，采用競爭力函數最大者得到資源的決策函數，即競爭者占用power (j)值最大的邊(j， dmin_j[j，1])，當兩個點具有相同的power (j)時，選編號小的j[3]。

5)競爭規則

采用以下的競爭規則:a)初始條件——圖是連通的且可形成回路;b)競爭條件——每個節點的度不超過2且不形成子回路[3];c)終止條件——在后面算法流程中介紹。

6)0-1觀測矩陣

對于n個節點的TSP，首先生成一個n×n的全零矩陣，利用概率幅進行編碼。例如對第i個競爭者的第一對概率幅中的β1進行觀測，若

| β1|2

0010001000100000000100010

則競爭者訪問的路徑為3→2→1→5→4→3。

7)量子門

本文采用量子旋轉門，定義如下:

R(θ)=cos θ-sin θsin θcos θ

其中:θ為旋轉角，角的大小影響收斂速度，角的符號影響收斂方向。經大量實驗計算，本文 θ角在[0.001π，0.05π]隨機生成，效果較好。方向采用文獻[16]確定量子門旋轉角方向的方法，因為現有很多文獻的量子門更新都是建立在求解背包問題的量子門更新方法基礎上的，這種更新方法是要預判所優化問題的最優解的原則，像背包這類問題的最優解原則是在可行的條件下使取“1”的概率幅盡量增大，使解中“1”的個數盡可能地多[16]，但是這種情況在很多優化問題中是無法預知的，本文采用文獻[16]的方法，使算法具有更廣泛的通用性。

旅行商問題的量子競爭決策算法流程如下:

a)初始化

if 滿足初始化條件then

{確定競爭群體的規模和量子位的數目，每個競爭者的概率幅隨機初始化，確定最大競爭步數，競爭步數=0}

else {退出程序};

b)每次隨機產生m個競爭者;

c)根據競爭力函數計算在當前格局下每個競爭者的競爭力;

d)根據當前決策函數決定競爭者占有某個資源而產生新的格局，由當前競爭力函數計算在新格局下每個競爭者的競爭力;

e)對每個競爭者進行觀測，得到0-1解矩陣;

f)量子門更新競爭者的量子比特信息，動態調整競爭者自身優化能力;

g)競爭步數=競爭步數+1，若競爭步數<最大競爭步數，采取進化穩定策略， 轉步驟b)，否則轉步驟h);

h)輸出量子競爭博弈得到的結果。

2.3實驗分析

為驗證量子競爭決策算法(QCDA)的可行性和有效性，采用標準TSPLIB中的算例進行計算， http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/上下載測試數據。同時將量子競爭決策算法(QCDA)和競爭決策算法[3](CDA)、元胞螞蟻算法[17](CAA)及文獻[18]中的算法進行比較，分別考察算法得到的最優解和誤差率兩個指標。表中問題名稱中的數字為節點總個數，量子競爭決策算法使用MATLAB在Windows XP環境下編程，量子競爭者個數為3，最大競爭步數為15，實驗結果如表1和2所示。

從表1和2的數據對比可以發現，量子競爭決策算法在求解旅行商問題上性能良好，部分算例的計算結果已達到公布的最優解，算法的誤差率基本上可控制在1%以下。除個別測試算例，量子競爭決策算法在最優解和誤差率上均優于元胞螞蟻算法、競爭決策算法和文獻[18]的算法。量子競爭決策算法將進化博弈論的學習機制引入到算法中，通過量子門的更新使得競爭者向最優解方向調整，體現出進化博弈論中策略收益低的博弈方改變自己的策略轉向有較高收益策略的思想，使競爭者具有自演化進化能力，同時充分利用量子進化計算的特點，增強了競爭群體的多樣性，使得算法有更強的尋優能力。進化博弈論在生物、經濟等方面應用較多，但很少用于優化問題中，量子競爭決策算法拓寬了進化博弈論的應用范圍，同時也提高了利用量子進化算法求解TSP的性能。

3 結束語

本文提出了的量子競爭決策算法，將進化博弈論中的學習機制和量子進化計算的特點及競爭決策相結合，避免早熟現象產生，算法具有較強的全局優化能力。TSP實驗結果表明了本算法有較好的優化性能。進一步的研究可在以下兩個方面展開:a)算法在其他NP難題中的應用，如二次分配、工件排序等;b)算法在連續空間優化問題中的應用。

參考文獻:

[1]寧愛兵，馬良. 競爭決策算法及其在車輛路徑問題中的應用[J]. 管理科學學報，2005，8(6):10-18.

[2]寧愛兵，馬良. 度約束最小生成樹(DCMST)的競爭決策算法[J]. 系統工程學報，2005， 20(6):630-634.

[3]寧愛兵，馬良. 大規模旅行商問題(TSP)的競爭決策算法[J]. 計算機工程， 2005， 31(9):23-26.

[4]寧愛兵，馬良. 最小比率旅行商(MRTSP)問題競爭決策算法[J]. 計算機工程與應用，2005，41(11): 30-32.

[5]謝識予.有限理性條件下的進化博弈論[J].上海財經大學學報，2001，3(5):3-9.

[6]NIELSEN M A， CHUANG I L.量子計算和量子信息(一)—量子計算部分[M].趙千川，譯.北京:清華大學出版社，2006.

[7]HAN K H， KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Trans on Evolutionary Computation， 2002，6(6): 580-593.

[8]王凌.量子進化算法研究進展[J].控制與決策，2008，23(12):1321-1326.

[9]HAN K H， KIM J H. Quantum-inspired evolutionary algorithm with a new termination criterion ，Hε gate and two-phase scheme[J].IEEE Trans on Evolutionary Compution，2004，8(2):156-169.

[10]付立群.進化博弈論:經濟學方法論的一次革命[J].武警工程學院學報，2004，20(4):17-22.

[11]李萬，田盛豐，黃厚寬.進化博弈論及agent自組織動力學[J].計算機研究與發展，2006，43(增刊):46-50.

[12]蘇小紅，楊博，王亞東.基于進化穩定策略的遺傳算法[J].軟件學報，2003，14(11):1863-1868.

[13]FUNDENBERG D， LEVINE D K.博弈學習理論[M]. 肖爭艷，侯成琪，譯.北京:中國人民大學出版社，2004.

[14]劉纘武.應用圖論[M].長沙:國防科技大學出版社，2006.

[15]郭平，鄢文晉.基于TSP問題的蟻群算法綜述[J].計算機科學，2007，34(10):181-184，194.

[16]張葛祥，李娜，金煒東，等.一種新量子遺傳算法及其應用[J].電子學報，2004，32(3):476-479.

[17]朱剛，馬良.TSP的元胞螞蟻算法求解[J].計算機工程與應用，2007，43(10):79-80，100.

[18]沈慶濤，張振宇.高效的求解TSP問題的近似算法[J].計算機工程與應用，2008，44(35):46-49.