多目標(biāo)模擬退火算法及其應(yīng)用研究進(jìn)展＊

李金忠，夏潔武，曾小薈，曾勁濤，劉新明，冷 明，孫凌宇

（井岡山大學(xué)電子與信息工程學(xué)院，江西 吉安343009）

1 引言

模擬退火SA（Simulated Annealing）算法［1］是由Kirkpatrick等于1983年首次提出的一種求解大規(guī)模組合優(yōu)化問題的有效算法，該算法是基于Monte Carlo迭代求解策略的隨機(jī)尋優(yōu)算法，源于熱力學(xué)中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性，在一給定初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解。因SA獨(dú)特的優(yōu)化機(jī)制及其對(duì)問題信息依賴較少，通用性、靈活性較強(qiáng)而在優(yōu)化領(lǐng)域得到了廣泛的應(yīng)用，其在多目標(biāo)優(yōu)化領(lǐng)域的研究近年來也得到了一定的發(fā)展。傳統(tǒng)的SA算法只針對(duì)單個(gè)優(yōu)化目標(biāo)進(jìn)行求解，解的優(yōu)劣很容易比較，而在多目標(biāo)問題中，各個(gè)目標(biāo)可能是相互沖突的或者相互獨(dú)立的，無法像單目標(biāo)問題的解那樣直接進(jìn)行優(yōu)劣比較。近若干年來也有一些研究成果結(jié)合多目標(biāo)優(yōu)化問題的特性，根據(jù)SA的思想，設(shè)計(jì)多目標(biāo)模擬退火算法，用來解決多目標(biāo)優(yōu)化問題。多目標(biāo)模擬退火MOSA（Multi－Objective Simulated Annealing）算法的研究始于1985年，早期的工作還包括Ulungu等和Serafini等［2］設(shè)計(jì)的一個(gè)完整的MOSA，并將其應(yīng)用于多目標(biāo)組合優(yōu)化問題。由于物體退火與多目標(biāo)優(yōu)化問題之間的本質(zhì)聯(lián)系，SA適合擴(kuò)展并應(yīng)用于多目標(biāo)優(yōu)化問題的求解。MOSA的出現(xiàn)為多目標(biāo)優(yōu)化問題的求解開辟了一條新的途徑，在多目標(biāo)優(yōu)化算法中也已表現(xiàn)出良好的性能和前景。

2 MOSA算法基本框架

當(dāng)前，已有多種MOSA算法被提出，根據(jù)近二十年來不同研究者所設(shè)計(jì)的 MOSA算法［2～23］，本文對(duì)MOSA算法進(jìn)行了歸納，統(tǒng)一于基本框架內(nèi)?；綧OSA算法描述如下：

步驟1 對(duì)算法的相關(guān)參數(shù)進(jìn)行初始化，如初始溫度、迭代次數(shù)等。

步驟2 隨機(jī)產(chǎn)生初始解X，計(jì)算其所有目標(biāo)函數(shù)值并將其加入到Pareto解集中。

步驟3 給定一種隨機(jī)擾動(dòng)，產(chǎn)生X的鄰域解Y，計(jì)算其所有目標(biāo)函數(shù)值。

步驟4 比較新產(chǎn)生的鄰域解Y與Pareto解集中的每個(gè)解并更新Pareto解集。

步驟5 如果新鄰域解Y進(jìn)入Pareto解集，則用Y替代X，并轉(zhuǎn)到步驟8。

步驟6 按某種方法計(jì)算接受概率。

步驟7 如果Y未進(jìn)入Pareto解集，則根據(jù)接受概率決定是否接受新解，如果新解被接受，則令其為新的當(dāng)前解X，如果新解未被接受，則保留當(dāng)前解。

步驟8 每隔一定迭代次數(shù)，從Pareto解集中隨機(jī)選擇一個(gè)解，作為初始解，重新搜索。

步驟9 采取某種降溫策略，執(zhí)行一次降溫。

步驟10 重復(fù)步驟3～步驟9，直到達(dá)到最低溫度，輸出結(jié)果，算法結(jié)束。

3 典型MOSA算法分析

在20世紀(jì)90年代，國際上關(guān)于MOSA算法的文獻(xiàn)較多，雖然最近幾年也發(fā)展了一些MOSA算法，但目前主要是應(yīng)用MOSA算法解決具體問題。本文將闡述幾種典型的MOSA算法。由于SA算法設(shè)計(jì)的關(guān)鍵是接受準(zhǔn)則和冷卻進(jìn)度表［2，3］，因此，本文將重點(diǎn)討論多目標(biāo)條件下如何設(shè)計(jì)接受準(zhǔn)則和冷卻進(jìn)度表，并對(duì)各種方法進(jìn)行分析。

3.1 UMOSA

UMOSA［4，5］算法使用加權(quán)聚合法將多維標(biāo)準(zhǔn)空間映射到一維標(biāo)準(zhǔn)空間，它構(gòu)建了一個(gè)潛在有效解列表，這些解不被任何其他產(chǎn)生的解所支配。根據(jù)決策者的選擇，UMOSA算法適應(yīng)于通過交互方式產(chǎn)生滿意的結(jié)果給決策者。對(duì)單目標(biāo)優(yōu)化問題，壞解的接受概率是唯一和無二義性的，而對(duì)于多目標(biāo)優(yōu)化問題，從當(dāng)前位置移動(dòng)到新位置存在三種可能：（1）新解的所有目標(biāo)都得到了改進(jìn)，即新解支配當(dāng)前解，以概率1接受；（2）新解的某些目標(biāo)函數(shù)得到了改進(jìn)，而另一些目標(biāo)函數(shù)變差了，即新解和當(dāng)前解彼此不受支配，此時(shí)所提出的策略必須能區(qū)分這些彼此不受支配的解；（3）新解的所有目標(biāo)函數(shù)都變差了，即當(dāng)前解支配新解，此時(shí)，接受概率必須考慮當(dāng)前解和新解之間的距離。Ulungu等使用加權(quán)聚合法綜合考慮了以上三種情況，提出了一種新的接受準(zhǔn)則：

其 中，Δs ＝s（f（y），λ）－s（f（x），λ），s（F，λ）＝為權(quán)重向量。

UMOSA算法在計(jì)算接受概率時(shí)僅僅考慮新解與當(dāng)前解之間的直接比較，導(dǎo)致一些良好的新解在搜索過程中可能被拒絕，于是 Haidine等［6］在UMOSA算法的基礎(chǔ)上，提出了一種多情形的多目標(biāo)模擬退火算法MC－MOSA。該算法改變了原算法的接受準(zhǔn)則，分多種情形計(jì)算接受概率（其計(jì)算方法詳見文獻(xiàn)［6］），從而改善了UMOSA算法，獲得了更好的性能，可產(chǎn)生更多能到達(dá)Pareto前沿的解。同時(shí)，作者也提出了MC－MOSA算法的三種變體：重復(fù)退火 MC－MOSA、快速退火 MCMOSA、兩階段退火MC－MOSA。

3.2 PSA

Czyzak等［7］對(duì)UMOSA算法進(jìn)行修改，提出了Pareto模擬退火算法PSA。為了改變目標(biāo)函數(shù)的接受概率，該算法在每一次迭代中，用一系列稱為產(chǎn)生樣本的解來控制目標(biāo)函數(shù)權(quán)重的大小。如果沒有一個(gè)最靠近樣本x的非劣解x′或者對(duì)x進(jìn)行第一次迭代，則設(shè)置隨機(jī)權(quán)值?λi≥0，∑λi＝1；否則，對(duì)每個(gè)目標(biāo)函數(shù)fi，設(shè)置其權(quán)值為：

其中，α＞1。

通過對(duì)權(quán)重大小的控制，可以增加或降低某個(gè)特定目標(biāo)的接受概率，從而保證所產(chǎn)生的解具有良好的多樣性。PSA算法是以概率p ＝ min（1，接受新解。

上述MOSA算法是先按照加權(quán)聚合法對(duì)多個(gè)要優(yōu)化的目標(biāo)進(jìn)行聚合，然后依據(jù)單目標(biāo)SA算法進(jìn)行求解。所謂加權(quán)聚合法是對(duì)要優(yōu)化的每個(gè)目標(biāo)，依據(jù)不同目標(biāo)的重要性分別賦予一個(gè)權(quán)重，通過對(duì)所有目標(biāo)加權(quán)聚合到一個(gè)目標(biāo)函數(shù)中，將多目標(biāo)優(yōu)化問題轉(zhuǎn)換成單目標(biāo)優(yōu)化問題。這是一種先決策后搜索的尋優(yōu)模式，本質(zhì)上仍然屬于單目標(biāo)優(yōu)化。這種方法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、易于使用，計(jì)算效率比較高，同時(shí)可以得到一個(gè)很好的優(yōu)化解；缺點(diǎn)是帶有一定的主觀性，不符合多目標(biāo)優(yōu)化問題自身的特點(diǎn)。

