劉 勇， 馬 良

（1.上海理工大學(xué)管理學(xué)院，上海 200093；2.鹽城工學(xué)院基礎(chǔ)教學(xué)部，鹽城 224051）

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

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

1 數(shù)學(xué)模型

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

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

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

2 求解方法

2.1 萬有引力搜索算法

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

2.2 序列二次規(guī)劃

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

2.3 混合算法

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

算法具體步驟如下：

第1步 初始化

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

第2步 計(jì)算物體的質(zhì)量

在時刻t時，物體的質(zhì)量定義為

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

第3步 計(jì)算萬有引力

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

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

第4步 計(jì)算合力

物體i所受的合力為

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

第5步 計(jì)算加速度

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

第6步 更新速度和位置

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

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

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

系統(tǒng)可靠性

系統(tǒng)費(fèi)用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.

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

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

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

表1 模型1的實(shí)驗(yàn)結(jié)果Tab.1 Computing results for model 1

表2 模型2的實(shí)驗(yàn)結(jié)果Tab.2 Computing results for model 2

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

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

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

4 結(jié) 語

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

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

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

［3］ 肖人彬，陶振武.群集智能研究進(jìn)展［J］.管理科學(xué)學(xué)報(bào)，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］ 許傳玉，朱若男，梁穎虹，等.遺傳算法在復(fù)雜系統(tǒng)可靠性優(yōu)化中的應(yīng)用［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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］.北京：科學(xué)出版社，2008.

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

［13］ 曾建潮，介婧，崔志華.微粒群算法［M］.北京：科學(xué)出版社，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.