求解復雜系統可靠性冗余問題的量子螢火蟲算法

王成亮，程鳳農

（1.上海理工大學 管理學院，上海 200093；2.山東師范大學 商學院，濟南 250014；3.山東女子學院 教育學院，濟南 250300）

在機械制造、土木建筑與集成電路等現代工程系統設計中，通常采用冗余優化技術來提高復雜系統的可靠性，以降低系統的故障率[1]。對復雜系統可靠性冗余問題的優化可有效利用資源，提高系統效率，使系統在一定資源約束條件下，達到經濟效益最大化的目的。復雜系統單元眾多，其可靠度函數和約束函數具有非線性的特點，通常是非凸和不連續的，因此，采用傳統方法對復雜系統可靠性冗余優化問題進行求解很難達到理想效果[2-3]。

目前，求解復雜系統可靠性冗余問題主要有動態規劃、啟發式算法和智能優化算法等。文獻[4]中分析了異構并行復雜系統的性能和可靠性，探討了異構系統可靠性的求解策略，并利用近似算法和啟發式算法對異構并行復雜系統可靠性冗余問題進行了求解。文獻[5]中提出了復雜系統可靠性冗余問題模型，并采用動態規劃的方法對此模型進行求解，實驗結果表明，復雜系統可靠性冗余問題的計算復雜度隨著約束條件的增加呈指數增長。文獻[6]中利用遺傳算法對復雜系統可靠度和冗余數分配問題進行了求解，并設計了復雜系統可靠度分配模型。文獻[7]中研究了具有冗余策略的串并聯復雜系統，并根據復雜系統的特點建立了相應的可靠度模型。最后，利用改進的遺傳算法對該模型進行求解。文獻[8]中利用直覺模糊集和粒子群算法對復雜系統的可靠度進行了分析和求解，在仿真實驗中將實驗結果與傳統方法進行了對比。

螢火蟲算法（Firefly Algorithm，FA）是通過模擬自然界螢火蟲求偶和覓食行為而來的一種新興仿生智能優化算法，具有通用性強、收斂速度快等特點，為解決復雜系統可靠性冗余問題提供了新的思路和方法。當前，螢火蟲算法已經成功應用于函數優化[9]、物流生產[10]和電力控制等領域[11-12]，在復雜系統可靠性冗余優化問題中的應用還不多見。本文將量子理論融入螢火蟲算法中，提出了一種解決復雜系統可靠性冗余優化問題的量子螢火蟲算法，該算法利用量子計算中的量子位編碼表示螢火蟲個體，通過量子旋轉門對螢火蟲進行變異和位置更新操作，防止了算法過早陷入局部最優值，使算法的全局搜索能力和搜索效率得到提高。仿真實驗表明，該算法是解決復雜系統可靠性冗余問題的一種有效方法。

1 模 型

復雜系統可靠性的優化設計應該在當前限定的條件下盡量使復雜系統的可靠度最大化。假設復雜系統由N個子系統組成，xi為第i個子系統，則整個復雜系統X=｛x1，x2，…，xi，…，xN｝；設第i個子系統xi對應的冗余數為pi，則各子系統的冗余數集合P=｛p1，p2，…，pi，…，pN｝；設第i個子系統xi對應的實施方案為qi，則各子系統的實施方案集合Q=｛q1，q2，…，qi，…，qN｝。因此，復雜系統可靠性的優化設計可以轉化為尋找最優冗余數P和實施方案Q，以使子系統在費用函數和權重函數滿足特定條件的情況下可靠度最大化。復雜系統可靠性冗余優化問題數學模型：

式中：ti（qi）為第i個子系統xi對應的實施方案qi的單位費用函數；T0為整個復雜系統的最大投資費用；η0為整個復雜系統的最大約束權重；ηi（qi）為第i個子系統xi對應的實施方案qi的單位權重函數；R（xi）為第i個子系統xi的可靠度函數；

為整個復雜系統的可靠度。根據子系統的體系結構可知，對于給定的pi和qi，R（xi）和f（R（x1），R（x2），…，R（xi），…，R（xN））分別為：

2 基本螢火蟲算法

基本螢火蟲算法由Krishnanand[13]和Yang[14]提出，他們提出的算法在具體實現方式上有一定的差異，但兩者的基本原理是相同的，即都是利用螢火蟲的發光機制進行尋優求解。在螢火蟲算法中，個體被隨機分布在解空間中，螢火蟲總是朝著比自已熒光素高的個體進行移動，并以一定概率的形式在領域半徑內進行交換和轉移。

設Xi（t）表示螢火蟲i在t時刻的位置，n只螢火蟲組成的群體為

設每只螢火蟲的位置由d維空間構成，螢火蟲i的位置Xi（t）=｛xi1（t），xi2（t），…，xid（t）｝。每只螢火蟲自身都攜帶一定能量的熒光素li，若t時刻螢火蟲i的熒光素為li（t），則t+1 時刻螢火蟲i的熒光素為