它們?cè)谇蠼舛嗄繕?biāo)優(yōu)化問題時(shí)存在的缺陷主要體現(xiàn)在：

（1）采用這些算法求解通常每次優(yōu)化只能得到一個(gè)最優(yōu)解，且該解的獲得與轉(zhuǎn)換過程中目標(biāo)參數(shù)權(quán)重的設(shè)定有很大關(guān)系。若要獲取更多的最優(yōu)解，需通過多次調(diào)整參數(shù)權(quán)重、多次運(yùn)行該算法來進(jìn)行尋優(yōu)，由于各次優(yōu)化過程相互獨(dú)立，導(dǎo)致得到的解往往不一致，如果對(duì)于被求解問題沒有足夠的先驗(yàn)知識(shí)，就很難找到讓決策者滿意的最優(yōu)解，令決策者較難有效地進(jìn)行多目標(biāo)決策，且還要花費(fèi)較多的CPU時(shí)間開銷。

（2）需要依據(jù)求解問題所需的與應(yīng)用背景相關(guān)的啟發(fā)式知識(shí)來設(shè)定相關(guān)的權(quán)重，不同參數(shù)的權(quán)重設(shè)置會(huì)導(dǎo)致產(chǎn)生不同的非劣解，這就要求決策者事先要對(duì)優(yōu)化問題有充分的認(rèn)識(shí)，能夠合適地選取參數(shù)權(quán)重，而這往往是一個(gè)很難的過程。

（3）實(shí)際應(yīng)用問題中不同目標(biāo)的度量單位和物理意義通常不同，同時(shí)各目標(biāo)之間通過決策變量相互制約，往往存在相互沖突的指標(biāo)，目標(biāo)之間不易直接進(jìn)行比較或加權(quán)，雖可用無量綱化來量化指標(biāo)以處理目標(biāo)函數(shù)，但這增加了算法的復(fù)雜性，且會(huì)引起目標(biāo)空間的改變，導(dǎo)致無法正常利用決策信息。

（4）對(duì)Pareto最優(yōu)前沿形狀很敏感，不能很好地處理前沿的凹部［8］，多次運(yùn)行算法得到的解不能保證相互非劣等。

基于上述缺陷，這種傳統(tǒng)的求解多目標(biāo)優(yōu)化問題的MOSA方法，在實(shí)際應(yīng)用中受到了一定的限制。

3.3 SMOSA

Suppapitnarm等［9］設(shè)計(jì)了SMOSA算法，采用return－to－base策略，使搜索重新從解區(qū)域中的一個(gè)已歸檔解啟動(dòng)，該區(qū)域的每一對(duì)非支配解至少有一個(gè)目標(biāo)彼此更優(yōu)。在該算法中，每一個(gè)目標(biāo)函數(shù)被指派一個(gè)不同的溫度參數(shù)，在一特定的溫度值時(shí)，使用可接受的解的標(biāo)準(zhǔn)偏差冷卻這些參數(shù)。當(dāng)達(dá)到迭代次數(shù)或者在一特定溫度超過預(yù)定值時(shí)的累積記錄次數(shù)，則周期性地更新這些溫度參數(shù)。在搜索期間，該算法只使用一個(gè)解，且退火過程是根據(jù)每個(gè)標(biāo)準(zhǔn)的解的性能獨(dú)立地調(diào)整各溫度參數(shù)，歸檔集儲(chǔ)存著多個(gè)目標(biāo)間的所有非支配解。該方法不使用組合目標(biāo)函數(shù)，而是直接與先前歸檔集中解相互比較每個(gè)目標(biāo)的改變，這確保了接受非支配解。該文提出了一種新的接受準(zhǔn)則：基于一個(gè)具有多個(gè)溫度（一個(gè)溫度對(duì)應(yīng)一個(gè)目標(biāo)）的冷卻進(jìn)度表，該接受準(zhǔn)則不使用任何權(quán)重向量，一個(gè)新解的接受概率依賴于它是否被添加到該潛在的Pareto優(yōu)化解集中，如果它被添加到該集合中，它以概率1被接受為當(dāng)前解，否則，一個(gè)多目標(biāo)的接受準(zhǔn)則被使用。即如果新解未進(jìn)入Pareto解集，則根據(jù)如下概率接受新解：

3.4 WMOSA

對(duì)于帶約束的多目標(biāo)優(yōu)化問題，大多數(shù)MOSA算法采用一種如懲罰函數(shù)法的分離技術(shù)，而由Suman［10，11］所提出的基于權(quán)重的多目標(biāo)模擬退火算法WMOSA則試圖通過在接受準(zhǔn)則中使用權(quán)重向量，直接在其主函數(shù)中處理約束。權(quán)重向量取決于解向量和目標(biāo)函數(shù)向量所違背的約束個(gè)數(shù)，具體定義為：Wi＝（解向量和目標(biāo)函數(shù)向量所滿足的約束數(shù)＋目標(biāo)函數(shù)向量的第i個(gè)元素所滿足的約束數(shù)）／（與解向量和決策向量有關(guān)的約束數(shù)＋

與目標(biāo)函數(shù)向量的第i個(gè)元素有關(guān)的約束數(shù)）

如果新解未進(jìn)入Pareto解集，則根據(jù)如下概率接受新解：

3.5 PDMOSA

Suman［11，12］設(shè)計(jì)了一種基于 Pareto支配接受準(zhǔn)則的多目標(biāo)模擬退火算法PDMOSA。在該算法中，其接受準(zhǔn)則是基于Pareto支配的適應(yīng)度值策略，它易于適應(yīng)SA算法中的接受準(zhǔn)則。PDMOSA算法的解的適應(yīng)度值等于Pareto優(yōu)化解集中支配該解的非劣解的個(gè)數(shù)再加1，其適應(yīng)度值越小，解的質(zhì)量越好。在算法搜索早期階段，當(dāng)前解和新解之間的適應(yīng)度差異較小，且溫度較高，任何一次移動(dòng)可在兩個(gè)方向上得到接受，而隨著迭代次數(shù)的增加，溫度下降，適應(yīng)度值間的差異增大，這使得移動(dòng)方位更具有選擇性，從而可獲得多樣性良好分布的Pareto優(yōu)化解集。PDMOSA沒有將權(quán)重向量引入到接受準(zhǔn)則中，懲罰函數(shù)法用來處理不可行解。PDMOSA與其他MOSA之間的主要差別：在接受準(zhǔn)則中，沒有使用目標(biāo)函數(shù)值，而是使用適應(yīng)度函數(shù)值，從而簡化了接受概率的計(jì)算，且減少了計(jì)算時(shí)間，并使搜索逼近Pareto優(yōu)化解。PDMOSA算法中接受新解的概率計(jì)算方法是：

其中，S′i，generated為在第i次迭代時(shí)產(chǎn)生的新解基于Pareto支配的適應(yīng)度值，而S′i－1，current為當(dāng)前解在第i－1次迭代時(shí)當(dāng)前解基于Pareto支配的適應(yīng)度值。

3.6 DM－MOSA

Smith等［13］提出了一種基于支配措施的多目標(biāo)模擬退火算法DM－MOSA。該算法利用一個(gè)解的相對(duì)支配關(guān)系作為系統(tǒng)能量進(jìn)行優(yōu)化，其能量函數(shù)是基于Pareto前沿的當(dāng)前估計(jì)值，它表示在退火過程迄今為止找到的非支配解合并聚集之后形成的集合，并采用了三種方法（有條件地刪除被支配解、線性插值和到達(dá)曲面采樣）設(shè)計(jì)細(xì)粒度的能量函數(shù)。它可以促進(jìn)Pareto前沿上稀疏區(qū)域的搜索能力，可消除與組合目標(biāo)函數(shù)相關(guān)的一些問題。該文也提出一種為選擇擾動(dòng)定標(biāo)因子的方法以改善搜索能力，使其對(duì)解的搜索盡量朝Pareto前沿方向邁進(jìn)。該算法接受概率的計(jì)算方法是：

3.7 MC－MOSA

