多學(xué)科設(shè)計(jì)優(yōu)化中的智能算法比較

摘要：對(duì)多學(xué)科設(shè)計(jì)優(yōu)化領(lǐng)域中涉及的幾種智能優(yōu)化算法的特點(diǎn)進(jìn)行了總結(jié)。在此基礎(chǔ)上提出了時(shí)間、精度、解決問題的個(gè)數(shù)等幾個(gè)比較指標(biāo)，首次將精度作為比較指標(biāo)，并且創(chuàng)新性地提出一個(gè)針對(duì)工程問題的有效比較指標(biāo)，即短時(shí)尋優(yōu)能力。通過對(duì)所選取的系列案例運(yùn)行得到一系列對(duì)工程問題有指導(dǎo)意義的結(jié)論，手機(jī)實(shí)例驗(yàn)證了所得到的結(jié)論的正確性。

關(guān)鍵詞：智能算法；多學(xué)科設(shè)計(jì)優(yōu)化；短時(shí)尋優(yōu)能力

中圖分類號(hào)：TH122；TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0093－03

多學(xué)科設(shè)計(jì)優(yōu)化(MDO)于20世紀(jì)80年代作為一個(gè)新的研究領(lǐng)域誕生，其主要是對(duì)相互影響、相互作用的子系統(tǒng)組成的復(fù)雜工程系統(tǒng)進(jìn)行設(shè)計(jì)，以使系統(tǒng)的綜合性能達(dá)到最優(yōu)的一種設(shè)計(jì)方法。它是算法研究的一個(gè)重要應(yīng)用領(lǐng)域。在設(shè)計(jì)優(yōu)化的過程中，算法選取的好壞直接關(guān)系到優(yōu)化過程的效率和優(yōu)化結(jié)果的準(zhǔn)確性。MDO中經(jīng)常用于優(yōu)化的算法有梯度法、序列二次規(guī)劃法、懲罰函數(shù)法、遺傳算法、模擬退火算法等，這些算法在解決實(shí)際問題中的表現(xiàn)各有所長(zhǎng)。對(duì)于一個(gè)具體問題，最重要的是如何選擇一個(gè)最適合該問題的研究算法，如在最短時(shí)間內(nèi)得到最優(yōu)解或求滿足一定精度要求的解等。不同的條件要求所采用的算法是不同的。目前專門針對(duì)算法比較的文章很少，并且對(duì)算法的研究方法大部分還停留在定性分析上，分析的角度各不相同，沒有統(tǒng)一的標(biāo)準(zhǔn)。文獻(xiàn)[1~3]對(duì)數(shù)值算法有一定的比較研究，但是比較的結(jié)果因?yàn)橄抻诠こ虒?shí)例的選取以及當(dāng)時(shí)硬件條件的限制，已經(jīng)對(duì)現(xiàn)在高精度、高要求的計(jì)算沒有很好的指導(dǎo)意義。對(duì)于智能算法的比較，除了有文章針對(duì)特定案例分析了各種方法的利弊外，目前還沒有文章對(duì)其進(jìn)行過綜合性的研究；并且在研究智能算法比較的方面，還沒有一個(gè)被大家所公認(rèn)的衡量標(biāo)準(zhǔn)。隨著對(duì)智能算法研究的深入以及智能算法在MDO中日益廣泛的應(yīng)用，很有必要對(duì)其加以比較研究，得出有真正指導(dǎo)意義的比較結(jié)果。

1算法特點(diǎn)

根據(jù)MDO領(lǐng)域中常用軟件對(duì)智能算法的總結(jié)和歸納，MDO中涉及的常用智能算法主要包括以下幾種：

a）模擬退火算法（adaptive simulated annealing，ASA）[4]。它是基于Mente Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程和一般組合優(yōu)化問題之間的相似性。它是一種通用的優(yōu)化算法。

b）遺傳算法（genetic algorithms，GA）[5]。它是受生物進(jìn)化論的啟發(fā)而提出的。它將問題的求解表示成染色體的適者生存過程，通過染色體群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到最適應(yīng)環(huán)境的個(gè)體，從而求得問題的最優(yōu)解或滿意解。