式中：f（Xi（t+1））為 螢 火 蟲 的 適 應 度 值；ρ∈（0，1）為螢火蟲的熒光變化率；γ為螢火蟲的適應度變化率。

在螢火蟲算法中，螢火蟲依靠熒光素的大小來吸引周圍的螢火蟲，在領域半徑內，螢火蟲i以概率pij向螢火蟲j移動，概率pij的大小為

式中，Ni（t）為領域半徑內比個體i熒光素更高的螢火蟲數目，即

式中：w為移動步長；||Xj（t）-Xi（t）||為螢火蟲j、i之間的歐氏距離；rs為螢火蟲信號識別感知區；nt為螢火蟲數量控制閾值；β為控制系數。

3 量子螢火蟲算法

3.1 編碼方案

設每只螢火蟲的位置由d維空間構成，n只螢火蟲組成的群體為

利用量子位編碼方式對螢火蟲個體進行編碼，令|Xi（t）>為單個螢火蟲的量子空間位置，對應的量子位概率幅分別為：

由式（11）、（12）可知，單個螢火蟲的量子空間位置為

式中：i為螢火蟲個數；j為螢火蟲的位置空間維數；i=1，2，…，n；j=1，2，…，d；θ為量子旋轉門的轉角，θ=2π˙rand（）；rand（）是位于0和1之間的隨機數。

3.2 量子空間的轉換

螢火蟲量子空間的轉換采用線性映射變換的方式進行，通過變換后，量子位概率幅將與函數變量的解空間建立起映射關系。由式（13）可知，

即|Xic（t）>∈[-1，1]，|Xis（t）>∈[-1，1]。螢火蟲i在第j維的量子空間位為，若函數變量的取值范圍為[m，n]，則通過線性映射變換后，|Xic（t）>和|Xis（t）>在[m，n]上可表示為：

由式（14）、（15）可知，

3.3 量子旋轉門及螢火蟲變異操作

螢火蟲在領域半徑內進行尋優時，容易出現聚集現象。一旦聚集現象產生，螢火蟲算法就會陷入局部最優值。為了避免這種現象的發生，本文利用量子旋轉門對螢火蟲個體進行變異操作。

定義1量子旋轉門。設Δθ為量子旋轉門的旋轉角度，U（Δθ）為量子旋轉門，為變異前個體為演化變異后新個體，其中，

量子旋轉門為

由以上定義1可知，經過量子旋轉門的變換之后，新個體為

定理1設為螢火蟲在量子空間中的最優個體為螢火蟲當前在量子空間中的尋優個體，若

則量子旋轉門旋轉方向的規則為：

（1）若B=0，則量子旋轉門旋轉方向為順時針和逆時針2個方向。

（2）若B≠0，則量子旋轉門旋轉方向為-sgn（B）。

證明設最優個體和當前尋優個體在量子空間中的旋轉度分別為θb和θi，由

可知，B=sin（θi-θb）。

若B=0，則B=sin（θi-θb）=0，旋轉門的轉動角度|θi-θb|=0或|θi-θb|=π，此時量子旋轉門往順時針和逆時針旋轉的效果相同。若B≠0，則B=sin（θi-θb）≠0，旋轉門的轉動角度為

0＜|θi-θb|＜π或π＜|θi-θb|＜2π

當0＜|θi-θb|＜π時，

當π＜|θi-θb|＜2π時，

由此可知，若B≠0，量子旋轉門旋轉方向始終為-sgn（B）。 證畢

根據定義1和定理1，結合式（13）、（19），推出螢火蟲變異過程：

在n只螢火蟲構成的群體中，以隨機方式選出k只螢火蟲進行變異，則變異率p=k/n，經過式（20）變異后，螢火蟲對應的量子位概率幅為

由式（21）可知，量子態|0>和量子態|1>兩種狀態可以進行有效轉換，從而避免了螢火蟲在領域半徑內大面積聚集的現象，防止了算法過早陷入局部最優值。

3.4 位置更新

在量子螢火蟲算法中，利用量子旋轉門對螢火蟲的位置進行更新。更新后的位置為

螢火蟲在量子空間進行移動時，隨著量子旋轉門U（Δθ（t+1））的變化，對應的量子位概率幅|Xic（t）>和|Xis（t）>不斷發生變化，在螢火蟲群體規模保持不變的情況下，采用量子位實數編碼和量子旋轉門的方式可以放大螢火蟲的尋優空間，同時使算法的全局搜索能力和搜索效率得到提高。

4 算法的實現流程

量子螢火蟲算法的實現流程：

（1）初始化。利用式（11）、（12）隨機產生螢火蟲的量子位概率幅|Xic（t）>和|Xis（t）>，利用式（13）隨機生成螢火蟲群體，其中螢火蟲量子位的數目為n。