Tekinalp等人［14］在2007年提出了一種具有多種冷卻進(jìn)度表的多目標(biāo)模擬退火算法MC－MOSA。該算法具有自適應(yīng)冷卻進(jìn)度和使用一個(gè)適應(yīng)度函數(shù)的種群以準(zhǔn)確地生成Pareto前沿。該算法產(chǎn)生新解的方法是y＝x＋l，其中為服從均勻分布的單位球面上所選擇的一個(gè)搜索方向，l為服從均勻分布的步長。每個(gè)適應(yīng)度函數(shù)對(duì)應(yīng)一個(gè)溫度，每當(dāng)遇到改善了的適應(yīng)度函數(shù)的新解時(shí)就接受該解，同時(shí)根據(jù)適應(yīng)度函數(shù)的最好值和次好值及當(dāng)前解的適應(yīng)度函數(shù)值冷卻與改善了的適應(yīng)度函數(shù)相關(guān)的溫度參數(shù)。MC－MOSA算法定義了一種新的適應(yīng)度函數(shù)：

該算法的接受概率的計(jì)算方法是：

最大值，

3.8 AMOSA

歸檔式多目標(biāo)模擬退火AMOSA是由Bandyopadhyay等人［15］于2008年提出的一種解決多目標(biāo)組合優(yōu)化問題的高效算法。該算法首先初始化相關(guān)參數(shù)，如初始溫度等，產(chǎn)生初始解，計(jì)算各解的各個(gè)目標(biāo)函數(shù)值，利用爬山操作和支配關(guān)系對(duì)解進(jìn)行迭代提煉，將非支配解儲(chǔ)存于歸檔集中，直至歸檔集中解的個(gè)數(shù)增至SL（SL表示對(duì)解執(zhí)行聚類操作前歸檔集中解的最大個(gè)數(shù)）。如果歸檔集中解的個(gè)數(shù)超過HL（HL表示用戶所需非支配解的最大個(gè)數(shù)），執(zhí)行聚類操作使解的個(gè)數(shù)減至HL。其次，從歸檔集中隨機(jī)地選擇一個(gè)解作為當(dāng)前解，并計(jì)算該解的多個(gè)目標(biāo)函數(shù)值。在每個(gè)溫度下重復(fù)執(zhí)行以下過程若干次：擾動(dòng)當(dāng)前解產(chǎn)生新解，計(jì)算該解的多個(gè)目標(biāo)函數(shù)值，并檢測新解與當(dāng)前解及歸檔集中解的支配關(guān)系?；谥潢P(guān)系的不同，以不同概率接受新解、當(dāng)前解或歸檔集中的某個(gè)解。若歸檔集中解的個(gè)數(shù)超過SL，執(zhí)行聚類操作以減至HL。每個(gè)溫度以一定冷卻率進(jìn)行退火，直至達(dá)到給定的最低溫度，結(jié)束循環(huán)。

AMOSA算法分三種情況計(jì)算該算法的接受概率：（1）當(dāng) 前解支配新 解，以概率p ＝設(shè)置新解為當(dāng)前解；（2）新解與當(dāng)前解彼此非支配，檢查新解與歸檔集中解的支配關(guān)系，若歸檔集中有k（k≥1）個(gè)解支配新解，則以概率新解為當(dāng)前解；（3）新解支配當(dāng)前解，檢查新解與歸檔集中解的支配關(guān)系，若歸檔集中有k（k≥1）個(gè)解支配新解，則以概率

置對(duì)應(yīng)于Δdommin最小的那個(gè)解為當(dāng)前解，否則設(shè)置新解為當(dāng)前解。

3.9 rMOSA

Sankarao B等人于2011年提出了一種魯棒的多目標(biāo)模擬退火算法rMOSA［16］，它在較少的模擬次數(shù)下能收斂到Pareto解集，這些Pareto解是具有擁擠良好分布的均勻非支配解。該算法在簡單MOSA算法的基礎(chǔ)上增加了兩個(gè)新的機(jī)制實(shí)施擾動(dòng)以選擇新解，從而具有魯棒性。這兩種機(jī)制分別是：（1）一個(gè)系統(tǒng)調(diào)用為執(zhí)行解的擾動(dòng)而在歸檔集中選擇一個(gè)隨機(jī)點(diǎn)，該機(jī)制的目的是加快收斂過程以獲得最終Pareto前沿；（2）另一個(gè)系統(tǒng)調(diào)用則為執(zhí)行解的擾動(dòng)在歸檔集中選擇一個(gè)最佳非擁擠解，該機(jī)制的目的是為獲得具有良好擁擠分布的均勻Pareto前沿。該算法基于一個(gè)概率函數(shù)接受一個(gè)差的解，其接受概率的計(jì)算方法是：

多目標(biāo)優(yōu)化問題的特征之一是其解往往不止一個(gè)，而是有很多個(gè)Pareto最優(yōu)解，即一組在多個(gè)目標(biāo)之間折衷的均衡解。解決多目標(biāo)優(yōu)化問題的關(guān)鍵是找到數(shù)量足夠多且分布均勻的具有代表性的Pareto最優(yōu)解組成的解集。

上述MOSA算法主要采用基于Pareto支配的方法。所謂基于Pareto支配的方法是指將多個(gè)目標(biāo)值直接映射到一種基于秩的適應(yīng)度函數(shù)中，通過Pareto支配關(guān)系來計(jì)算適應(yīng)值。首先種群中的所有非支配解被賦予序值1，然后從種群中忽略它們，這時(shí)在種群中新的非支配解被賦予序值2，直到種群中所有解被賦予序值為止。該方法每輪運(yùn)行時(shí)會(huì)考慮許多非支配解，且會(huì)儲(chǔ)存產(chǎn)生的Pareto前沿的近似解，更好地反映多目標(biāo)優(yōu)化問題的實(shí)質(zhì)，實(shí)現(xiàn)了真正意義上的多目標(biāo)優(yōu)化，不僅可以求出比單目標(biāo)方法更優(yōu)的解，而且通過一次優(yōu)化計(jì)算可得到多個(gè)較優(yōu)的Pareto最優(yōu)解。

基于Pareto支配的方法是目前采用得最多的一種方法，根據(jù)Pareto最優(yōu)解支配概念使用MOSA算法求解多目標(biāo)優(yōu)化問題時(shí)，需要解決以下兩個(gè)關(guān)鍵問題：（1）收斂性，即解應(yīng)盡快地向Pareto前沿方向進(jìn)化；（2）多樣性，即非劣解應(yīng)盡量在Pareto前沿面上均勻分布?；赑areto支配的MOSA算法對(duì)解的搜索方式實(shí)現(xiàn)了多向性和全局性，能充分利用解的多樣性，使得算法能夠在一次運(yùn)行中獲得多個(gè)Pareto最優(yōu)解集。在這些MOSA中，有些使用目標(biāo)函數(shù)，有些使用適應(yīng)度函數(shù)值，來確定接受概率的計(jì)算公式。這些算法的主要差別在于接受準(zhǔn)則，單目標(biāo)條件下的接受準(zhǔn)則需要進(jìn)行擴(kuò)展，以滿足多目標(biāo)優(yōu)化的要求。

3.1 0 混合 MOSA

算法混合的思想已成為提高算法優(yōu)化性能的一個(gè)重要而有效的途徑，其出發(fā)點(diǎn)是使單一算法互相取長補(bǔ)短，產(chǎn)生更好的優(yōu)化能力和效率，期望獲得優(yōu)化性能和時(shí)間性能的雙贏，改善解的質(zhì)量。

Ba?os等［17］在2007年提出了一種新穎的基于模擬退火和禁忌搜索的混合思想的多目標(biāo)元啟發(fā)式方法——多目標(biāo)模擬退火和禁忌搜索算法，該算法使用一個(gè)多解的主種群和一個(gè)用于保存在主種群中找到的優(yōu)秀解的外部歸檔集。在優(yōu)化過程中，它合并了模擬退火算法和禁忌搜索算法，其新解的接受概率是基于解中的Pareto支配關(guān)系而決定的。

Maulik等［18］于2010年在AMOSA算法的基礎(chǔ)上提出了一個(gè)新穎的并行版的基于粗糙集的歸檔式多目標(biāo)模擬退火算法，該算法融合了粗糙集理論與具有歸檔式多目標(biāo)模擬退火方法的可伸縮的分布式范式的原則。

3.1 1 其他 MOSA

