張立行 金 琦 魏振華

(火箭軍工程大學 西安 710025)

?

不確定性智能規(guī)劃算法研究*

張立行 金 琦 魏振華

(火箭軍工程大學 西安 710025)

在眾多研究領域都存在著客觀或者人為的不確定優(yōu)化問題，傳統(tǒng)方法很難解決此類問題。論文在簡述了傳統(tǒng)量子遺傳算法的原理和結構的基礎上，分析了傳統(tǒng)量子遺傳算法主要存在的問題，即解空間轉(zhuǎn)換和如何確定量子門的旋轉(zhuǎn)相位，以此進行算法的改進，給出了改進量子遺傳算法的流程，并以Shaffer’s F1多峰不確定優(yōu)化問題為例，分析了IQGA的運行效率、收斂速度等性能。通過仿真研究表明IQGA運行效率較高，收斂速度較快，能較好地支持不確定規(guī)劃問題。

不確定性; 智能規(guī)劃; 進化算法; IQGA

Class Number TN99

1 引言

從系統(tǒng)觀點出發(fā)，研究綜合處理各類不確定性信息的理論與方法，稱之為不確定性系統(tǒng)理論[1～2]。在運籌學、管理科學、信息科學等眾多研究領域的問題中，都存在著客觀的或人為的不確定性，伴隨著這些千姿百態(tài)的不確定性，顯然存在著大量的不確定優(yōu)化問題[3]。傳統(tǒng)方法遠遠不能滿足解決具有雙重或多重不確定性的決策系統(tǒng)優(yōu)化問題的要求，因此，大量智能算法應運而生。

目前，國內(nèi)外提出了大量的智能算法，如遺傳算法、免疫算法等[4～7]。然而，每種進化算法都有其優(yōu)點和不足，為了使多種智能算法優(yōu)勢互補，遵循“組合優(yōu)化”的思想，對不同智能優(yōu)化算法進行融合是一個重要的研究方向[8～11]。

1996年，Narayanan和Moore等將量子多宇宙的概念最先引入遺傳算法，提出量子衍生遺傳算法(Quantum Inspired Genetic Alogrithm)，并成功地用它解決了TSP問題，開創(chuàng)了量子計算與進化計算融合的新方向[12～13]。在已有的量子遺傳算法中，量子門起到了至關重要的作用，然而關于量子門的設計卻沒有給出具體方法；另外，也可以發(fā)現(xiàn)量子計算與進化算法的融合點主要集中在種群編碼方式和進化策略的構造上。量子計算呈現(xiàn)出的強大并行性對傳統(tǒng)算法具有加速作用，但只有應用由量子硬件構造的量子計算機才能實現(xiàn)[14]。然而，在智能優(yōu)化算法中，引入量子機制，用量子位構造尋優(yōu)個體，用量子旋轉(zhuǎn)門更新個體上的量子位，用量子非門實現(xiàn)個體變異，進而實現(xiàn)與傳統(tǒng)優(yōu)化算法截然不同的量子搜索機制。這種搜索機制能夠增強對解空間的遍歷性，增強種群多樣性，并能應用量子位的概率幅將最優(yōu)解表述為搜索空間中的多種表述形式，從而增加獲得全局最優(yōu)解的概率，本文以此展開研究。

2 量子遺傳算法

2.1 算法原理

近幾年來，學術界提出了很多有代表性的量子遺傳算法。2000年，由K.H.Han等給出的QGA算法分析量子遺傳算法的原理，該算法主要是由于K.H.Han等首先將量子位和量子門的概念引入進化算法，具有代表性[15～16]。

1) 量子比特

QGA是基于量子位和量子疊加態(tài)的概念提出的。量子位或量子比特是量子計算機中的最小信息單位。一個量子位可以處于|0〉態(tài)、|1〉態(tài)以及|0〉和|1〉之間的任意疊加態(tài)。一個量子位的狀態(tài)可以描述為

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

(1)

其中α、β是復數(shù)，稱為量子對應態(tài)的概率幅。|α|2表示量子態(tài)被觀測為|0〉態(tài)的概率，|β|2表示量子態(tài)被觀測為|1〉態(tài)的概率，且滿足歸一化條件

|α|2+|β|2=1

(2)

如果系統(tǒng)有m個量子位，則該系統(tǒng)可同時描述2m個狀態(tài)，然而在觀測時，該系統(tǒng)將坍塌為一個確定的狀態(tài)。

2) 量子染色體

(3)