（2）更新螢火蟲的量子位概率幅。采用線性映射變換的方式對螢火蟲的解空間進行變換，利用式（16）、（17）將取值范圍為[m，n]的函數變量映射到量子空間，分別更新每只螢火蟲對應的量子位概率幅，找出螢火蟲群體中的精英個體。

（3）終止條件的判定。判定算法是否達到要求，如果是，則轉（8），否則轉（4）。

（4）螢火蟲的位置更新。利用式（6）、（7）和式（10）對領域半徑內的螢火蟲進行跟蹤，然后采用量子旋轉門轉動的方式對螢火蟲進行位置更新，通過式（22）計算每只螢火蟲的新位置。

（5）螢火蟲變異操作。利用式（20）、（21）對螢火蟲進行變異操作，其變異率p=k/n。

（6）適應度的計算。重新計算每只螢火蟲的量子位概率幅，分別求出相應的適應度值，確定螢火蟲群體中的精英個體。

（7）終止條件的判定。判定算法是否達到要求，如果是，則轉（8），否則轉（4）。

（8）輸出結果和最優的螢火蟲精英個體。

5 仿真結果分析

為了驗證本文提出的量子螢火蟲算法的性能，選擇Sphere函數、Schaffer函數和Rastrigin函數3個典型的基準函數進行測試，并將測試結果與基本粒子群算法進行對比。同時，將本文提出的算法應用于復雜系統可靠性冗余優化問題中，給出了具體的實施方案和優化結果。

仿真實驗環境在Win 7 操作系統下的Matlab R2012b中進行。仿真實驗的具體環境：處理器為Intel（R）Xeon（R）CPU E31225@3.10 GHz；操作系統為64 位Windows 7 旗艦版；編程軟件為Matlab R2012b；內存為4 GB。

5.1 函數測試

（1）Sphere函數

（2）Schaffer函數

（3）Rastrigin 函 數

螢火蟲數目為100，粒子群算法的慣性權重最大值和最小值分別為1和0.4，學習因子為1.47，兩種算法的最大迭代次數為100。為了減小誤差，取10次試驗的平均值作為比較結果。圖1～3分別為3個函數的優化曲線比較圖。

圖1 測試Sphere函數的性能比較圖

在測試Sphere函數時，粒子群算法的優化結果為4.47×10-2，而量子螢火蟲算法的優化結果為7.2×10-3，同時，粒子群算法在第37代時收斂到最小值，量子螢火蟲算法在第28代時收斂到最小值。在測試Schaffer函數時，粒子群算法的優化結果為3.171×10-6，而量子螢火蟲算法的優化結果為1.001 4×10-7，同時，粒子群算法在第25代時收斂到最小值，量子螢火蟲算法在第18代時收斂到最小值。在測試Rastrigin 函數時，兩種算法的測試結果差別更大，粒子群算法的優化結果為3.01×10-2，而量子螢火蟲算法的優化結果為9.794×10-5，其迭代次數分別為38和29。由仿真結果可以發現，量子螢火蟲算法在分析函數優化時具有收斂精度高和魯棒性好的特點。

圖2 測試Schaffer函數的性能比較圖

圖3 測試Rastrigin函數的性能比較圖

5.2 復雜系統冗余優化

將本文提出的量子螢火蟲算法應用于復雜系統可靠性冗余優化的實驗中，利用量子位編碼方式對螢火蟲個體進行編碼，令|Xi（t）>單個螢火蟲的量子空間位置，所優化的復雜系統包括6個子系統，每個子系統有3套可供選擇的實施方案，且冗余數最多不超過2個，每個子系統實施方案的相關參數如表1所示。

表1 子系統實施方案數據表

對復雜系統可靠性冗余度進行優化時，待優化向量θ=[p1，q1，p2，q2，…，p6，q6]T，其中，1≤pi≤2，1≤qi≤3，i=1，2，…，6，種群規模為80，最大迭代次數為200，算法運行的迭代次數與復雜系統可靠性的變化曲線如圖4所示。

圖4 復雜系統可靠性變化曲線

由圖4可見，本文所提出的算法迭代到第16代后就找到最優解，在實驗過程中，將程序運行100次，得出最優解

對應的子系統實施方案與冗余度分配如表2所示。

表2 子系統實施方案與冗余度分配

由表2可知，子系統1～6的可靠度分別為：

6 結語

復雜系統可靠性冗余優化問題具有非線性系統的特點，是典型的NP難題。本文將量子進化計算中的量子位、量子旋轉門等理論與螢火蟲算法相結合，提出一種解決復雜系統可靠性冗余優化問題的量子螢火蟲算法。該算法利用量子位對螢火蟲個體進行編碼，使量子位概率幅與復雜系統函數變量的解空間建立起映射關系，利用量子旋轉門對螢火蟲進行變異和位置更新操作。仿真實驗表明，該算法在解決復雜系統可靠性冗余優化問題時具有良好的性能。