劉 勇， 馬 良

（1.上海理工大學管理學院，上海 200093；2.鹽城工學院基礎教學部，鹽城 224051）

可靠性問題是系統(tǒng)設計、研究和運行過程中的一個重要因素，可靠性的高低直接影響系統(tǒng)的性能.若可靠性達不到相應的指標要求，系統(tǒng)越復雜出故障的可能性越大，造成的損失也越大［1］.因此，如何對復雜系統(tǒng)可靠性進行優(yōu)化已成為一個重要的研究課題.所謂復雜系統(tǒng)可靠性優(yōu)化是指在滿足一定的可靠性指標要求下使投資費用最小或在一定的資源約束條件下使系統(tǒng)的可靠度達到最大.由于其目標函數(shù)和約束條件都是非線性的，而且目標函數(shù)通常都是具有多個局部極值的函數(shù)，這些給問題的求解帶來了一定的困難.采用傳統(tǒng)的優(yōu)化算法求解往往達不到全局最優(yōu)，解決此類問題難度較大.近年來，智能算法在求解很多復雜困難的優(yōu)化問題中表現(xiàn)出良好的性能，已成為一個研究熱點［2－3］.目前用于復雜系統(tǒng)可靠性優(yōu)化的智能算法有模擬退火算法［4］、遺傳算法［5］、蟻群算法［6］等.這些算法在一定程度上可求解復雜系統(tǒng)可靠性優(yōu)化問題，但算法都存在著各自的局限性，求解質量有待進一步改進.因此，探尋有效的求解方法頗為重要.

基本萬有引力搜索算法是一種新的基于群體智能的優(yōu)化算法，由Rashedi等［7］在2009年提出.算法具有操作簡單，參數(shù)設置少等特點，并在優(yōu)化benchmark函數(shù)時表現(xiàn)出較好的性能.但研究表明，萬有引力搜索算法全局搜索能力較強，可局部搜索優(yōu)化能力較弱，易早熟收斂.為解決這一不足，本文將序列二次規(guī)劃算法引入算法中，提出一種混合萬有引力搜索算法.利用萬有引力搜索算法尋找全局最優(yōu)解，并利用序列二次規(guī)劃算法進行局部搜索，實現(xiàn)全局探索和局部開發(fā)能力的平衡，避免基本萬有引力搜索算法陷入局部極值.將算法用于求解復雜系統(tǒng)可靠性優(yōu)化問題，通過數(shù)值實驗和與現(xiàn)有智能算法的比較，表明算法可行有效.

1 數(shù)學模型

考慮一類典型的復雜系統(tǒng)可靠性優(yōu)化問題［4－6］，對于一個給定的系統(tǒng)，在滿足一定的可靠性約束條件下，通過為每一個子系統(tǒng)或部件選擇合適的可靠性，使系統(tǒng)費用最小.

式中，Cs為系統(tǒng)費用；Ri，Ri，min為部件可靠性和部件可靠性下界；Rs，Rs，min為系統(tǒng)可靠性和系統(tǒng)可靠性下界.

上述模型中，目標函數(shù)和約束函數(shù)均為非線性，而且目標函數(shù)具有多個局部極值，給尋找全局最優(yōu)解帶來了困難.解決這類問題，智能優(yōu)化算法效果顯著.因此，本文設計了一種混合萬有引力搜索算法的求解方法.

2 求解方法

2.1 萬有引力搜索算法

萬有引力搜索算法（gravitational search algorithm，GSA）是由Rashedi等提出的，是一種模擬萬有引力規(guī)律的智能優(yōu)化算法.算法將優(yōu)化問題的解視為一組在空間運行的物體，物體之間通過萬有引力作用相互吸引，物體運動遵循動力學規(guī)律，萬有引力的作用使得物體朝著質量最大的物體移動，而最大質量的物體占據(jù)最優(yōu)位置，從而可求出優(yōu)化問題的最優(yōu)解.算法通過個體間的萬有引力相互作用實現(xiàn)優(yōu)化信息的共享，引導群體向最優(yōu)解區(qū)域搜索.進一步研究發(fā)現(xiàn)，在迭代的早期，算法具有較好的尋優(yōu)性能，但在后期算法會出現(xiàn)在局部最優(yōu)解附近“振蕩”的現(xiàn)象，趨同化嚴重，易早熟收斂.

2.2 序列二次規(guī)劃

序列二次規(guī)劃（sequential quadratic programming，SQP）最初由Wilson于1963年提出，是解無約束優(yōu)化問題的牛頓法和擬牛頓法對約束優(yōu)化問題的推廣，具體是通過求解一系列二次規(guī)劃的子問題逐步得到原問題的最優(yōu)解［8］.目前SQP算法是非線性約束優(yōu)化研究中一個十分活躍的領域.SQP具有保持局部超一次收斂等特性，但不足之處是在優(yōu)化有多個局部極值的目標函數(shù)時，對初始點的選取非常敏感，若選擇不當會極大影響算法的性能［9－10］.