Huang等人［19］于2008年在正交實(shí)驗(yàn)設(shè)計(jì)的基礎(chǔ)上，利用基于Pareto支配的計(jì)分函數(shù)和多目標(biāo)產(chǎn)生機(jī)理，提出了一種新穎的智能MOSA算法。Shu等［20］提出了一種新穎的用于解決具有大量參數(shù)的多目標(biāo)優(yōu)化問題的多目標(biāo)正交SA算法。Li等［21］提出了一種具有自適應(yīng)性和競爭性的搜索導(dǎo)向的進(jìn)化 MOSA算法。張長林等［22］提出了一種用于求解非線性約束最優(yōu)化問題的有效MOSA算法。蘆金蟬等［23］利用多目標(biāo)優(yōu)化和物體退火之間的類比關(guān)系構(gòu)建了基于SA的多目標(biāo)優(yōu)化算法。Bandyopadhyay［24］于 2011 年在 其 早 期 文 獻(xiàn)［15］的基礎(chǔ)上提出了一種具有穩(wěn)定性和有效性的用于模糊聚類的MOSA算法。

4 MOSA的應(yīng)用進(jìn)展

目前，MOSA算法一直受到人們的廣泛重視，并在諸多工程領(lǐng)域得到迅速推廣和應(yīng)用，下面列出幾個(gè)典型的應(yīng)用領(lǐng)域。

4.1 圖像處理

Ba?os等［17］將他們所提出的 MOSATS算法用于優(yōu)化圖像分割問題。Saha等采用AMOSA算法對(duì)遙感衛(wèi)星圖像中自動(dòng)像素分類［25］和衛(wèi)星圖像中無監(jiān)督式像素分類的影像數(shù)據(jù)［26］進(jìn)行多目標(biāo)優(yōu)化設(shè)計(jì)。在遙感衛(wèi)星圖象的自動(dòng)像素分類中，Saha等［27］還使用 multicenter－AMOSA 算法對(duì)遙感圖象數(shù)據(jù)集合同時(shí)優(yōu)化以檢測出適當(dāng)數(shù)量的集群和恰當(dāng)?shù)姆指顓^(qū)。

4.2 生物科學(xué)

Wang等［28］運(yùn)用AMOSA算法對(duì)基因進(jìn)行基于特征選擇的轉(zhuǎn)錄起始位點(diǎn)的預(yù)測。劉鵬飛等［29］應(yīng)用MOSA算法對(duì)非編碼RNA比對(duì)及預(yù)測并行模型的多個(gè)代價(jià)函數(shù)進(jìn)行優(yōu)化以提高解的多樣性。Lashkargir［30］等運(yùn)用AMOSA算法在微陣列數(shù)據(jù)中發(fā)現(xiàn)基因表達(dá)數(shù)據(jù)的雙向聚類，采用擁擠距離機(jī)制維持雙群的多樣性。

4.3 工業(yè)控制

Huang等［20］利用智能多目標(biāo)模擬退火IMOSA算法解決魯棒PID控制器的設(shè)計(jì)問題。鐘愛蓮［31］將AMOSA算法用于優(yōu)化非相關(guān)平行機(jī)臺(tái)排程問題以提供排程決策者更適合工廠現(xiàn)況的排程方法機(jī)制。李瑞琪［32］探討不同策略之多目標(biāo)模擬退火算法以求解非相關(guān)平行機(jī)臺(tái)排程問題。Chang等［33］應(yīng)用AMOSA算法對(duì)變速機(jī)調(diào)度以最大化完工時(shí)間和拖期的滿意度。

4.4 機(jī)械設(shè)計(jì)

Tekinalp等［14］將所提出的具有多冷卻率的MOSA算法用于運(yùn)載火箭彈道的優(yōu)化設(shè)計(jì)。熊慶輝等［34］采用MOSA算法實(shí)現(xiàn)壓電堆執(zhí)行器的關(guān)鍵結(jié)構(gòu)參數(shù)全局多目標(biāo)優(yōu)化設(shè)計(jì)，對(duì)高壓共軌噴油器的關(guān)鍵結(jié)構(gòu)參數(shù)進(jìn)行多目標(biāo)仿真優(yōu)化設(shè)計(jì)［35］，對(duì)高壓共軌電控噴油器響應(yīng)特性進(jìn)行了優(yōu)化設(shè)計(jì)［36］。李鐵栓等［37］采用 MOSA對(duì)高壓共軌電控噴油器高速電磁閥的關(guān)鍵結(jié)構(gòu)參數(shù)進(jìn)行多目標(biāo)優(yōu)化設(shè)計(jì)。潘金坤［38］等采用多目標(biāo)模擬退火優(yōu)化算法MOSA，以合模油缸推力和機(jī)構(gòu)總長度為目標(biāo)函數(shù)建立多目標(biāo)優(yōu)化設(shè)計(jì)模型，對(duì)雙曲肘合模機(jī)構(gòu)的關(guān)鍵結(jié)構(gòu)參數(shù)進(jìn)行多目標(biāo)優(yōu)化計(jì)算。熊慶輝等［39］采用多目標(biāo)模擬退火優(yōu)化算法，以換擋開關(guān)電磁閥的開啟延遲時(shí)間、關(guān)閉延遲時(shí)間和電磁力為目標(biāo)建立了多目標(biāo)優(yōu)化模型，對(duì)換擋開關(guān)電磁閥的主要結(jié)構(gòu)參數(shù)開展多目標(biāo)優(yōu)化設(shè)計(jì)。

4.5 電路設(shè)計(jì)

He等［40］為設(shè)計(jì)能充分表示全功能的組合邏輯電路提出了一個(gè)多目標(biāo)優(yōu)化技術(shù)，該技術(shù)采用MOSA算法優(yōu)化組合邏輯電路以最小化邏輯電路門的數(shù)量。Antunes等［41］采用 MOSA算法解決電力系統(tǒng)中無功補(bǔ)償問題以優(yōu)化電容器的大小和安裝位置，有助于釋放系統(tǒng)容量、提高電壓等級(jí)。

4.6 網(wǎng)絡(luò)優(yōu)化

Santamaria等［42］采用 MOSA算法對(duì)時(shí)間驅(qū)動(dòng)的傳感器網(wǎng)絡(luò)同時(shí)考慮多個(gè)相關(guān)性能目標(biāo)進(jìn)行路由優(yōu)化。Smith［43］將所提出的基于優(yōu)勝關(guān)系的多目標(biāo)模擬退火算法用于移動(dòng)通信領(lǐng)域中CDMA網(wǎng)絡(luò)的優(yōu)化配置。Xu等［44］提出了一個(gè)具有變鄰域的進(jìn)化多目標(biāo)模擬退火算法以解決電信系統(tǒng)中多組播路由優(yōu)化問題。

4.7 車間調(diào)度

Varadharajan等［45］應(yīng)用 MOSA算法進(jìn)行置換流水車間的調(diào)度以最小化作業(yè)的完工時(shí)間和總的流程時(shí)間。Issam等［46］使用一個(gè)基于MOSA算法的多智能系統(tǒng)解決靜態(tài)電話預(yù)約乘車調(diào)度問題。Issam等［47］將電話預(yù)約乘車調(diào)度問題表示為一個(gè)多目標(biāo)數(shù)學(xué)模型，采用MOSA算法解決動(dòng)態(tài)電話預(yù)約乘車調(diào)度問題。Mokotoff［48］采用 MOSA算法解決在實(shí)際語境中置換流水車間調(diào)度問題以極小化最大完工時(shí)間和總完工時(shí)間。

4.8 其他應(yīng)用領(lǐng)域

Kumral［49］基于 MOSA算法解決不同的有效礦物的最佳混合問題。Lucic等［50］將MOSA算法用于解決多目標(biāo)空勤人員排班問題。Safaei等［51］采用MOSA算法解決一個(gè)現(xiàn)實(shí)的維護(hù)人力調(diào)度問題，旨在同時(shí)最大限度地降低勞動(dòng)力成本和最大限度地提高設(shè)備的可用性。Ekbal等［52］采用MOSA算法，通過優(yōu)化多個(gè)目標(biāo)函數(shù)以解決指代消解的特征選擇問題。Ekbal等［53］以基于MOSA算法的分類器集成在印第安語中的命名實(shí)體識(shí)別作為個(gè)案進(jìn)行研究。

5 結(jié)束語

