【畢業(yè)學(xué)位論文】多目標(biāo)進(jìn)化算法及其在約束優(yōu)化中的應(yīng)用研究-模式識(shí)別與智能系統(tǒng)

分類號(hào) 密級(jí) U D C 編號(hào) 士學(xué)位論文 論 文 題 目 多目標(biāo)進(jìn)化算法及其在約束 優(yōu)化中的應(yīng)用研究 學(xué)科、專業(yè) 模式識(shí)別與智能系統(tǒng) 研究生姓名 曾威 導(dǎo)師姓名及 專業(yè)技術(shù)職務(wù) 蔡自興 教授 日 期 ts 要 科學(xué)和工程中的很多優(yōu)化問題都是多目標(biāo)問題，因此，對(duì)其進(jìn)行研究非常具有實(shí)際意義和科研價(jià)值。 多目標(biāo)優(yōu)化問題中各目標(biāo)之間往往相互制約，對(duì)其中一個(gè)目標(biāo) 優(yōu)化必須以其它目標(biāo)作為代價(jià)。 80 年代中期以來(lái)，進(jìn)化算法開始應(yīng)用于該問題，并行成了最近的一個(gè)熱門領(lǐng)域，對(duì)多目標(biāo)進(jìn)化算法的研究也是近年來(lái)求解多目標(biāo)優(yōu)化的重點(diǎn)。 本文首先對(duì)多目標(biāo)優(yōu)化問題的一般定義、 優(yōu)解集和優(yōu)邊界等進(jìn)行了討論，對(duì)多 目標(biāo)優(yōu)化進(jìn)化算法的國(guó)內(nèi)外研究現(xiàn)狀進(jìn)行了回顧，然后提出了兩種多目標(biāo)優(yōu)化進(jìn)化算法，并將多目標(biāo)優(yōu)化的思想用來(lái)求解約束優(yōu)化問題。主要內(nèi)容如下： 1、將多目標(biāo)屬性決策方法中的 引入到多目標(biāo)優(yōu)化進(jìn)化算法中，提出了一種新的多目標(biāo)優(yōu)化算法。構(gòu)造出一種新的超序關(guān)系對(duì)個(gè)體進(jìn)行排序，并證明了該超序關(guān)系比 劣關(guān)系弱，利用此超序關(guān)系能增加進(jìn)化過(guò)程中的選擇壓，加快收斂速度。通過(guò)數(shù)據(jù)試驗(yàn)，表明算法能很好地收斂到 優(yōu)，有效保持解的多樣性。 2、提出了一種基于差異進(jìn)化 的多目標(biāo)優(yōu)化算法，利用 優(yōu)超關(guān)系來(lái)保存進(jìn)化中的非劣個(gè)體 ，并對(duì) 法中個(gè)體存檔準(zhǔn)則進(jìn)行了改進(jìn)。將 過(guò)對(duì)一系列標(biāo)準(zhǔn)的測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)， 實(shí)驗(yàn)結(jié)果表明該算法在保持解集分布性和收斂性方面非常有效。 3、將多目標(biāo)優(yōu)化思想引入到 約束優(yōu)化中，提出了非劣個(gè)體替換準(zhǔn)則。 為了有效利用不可行解， 提出了一種不可行解保存和替換機(jī)制，對(duì) 6 個(gè)測(cè)試函數(shù)進(jìn)行了測(cè)試，測(cè)試結(jié) 果表明該算法優(yōu)于其它算法。 最后，提出了多目標(biāo)進(jìn)化算法中值得進(jìn)一步研究的問題。 關(guān)鍵詞 多目標(biāo)進(jìn)化算法 , 約束優(yōu)化 , , 差異進(jìn)化 in of to do a to a of on is is of of at by as 1、 a a in to to a is to be to of 2、 a on a in to to a of We in to to of in of an is to is on is to be in 第一章 緒論.目標(biāo)優(yōu)化概述 .化算法及多目標(biāo)進(jìn)化算法 .束優(yōu)化進(jìn)化算法 .論文的主要工作 .第二章 多目標(biāo)進(jìn)化算法綜述.題的描述 .集函數(shù)法 .論研究方面 .第三章 基于 的多目標(biāo)優(yōu)化進(jìn)化算法.體的多樣性和分布性 .法描述 .法流程 .叉算子 .應(yīng)值分配及環(huán)境選擇 .驗(yàn)分析 .試函數(shù) .試結(jié)果 .結(jié) .第四章 差異進(jìn)化多目標(biāo)優(yōu)化算法.異進(jìn)化算法介紹 .關(guān)研究 .體算法描述 .體比較 .案群體的更新 .驗(yàn)結(jié)果及其比較 .價(jià)方法： .試函數(shù)及實(shí)驗(yàn)結(jié)果 .結(jié) .第五章 多目標(biāo)優(yōu)化進(jìn)化算法求解約束優(yōu)化問題 .束優(yōu)化問題介紹 .束處理技術(shù) .于多目標(biāo)優(yōu)化的進(jìn)化算法 . 劣個(gè)體替換策略 .于群體的算法發(fā)生器模型 .可行解存檔和替換機(jī)制 .組算子 .體流程 .驗(yàn)結(jié)果分析 .論 .第六章 總結(jié)與展望.文工作總結(jié) .一步的研究方向 .參考文獻(xiàn) .致 謝 .攻讀學(xué)位期間主要的研究成果. 第一章 緒論 j 1第一章 緒論 目標(biāo)優(yōu)化概述 在實(shí)際應(yīng)用中，人們經(jīng)常遇到需要使多個(gè)目標(biāo) 在給定區(qū)域上均盡可能最佳的優(yōu)化問題。例如在設(shè)計(jì)新產(chǎn)品時(shí)，既要考慮 使產(chǎn)品具有較好的性能，又要考慮使其制造成本最低，同時(shí)還要考慮產(chǎn)品的可 制造性、可靠性、可維修性等，這些設(shè)計(jì)目標(biāo)的改善可能相互抵觸，譬如好的 可維修性會(huì)引起可靠性的降低，因此須在這些設(shè)計(jì)目標(biāo)之間取一折衷結(jié)果。再 如投資問題，一般希望所投入的資金量少，風(fēng)險(xiǎn)最小，且所獲得的收益最大。 這種多于一個(gè)的數(shù)值目標(biāo)在給定區(qū)域上的最優(yōu)化問題一般就稱為多目標(biāo)優(yōu)化問題 (1。多目標(biāo)有時(shí)也稱多準(zhǔn)則、多屬性或多指標(biāo)，目標(biāo)分為總目標(biāo)和子目標(biāo)，這里所謂的多目標(biāo)優(yōu)化 是指對(duì)多個(gè)子目標(biāo)同時(shí)實(shí)施最優(yōu)化。這些實(shí)際問題非常復(fù)雜、困難，要很好地 解決這類優(yōu)化問題需要科研人員投入更多的精力。因此，解決多目標(biāo)優(yōu)化問題 是一個(gè)非常有實(shí)際意義和科研價(jià)值的課題。 化算法及多目標(biāo)進(jìn)化算法 進(jìn)化算法 一種模擬自然進(jìn)化過(guò)程的隨機(jī)優(yōu)化方法。 起源可追溯到 50 年代末 70 年代以來(lái)產(chǎn)生了幾種進(jìn)化方法如：遺傳算法 、 進(jìn)化規(guī)劃 、和進(jìn)化策略 進(jìn)化算法是模擬由個(gè)體組成的群體的集體學(xué)習(xí)過(guò)程，其中每個(gè)個(gè)體表示給定問題搜索 空間中的一點(diǎn)，進(jìn)化算法從任一初始的群體出發(fā)，通過(guò)隨機(jī)選擇（在某些算法 中是確定的）變異和交叉（有時(shí)被完全省去）過(guò)程使群體進(jìn)化到搜索空間中越來(lái)越好的區(qū)域2,3。 差異進(jìn)化算法由 提出，它是一種基于種群的隨機(jī)搜索算法，對(duì)實(shí)數(shù)值、多模式目標(biāo)函數(shù)優(yōu)化具有很好 的尋優(yōu)效果。差異進(jìn)化算法的特征是：簡(jiǎn)單，高效，采用浮點(diǎn)數(shù)編碼而非二進(jìn) 制編碼，對(duì)初始值無(wú)要求，收斂速度快，適合求解非線性問題。同其他進(jìn)化算 法類似，差異算法也是先隨機(jī)產(chǎn)生初始種群，然后采用選擇，變異交叉等操作 ，對(duì)種群進(jìn)行不斷的優(yōu)化。在本文第四章中有對(duì)差異進(jìn)化算法的詳細(xì)介紹。 最近大量事例和跡象表明 機(jī)理最適合求解多目標(biāo)優(yōu)化,因?yàn)樗鼈兛稍趩屋喣M過(guò)程中找到多個(gè) 優(yōu)解，通過(guò)逐代組合尋找具有某些特征的碩士學(xué)位論文 第一章 緒論 j 2個(gè)體。甚至有的學(xué)者認(rèn)為，在多目標(biāo)優(yōu)化領(lǐng)域 優(yōu)于其它盲目搜索方法5,6。雖然這種提法與最優(yōu)化領(lǐng)域中的沒有免費(fèi)的午餐（ no 理7不太吻合，但迄今為止還沒有找到其它方法比 能有效地解決。多目標(biāo)進(jìn)化算法（ 國(guó)外的許多應(yīng)用案例和掀起的研究熱潮已成為事實(shí)。 進(jìn)化算法應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域， 始于 80 年代中期9,10。 在 19911994 年期間，有幾種 提出來(lái)11,12,13，后來(lái)這些方法及其變種在實(shí)際多目標(biāo)優(yōu)化問題中得到了成功的應(yīng)用14,15。近年來(lái)一些學(xué)者集中研究了基于進(jìn)化算法的多目標(biāo)搜索中的某些專題，如 優(yōu)前端的收斂性16、小生境技術(shù)17、精英策略18,19。同時(shí)有關(guān)權(quán)威人士在不同時(shí)間對(duì) 別進(jìn)行了總結(jié)和綜述20,21。 束優(yōu)化進(jìn)化算法 約束優(yōu)化問題（稱 一類廣泛存在實(shí)際工程中但又較難求解的問題， 傳統(tǒng)的求解這類問題的方法通常是基于梯度的搜索方法，如可行方向法、投影 梯度法、簡(jiǎn)約梯度法、各類外點(diǎn)罰函數(shù)法和內(nèi)點(diǎn)法、些方法存在的主要問題是求解需要設(shè)置很好的初值點(diǎn)和需要函數(shù)的梯 度信息，他們對(duì)于不可導(dǎo)、可行域不連通、甚至根本沒有顯式數(shù)學(xué)表達(dá)式等問 題無(wú)能為力。同傳統(tǒng)的優(yōu)化方法相比，進(jìn)化算法更適合于求解約束優(yōu)化問題，已有許多學(xué)者進(jìn)行了廣泛的研究，并且提出了大量的約束優(yōu)化進(jìn)化算法22,23,24,25,26。 進(jìn)化算法在約束優(yōu)化問題中的成功應(yīng)用，取決于以下幾個(gè)主要原因： 1 進(jìn)化算法從一個(gè)群體即多個(gè)點(diǎn)而 不是一個(gè)點(diǎn)開始搜索，這使它能以較大概率找到全局最優(yōu)解； 2 同傳統(tǒng)優(yōu)化方法相比，進(jìn)化算法對(duì)所優(yōu)化問題的特征不敏感； 3 進(jìn)化算法很容易執(zhí)行和使用。 論文的主要工作 在吸取已有研究成果的基礎(chǔ)上，本文設(shè)計(jì)和討 論了兩個(gè)多目標(biāo)優(yōu)化算法，并將多目標(biāo)優(yōu)化的思想應(yīng)用到約束優(yōu)化中。 1）針對(duì)單純 化算法很難解決目標(biāo)數(shù)目很多的優(yōu)化問題，本文在多個(gè)指標(biāo) 之間引入偏好信息，提出一種求解高維多目標(biāo)優(yōu)化的新型進(jìn)化算法，使進(jìn)化群 體按協(xié)調(diào)模型進(jìn)行偏好排序而不是單純的基于 于關(guān)系來(lái)比較個(gè)體優(yōu)劣。 2）將 水平比較準(zhǔn)則引入到多目標(biāo)進(jìn)化算法中，提出一種新的基于差異進(jìn)化的多目標(biāo)進(jìn)化算法。 后續(xù)章節(jié)安排如下： 碩士學(xué)位論文 第一章 緒論 j 3第二章 給出了多目標(biāo)優(yōu)化問題的一般定義， 對(duì)具有代表性的多目標(biāo)優(yōu)化進(jìn)化算法進(jìn)行了介紹并分析了各算法的優(yōu)點(diǎn)以及 不足之處，對(duì)國(guó)內(nèi)外的研究現(xiàn)狀進(jìn)行了介紹。 第三章 首先分析了基于 較準(zhǔn)則在求解高維多 目標(biāo)優(yōu)化問題的缺陷，然后對(duì)多目標(biāo)決策中的 行了介紹，將其引入到多目標(biāo)優(yōu)化進(jìn)化算法中，定義了一種新的關(guān)系，提出了一個(gè) 新的多目標(biāo)優(yōu)化算法，最后，用實(shí)驗(yàn)方法驗(yàn)證了本文提出的算法的有效性和正確性。 第四章 首先對(duì)差異進(jìn)化算法進(jìn)行了介紹，提出了一種新算法，在處理約束條件時(shí)，將 水平比較準(zhǔn)則引入到算法中，利用 優(yōu)劣關(guān)系來(lái)保存外部種群個(gè)體，提高分布的均勻性，最后對(duì)一些測(cè)試函數(shù) 進(jìn)行了測(cè)試，同目前流行的算法進(jìn)行了比較。 第五章 首先對(duì)約束優(yōu)化問題作了簡(jiǎn)單的介紹， 對(duì)目前存在的算法進(jìn)行了分類。接著，提出了一種基于多目標(biāo)優(yōu)化技術(shù)的 約束優(yōu)化進(jìn)化算法。該方法的主要特點(diǎn)是利用多目標(biāo)優(yōu)化思想比較和選擇個(gè)體 ，并將基于群體的算法發(fā)生器模型與一個(gè)不可行解存檔和替換機(jī)制相結(jié)合。最后，通過(guò) 6 個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)對(duì)新算法的優(yōu)化性能進(jìn)行了測(cè)試。 第六章 對(duì)于本論文的研究進(jìn)行了總結(jié)， 并對(duì)有待進(jìn)一步研究的問題進(jìn)行了分析和展望。 碩士學(xué)位論文 第二章 多目標(biāo)進(jìn)化算法綜述 j 4第二章 多目標(biāo)進(jìn)化算法綜述 進(jìn)化算法（ 其擅長(zhǎng)求解高度復(fù)雜的非線性問題而得到了非常廣泛的應(yīng)用，同時(shí)它又具有 較好的通用性。在解決只有單個(gè)目標(biāo)的復(fù)雜系統(tǒng)優(yōu)化問題時(shí)，充分展現(xiàn)了進(jìn)化 算法的優(yōu)勢(shì)。但是，現(xiàn)實(shí)世界中的優(yōu)化通常是由多個(gè)目標(biāo)組成的，如一個(gè)國(guó)家 的最優(yōu)良性發(fā)展，涉及到經(jīng)濟(jì)的快速增長(zhǎng)、社會(huì)秩序的穩(wěn)定等多個(gè)方面。在這 里，經(jīng)濟(jì)的快速增長(zhǎng)和社會(huì)秩序穩(wěn)定這兩個(gè)優(yōu)化目標(biāo)是相輔相成的，互相促進(jìn) 的，通常稱之為一致的。與此同時(shí)，有一些優(yōu)化問題，如產(chǎn)品質(zhì)量與生產(chǎn)成本 ，也是多目標(biāo)優(yōu)化問題，但其被優(yōu)化的多個(gè)目標(biāo)之間是相互沖突的（站在生產(chǎn)者的角度來(lái)看） 。當(dāng)我們使用進(jìn)化算法來(lái)解決多個(gè)目標(biāo)的優(yōu)化問題時(shí)，就顯得有 點(diǎn)力不從心了。我們?yōu)榱藢ふ铱偰繕?biāo)的最優(yōu)化，對(duì)于相互沖突的子目標(biāo)通常需 要綜合考慮，即對(duì)各個(gè)子目標(biāo)進(jìn)行折衷（ ，這樣就存在多個(gè)解。針對(duì)多目標(biāo) 的優(yōu)化問題，出現(xiàn)了多目標(biāo)進(jìn)化算法（ . 無(wú)論在科學(xué)或工程上，多目標(biāo)優(yōu)化問題都是非 常重要的研究課題。這不僅僅是因?yàn)樵S多現(xiàn)實(shí)世界中的問題涉及到多目標(biāo) 優(yōu)化，還有一些與多目標(biāo)優(yōu)化有關(guān)的問題也是難以回答的，如最優(yōu)解，它不同 于單目標(biāo)的優(yōu)化，通常由多個(gè)；對(duì)于多個(gè)最優(yōu)解，究竟哪個(gè)是我們要找的呢？這取決于決策者。 早在 1967 年 建議采用基于進(jìn)化的搜索來(lái)處理多目標(biāo)優(yōu)化問題，但他沒有具體實(shí)現(xiàn)。 1984 年， 次在機(jī)器學(xué)習(xí)中實(shí)現(xiàn)了向量評(píng)估遺傳算法（ 。此后，多目標(biāo)進(jìn)化算法的研究進(jìn)入了低谷，直至 1989 年 其著作 ，提出了用進(jìn)化算法實(shí)現(xiàn)多目標(biāo)的優(yōu)化技術(shù)， 使多目標(biāo)進(jìn)化算法的研究出現(xiàn)了重大轉(zhuǎn)折。 近 17 年來(lái)，多目標(biāo)進(jìn)化算法（或多目標(biāo)遺傳算法， 起了許多研究者的廣泛關(guān)注，并涌現(xiàn)出了大量的研究成果。 題的描述 為了方便闡述多目標(biāo)進(jìn)化算法的研究現(xiàn)狀，我們?cè)诖讼扔懻撘幌露嗄繕?biāo)優(yōu)化問題的一般定義。值得注意的是，有關(guān)多目標(biāo)優(yōu)化問題及其最優(yōu)解的定義在許多專著或論文上都有介紹，此處討論的定義只是其中的一種。 給定決策向量12 , ,. xx x= ， 它滿足下列約束21： 碩士學(xué)位論文 第二章 多目標(biāo)進(jìn)化算法綜述 j 5( ) 0 1,2,.,i k= (2( ) 0 1,2,.,i l= (2設(shè)有 r 個(gè)優(yōu)化目標(biāo)，且這 r 個(gè)優(yōu)化目標(biāo)可能是相互沖突的，優(yōu)化目標(biāo)可表示為： 12()(), (),.()fX f X f X= （ 2 尋求*12 , ,. xx x= ，使*()f X 在滿足約束（ 2（ 2同時(shí)達(dá)到最優(yōu)。 這里所講的最優(yōu)，是由 1896 年提出的，故稱之為 ，定義如下： 稱*X F 是最優(yōu)解（即 ，若 X F 滿足： 或者*() ( )= （ 2 或者至少存在一個(gè) j，使： *() ( ) (2其中 F 是滿足式（ 1式（ 1可行解集，即： | ( ) 0, 1, 2,. ; ( ) 0, 1, 2,. i j l= = = = (2通常情況下，最優(yōu)解不只一個(gè)，而是一個(gè)最優(yōu)解集（ 。所需做的工作時(shí)，構(gòu)造非支配集（ ,并使非支配集不斷逼近最優(yōu)解集，最終達(dá)到最優(yōu)。 多目標(biāo)進(jìn)化算法的研究主要實(shí)現(xiàn)三個(gè)目標(biāo)。一是使算法收斂到 是使解集具有好的分布性或多樣性；三是在確保算法收斂到 優(yōu)邊界，并使解集具有好的分布性的 前提下，算法具有較快的收斂速度。從已有的研究成果中，如文獻(xiàn) 27，可以看出，具有良好分布性的算法通常需要較大的時(shí)間開銷；同樣地，運(yùn)行效率比 較高的算法，其解集的分布性和多樣性就相對(duì)較差一些。接下來(lái)，本文將較為 詳細(xì)地介紹多目標(biāo)優(yōu)化進(jìn)化算法的研究成果，同時(shí)，也概要性地介紹所存在的 不足。概括起來(lái)，當(dāng)前比較典型的多目標(biāo)進(jìn)化算法主要有： （ 1） 聚集函數(shù)法（ （ 2） 向量評(píng)估進(jìn)化算法（ （ 3） 4） 5） 提出的 6） 提出的 7） 提出的 士學(xué)位論文 第二章 多目標(biāo)進(jìn)化算法綜述 j 集函數(shù)法 聚集函數(shù)法將多目標(biāo)優(yōu)化問題中的多個(gè)目標(biāo)進(jìn) 行線性組合，并對(duì)各個(gè)子目標(biāo)賦予不同的權(quán)值，將其轉(zhuǎn)化為單目標(biāo)問題的優(yōu)化。 設(shè)有 r 個(gè)子目標(biāo) )、 )、 、 )， 其對(duì)應(yīng)的適應(yīng)度函數(shù)分別為 、用權(quán)重系數(shù)法可綜合目標(biāo)適應(yīng)度為： 12.+ (2其中 0 1,2,.= 且滿足：11（ 2 優(yōu)化目標(biāo)可表示為：1()f (2這是早期使用的方法，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化 為單個(gè)目標(biāo)的優(yōu)化問題，方法比較簡(jiǎn)單。這種方法的主要優(yōu)點(diǎn)是效率比較 高，比較適合產(chǎn)生初始非支配集（ ， 然后再用其他方法進(jìn)一步優(yōu)化。 但缺點(diǎn)也比較明顯，如在群體進(jìn)化過(guò)程中通常要不斷地改變權(quán)值， 而對(duì)一個(gè)具體的多目標(biāo)優(yōu)化問題，要準(zhǔn)確地找出權(quán)重系數(shù)的變化規(guī)律也不是一件 容易的事情；有時(shí)根據(jù)需要也可以考慮使用懲罰函數(shù)（ ,對(duì)參數(shù)或懲罰函數(shù)稍有改變，算法都表現(xiàn)得非常靈敏。更為嚴(yán)重的是，當(dāng)搜索空間 呈凹狀時(shí)，無(wú)論如何改變權(quán)值都難以找到合適的最優(yōu)解（即 。這種方法已被證明存在著嚴(yán)重問題。 向量評(píng)估遺傳算法 1984 年， 在他的博士論文中， 提出了向量評(píng)估進(jìn)化算法 （ 10，并用 解多目標(biāo)優(yōu)化問題，但似乎只能發(fā)現(xiàn)最優(yōu)邊界（ 的極端點(diǎn)，因?yàn)樗荒芨鶕?jù)各子目標(biāo)的屬性（ 行折衷和權(quán)衡。 簡(jiǎn)單進(jìn)化算法（ 行擴(kuò)充，使 單個(gè)目標(biāo)的處理變成 而可以對(duì)目標(biāo)向量進(jìn)行處理，即對(duì)多個(gè)目標(biāo)進(jìn)行處理。設(shè)有 r 個(gè)目標(biāo)，針對(duì)每個(gè)目標(biāo)利用比例選擇算法，分別可產(chǎn)生 r 個(gè)子群體，每個(gè)子群體的大小為 N/r，其中 N 為群體大小。將 r 個(gè)子群體合并為一個(gè)群體大小為 N 的新群體，進(jìn)行交叉操作和變異操作。 識(shí)到，采用他的 產(chǎn)生的非支配解（ 是全局的，因?yàn)槠浞侵浣饧偸窍拗圃诋?dāng)前群體，局部的被支配個(gè)體（ 定是全局被支配個(gè)體， （ ，但局部的非支配個(gè)體（ 必就是全局非支配個(gè)體（ 。一個(gè)個(gè)體在當(dāng)前是非支配的，可能在下碩士學(xué)位論文 第二章 多目標(biāo)進(jìn)化算法綜述 j 7一代或后續(xù)代變成被支配個(gè)體。另一 個(gè)更為嚴(yán)重的問題就是“物種形成（ ” ，如在群體中可能存在著某些方 面表現(xiàn)突出的物種。究其原因是因?yàn)樵谶x擇操作時(shí)只考慮了一個(gè)目標(biāo) 而忽視了其它的目標(biāo)。 “物種形成（ ” 與尋求折衷解 （ 的目標(biāo)是不一致的。 主要優(yōu)點(diǎn)是簡(jiǎn)單，但當(dāng)搜索空間呈凹狀時(shí)難以找到 優(yōu)解集（ 。 提出了一種方法 13， 對(duì)每個(gè)個(gè)體分別計(jì)算其分類序號(hào)（ ，所有非支配個(gè)體的分類序號(hào)定義為 1，其它個(gè)體的分類序號(hào)為支配它的個(gè)體數(shù)目加 1。 設(shè) i 的個(gè)數(shù)， 則對(duì)任意一個(gè)個(gè)體 i 有分類序號(hào)： i)=1+n; (2這樣有可能存在多個(gè)個(gè)體具有相同的分類序號(hào) 的情況，選擇操作按分類序號(hào)從小到大依次進(jìn)行，具有相同分類序號(hào)者用目標(biāo)函數(shù)共享機(jī)制進(jìn)行選擇。 在 ，依據(jù)個(gè)體之間的支配關(guān)系來(lái)確定個(gè)體的分類序號(hào)，這是一個(gè)非常重要的工作。 但這種方法可能產(chǎn)生較大的選擇壓力從而導(dǎo)致非成熟收斂。此外，當(dāng)多個(gè)不同的 優(yōu)解（ 應(yīng)于相同的目標(biāo)函數(shù)值時(shí)， 以找出多個(gè)解。 主要優(yōu)點(diǎn)是運(yùn)行效率高，同時(shí)比較易于實(shí)現(xiàn)。它的不足之處是過(guò)于依賴共享參數(shù)的選擇。 目標(biāo)進(jìn)化算法的目標(biāo)是尋找一個(gè)滿足總目標(biāo) 最優(yōu)化的解集，這個(gè)解集稱之為 優(yōu)解集（ 。 議使用“非支配排序（ 方法9， 使候選解不斷集散到最優(yōu)解集邊界上 （ 。 基于 配關(guān)系，提出了 A 13。采用小生境技術(shù)（ 現(xiàn)共享來(lái)維持候選解集（ 多樣性。 隨機(jī)地從進(jìn)化群體中選擇兩個(gè)個(gè)體 i 和 j，再隨機(jī)地從進(jìn)化群體中選取一個(gè)比較集 于 2，一般約為 10） ，然后用個(gè)體 i 和個(gè)體 j 分別與 果其中之一受 配（稱之為 ，而另一個(gè)個(gè)體不受 配（稱之為 ，那么這個(gè)被選中參入下一代進(jìn)化。 如果個(gè)體 i 和個(gè)體 j 都不受碩士學(xué)位論文 第二章 多目標(biāo)進(jìn)化算法綜述 j 8或都受 配，則只能采用共享機(jī)制來(lái)選取其中之一參入下一代進(jìn)化。將選擇共享適應(yīng)度大的（或小生境計(jì)數(shù)小的）個(gè)體參入下一代進(jìn)化操作。 適應(yīng)度共享（ 實(shí)現(xiàn)群體多樣性的有效方法。設(shè)個(gè)體 i 針對(duì)某個(gè)子目標(biāo)的適應(yīng)度為 體 i 的小生境計(jì)數(shù)（ (,)d i j(2其中 當(dāng)前進(jìn)化群體， (, )di i 和 j 之間的距離或稱相似程度，shd為共享函數(shù)， shd的定義如下： (2其中小生境半徑（ ，通常由用戶根據(jù)最優(yōu)解集（ 個(gè)體之間的最小期望間距來(lái)確定。 定義 fi/，此處 i 的小生境之聚集程度。同一小生境內(nèi)的個(gè)體互相降 低對(duì)方的共享適應(yīng)度。個(gè)體的聚集程度越高，其相對(duì)于適應(yīng)度的共享適應(yīng)度就 被降低的越多。使用共享適應(yīng)度的目的在于將進(jìn)化群體分散到整個(gè)搜索空間（ 不同峰值區(qū)域上。在經(jīng)典 引入小生境技術(shù)的目的是為了防止早熟收斂。在 ，當(dāng)共享適應(yīng)度與錦標(biāo)賽選擇（ 結(jié)合時(shí)可能會(huì)出現(xiàn)混沌行為（ 19，此時(shí)小生境子群體內(nèi)不會(huì) 出現(xiàn)劇烈的波動(dòng)。文獻(xiàn) 19建議不斷修改共享參數(shù)。 主要優(yōu)點(diǎn)是運(yùn)行效率比較高，且能獲得較好的 優(yōu)邊界（ 。它的不足是共享參數(shù)的選擇以及比較集大小的選擇沒有一個(gè)通用的法則。 提出的 提出了非支配集排序方法 8。算法采用了快速排序的方法來(lái)構(gòu)造非支配集：根據(jù)非支配級(jí)別對(duì)一個(gè)規(guī)模為 N 的種群進(jìn)行排序，每一個(gè)解需要與任何一個(gè)其它的解比較是否被支配，在 所有種群個(gè)體中，尋找出非劣個(gè)體，歸為第一層（ ，找出剩下個(gè)體中的非劣個(gè)體，歸為第二層（ ，重復(fù)上述過(guò)程，直到所有個(gè)體都被分屬某一層次中。 另外它采用聚集比較過(guò)程保持解得分布性：計(jì) 算同一面上相鄰的兩個(gè)個(gè)體在每個(gè)目標(biāo)上距離的平均值。在種群中將僅包含個(gè)體 i 的最大的立方體的大小為密集距離） 。然后基于密集距離對(duì)同一個(gè)體面上的點(diǎn)進(jìn)行排序，選擇分布度較好（密集距離大）的個(gè)體。 01/= N ,則對(duì)1取某種截?cái)嗖呗?使其規(guī)模變?yōu)?N ,同時(shí)使外部?jī)?yōu)勢(shì)群體中的個(gè)體具有良好的分布性。 若|1 ，則按下列方法(次選取個(gè)體 i 從1刪除： 10|: 。要滿足隨機(jī)產(chǎn)生的整數(shù)1r ，2r ，3r 互不相同這個(gè)條件， 值至少應(yīng)為 4。 F 是一個(gè)實(shí)值常數(shù)，取值范圍為 0， 2，用來(lái)控制差異的變化，即23,rG x 的幅度變化。圖 4描述了不同的參數(shù)向量在變異向量,1生的過(guò)程中所起的作用。 交叉 為了增加擾動(dòng)參數(shù)向量的多樣性， 引入交叉操作， 為此， 生成試驗(yàn)向量 （ ； ,1 1,1 2,1 ,1(, ,., )iG iG u+ += (4這里 (4在公式 4， ()j 是第 j 個(gè)服從均勻分布的隨機(jī)數(shù)，取值在 0， 1之間。 交叉常數(shù)，取值范圍為 0， 1。 ()i 是在 1， 2， D 中隨機(jī)選取的一個(gè)標(biāo)志位， 用以確保向量,1u+中至少有一個(gè)參數(shù)來(lái)自向量,1 圖 4 維向量交叉機(jī)制的示例。 ,1,1,() ()() ()1,2,.,v if j CR or j if j CR or j =碩士學(xué)位論文 第四章 差異進(jìn)化多目標(biāo)優(yōu)化算法 22圖 4體交叉示意圖 選擇 為了選擇向量進(jìn)入下一代群體 （ G+1 代） ， 將試驗(yàn)向量,1目標(biāo)向量,果向量,1生的函數(shù)值小于,產(chǎn)生的函數(shù)值，則,1入下一代種群，即,1 ,1iG u+= ，否則，,入下一代種群，即,1 ,iG x+= 。 偽代碼 圖 4示的 C 偽代碼充分說(shuō)明了 簡(jiǎn)潔性。 其它形式的差異進(jìn)化算法 上面所講述的只是差異進(jìn)化算法的一種形式， 還有其它變種，也被證明是高效的。為了便于對(duì)這些算法進(jìn)行分類，我們引入如下標(biāo)識(shí)： x / y / z (4x 指明當(dāng)前變異的向量是在種群中隨機(jī)選擇（ 是選擇種群中函數(shù)花費(fèi)最小的向量（ 。 y 為差異向量的數(shù)目，一般為 1 或 2 z 為交叉策略的類型。 采用這種標(biāo)識(shí)，上述的差異進(jìn)化算法可表示為 1 / 它形式的差異進(jìn)化算法有： 2 / 1234,1 , , , , ,()iG r G r G r G r + (4 2 / 12345,1 , , , , ,iG r G r G r G r G r + + (4to 2 / 碩士學(xué)位論文 第四章 差異進(jìn)化多目標(biāo)優(yōu)化算法 2312,1 , , , , ,()()iG iG iG r G r + + (4圖 4E 的 C 偽代碼 /* 碩士學(xué)位論文 第四章 差異進(jìn)化多目標(biāo)優(yōu)化算法 27定義如下： (P ) )f (4 表明最小化問題是基于 比較準(zhǔn)則進(jìn)行的， 表明問題 P 的約束條件違反程度由 () 0 松弛為 () ，約束條件降低。 (P ) ) )f (4從上式可以看出，采用 水平比較，一個(gè)約束優(yōu)化問題可以轉(zhuǎn)換為相應(yīng)的無(wú)約束優(yōu)化問題。將 水平比較準(zhǔn)則同現(xiàn)有的無(wú)約束優(yōu)化方法結(jié)合起來(lái)，可為求解約束優(yōu)化問題提供新的途徑。在求解無(wú)約 束優(yōu)化問題的相關(guān)算法中，將通常的比較準(zhǔn)則用 水平比較替換，即可利用算法來(lái)求解約束優(yōu)化問題。需要注意的是，當(dāng) 變?yōu)?0 時(shí)，就可得到原問題的最優(yōu)解。類似于在罰函數(shù)方法中，將懲罰系數(shù)增加到無(wú)窮大。 的控制 一般情況下， 的值不需要特別的控制， 很多約束優(yōu)化問題可直接按照當(dāng) 等于 0 時(shí)字典排序求解。但當(dāng)問題中存在等式約束條件時(shí)