2.3 混合算法

基于萬有引力搜索算法和序列二次規(guī)劃各自的特點，提出一種混合萬有引力搜索算法（hybrid gravitational search algorithm，HGSA）.算法首先利用萬有引力搜索算法進行全局搜索，保存當前的最優(yōu)位置，利用該最優(yōu)位置作為SQP算法迭代的初始點，利用SQP進行局部搜索，有利于算法跳出局部極值，使算法全局搜索和局部開發(fā)的能力達到平衡.同時在當前最好位置附近進行局部搜索，找到全局最優(yōu)點的可能性增大，加快算法尋優(yōu)速度.

算法具體步驟如下：

第1步 初始化

考慮由N個物體組成的系統(tǒng)，每個物體定義在D維搜索空間中，物體的位置代表優(yōu)化問題的解.第i個物體的位置定義為

第2步 計算物體的質量

在時刻t時，物體的質量定義為

式中，fiti（t），Mi（t）分別為在時刻t時第i個物體的函數(shù)值和質量；best（t），worst（t）分別為在時刻t時所有物體中最優(yōu)函數(shù)值和最差函數(shù)值，對最小化問題其定義為

第3步 計算萬有引力

物體i和j之間的萬有引力定義為

式中，G（t）為在時刻t時萬有引力常數(shù)，在算法中隨著t逐漸減?。籖ij（t）為物體i和j之間歐式距離；ε為一常數(shù)，防止分母為零.

第4步 計算合力

物體i所受的合力為

式中，randj為在［0，1］之間的一個隨機數(shù).

第5步 計算加速度

根據(jù)牛頓運動定律，在時刻t物體i在第d維的加速度為

第6步 更新速度和位置

物體i速度和位置的更新方程為

式中，randi表示在［0，1］之間的一個隨機數(shù).

第7步 以當前群體的最優(yōu)位置Lbest作為初始點，利用SQP方法進行搜索.

第8步 如果沒有達到最大迭代次數(shù)，轉第2步；否則，停止計算，輸出當前的最優(yōu)解.

由上述算法步驟很容易得到算法的時間復雜度，設群體規(guī)模為N，問題規(guī)模為D，最大迭代次數(shù)為T.基本萬有引力搜索算法的主要操作是計算質量、計算引力、更新加速度及速度和位置，時間復雜度為O（T×N×D）.混合萬有引力搜索算法增加的操作是利用SQP進行局部搜索，設其最大迭代次數(shù)為Maxiter，則混合算法的時間復雜度為O（T×N ×D）＋O（T×Maxiter），第2項的時間復雜度比第1項小的多，因此在計算時間方面混合算法不會比基本萬有引力搜索算法有顯著增加.

3 數(shù)值實驗

采用一種典型的復雜系統(tǒng)——非串聯(lián)－并聯(lián)系統(tǒng)［4－6］進行分析，系統(tǒng)結構如圖1所示.

圖1 非串聯(lián)-并聯(lián)系統(tǒng)Fig.1 Non－Series－Parallel Systems

系統(tǒng)可靠性

系統(tǒng)費用Cs有兩種形式：

其中，k1＝1，k2＝100，k3＝200，k4＝150，α1＝α2＝α3＝α4＝0.6，Ri，min＝0.5，Rs，min＝0.9.

其中，k1＝25，k2＝25，k3＝50，k4＝37.5，α1＝α2＝α3＝α4＝1，Ri，min＝0.5，Rs，min＝0.99.

在求解上述模型時，先將問題轉換為無約束優(yōu)化問題的形式.罰函數(shù)的形式一般為和的形式、和的平方形式及乘積形式等.為方便起見，本文采用和的形式，這樣在計算過程中可直接考慮對目標函數(shù)的優(yōu)化，可行性的要求由罰函數(shù)的作用來強制其滿足.

采用混合萬有引力搜索算法（hybrid gravitational search algorithm，HGSA）進行求解，并與蟻群優(yōu)化算法［11－12］（ant colony optimization algorithm，ACO）、微粒群算法［13］（particle swarm optimization algorithm，PSO）、人工蜂群算法［14－15］（artificial bee colony algorithm，ABC）的求解性能進行比較.ACO和PSO屬于經(jīng)典的智能優(yōu)化算法，ABC是最近提出的一種新的智能算法，這3種算法已成功用于求解很多復雜困難的優(yōu)化問題，有關這3種算法的詳細信息可參考文獻［11－15］.