其中|αi|2+|βi|2=1,i=1,2,…,m。

由于量子系統(tǒng)具有疊加態(tài)，才使得基于量子位編碼的進化算法比傳統(tǒng)進化算法具有更好的種群多樣性。

2.2 算法結構

(4)

其中m是量子位數(shù)，即量子染色體的長度，j=1,2,…,n。

(5)

然后，計算P(t)中每個解的適應度，存儲最優(yōu)解。

(6)

最后選擇P(t)中的當前最優(yōu)解，若該最優(yōu)解優(yōu)于目前存儲的最優(yōu)解，則用該最優(yōu)解將其替換。

上面給出的是最基本的量子遺傳算法，由于量子本身具有量子疊加態(tài)使個體具有多樣性，從而省略了交叉、變異等遺傳操作。對于不確定規(guī)劃而言，量子遺傳算法主要存在兩方面的問題限制了其執(zhí)行效率，即解空間轉(zhuǎn)換和如何確定量子門的旋轉(zhuǎn)相位。本文以此為重點對傳統(tǒng)量子遺傳算法進行改進。

3 改進量子遺傳算法設計

1) 解空間轉(zhuǎn)換

不論對于連續(xù)函數(shù)優(yōu)化問題，還是不確定性規(guī)劃中的常見目標函數(shù)求解，都可以轉(zhuǎn)換為常規(guī)的規(guī)劃模型。因此，可以直接將參數(shù)用2位或更多位的量子編碼表示出來，本文采用雙鏈編碼方案實施編碼，如式(7)所示。

(7)

(8)

2) 量子旋轉(zhuǎn)門轉(zhuǎn)角的確定

量子染色體第i個量子位為(αi,β)，更新方式是

(9)

其中θi=s(αiβi)Δθi，Δθi和s(αiβi)取值可按表1方式獲得。

表1 種群初始化

結合量子遺傳算法得到改進的量子遺傳算法流程，如圖1所示，其方法步驟不再贅述。

4 仿真算例

以Shaffer’sF1多峰不確定規(guī)劃為例，檢驗算法的性能。

在算法實現(xiàn)時考慮了兩種方式，其一是由于給出的算例復雜度較低，可以利用窮舉的方式搜索解空間，因此從時間效率與其同遺傳算法進行比較；其二是對算法的進化代數(shù)的不同對解空間的收斂程度進行比較。

函數(shù)表示為

f(x,y)=-(x2+y2)0.25(sin2(50(x2+y2)0.1)+1.0)

(10)

圖1 改進的量子遺傳算法流程圖

將其改為具有不確定規(guī)劃模型的表達式為

maxf(x,y)=-(x2+y2)0.25(sin2((50+ζ)(x2+y2)0.1)+(1.0+ζ))

(11)

圖2是用Matlab繪制出的ζ=0時的三維曲面。

圖2 仿真函數(shù)三維曲面圖

針對該規(guī)劃問題控制遺傳參數(shù)：種群規(guī)模m=100；量子位n=2；變異概率pm=0.1；轉(zhuǎn)角步長初值為θ0=0.01π；最大遺傳迭代次數(shù)Genmax=2000。在配置CPU為AMD3500+，內(nèi)存2G，WindowsXP系統(tǒng)下，經(jīng)過仿真計算得到改進量子遺傳算法與其他算法比較的最終結果，如表2，其IQGA與GA方法收斂次數(shù)對比圖如圖3所示。

表2 改進量子遺傳算法與其他算法比較

圖3 IQGA與GA方法收斂次數(shù)對比圖

從表2、圖3中可以看出：枚舉算法最直接，在給出取值范圍時一定可以找到結果，但效率受精度影響；遺傳算法效果較好，在17.456s內(nèi)可以找到最優(yōu)解；改進的量子遺傳算法在6.489s即可完成搜索。

5 結語

量子遺傳算法的高效性來源于量子態(tài)的并行性，本文在簡述了傳統(tǒng)量子遺傳算法的原理和結構的基礎上，分析了傳統(tǒng)量子遺傳算法主要存在的問題，即解空間轉(zhuǎn)換和如何確定量子門的旋轉(zhuǎn)相位，以此進行算法的改進，給出了改進量子遺傳算法的流程，并以Shaffer’s F1多峰不確定規(guī)劃為例，分析了IQGA的運行效率、收斂速度等性能。通過仿真研究表明：IQGA運行效率較高，收斂速度較快，能較好地支持不確定規(guī)劃問題。

