量子進化算法在機器人聯(lián)盟問題中的應(yīng)用

李 絮，郭 英，劉爭艷

(阜陽師范學(xué)院計算機與信息工程學(xué)院，安徽阜陽 236037)

量子進化算法在機器人聯(lián)盟問題中的應(yīng)用

李 絮，郭 英，劉爭艷

(阜陽師范學(xué)院計算機與信息工程學(xué)院，安徽阜陽 236037)

量子進化算法是一種新的基于量子計算的概率搜素算法，它采用量子比特來編碼染色體，采用量子門對種群進行更新進化，具有較快的收斂速度和良好的全局尋優(yōu)能力。機器人聯(lián)盟問題是一個復(fù)雜的組合優(yōu)化問題，本文運用量子進化算法對該問題進行算法設(shè)計與應(yīng)用研究，設(shè)計了一種量子變異算子，并對算法參數(shù)進行了研究。仿真實驗結(jié)果驗證了量子進化算法的可行性與有效性。

量子計算;進化算法;機器人;聯(lián)盟

在多機器人系統(tǒng)中，受單個機器人能力的限制，機器人之間往往需要相互協(xié)作，通過結(jié)成聯(lián)盟才能夠完成任務(wù)［1］。由于不同的機器人聯(lián)盟具備的能力不同(成員的數(shù)量和能力不同)，且它們執(zhí)行任務(wù)的效率和代價也不相同，在通過聯(lián)盟完成任務(wù)時希望能夠以最小的代價獲取最大的利益。機器人聯(lián)盟問題主要研究的就是如何動態(tài)生成面向任務(wù)的最優(yōu)機器人聯(lián)盟，隨著系統(tǒng)中機器人數(shù)量的增加，可能的聯(lián)盟總數(shù)將會呈指數(shù)級增長，因此機器人聯(lián)盟問題是一個復(fù)雜的組合優(yōu)化問題［2］。

量子進化算法(Quantum-inspired Evolutionary Algorithms，QEA)是近年來發(fā)展起來的一種概率進化算法，是量子計算與進化算法相結(jié)合的產(chǎn)物［3］。基于量子衍生機制的概率編碼方式能夠很好的表達不確定信息，同時由于量子具有干涉、糾纏及并行等特性，使得量子進化算法非常適合求解組合優(yōu)化問題。前期我們在文獻［4］中將量子進化算法應(yīng)用到典型的背包問題中，取得了良好的效果。受可此啟發(fā)，本文將量子進化算法應(yīng)用到機器人聯(lián)盟問題中，并進行仿真實驗，實驗結(jié)果證明了該算法的行性與有效性。

1 機器人聯(lián)盟問題

1.1 聯(lián)盟定義

一個機器人聯(lián)盟就是能夠完成任務(wù)的一個或多個機器人集合。若系統(tǒng)中機器人集合為R，則定義一個機器人聯(lián)盟C就是R的一個非空子集。例如，假設(shè)機器人集合R={a，b，c}，則可能的機器人聯(lián)盟C就有如下7個:{a}，，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}。

1.2 問題描述

設(shè)n個機器人集合R={R1，R2，…，Rn}，任意機器人Ri都具有一個r維能力向量，其中(1≤j≤r)用于定量描述Ri執(zhí)行某種特定動作的能力大小［5］。聯(lián)盟C則具有一個能力向量，BC是聯(lián)盟中所有機器人能力向量的總和，即。任務(wù)t具有一定的能力需求。聯(lián)盟C能夠完成任務(wù)t的必要條件是:BC≥Bt，即。

任何一個聯(lián)盟C都具有聯(lián)盟代價CostC、聯(lián)盟收益ProfitC和聯(lián)盟值ValueC，聯(lián)盟代價CostC是聯(lián)盟成員通過聯(lián)盟活動完成任務(wù)的開銷總和，聯(lián)盟收益ProfitC是聯(lián)盟完成任務(wù)獲得的利益，而聯(lián)盟值ValueC則由 CostC和 ProfitC共同確定［6］。機器人聯(lián)盟問題就是要求出擁有最大ValueC值的聯(lián)盟。

