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

張立行 金 琦 魏振華

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

?

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

張立行 金 琦 魏振華

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

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

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

Class Number TN99

1 引言

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

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

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

2 量子遺傳算法

2.1 算法原理

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

1) 量子比特

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

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

(1)

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

|α|2+|β|2=1

(2)

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

2) 量子染色體

(3)

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

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

2.2 算法結(jié)構(gòu)

(4)

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

(5)

然后，計(jì)算P(t)中每個(gè)解的適應(yīng)度，存儲(chǔ)最優(yōu)解。

(6)

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

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

3 改進(jìn)量子遺傳算法設(shè)計(jì)

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

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

(7)

(8)

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

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

(9)

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

表1 種群初始化

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

4 仿真算例

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

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

函數(shù)表示為

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

(10)

圖1 改進(jìn)的量子遺傳算法流程圖

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

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

(11)

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

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

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

表2 改進(jìn)量子遺傳算法與其他算法比較

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

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

5 結(jié)語

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

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

TN99

10.3969/j.issn.1672-9722.2016.11.011