[1] NARAYANAN A, MOORE M. Quantum-inspired genetic algorithm[C]//Proceeding of IEEE International Conference on Evolutionary Computation, Nagoya, Japan,2010:61-66.

[2] Ben-Tal, A., Nemirovski, A. On tractable approximations of uncertain linear matrix inequalities acected by interval uncertainty[J]. SIAM J. Optimization,2012,12:811-833.

[3] LIU Shaofeng, DONG Jian, WU Zhibo. A Dynamic-feedback Scheduling Algorithm for Cluster Load Balancing based on Priority Queue[J]. Intelligent Computer and Applications,2014,12(4):45-49.

[4] TU Gang, YANG Fumin, LU Yansheng. An Optimal Scheduling Algorithm for Soft Aperiodic Tasks[J]. Journal of Computer Research and Development,2014,42(11):23-24.

[5] LIAO Daqiang, ZOU Du, YIN Jiana. Grid Scheduling Algorithm Based on Priority[J]. Computer Engineering,2014,40(10):11-16.

[6] LIAO Daqiang, YIN Jian, WU Yilin, et al. Interest Propagation-Based User Similarity Computation Method[J]. Computer Applications and Software,2015,32(10):95 400,104.

[7] KHORSAND A R, AKBARZANEH M R. Quantum gate optimization in a meta-level genetic quantum algorithm[C]//2005 IEEE International Conference on Systems, Man and Cybernetics,2015,4:3055-3062.

[8] ZHANG G X, JIN W D, HU L Z. A novel parallel quantum genetic algrothm[C]//Proceedings of the Fouth International Conference on Parallel and Distributed Computing, Applications and the Technologies,2013:693-697.

[9] LI Shi-yong, LI Pan-chi, YUAN Li-ying. Quantum genetic algorithm with application in fuzzy controller parameter optimization[J]. Systems Engineering and Electronics,2013,29(7):1143-1138.

[10] LI P C, LI S Y. Quantum-inspired evolutionary algorithm for continuous spaces optimization based on Bloch coordinates of qubits[J]. Neurocomputing,2011,72:581-591.

[11] LIAO Da-Qiang. Multi Objective Planning Research of Resource Scheduling Algorithm for Cloud Computing[J]. Computer Systems & Applications,2016,25(2):180-189.

[12] ZHONG Hao-tao. Dynamic scheduling grouping algorithm based on genetic algorithm[J]. Chinese Journal of Computers,2013,45(8):11-12.

[13] Ben-Tal, A., Nemirovski, A. Robust solutions of Linear Programming problems contaminated with uncertain data[J]. Math. Program.,2010,88:411-424.

[14] ZHANG G X, JIN W D, HU L Z. A novel parallel quantum genetic algrothm[C]//Proceedings of the Fouth International Conference on Parallel and Distributed Computing, Applications and the Technologies,2013:693-697.

[15] YANG J A, LI B, ZHUANG Z Q. Muti-universe parallel quantum genetic algorithm and its application to blind-source separation[C]//Proceedings of the International Conference on Neural Networks and Singal Processing,2012,1:393-398.

[16] CHEN H, ZHANG J H, ZHANG C. Chaos updating rotated gates quantum-inspired genetic algorithm[C]//Proceedings of the International Conference on Communications, Cuircuits and Systems,2010,2:1108-1112.

Uncertainty Intelligent Planning Algorithm

ZHANG Lixing JIN Qi WEI Zhenhua

(Rocket Force Engineering University, Xi’an 710025)

There is an objective or artificial uncertain optimization problem in many area, the traditional methods are difficult to solve such problems. The paper firstly introduces the principle and structure of the traditional quantum genetic algorithm (QGA), analyzes the main problem of the traditional quantum genetic algorithm, namely the problem of the solution space conversion, and how to determine the rotational phase of the quantum gate. Then the paper improves the algorithm based on the analysis, gives the process of improved quantum genetic algorithm (IQGA), and takes Shaffer's F1 multimodal uncertain planning for example, analyzes the properties of the running efficiency and the convergence efficiency etc. of IQGA. The simulation results show that the running efficiency of IQGA is higher, and convergence efficiency is faster, therefore, the uncertain planning problem can be better supported by IQGA.

uncertainty, intelligent planning, evolutionary algorithm, IQGA

2016年5月16日,

2016年6月21日

張立行，男，研究方向：通信工程。金琦，女，研究方向：通信工程。魏振華，男，研究方向：通信自動化。

TN99

10.3969/j.issn.1672-9722.2016.11.011