2 量子進化算法

量子進化算法(QEA)是一種將量子計算與進化算法相結(jié)合的概率搜索算法。它以量子計算的一些概念和理論為基礎(chǔ)，充分利用量子態(tài)的衍生與相干特性，采用量子比特編碼來表示染色體，同時利用量子旋轉(zhuǎn)門對染色體進行更新，并保留最優(yōu)染色體，使算法不斷尋優(yōu)，從而實現(xiàn)對目標問題的優(yōu)化求解［7］。

2.1 量子比特編碼

量子比特是基本的信息存儲單元，其狀態(tài)是由兩個基態(tài)|0〉和|1〉的任意疊加態(tài)構(gòu)成，一個量子比特狀態(tài)可表示為

其中，α、β為一對復(fù)數(shù)，分別表示基態(tài)|0〉和

在QEA中，染色體不是采用二進制、十進制或浮點等編碼方式，而是采用一種新的量子比特編碼方式，稱為量子染色體。一個由m個量子比特構(gòu)成的量子染色體q的表示形式可以描述為

2.2 量子旋轉(zhuǎn)門

在QEA中，采用量子旋轉(zhuǎn)門U(θ)來實現(xiàn)對量子染色體的更新，對量子染色體的更新是通過對每個量子比特的更新來實現(xiàn)的，量子旋轉(zhuǎn)門更新方式表示如下:

旋轉(zhuǎn)角度θ的大小對種群的更新進化起著關(guān)鍵作用，若θ值太大，能夠使種群快速進化，但很可能會早熟收斂于一個局部最優(yōu)解。若θ值太小，又會使種群更新進化速度較慢，影響算法收斂。

2.3 算法流程

量子進化算法的一般步驟如下:

(1)初始化種群Q(t)，t=0;

(2)測量種群Q(t)，得到一組相應(yīng)的二進制解P(t);

(3)用適應(yīng)度函數(shù)對P(t)進行評價，并保存最優(yōu)解;

(4)若滿足終止條件，算法結(jié)束，否則算法繼續(xù);

(5)利用量子旋轉(zhuǎn)門更新;

(6)t=t+1，算法返回(2)繼續(xù)進行。

其中，在第(1)步初始化種群時，量子染色體的每個量子比特都取1，這意味著所有可能的疊加態(tài)以相同的概率出現(xiàn)。在第(2)步中，測量Q(t)生成P(t)的具體操作過程如下:隨機產(chǎn)生一個［0，1］之間的隨機數(shù)，若它大于，則相應(yīng)二進制解的比特位取1，否則取0。

3 基于QEA算法的機器人聯(lián)盟優(yōu)化

將QEA算法應(yīng)用到機器人聯(lián)盟問題中，在設(shè)計算法優(yōu)化求解時需要考慮以下幾個方面:

(1)聯(lián)盟編碼

設(shè)m個機器人集合R={R1，R2，…，Rm}，一個機器人聯(lián)盟C采用二進制編碼，表示為C={r1，r2，···，rm}，每個基因ri(i=1，2，…，m)為0或1。ri=1表示機器人Ri在聯(lián)盟中，ri=0，則表示機器人Ri不在聯(lián)盟中。

(2)初始聯(lián)盟

其中，m為機器人個數(shù)。

測量種群Q(0)，得到一組相應(yīng)的二進制解，其中每個pi(i=1，2，…，n)即為一個初始聯(lián)盟。

(3)適應(yīng)度函數(shù)