本文對(duì)MOSA算法及其應(yīng)用進(jìn)行了積極的調(diào)研，對(duì)其進(jìn)展作出了一個(gè)較全面的綜述。盡管在最近的二十多年已經(jīng)出現(xiàn)了大量有關(guān)MOSA的研究工作，但相對(duì)于多目標(biāo)微粒群算法、多目標(biāo)遺傳算法等算法的發(fā)展，MOSA算法的研究仍然是滯后的。與許多智能優(yōu)化算法一樣，MOSA算法的不成熟和數(shù)學(xué)基礎(chǔ)的相對(duì)薄弱，決定了在未來相當(dāng)長的時(shí)間內(nèi)，仍然有許多開放性的問題值得關(guān)注和探討，許多具有挑戰(zhàn)性的問題亟待解決，未來的研究工作可從以下若干方面展開。

（1）冷卻進(jìn)度表參數(shù)的優(yōu)化選取。冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù)，用以逼近SA算法的漸進(jìn)收斂性，使算法在有限執(zhí)行時(shí)間后返回一個(gè)近似最優(yōu)解。冷卻進(jìn)度表是影響SA算法性能的重要因素，其合理選取是算法應(yīng)用的關(guān)鍵［54］。大部分MOSA與其他SA算法一樣，其求解性能依賴于一些參數(shù)的優(yōu)化設(shè)置，如算法中關(guān)于初始溫度、溫度更新函數(shù)、內(nèi)外循環(huán)終止條件等。MOSA算法對(duì)具體問題和應(yīng)用環(huán)境的依賴性比較大，在不同參數(shù)及同一參數(shù)的不同取值情況下，針對(duì)不同類型的目標(biāo)函數(shù)，特別是針對(duì)不同的應(yīng)用問題，所得到的解是不同的。如何尋找所選各參數(shù)的不同取值的最佳組合是算法設(shè)計(jì)的一個(gè)關(guān)鍵方向，直接關(guān)系到所獲取解的質(zhì)量。至今MOSA算法的參數(shù)選擇依然是一個(gè)難題，通常只能依據(jù)一定的啟發(fā)式準(zhǔn)則或大量的實(shí)驗(yàn)加以選取。因此，如何指導(dǎo)參數(shù)的優(yōu)化選擇，需要在理論上進(jìn)行更深入的探索，將來在這方面的研究突破會(huì)極大地推進(jìn)MOSA算法研究的發(fā)展。

（2）參數(shù)的自動(dòng)控制。MOSA算法中涉及各種參數(shù)設(shè)置，如初始溫度、冷卻率等，沒有確切的理論依據(jù)。MOEA參數(shù)的自動(dòng)控制機(jī)制（如在線適應(yīng)和自適應(yīng)等，它能在無需人工干預(yù)的情況下適應(yīng)性地調(diào)整其參數(shù)）的設(shè)計(jì)很少被探索［55］。因此，如何設(shè)計(jì)不用用戶調(diào)整參數(shù)而使算法依據(jù)其優(yōu)化進(jìn)展情況適應(yīng)性地調(diào)整參數(shù)的MOSA算法，使得算法既能避免早熟又能比較快速地收斂，是一個(gè)具有挑戰(zhàn)性的問題。

（3）接受準(zhǔn)則的設(shè)計(jì)。SA算法設(shè)計(jì)的關(guān)鍵是接受準(zhǔn)則和冷卻進(jìn)度表，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞，以一定概率接受新解［2］，MOSA需要對(duì)單目標(biāo)條件下的接受準(zhǔn)則進(jìn)行擴(kuò)展，以滿足多目標(biāo)優(yōu)化的要求。如何設(shè)計(jì)MOSA算法的接受準(zhǔn)則，是使用目標(biāo)函數(shù)還是使用適應(yīng)度函數(shù)值，抑或是采用其他參數(shù)值來確定接受概率的計(jì)算公式，值得在今后的工作中進(jìn)一步摸索和探討。

（4）終止條件的研究。終止條件包括外循環(huán)和內(nèi)循環(huán)終止條件，內(nèi)循環(huán)終止條件用來決定各溫度下產(chǎn)生候選解的數(shù)目，外循環(huán)終止條件即算法終止條件，用來決定算法何時(shí)結(jié)束［56］。當(dāng)前，內(nèi)循環(huán)終止條件主要是按一定的步數(shù)抽樣，一般可考慮算法搜索到的最優(yōu)解用連續(xù)若干步的目標(biāo)函數(shù)值變化較小或檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定等方法來決定是否終止內(nèi)循環(huán)；而外循環(huán)終止條件主要是以預(yù)先設(shè)定終止溫度的閾值或最大迭代次數(shù)作為終止條件，以保證滿足運(yùn)算時(shí)間的要求，但卻不一定能收斂到Pareto前沿。如何設(shè)計(jì)有效的算法終止準(zhǔn)則是MOSA的一個(gè)基礎(chǔ)理論難題之一，如何有效地證明或給出明確的算法終止準(zhǔn)則仍是有待研究的，很難明確地判斷算法迭代到一定次數(shù)已經(jīng)達(dá)到了最優(yōu)或者說可以終止，尋找更好的終止條件是一個(gè)亟待解決的問題。

（5）收斂性分析和證明。收斂性一直是智能優(yōu)化算法研究的重點(diǎn)和難點(diǎn)，目前求解多目標(biāo)問題的MOSA算法缺乏與單目標(biāo)SA算法相類似的收斂性理論。從理論上分析和證明MOSA算法的收斂性，從實(shí)驗(yàn)方面驗(yàn)證MOSA算法的收斂性和收斂速度等尚沒有形成通用的、完整的分析和證明方法。為此，有必要對(duì)MOSA算法的收斂性的分析和證明進(jìn)行更深入的研究，提高算法的尋優(yōu)能力，使得算法能更加快速、準(zhǔn)確地尋找到全局最優(yōu)解，以期為設(shè)計(jì)出性能更優(yōu)的MOSA算法提供指導(dǎo)。

（6）解的多樣性保持機(jī)制的研究。對(duì)于MOSA算法，解的多樣性目前主要是通過外部歸檔集的維護(hù)來保證的，如文獻(xiàn)［15］通過聚類操作來維護(hù)外部歸檔集以保持解的多樣性。可否尋找更高效的機(jī)制提高解的多樣性。這是一個(gè)值得探討的問題。如何使算法在得到一個(gè)具有良好分布性Pareto解集的同時(shí)，也能獲得一個(gè)理想的收斂性，將是今后研究工作所追求的一個(gè)重要目標(biāo)，對(duì)維持解的多樣性、改進(jìn)所獲取的解的質(zhì)量等方面具有現(xiàn)實(shí)意義。

（7）改變算法進(jìn)程的一些方法的移植。在SA算法中，改變算法進(jìn)程的一些方法有回火退火法、加溫退火法、多次尋優(yōu)法等［54］。這些改進(jìn)方法能否直接或間接移植到MOSA算法中，有待于研究者在理論上和實(shí)踐中去驗(yàn)證。

（8）針對(duì)不同計(jì)算環(huán)境的 MOSA算法的研究。隨著計(jì)算機(jī)硬件體系結(jié)構(gòu)和平臺(tái)技術(shù)的快速發(fā)展，如面對(duì)Cluster集群、多核CPU、GPU、Cell BE、超級(jí)計(jì)算機(jī)等不同的計(jì)算機(jī)體系結(jié)構(gòu)，網(wǎng)格計(jì)算平臺(tái)和云計(jì)算平臺(tái)等不同平臺(tái)技術(shù)，針對(duì)不同的計(jì)算環(huán)境對(duì)MOSA算法的性能和復(fù)雜性及其應(yīng)用展開研究工作，對(duì)MOSA算法作進(jìn)一步的完善也是一項(xiàng)有著重大應(yīng)用價(jià)值和有意義的工作。

（9）并行MOSA算法的設(shè)計(jì)。隨著計(jì)算技術(shù)的不斷發(fā)展，算法的并行實(shí)現(xiàn)也越來越容易；隨著并行化處理的不斷深入，對(duì)并行化算法的研究也越來越普遍，并行化在算法性能提升方面的巨大潛力顯而易見［57］。并行 MOSA的設(shè)計(jì)目標(biāo)在于利用更少的時(shí)間、更少的計(jì)算資源或搜索更多可行解，獲取比MOSA算法更多更好的優(yōu)化解。對(duì)于增強(qiáng)MOSA算法的性能，并行技術(shù)和使用種群信息將是好的方法［58］。文獻(xiàn)［54］討論了SA算法的并行實(shí)現(xiàn)方法和形式，文獻(xiàn)［59］提出了一種并行SA算法。那么，對(duì)于MOSA算法，能否移植并行單目標(biāo)SA算法的思想來構(gòu)建并行MOSA算法，MOSA算法的并行實(shí)現(xiàn)的可能性和途徑、并行策略及在并行領(lǐng)域的實(shí)際應(yīng)用，值得在今后的工作中進(jìn)一步探討。Maulik等［18］于2010年在AMOSA算法的基礎(chǔ)上提出了一個(gè)新穎的并行版的基于粗糙集的AMOSA算法，這為并行化MOSA提供了可鑒思路。因此，尋找有效并行技術(shù)和性能度量方法是未來的工作，實(shí)現(xiàn)MOSA算法的并行化，讓算法在分布（并行）的計(jì)算環(huán)境中運(yùn)行顯然是一種有意義的值得期待的嘗試。