本文算法采用Matlab 7.1語言編程實現(xiàn)，在Windows XP操作系統(tǒng)中，CPU為P4 2.4GHz和內(nèi)存為1G的計算機上運行.為方便起見，5種算法設置相同的群體規(guī)模和最大迭代次數(shù)，群體規(guī)模和最大迭代次數(shù)均為50.在ACO算法中，信息啟發(fā)因子α＝1，能見度因子β＝1，軌跡的持久性參數(shù)ρ＝0.7，信息素常數(shù)Q＝1；在PSO算法中，學習因子c1＝c2＝2，慣性權重w從0.9線性遞減到0.2；在ABC算法中，引領蜂規(guī)模和跟隨蜂的規(guī)模均為25，偵察蜂規(guī)模為1，閾值limit＝100，采用輪盤賭的選擇機制；GSA算法和HGSA算法參數(shù)設置相同：萬有引力常數(shù)G隨迭代次數(shù)遞減，即G（t）＝其中G0＝100，α＝1，t表示當前迭代次數(shù).每個算例獨立運行20次并統(tǒng)計最優(yōu)結果，具體結果如表1和表2所示.

表1 模型1的實驗結果Tab.1 Computing results for model 1

表2 模型2的實驗結果Tab.2 Computing results for model 2

由表1和表2可知，對模型1而言，HGSA算法的最優(yōu)結果小于ABC算法結果，遠小于GSA算法、PSO算法及ACO算法的結果；對模型2而言，HGSA算法的最好結果小于PSO算法的結果，比GSA算法、ABC算法及ACO算法的結果小的多.HGSA算法表現(xiàn)出較高的優(yōu)化精度，為進一步分析算法的性能，圖2給出了5種算法的尋優(yōu)曲線圖.

圖2 尋優(yōu)曲線圖Fig.2 The varying curves

由圖2可知，在這5種算法中，HGSA算法具有最快的優(yōu)化速度，算法只需很少的迭代次數(shù)就能達到最優(yōu)并趨向穩(wěn)定，算法具有較好的穩(wěn)定性.HGSA算法在優(yōu)化精度和尋優(yōu)速度兩方面均表現(xiàn)優(yōu)異.分析原因，基本GSA算法全局搜索能力強，局部搜索能力弱，HGSA算法中嵌入了SQP算法，改善局部搜索能力，能避免算法早熟收斂，實現(xiàn)全局探索和局部開發(fā)能力的平衡，提高優(yōu)化性能.

4 結 語

復雜系統(tǒng)可靠性優(yōu)化是一個復雜的優(yōu)化問題，將萬有引力搜索算法和SQP算法結合，提出一種求解系統(tǒng)可靠性優(yōu)化問題的混合算法.將算法用于求解一類典型的復雜系統(tǒng)可靠性優(yōu)化模型，并與蟻群算法、微粒群算法、人工蜂群算法、基本萬有引力搜索算法進行比較.實驗結果表明，本文提出的算法具有較高的求解精度和較快的優(yōu)化速度，為該類問題的求解提供了一個新的有競爭力的方法.將算法用于可靠性網(wǎng)絡優(yōu)化是下一階段的研究工作.

［1］ 宋何維.系統(tǒng)可靠性設計與分析［M］.西安：西北工業(yè)大學出版社，2008.

［2］ 邢文訓，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京：清華大學出版社，2005.

［3］ 肖人彬，陶振武.群集智能研究進展［J］.管理科學學報，2007，10（3）：80－96.

［4］ Ravi V，Murty B S N，Reddy P J.Nonequilibrium simulated annealing algorithm applied to reliability optimization of complex systems［J］.IEEE Transactions on Reliability，1997，46：233－239.

［5］ 許傳玉，朱若男，梁穎虹，等.遺傳算法在復雜系統(tǒng)可靠性優(yōu)化中的應用［J］.哈爾濱理工大學學報，2000，5（3）：90－93.

［6］ Shelokar P S，Jayaraman V K，Kulkarni B D.Ant algorithm for single and multiobjective reliability optimization problems［J］.Quality and Engineering International，2002，18：497－514.

［7］ Rashedi E，Nezamabadi－pour H，Saryazdi S.GSA：a gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232－2248.

［8］ Fletcher R.Practical methods of optimization［M］.New York：Wiley，1987.

［9］ Boggs P T，Tolle J W.Sequential quadratic programming［J］.Acta Numerica，1995，4：1－51.

［10］ Michael B B.Sequential quadratic programming［J］.Springer Optimization and Its Application，2008，19：1－14.

［11］ 馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京：科學出版社，2008.

［12］ 劉士新，宋健海，唐加福.蟻群最優(yōu)化——模型、算法及應用綜述［J］.系統(tǒng)工程學報，2004，19（5）：496－502.

［13］ 曾建潮，介婧，崔志華.微粒群算法［M］.北京：科學出版社，2004.

［14］ Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）：459－471.

［15］ Karaboga D，Basturk B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）：687－697.