機器人聯(lián)盟問題就是要求出能夠以最小代價獲取最大收益的最大聯(lián)盟值。因此機器人聯(lián)盟問題的適應(yīng)度函數(shù)實際上就是求解聯(lián)盟值的函數(shù)。聯(lián)盟值ValueC與聯(lián)盟代價CostC和聯(lián)盟收益ProfitC有關(guān)，它會隨著ProfitC值的遞增而遞增，隨著CostC的遞增而遞減。因此，將適應(yīng)度函數(shù)定義為:F(C)=ValueC=ProfitC/CostC(當聯(lián)盟C不能完成任務(wù)時，ProfitC=0)。用適應(yīng)度函數(shù)對種群中每個聯(lián)盟進行評價，保留全局最優(yōu)聯(lián)盟。

(4)旋轉(zhuǎn)角選擇策略

量子旋轉(zhuǎn)門的旋轉(zhuǎn)角通過查表方式獲得，具體選擇策略如表1所示。

若當前聯(lián)盟與最優(yōu)聯(lián)盟中對應(yīng)基因位上的二進制值相同，則旋轉(zhuǎn)角度θ為0，否則按照表1對量子比特進行更新操作。

表1 旋轉(zhuǎn)角選擇策略

(5)量子變異

為了防止算法早熟收斂，使其能夠搜索到聯(lián)盟問題的真正最優(yōu)解，本文引入量子非門Unot對量子染色體進行變異操作，即利用量子非門將量子比特概率幅對調(diào)。這樣就使得原來傾向于坍縮到狀態(tài)“1”的變?yōu)閮A向于坍縮到狀態(tài)“0”，或者相反。量子非門的執(zhí)行方式如下:

在利用量子旋轉(zhuǎn)門對種群進行更新之后，執(zhí)行量子變異操作，其具體過程如下:

(i)按照一個給定的變異概率，從種群中隨機選擇若干量子染色體;

(ii)對選中的量子染色體隨機確定一個或多個變異位;

(iii)對選中位的量子比特執(zhí)行量子非門操作。

4 仿真實驗

為了驗證基于QEA算法求解機器人聯(lián)盟問題的有效性，本文設(shè)定機器人聯(lián)盟問題的相關(guān)數(shù)據(jù)如下:設(shè)系統(tǒng)中機器人總數(shù)為25個，每個機器人Ri具有4種不同的能力，如表2所示。每個機器人Ri需花費的代價為，完成任務(wù)t需要4種不同的能力，完成任務(wù)t獲得的收益為。QEA算法的相關(guān)數(shù)據(jù)如下:種群規(guī)模為10，量子變異概率為0.5，最大迭代次數(shù)為1 000，為了驗證量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度對算法收斂速度和求解質(zhì)量的影響，將旋轉(zhuǎn)角θ分別取0.001π和0.01π。

針對不同的θ取值，分別運行本文算法各50次，并統(tǒng)計50次實驗中算法找到的最優(yōu)聯(lián)盟值、最差聯(lián)盟值、平均聯(lián)盟值、以及搜索到最優(yōu)解的次數(shù)和最快搜索到最優(yōu)解的進化代數(shù)，結(jié)果如表3所示。同時，繪出50次實驗中最優(yōu)聯(lián)盟值隨迭代次數(shù)的進化曲線，如圖1、圖2所示。

表2 機器人Ri具有的4種能力

表3 運行不同θ值的QEA各50次的實驗結(jié)果

圖1 QEA(θ=0.001π)50次實驗運行結(jié)果

圖2 QEA(θ=0.01π)50次實驗運行結(jié)果

從表3及圖1、圖2中能夠很直觀地發(fā)現(xiàn)，QEA中旋轉(zhuǎn)角θ取不同的值對算法的收斂速度和求解質(zhì)量有著明顯的影響。θ值較小，使得搜索網(wǎng)格也較小，能夠擴大算法的搜索空間，不易陷入局部最優(yōu)，但同時種群更新進化也較慢，影響算法收斂速度;θ值較大，使得搜索網(wǎng)格也較大，能夠使算法在早期快速進化，但很可能會早熟收斂，陷入局部最優(yōu)解。如表3中所示，θ為0.001π時，50次實驗中最快搜索到最優(yōu)解是在算法進化226代后，而θ為0.01π時，能夠在57代就搜索到最優(yōu)解。從圖1和圖2中也能明顯看到，在算法運行前期，θ為0.01π時收斂速度較快。但同時也能看到，θ為0.01π時算法的求解質(zhì)量卻不如θ取0.001π時。因此，在進行算法應(yīng)用時，應(yīng)該根據(jù)應(yīng)用問題是注重收斂速度還是注重求解質(zhì)量，合理地設(shè)置θ值。