（10）基于MapReduce的并行MOSA算法的設(shè)計(jì)。MapReduce［60］框架是Google提出的一種處理超大規(guī)模數(shù)據(jù)集的新型分布式并行編程模型，采用了“分而治之”的思想。Monte Carlo是一種隨機(jī)模擬和不確定性方法，是一種可以有效實(shí)現(xiàn)并行計(jì)算的算法結(jié)構(gòu)，任何一個(gè)屬于Monte Carlo方法的應(yīng)用都可以運(yùn)行在云計(jì)算環(huán)境中。MOSA是一種基于Monte Carlo迭代求解策略的啟發(fā)式隨機(jī)優(yōu)化算法，而Monte Carlo方法又是一種典型可并行化的方法，且MapReduce是目前云計(jì)算的核心計(jì)算模式。基于此，我們可以采用MapReduce技術(shù)，設(shè)計(jì)云計(jì)算環(huán)境下的基于MapReduce的并行MOSA算法，這在云計(jì)算時(shí)代具有很好的應(yīng)用前景。

（11）動(dòng)態(tài)MOSA算法的設(shè)計(jì)。對(duì)于動(dòng)態(tài)環(huán)境優(yōu)化問題，在其求解的過程中，它的決策參數(shù)、目標(biāo)函數(shù)值、約束條件等都可能發(fā)生變化，目前國內(nèi)外相關(guān)的研究文獻(xiàn)相對(duì)比較少。對(duì)于動(dòng)態(tài)優(yōu)化進(jìn)化算法，大多還是集中在如何得到盡可能滿足問題條件的最優(yōu)解或近似最優(yōu)解，對(duì)算法的有效性、收斂性及解的質(zhì)量等考慮的較少［61］。因此，如何設(shè)計(jì)動(dòng)態(tài)MOSA算法，使算法盡可能有效地跟蹤動(dòng)態(tài)多目標(biāo)優(yōu)化問題隨時(shí)間（環(huán)境）發(fā)生變化的Pareto最優(yōu)解，使算法在動(dòng)態(tài)變化的環(huán)境下能求得質(zhì)量較好、數(shù)量較多、分布較廣且均勻的Pareto最優(yōu)解，以及在求解過程中如何動(dòng)態(tài)調(diào)整MOSA的一些參數(shù)，以自適應(yīng)求解動(dòng)態(tài)環(huán)境下的優(yōu)化問題，這是一個(gè)挑戰(zhàn)。

（12）基于新型占優(yōu)機(jī)制的 MOSA算法的設(shè)計(jì)。很多學(xué)者開始注意到Pareto占優(yōu)的局限性，如何引入新的占優(yōu)機(jī)制以有效解決高維多目標(biāo)優(yōu)化問題成為進(jìn)化多目標(biāo)優(yōu)化研究者接下來的主要任務(wù)之一［55］。將新型占優(yōu)機(jī)制，如ε－占優(yōu)的檔案更新策略［63］引入到MOSA中，并應(yīng)用其解決多目標(biāo)優(yōu)化問題，且通過理論和結(jié)合實(shí)際多目標(biāo)優(yōu)化問題驗(yàn)證算法解決實(shí)際問題的可行性，有效性等。

（13）混合MOSA算法的設(shè)計(jì)。單純依賴一種算法求解復(fù)雜優(yōu)化問題，有時(shí)效果并不好，與其他算法進(jìn)行混合是提高算法優(yōu)化性能的一個(gè)重要且有效的途徑，不同算法的相互補(bǔ)充、融合已被證明是一種有效地改良方式。MOSA作為一種多目標(biāo)智能優(yōu)化算法，與其他算法融合和比較的研究仍處于初級(jí)階段，相關(guān)的研究文獻(xiàn)和報(bào)告較少。MOSA具有大范圍快速全局搜索能力，但對(duì)系統(tǒng)中的反饋信息利用不夠，當(dāng)求解到一定范圍時(shí)往往做大量無為的冗余迭代，求精確解效率降低，若能在MOSA中融合蟻群算法思想找鄰域解，可能效果會(huì)更好，如在MOSA中融合禁忌搜索算法以避免算法迂回搜索、采用微粒群算法為MOSA提供初始解等，進(jìn)一步改善 MOSA的性能，以及探討MOSA與其他算法之間的聯(lián)系都是非常有意義的研究方向。因此，尋求MOSA算法的弱點(diǎn)，充分利用其它算法的優(yōu)勢(shì)，取長補(bǔ)短，基于算法統(tǒng)一框架，發(fā)展高效的混合MOSA算法，已成為人們關(guān)注的熱點(diǎn)。

（14）其他新穎的MOSA算法的設(shè)計(jì)。針對(duì)搜索全局性、快速性和魯棒性，根據(jù)現(xiàn)有多目標(biāo)優(yōu)化方法所采用的思想和技術(shù)（擁擠距離、聚類、混沌、模糊集等），引入新的優(yōu)化機(jī)制和操作，如在MOSA中引入偏好排序代替Pareto支配排序、采用新的存檔策略等，設(shè)計(jì)出新穎的MOSA算法，通過理論和實(shí)踐證明其優(yōu)越性和不足之處，并不斷完善這將是一個(gè)令人期待和極富挑戰(zhàn)的研究領(lǐng)域。

（15）與其他多目標(biāo)智能優(yōu)化算法的比對(duì)研究。新型的算法結(jié)構(gòu)或混合算法對(duì)算法性能和效率有較大幅度的改善。結(jié)合實(shí)際應(yīng)用或理論問題對(duì)算法進(jìn)行對(duì)比研究也是算法研究中值得關(guān)注的內(nèi)容。它有助于分析算法的性能和適用域，且由比較可發(fā)現(xiàn)各算法獨(dú)特的優(yōu)點(diǎn)和不足，來改進(jìn)結(jié)構(gòu)或操作或參數(shù)，發(fā)展各種可能的高效混合算法［56］。因此，將MOSA算法與其他多目標(biāo)智能優(yōu)化算法進(jìn)行比對(duì)研究，以進(jìn)一步完善算法。

（16）拓展 MOSA算法的應(yīng)用領(lǐng)域。MOSA是一種新穎的多目標(biāo)優(yōu)化算法，可用于解決大多數(shù)多目標(biāo)優(yōu)化問題，雖已被應(yīng)用到一些領(lǐng)域，但遠(yuǎn)沒有其他多目標(biāo)智能優(yōu)化算法（如多目標(biāo)微粒群算法、多目標(biāo)遺傳算法等）應(yīng)用廣泛。因此，拓寬MOSA算法在實(shí)際工程問題中的應(yīng)用，如交通與物流系統(tǒng)優(yōu)化、多播QoS路由優(yōu)化、Web服務(wù)組合、數(shù)據(jù)挖掘等領(lǐng)域，將是MOSA算法應(yīng)用研究中值得重視的有實(shí)際價(jià)值的課題。將MOSA算法用于解決更多的實(shí)際問題，驗(yàn)證算法的適用性和有效性，進(jìn)一步進(jìn)行更廣泛更深入的應(yīng)用研究，再根據(jù)應(yīng)用的反饋信息，改進(jìn)和完善現(xiàn)有算法的性能，從而達(dá)到算法理論與實(shí)際應(yīng)用相互促進(jìn)的目的，這仍舊是一個(gè)開放問題。

總之，未來在設(shè)計(jì)或改進(jìn)MOSA算法時(shí)要同時(shí)注意：算法應(yīng)具有較快的收斂速度，所得的最優(yōu)解要盡可能接近Pareto前沿、盡可能寬廣均勻地分布在Pareto前沿，并且盡可能將其用于解決實(shí)際應(yīng)用問題等。

［1］ Kirkpatrick S，Gerlatt C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671－680.

［2］ Lei De－ming，Yan Xin－ping.Multi－objective intelligent optimization algorithm and its application［M］.Beijing：Science Press，2009.（in Chinese）