MDO環(huán)境下的常用軟件中涉及的與遺傳算法有關(guān)的算法主要有以下幾種：

a）多島遺傳算法（multi island genetic algorithm，MIGA）。它將一個(gè)單一的種群分成幾個(gè)獨(dú)立的島嶼，從而增加個(gè)體的多樣性，提高了全局的搜尋能力并改進(jìn)了收斂效率。

b）鄰域培植遺傳算法（neighborhood cultivation genetic algorithm，NCGA）。其交叉操作基于近鄰培養(yǎng)機(jī)制。

c）非支配解排序遺傳算法（non dominated sorting genetic algorithm，NSGA Ⅱ）。將計(jì)算復(fù)雜度由NSGA的O（nN3）降到O（mN2）。其中：m表示目標(biāo)函數(shù)的數(shù)目；N表示種群中的個(gè)體數(shù)目。其擴(kuò)大了采樣空間，可迅速提高種群整體水平。

在文獻(xiàn)[6]的基礎(chǔ)上作了一些增刪，歸納出這幾種算法的特點(diǎn)，如表1所示。

其中：“1”表示該算法具有這種特征。從表1可以看出，這幾種智能算法的特點(diǎn)非常類似：普遍對(duì)多約束、高度非線性問題不適應(yīng)；不適合解決大規(guī)模的復(fù)雜優(yōu)化問題，對(duì)問題的約束條件要求較松；對(duì)數(shù)值算法要求嚴(yán)格的K T條件沒有限制；對(duì)變量類型沒有特殊要求。若要選擇具體的算法，該表格明顯不能提供足夠的依據(jù)，還需要一些具體指標(biāo)來對(duì)算法的性能加以評(píng)判。

2算法比較指標(biāo)

算法的比較是相對(duì)的。文獻(xiàn)[7]中提到優(yōu)化問題沒有免費(fèi)的午餐定理。這個(gè)定理在某種程度上說明了沒有一種方法對(duì)解決所有問題來說都是最好的，對(duì)于一個(gè)特定的問題或某一類問題可以有針對(duì)此類問題相對(duì)較好的解決途徑。鑒于算法比較的這些特點(diǎn)，本文提出了以下幾個(gè)方面的比較指標(biāo)，以期對(duì)算法選擇有一定的指導(dǎo)意義。

1）短時(shí)尋優(yōu)能力鑒于工程實(shí)踐中的問題比較復(fù)雜、運(yùn)行時(shí)間十分漫長(zhǎng)，許多工程實(shí)際問題所關(guān)心的焦點(diǎn)往往是在短時(shí)間內(nèi)得到滿意的解區(qū)間，而不是耗費(fèi)大量時(shí)間求得問題的最終收斂最優(yōu)解。

智能算法涉及的參數(shù)較多，方法不同、參數(shù)不同。因此需要首先定位一個(gè)基準(zhǔn)，起到為其他算法參數(shù)調(diào)整提供參照物的作用。為此，本文使用了ASA作為標(biāo)準(zhǔn)算法來嘗試參數(shù)的設(shè)置。因?yàn)锳SA的基本設(shè)置中僅需要改動(dòng)最大生成設(shè)計(jì)個(gè)數(shù)即可對(duì)算法結(jié)果產(chǎn)生影響，易于控制。

本文使用的具體參數(shù)設(shè)置步驟如下：

a）使用ASA作為優(yōu)化器，根據(jù)每個(gè)案例優(yōu)化運(yùn)行周期長(zhǎng)短將最大生成設(shè)計(jì)個(gè)數(shù)設(shè)為200~500的數(shù)值，其他參數(shù)可以適當(dāng)微調(diào)。運(yùn)行案例得到優(yōu)化后的結(jié)果。

b）將運(yùn)行結(jié)果與案例文檔提供的結(jié)果進(jìn)行比較。如果結(jié)果滿意（優(yōu)于或至少相差不多，如10%）則保留設(shè)置，跳轉(zhuǎn)到d）；否則轉(zhuǎn)到c)繼續(xù)執(zhí)行。