5 結(jié)束語

機器人聯(lián)盟問題是多機器人系統(tǒng)研究中一個基礎(chǔ)性問題，同時也是一個復(fù)雜的組合優(yōu)化問題。量子進化算法作為一種新的概率搜索算法，采用了量子比特編碼方式，使算法具有豐富的多樣性和并行性。同時采用量子旋轉(zhuǎn)門和量子非門等尋優(yōu)機制，利用最優(yōu)解的信息對種群進行更新進化，使算法具有很好的優(yōu)化與收斂性能。對機器人聯(lián)盟問題的研究驗證了該算法的可行性與有效性。對該算法的進一步改進，包括進化算子與旋轉(zhuǎn)角的設(shè)計，同時進一步擴大其應(yīng)用領(lǐng)域，將是我們未來的研究工作。

［1］劉淑華，張 崳，付 帥，等.基于群體智能的多機器人任務(wù)分配［J］.吉林大學(xué)學(xué)報，2010，40(1): 123-129

［2］傅一峰，曹 健，李明祿.面向復(fù)雜任務(wù)結(jié)構(gòu)的A-gent聯(lián)盟算法［J］.小型微型計算機系統(tǒng).2011，32 (3):402-406.

［3］申曉寧，謝文武.基于量子進化算法的移動機器人實時路徑規(guī)劃［J］.計算機科學(xué)，2013，40(5):229-232

［4］李 絮，劉爭艷.改進的多宇宙并行量子進化算法.計算機工程與應(yīng)用［J］.2010，46(34):35-38

［5］Travis C，Julie A.Coalition formation for task allocation:theory and algorithms［J］.Auton Agent Multi-A-gent Syst，2011，22(2):225-248.

［6］王 皓，曹 健.分布式環(huán)境下面向復(fù)雜任務(wù)的A-gent聯(lián)盟構(gòu)建［J］.計算機工程，2013，39(12):216-221.

［7］錢 潔，鄭建國.引入逆學(xué)習(xí)的量子自適應(yīng)禁忌搜索算法［J］.電子學(xué)報，2013，1(6):1070-1075.

Application of quantum-inspired evolutionary algorithm in robot coalition problem

LI Xu，GUO Ying，LIU Zheng-yan
(School of Computer and Information Engineering，F(xiàn)uyang Teachers College，F(xiàn)uyang Anhui236037，China)

Quantum-inspired evolutionary algorithm(QEA)is a new probabilistic search algorithm inspired by quantum computing.It uses quantum bits to encode the chromosomes，and uses quantum gates to update the population，so it has a faster convergence speed and good global optimization capability.Robot coalition problem is a complex combinatorial optimization problem.In this paper，the QEA is used for algorithm design and application research for this problem，and a quantum mutation operator is designed and the algorithm parameters are studied.Simulation results verify the feasibility and effectiveness of the QEA.

quantum computing;evolutionary algorithm;robot;coalition

TP242

：A

：1004-4329(2015)01-049-05

2014-04-23

安徽省教育廳自然科學(xué)基金項目(KJ2013Z259);阜陽師范學(xué)院自然科學(xué)基金項目(2013FSKJ02ZD，2014FSKJ09);阜陽師范學(xué)院大學(xué)生創(chuàng)新訓(xùn)練項目(FS201310371122);全國統(tǒng)計科學(xué)研究重點項目(2014LZ32)資助。

李 絮(1983－)，女，碩士，講師。研究方向：智能優(yōu)化。