［3］ Suman B，Kumar P.A survey of simulated annealing as a tool for single and multi－objective optimization［J］.Journal of

the Operational Research Society，2006，57：1143－1160.

［4］ Ulungu E L，Teghem J，Ost C.Interactive simulated annealing in a multi－objective framework：Application to an industrial problem［J］.Journal of the Operational Research Society，1998，49：1044－1050.

［5］ Ulungu E L，Teghem J，F(xiàn)ortmeps P H，et al.MOSA method：A Tool for solving multi－objective combinatorial optimization problems［J］.Journal of Multi－Criteria Decision Analysis，1999（8）：221－236.

［6］ Haidine A，Lehnert R.Multi－case multi－objective simulated annealing（MC－MOSA）：New approach for adapt simulated annealing to multi－objective ptimization［EB／OL］.［2012－05－16］.http：／／www.akademik.unsri.ac.id／download／journal／files／waset／v4－3－28－6.pdf.

［7］ Czyzak P，Jaszkiewicz A.Pareto simulated annealing－a meta－h(huán)euristic technique for multiple－objective combinatorial optimization［J］.Journal of Multi－Criteria Decision Analysis，1998（7）：34－47.

［8］ Cui Xun－xue.Multi－objective evolutionary algorithm and its application［M］.Beijing：National Defense Industry Press，2008.（in Chinese）

［9］ Suppapitnarm A，Seffen K A，Parks G T.Simulated annealing：An alternative approach to true multi－objective optimization［J］.Engineering Optimization，2000，33（1）：59－85.

［10］ Suman B.Multi－objective simulated annealing—a meta－h(huán)euristic technique for multi－objective optimization of a constrained problem［J］.Foundations of Computing and Decision Sciences，2002，27（3）：171－191.

［11］ Suman B.Simulated annealing－based multi－objective algorithms and their application for system reliability［J］.Engineering Optimization，2003，35（4）：391－416.

［12］ Suman B.Study of simulated annealing based algorithms for

multi－objective optimization of a constrained problem［J］.

Computers ＆ Chemical Engineering，2004，28：1849－1871.［13］ Smith K I，Everson R M，F(xiàn)ieldsend J E，et al.Dominance measures for multi－objective simulated annealing［C］∥Proc of Congress on Evolutionary Computation（CEC2004），2004：23－30.

［14］ Tekinalp O，Karsli G.A new multi－objective simulated annealing algorithm ［J］.Journal of Global Optimization，2007，39（1）：49－77.

［15］ Bandyopadhyay S，Saha S，Maulik U，et al.A simulated annealing based multi－objective optimization algorithm：AMOSA［J］.IEEE Transactions on Evolutionary Computation，2008，12（3）：269－283.

［16］ Sankara O B，Chang K Y.Development of a robust multiobjective simulated annealing algorithm for solving multiobjective optimization problems［J］.Industrial ＆ Engineering Chemistry Research，2011，50（11）：6728－6742.

［17］ Ba?os R，Gil C，Paechter B，et al.A hybrid meta－h(huán)euristic for multi－objective optimization：MOSATS［J］.Journal of Mathematical Modeling and Algorithms，2007，6（2）：213－230.

［18］ Maulik U，Sarkar A.Evolutionary rough parallel multi－objective optimization algorithm［J］.Fundamenta Informaticae，2010，99（1）：13－27.

［19］ Huang M H，Shu L S，Ho S J，et al.A novel intelligent multi－objective simulated annealing algorithm for designing robust PID controllers［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part A：Systems and Humans，2008，38（2）：319－329.

［20］ Shu L S，Ho S J，Ho S Y，et al.A novel multi－objective orthogonal simulated annealing algorithm for solving multiobjective optimization problems with a large number of parameters［EB／OL］.［2012－05－15］.http：／／www.springerlink.com／index／ULJ9BFAGK6U1N0LC.pdf.

［21］ Li H，Landa－silva D.Evolutionary multi－objective simulated annealing with adaptive and competitive search direction［EB／OL］.［2012－05－18］.http：／／www.cs.nott.ac.uk／～jds／research／files／jdls＿cec2008.pdf.

［22］ Zhang Chang－lin，Yu Jian－xing，Yang Zhen－guo.The multiobject simulated annealing algorithm for the nonlinear constraint optimization problem［J］.Journal of Fudan University：Natural Science，2003，42（1）：93－97.（in Chinese）

［23］ Lu Jin－chan，Li Nai－cheng，Wang Wei－dong.Multi－objective optimization approach based on simulated annealing［J］.Computer Engineering and Applications，2003（23）：92－94.（in Chinese）

［24］ Bandyopadhyay S.Multi－objective simulated annealing for fuzzy clustering with stability and validity［J］.IEEE Transactions on Systems，Man and Cybernetics－Part C：Applications and Reviews，2011，41（5）：682－691.

［25］ Saha S，Bandyopadhyay S.Use of different forms of symmetry and multi－objective optimization for automatic pixel classification in remote－sensing satellite imagery［J］.International Journal of Remote Sensing，2010，31（22）：5751－5775.

［26］ Saha S，Bandyopadhyay S.Unsupervised pixel classification in satellite imagery using a new multi－objective symmetry based clustering approach［C］／／Proc of the IEEE TENCON，2008：1－6.

［27］ Saha S，Bandyopadhyay S.Automatic pixel classification in remote sensing satellite imagery using a new multi－objective simulated annealing based clustering technique［C］∥Proc of Seminar on Spatial Information Retrieval，Analysis，Reasoning and Modelling，2009：98－118.

［28］ Wang X，Bandyopadhyay S，Xuan Z，et al.Prediction of transcription start sites based on feature selection using AMOSA［C］∥Proc of Computational Systems Bioinformatics Conference，2007：183－193.

［29］ Liu Peng－fei，Dong Shou－bin，Cao Yi－cheng，et al.Alignment and prediction of multi－objective optimized non－coding RNA［J］.Computer Engineering，2009，35（9）：225－226.（in Chinese）

［30］ Lashkargir M，Tabatabaeifar M S，Taghizadeh S.An archived multi－objective simulated annealing method to discover biclusters in microarray data［J］.International Journal on Advanced Science，Engineering and Information Technology，2011，1（3）：257－261.

［31］ Jhong Ai－lian.Archive－based optimization heuristics for fuzzy multi－objective unrelated parallel machine scheduling problems［D］.Taiwan：Yuan Ze University，2009.（in Chinese）

［32］ Li Ruei－chi.Applying simulated annealing with matching improvement to solve fuzzy multi－objective unrelated parallel machine scheduling problems［D］.Taiwan：Yuan Ze U－niversity，2010.（in Chinese）

［33］ Chang Wei－shung，Chyu Chiuh－cheng，Li Ruei－chi.Archived simulated annealing for unrelated parallel machine scheduling to maximize satisfactions of makespan and tardiness［EB／OL］.［2012－05－18］.http：／／apiems.net／archive／apiems2010／pdf／AI／88.pdf.

［34］ Xiong Qing－h(huán)ui，ZhangYou－tong，Su Hai－feng，et al.Simulation research of the multilayer piezoelectric stack actuator based on the MOSA algorithm［J］.Small Internal Combustion Engine and Motorcycle，2011，40（1）：6－10.（in Chinese）

［35］ Xiong Qing－h(huán)ui，Zhang You－tong.Multi optimization simulation design of a high pressure common rail injector based on MOSA algorithm［J］.Transactions of the Chinese Society for Agricultural Machinery，2011，42（1）：27－30.（in Chinese）

［36］ Xiong Qing－h(huán)ui，Zhang You－tong，Wang Ding－biao，et al.Multi－objective optimizing simulation research of common rail injector ［J］.Journal of System Simulation，2011，23（6）：1137－1140.（in Chinese）

［37］ Li Tie－shuan，Zhang You－tong，Wang Ding－biao，et al.Optimization design of high－speed solenoid based on multi－objective simulated annealing method［J］.Vehicle Engine，2010（4）：6－10.（in Chinese）

［38］ Pan Jin－kun，Wang Xian－min.Multi－Objective optimization on the joint－double clamping unit［J］.Journal of Mechanical Transmission，2012，35（10）：81－85.（in Chinese）

［39］ Xiong Qing－h(huán)ui，Gu Hong－tao，Li Juan，et al.Multi－objectives optimization design on the on－off shift solenoid of integrated transmission ［J］.Vehicle ＆ Power Technology，2012（3）：1－4.（in Chinese）