c)調(diào)整ASA參數(shù)，主要是增加最大運(yùn)行次數(shù)，運(yùn)行優(yōu)化過程得到結(jié)果并轉(zhuǎn)到b)。

d)根據(jù)ASA的最大運(yùn)行次數(shù)設(shè)置，分別調(diào)整其他三種算法的參數(shù)設(shè)置，使其最大運(yùn)行次數(shù)與ASA大致相仿。

e)將算法結(jié)果與案例文檔提供的結(jié)果比較。如果能得到可行解且不相差過大（數(shù)量級(jí)差距）則保留設(shè)置，記錄結(jié)果；否則轉(zhuǎn)回d）。

3）解決問題的個(gè)數(shù)它是指同一算法解決不同案例所最終能夠求得的最優(yōu)解的案例個(gè)數(shù)。較好的算法應(yīng)該可以在盡可能短的時(shí)間內(nèi)解決盡可能多的問題。為了反映這一需求，將相對(duì)時(shí)間分段，如用ni表示某種算法在某一相對(duì)時(shí)間段內(nèi)解決問題的個(gè)數(shù)，這樣就建立了相對(duì)運(yùn)行時(shí)間和解決問題個(gè)數(shù)的關(guān)系。

4）精度沒有精度的比較是沒有意義的比較。精度要求對(duì)時(shí)間的影響很大。一般來說，在相同的運(yùn)行環(huán)境下，要求的精度越高，算法運(yùn)行所需要的時(shí)間越長(zhǎng)。目前，常用的有兩種精度選取標(biāo)準(zhǔn)：目標(biāo)函數(shù)的相對(duì)精度和設(shè)計(jì)變量的相對(duì)精度。目標(biāo)函數(shù)的相對(duì)精度表示了設(shè)計(jì)的優(yōu)劣，而工程界關(guān)注的是最終的設(shè)計(jì)成果，因此采用目標(biāo)函數(shù)的相對(duì)精度作為評(píng)判標(biāo)準(zhǔn)。當(dāng)f(x)=0時(shí)，εf=f(x)；當(dāng)f(x)≠0時(shí)，εf=[f(x)-f(x)]/f(x)。其中：f(x)是目標(biāo)函數(shù)的理想值，可以取所有算法得到的最優(yōu)值中的最小值；f(x)是某個(gè)算法得到的目標(biāo)函數(shù)值。

3案例的選擇及描述

案例的選擇對(duì)算法比較有很大的影響。由于是在MDO框架下研究智能算法，所選取的測(cè)試問題必須符合MDO研究對(duì)象的特點(diǎn)，即多變量、多學(xué)科等，單一的測(cè)試問題不能滿足測(cè)試多樣性的要求。為了較全面地反映研究算法的性能，根據(jù)前述各算法的特點(diǎn)，本文選擇了12個(gè)案例，在變量個(gè)數(shù)、約束個(gè)數(shù)、約束類型等方面都覆蓋得比較全面。有關(guān)12個(gè)案例的特點(diǎn)描述如表2所示。

4數(shù)據(jù)收集與整理

并不是所選的案例都具有研究意義，也并不是所有的算法對(duì)每個(gè)案例都有效。為了確定所收集數(shù)據(jù)的有效性，剔除無(wú)效案例和算法，對(duì)案例的有效性和算法有效性定義如下：

對(duì)某個(gè)確定算法，如果對(duì)于同一個(gè)案例，有兩種及以上算法所求出的答案基本一致，該案例視為有效案例；否則將該案例剔除。

對(duì)某個(gè)確定案例，若某種算法無(wú)法計(jì)算得出優(yōu)化值的算法，或該算法求解的目標(biāo)函數(shù)相對(duì)精度大于0.1時(shí)，則認(rèn)為該案例無(wú)效，將其剔除。