［40］ He Guo－liang，Li Yuan－xiang，Wang Xuan，et al.Multiobjective simulated annealing for design of combinational logic circuits［C］∥Proc of the 6th World Congress on Intelligent Control and Automation （WCICA），2006：3481－3484.

［41］ Antunes C H，Lima P，Oliveira E，et al.A multi－objective simulated annealing approach to reactive power compensation［J］.Engineering Optimization，2011，43（10）：1063－1077.

［42］ Santamaria M L，Galmes S.Multi－objective simulated an－nealing approach for optimal routing in time－driven sensor networks［C］∥Proc of the 19th Annual IEEE International Symposium on Modeling，Analysis，and Simulation of Computer and Telecommunication Systems，2011：45－461.

［43］ Smith K I.A study of simulated annealing techniques for multi－objective optimization［EB／OL］.［2012－05－15］.https：／／eric.exeter.ac.uk／repository／bitstream／handle／10036／3176／ksmith＿thesis.pdf？sequence＝1.

［44］ Xu Y，Qu R.Solving multi－objective multicast routing problems by evolutionary multi－objective simulated annealing algorithms with variable neighborhoods［J］.Journal of the Operational Research Society，2011，62：313－325.

［45］ Varadharajan T K，Rajendran C.A multi－objective simulated－annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs［J］.European Journal of Operational Research，2005，167（3）：772－795.

［46］ Issam Z，Kamel Z，Khaled M，et al.A multi－agent system based on the multi－objective simulated annealing algorithm for the static dial a ride problem［C］∥Proc of the 18th World Congress of the International Federation of Automatic Control（IFAC），2011：2172－2177.

［47］ Issam Z，Khaled M，Kamel Z，et al.A new approach based on the multi－objective simulated annealing to solving the dynamic dial a ride problem［C］∥Proc of the 4th International Conference on Logistics（LOGISTIQUA’2011），2011：157－163.

［48］ Mokotoff E.Multi－objective simulated annealing for permutation flow shop problems［J］.Computational Intelligence in Flow Shop and Job Shop Scheduling，2009：101－150.

［49］ Kumral M.Application of chance－constrained programming based on multi－objective simulated annealing to solve a mineral blending problem［J］.Engineering Optimization，2003，35（6）：661－673.

［50］ Lucic P，Teodorovic D.Simulated annealing for the multiobjective aircrew rostering problem［EB／OL］.［2012－05－16］.http：／／filebox.vt.edu／users／duteodor／P%2034.pdf.

［51］ Safaei N，Banjevic D，Jardine A K S.Multi－objective simulated annealing for a maintenance workforce scheduling problem：A case study［EB／OL］.［2012－05－18］.http：／／delta.cs.cinvestav.mx／～ccoello／EMOO／safaei08.pdf.gz.

［52］ Ekbal A，Saha S，Uryupina O，et al.Multi－objective simulated annealing based approach for feature selection in anaphora resolution［C］∥Proc of DAARC’11，2011：47－58.

［53］ Ekbal A，Saha S.A multi－objective simulated annealing approach for classifier ensemble：Named entity recognition in Indian languages as case studies［J］.Expert Systems with Applications，2011，38（12）：14760－14772.

［54］ Kang Li－shan，Xie Yun，You Shi－yong，et al.Non－numerical parallel algorithm （The first volume）：Simulated annealing algorithm ［M］.Beijing：Science Press，1994.（in Chinese）

［55］ Coello C A C.Evolutionary multi－objective optimization：Some current research trends and topics that remain to be explored［J］.Fronters Computer Science in China，2009，3（1）：18－30.

［56］ Wang Ling.Intelligent optimization algorithm and its application［M］.Beijing：Tsinghua University Press，2003.（in Chinese）

［57］ Yang Hai－jun，Li Jian－wu，Li Min－qiang.Study on the pattern emergence and the difficulty of the evolutionary algorithm［M］.Beijing：Science Press，2012.（in Chinese）

［58］ Nam D K，Park C H.Multi－objective simulated annealing：A comparative study to evolutionary algorithms［EB／OL］.［2012－05－15］.http：／／citeseerx.ist.psu.edu／viewdoc／download？doi＝10.1.1.74.2194＆rep＝rep1＆type＝pdf.

［59］ Su C T，Hsu C M.Multi－objective machine－part cell formation through parallel simulated annealing［J］.International Journal of Production Research，1998，36（8）：2185－2207.

［60］ Dean J，Ghemawat S.MapReduce：Simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

［61］ Liu Chun－an.Dynamic multi－objective optimization evolutionary algorithm and its application［M］.Beijing：Science Press，2011.（in Chinese）

［62］ Jiao Li－cheng，Shang Rong－h(huán)ua，Ma Wen－ping，et al.Multiobjective optimization immune algorithm，theory and application［M］.Beijing：Science Press，2010.（in Chinese）

［63］ Zheng Xiang－wei，Liu Hong.A cooperative co－evolutionary andε－dominance based MOPSO［J］.Journal of Software，2007，18（Suppl）：109－119.（in Chinese）

附中文參考文獻(xiàn)：

［2］ 雷德明，嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京：科學(xué)出版社，2009.

［8］ 崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用［M］.北京：國防工業(yè)出版社，2008.

［22］ 張長林，余建星，楊振國.非線性約束最優(yōu)化問題的多目標(biāo)模擬退火算法［J］.復(fù)旦學(xué)報(bào)：自然科學(xué)版，2003，42（1）：93－97.

［23］ 蘆金嬋，李乃成，王偉東.基于模擬退火的多目標(biāo)優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003（23）：92－94.

［29］ 劉鵬飛，董守斌，曹以誠，等.多目標(biāo)優(yōu)化的非編碼RNA比對(duì)及預(yù)測 ［J］.計(jì)算機(jī)工程，2009，35（9）：225－226.

［31］ 鐘愛蓮.模糊多目標(biāo)非相關(guān)平行機(jī)臺(tái)排程問題之解算［D］.臺(tái)灣：元智大學(xué)，2009.

［32］ 李瑞琪.模擬退火結(jié)合配對(duì)機(jī)制求解多目標(biāo)非相關(guān)平行機(jī)臺(tái)排程問題［D］.臺(tái)灣：元智大學(xué)，2010.

［34］ 熊慶輝，張幽彤，蘇海峰，等.基于 MOSA算法的壓電堆執(zhí)行器多目標(biāo)優(yōu)化仿真研究 ［J］.小型內(nèi)燃機(jī)與摩托車，2011，40（1）：6－10.

［35］ 熊慶輝，張幽彤.基于MOSA算法的高壓共軌噴油器多目標(biāo)仿真優(yōu)化設(shè)計(jì) ［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2011，42（1）：27－30.

［36］ 熊慶輝，張幽彤，王定標(biāo)，等.高壓共軌噴油器多目標(biāo)優(yōu)化仿真研究 ［J］.系統(tǒng)仿真學(xué)報(bào)，2011，23（6）：1137－1140.

［37］ 李鐵栓，張幽彤，王定標(biāo)，等.基于多目標(biāo)模擬退火算法的高速電磁閥優(yōu)化設(shè)計(jì)［J］.車用發(fā)動(dòng)機(jī)，2010（4）：6－10.

［38］ 潘金坤，王賢民.雙曲肘合模機(jī)構(gòu)的多目標(biāo)優(yōu)化設(shè)計(jì)［J］.機(jī)械傳動(dòng)，2012，35（10）：81－85.

［39］ 熊慶輝，顧宏，李娟，等.綜合傳動(dòng)裝置換擋開關(guān)電磁閥多目標(biāo)優(yōu)化設(shè)計(jì)［J］.車輛與動(dòng)力技術(shù)，2012（3）：1－4.

［54］ 康立山，謝云，尤矢勇，等.非數(shù)值并行算法（第一冊(cè)）：模擬退火算法［M］.北京：科學(xué)出版社，1994.

［56］ 王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2003.

［57］ 楊海軍，李建武，李敏強(qiáng).進(jìn)化算法的模式涌現(xiàn)與困難性研究［M］.北京：科學(xué)出版社，2012.

［61］ 劉淳安.動(dòng)態(tài)多目標(biāo)優(yōu)化進(jìn)化算法及其應(yīng)用［M］.北京：科學(xué)出版社，2011.

［62］ 焦李成，尚榮華，馬文萍，等.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用［M］.北京：科學(xué)出版社，2010.

［63］ 鄭向偉，劉 弘.一種基于合作型協(xié)同和ε－占優(yōu)的多目標(biāo)微粒群算法［J］.軟件學(xué)報(bào)，2007，18（Suppl）：109－119.