根據(jù)事先的策略要求，最終得到三個(gè)數(shù)據(jù)表格：一個(gè)是短時(shí)尋優(yōu)能力指標(biāo)需要的參數(shù)調(diào)整對(duì)應(yīng)的結(jié)果表（表3中列出了兩組典型數(shù)據(jù)）；另外兩個(gè)是原始數(shù)據(jù)表，分別是絕對(duì)時(shí)間表和目標(biāo)函數(shù)值表。分別以這兩個(gè)表為依據(jù)可以得到相對(duì)時(shí)間數(shù)據(jù)表和運(yùn)行精度數(shù)據(jù)表，根據(jù)這些數(shù)據(jù)繪制出兩個(gè)曲線圖，如圖1和2所示。因?yàn)榭v坐標(biāo)采用的是所采集數(shù)據(jù)的倒數(shù)，所以圖1和2中，越靠近原點(diǎn)的區(qū)域表示結(jié)果越理想。

上述曲線圖和案例運(yùn)行后得到的一系列數(shù)據(jù)表都將作為算法比較的依據(jù)。

5案例研究

以手機(jī)的造型設(shè)計(jì)和動(dòng)力學(xué)分析實(shí)例為例來驗(yàn)證本文結(jié)論的正確性。手機(jī)模型如圖3所示。

從表4可以看到，NSGA Ⅱ算法的精度較高（因?yàn)椴捎孟鄬?duì)精度，故精度最高的算法對(duì)應(yīng)的相對(duì)精度是0）。表5表明算法ASA具有優(yōu)秀的短時(shí)尋優(yōu)能力，運(yùn)行時(shí)間最短，但結(jié)果也是最優(yōu)的。

6結(jié)束語(yǔ)

本文對(duì)智能優(yōu)化算法的比較問題進(jìn)行了探索性的研究，通過對(duì)所得到的數(shù)據(jù)及案例進(jìn)行分析可以得到如下結(jié)論： 

a）ASA具有較其他幾種算法更出色的短時(shí)尋優(yōu)能力。因此，對(duì)于復(fù)雜的工程問題，可以首先采用此算法快速捕捉到一個(gè)較小的解區(qū)間，如要進(jìn)一步尋找最優(yōu)解，可采用其他方法加快尋優(yōu)速度。

b）就運(yùn)行時(shí)間、精度和解決問題個(gè)數(shù)三方面綜合考慮，在算法選擇上可以優(yōu)先考慮ASA和MIGA。尤其對(duì)高度非線性優(yōu)化問題，ASA表現(xiàn)出了比預(yù)期更好的魯棒性。

c）僅就精度而言，算法NSGA Ⅱ的精度較高；其次是NCGA；然后依次是ASA和MIGA。

d）NSGA Ⅱ?qū)τ谧兞看笥?00的多設(shè)計(jì)變量問題無(wú)效。

本文所有的結(jié)果是在易擎公司所提供的iSIGHT軟件環(huán)境下運(yùn)行得到的。另外，本文只選取了具有典型意義的12個(gè)案例。案例個(gè)數(shù)的多寡對(duì)于基礎(chǔ)數(shù)據(jù)的累積統(tǒng)計(jì)會(huì)帶來不同程度的影響。本文今后將嘗試在不同的軟件環(huán)境、在更多的案例支持下繼續(xù)完善所得到的結(jié)論。

參考文獻(xiàn)：

［1］COLVILLEA R.A comparative study of nonlinear programming codes，320 2949[R].New York:IBM New York Scientific Center，1968.

[2]EASON E D，F(xiàn)ENTON R G.Testing and evaluation of numerical methods for design optimization，UTME TP 7204[R].Toronto:University of Toronto， 1972.

[3]SAND G E，RAGSDELL K M.The utility of nonlinear programming algorithms:a comparative study[J].ASME Journal of Mechanical Design，1980，102(3): 540－551.

[4]王凌.智能優(yōu)化算法及其應(yīng)用[M]. 北京：清華大學(xué)出版社，2004：17－35.

[5]玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].于歆杰，等譯.北京：清華大學(xué)出版社，2004：76－99.

[6]iSIGHT reference guide[K].Beijing:Sightna Corporation，2002.

[7]GRIFFITHS E J，ORPONEN P.Optimization， block designs and no free lunch theorems， short communication[J].Information Proces sing Letters，2005，94(2):55－61.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”