（管理科學與工程專業(yè)論文）遺傳算法及其在多目標優(yōu)化中的應用研究.pdf

遺傳算法及其在多目標優(yōu)化中的應用研究 摘要 遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的一種新的 迭代的全局優(yōu)化搜索算法，已經廣泛地應用到組合優(yōu)化問題求解、自適應控制、 規(guī)劃設計、機器學習和人工生命等領域。由于現(xiàn)實世界中存在的問題往往呈現(xiàn) 為多目標屬性，而且需要優(yōu)化的多個目標之間又是相互沖突的，從而多目標遺 傳算法應運而生，它使得進化群體并行搜尋多個目標，并逐漸找到問題的最優(yōu) 解。 本文在廣泛深入地查閱國內外文獻的基礎上，對遺傳算法及其面向多目標 優(yōu)化問題的基礎理論和基本方法進行了深入的理論研究和實驗分析，主要內容 如下： 系統(tǒng)、詳盡地介紹了遺傳算法的一般流程和基本理論、方法，以及面向多 目標優(yōu)化問題的遺傳算法的基本理論和方法。對經典的方法進行了全面的分析 和比較，指出其應用范圍、不足之處，并在此基礎之上提出了改進的算法。 提出了對遺傳算法的改進策略，在具體問題中結合相應的特點再作相應的 改進，通過t s p 等算例的驗證，表明算法是可行的，同時也提高了算法的效率。 介紹了多目標優(yōu)化問題的基本概念和實現(xiàn)步驟，探討了多種采用遺傳算法 的實現(xiàn)方法并比較了其優(yōu)缺點，表明了遺傳算法用來解決多目標優(yōu)化問題的有 效性。該文以n s g a i i 為基準，提出了改進的多目標遺傳算法。針對多目標j s s p 問題，比較試驗結果表明算法在運行效率與保持群體多樣性等方面取得了較好 效果。 關鍵詞：遺傳算法；多目標遺傳算法；p a r e t o 最優(yōu)解；多目標優(yōu)化 小生鏡技術 g e n e t i ca l g o r i t h ma n di t sa p p l i c a t i o nr e s e a r c hi n m u l t i - o b j e c t i v eo p t i m i z a t i o n a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sas e to fn e w g l o b a l o p t i m i s t i cr e p e a t e d l ys e a r c h a l g o r i t h mw h i c hs i m u l a t e st h ep r o c e s so fc r e a t u r ee v o l u t i o nt h a to fd a r w i n i a n s g e n e t i cs e l e c t i o na n dn a t u r a le l i m i n a t i o n i ti sw i d e l ya p p l i e dt ot h ed o m a i no f c o m b i n a t i o n a l e v o l u t i o n a r yp r o b l e ms e e k i n g ，s e l f - a d a p tc o n t r o l l i n g ，p l a n n i n g d e v i s i n g ，m a c h i n el e a r n i n ga n da r t i f i c i a l l i f e e t c h o w e v e r ，t h e r e a r e m u l t i - o b j e c t i v ea t t r i b u t e si nr e a l - w o r l do p t i m i z a t i o np r o b l e m st h a ta l w a y sc o n f l i c t ， s ot h em u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ( m o g a ) i sp u tf o r w a r d m o g ac a nd e a l s i m u l t a n e o u s l yw i t hm a n yo b j e c t i o n s ，a n df i n dp a r e t o o p t i m a ls o l u t i o n sg r a d u a l l y b a s e do ne x t e n s i v ea n dd e e pr e v i e wo fl i t e r a t u r e ，at h o r o u g ha n a l y s i sa n d r e s e a r c ho nm a n yt h e o r e t i c a la n da p p l i c a t i o no r i e n t e dp r o b l e m si sp r e s e n t e d t h e m a i nc o n t e n t sf o l l o w ： t h eb a s i ct h e o r ya n d a p p l i c a t i o n o fg a sa n dg a sf o r m u l t i - o b j e c t i v e o p t i m i z a t i o na r es y s t e m a t i c a l l ya n dt h o r o u g h l yi n t r o d u c e d b ya n a l y z i n go nt h e c l a s s i c a l m e t h o d s ，t h et h e s i sp o i n t so u tt h e i rs p e c i a la p p l y i n ga r e a sa n d s h o r t c o m i n g s s o m ei m p r o v e da l g o r i t h m sa r ei n t r o d u c e d ak i n do fg e n e r a li m p r o v e m e n ti ng e n e t i ca l g o r i t h mi sp r e s e n t e d ，c o m b i n i n g s o m ec o n c r e t ef e a t u r e s ，s u c ha st s p p r o g r a m m i n g s i m u l a t i o nr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mi sf e a s i b l e ，e n h a n c i n gt h ee f f i c i e n c ya tt h es a m et i m e t h i st h e s i sp r e s e n t st h ec o n c e p to ft h em u l t i - o b j e c t i v eo p t i m i z a t i o nm e t h o d s ， a n a l y s i si t si m p l e m e n t a t i o ns t e p sa n dt h ei m p l e m e n t a t i o nm e t h o d sw i t hg e n e t i c a l g o r i t h m ，a n ds h o w st h a ta l g o r i t h mi sp r a c t i c a l i nt h i sp a p e r , w et a k en s g a i ia s ab e n c h m a r k i ti m p r o v e ss i m u l a t i o nr e s u l t so nm u l t i o b j e c t i v ej s s pp r o b l e m sa n d s h o w st h a tt h ei m p r o v e dm u l t i o b j e c t i v eg e n e t i ca l g o r i t h mh a si d e a le f f e c t so nt h e a s p e c t so fi t ss p e e da n dd i v e r s i t y k e y w o r d s ：g e n e t i ca l g o r i t h m ，m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ，p a r e t o - o p t i m a l s o l u t i o n s ，m u l t i - o b j e c t i v eo p t i m i z a t i o n ，n i c h et e c h n o l o g y - 插圖清單 圖1 1 論文結構圖7 圖2 1 遺傳算法的基本流程圖9 圖2 2 雙點交叉示意圖1 3 圖2 3 基本變異算子示意圖一1 5 圖2 4 逆轉變異算子示意圖。1 5 圖3 1 改進選擇算子算法流程圖2 9 圖3 2t s p 問題的路徑編碼3 0 圖4 1 位移交異算子。 表格清單 表3 1n e i h g b o r 1 0 5 數(shù)組具體值3 1 表3 25 0 個城市的坐標3 3 表4 1 3 3j o b s h o p 調度問題4 2 表4 23 3j o b s h o p 調度解4 2 表4 3 標準實例問題數(shù)據“ 表4 4 實驗調度結果比較4 5 獨創(chuàng)性聲明 本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。據我所 知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經發(fā)表或撰寫過的研究成果， 也不包含為獲得 金目b 王些盔堂 或其他教育機構的學位或證書而使用過的材料。與我一同 工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。 學位論文作者簽名：孫 偉黜 簽字日期：7 茍 ! 年鈿5 目 學位論文版權使用授權書 本學位論文作者完全了解盒膽王些太堂有關保留、使用學位論文的規(guī)定，有權保留并向國 家有關部門或機構送交論文的復印件和磁盤，允許論文被查閱和借閱。本人授權盒膽工些盔堂可 以將學位論文的全部或部分內容編入有關數(shù)據庫進行檢索，可以采用影印、縮印或掃描等復制手 段保存、匯編學位論文。 ( 保密的學位論文在解密后適用本授權書) 學位論文作者簽名：私仲弄q 簽字日期： 面 年6 月彳日 學位論文作者畢業(yè)后去向 工作單位： 通訊地址： 導師簽名 留鉚 簽字日期：加一年月y 日 電話 郵編 致謝 值此論文完成之際，我謹向所有關心和幫助過我的老師、同學、朋友以及 家人致以最真誠的謝意。 首先，我要深深地感謝我的導師倪志偉教授。本人在學習、論文寫作以及 平時的生活中，自始至終得到了倪老師的悉心指導。無論從課程學習、論文選 題，還是到資料收集、論文修改定稿，無不滲透著倪老師的智慧和心血。倪老 師淵博的知識、嚴謹?shù)闹螌W作風以及富于創(chuàng)新的學術思想，讓我在學業(yè)上受益 匪淺，同時也培養(yǎng)了我踏踏實實研究學問的態(tài)度，這些都將使我終身受益，并 激勵我不斷前進。 在此，真誠感謝管理學院的全體老師，他們的教誨為本文的研究提供了理 論基礎，并創(chuàng)造了許多必要條件和學習機會。 感謝智能管理研究所的所有同學，正是通過與你們的互相交流、互相幫助， 我才得以不斷提高。衷心地祝各位前程似錦! 此外，特別感謝我的室友王小紅、徐瑩在本文撰寫期間所提供的幫助，以 及在生活中給予我的照顧。 同時，研究生階段學習和生活中，我得到了許多朋友的關心、幫助和支持， 在此表示衷心感謝! 感謝各位評審專家在百忙之中抽出時間對論文進行了仔細的評閱l 借此機會，感謝我的父母家人，是他們二十多年來的呵護、關心，支持和 鼓勵，使我得以順利完成學業(yè)。感謝他們給我健康的身體、上進的思想! 1 1 論文選題的背景 第一章緒論 遺傳算法【l 】是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu) 化自適應概率搜索算法。與傳統(tǒng)的啟發(fā)式優(yōu)化搜索算法相比，遺傳算法的主要 本質特征在于群體搜索策略和簡單的遺傳算子。群體搜索使遺傳算法得以突破 鄰域搜索的限制，可以實現(xiàn)整個解空間上的分布式信息探索、采集和繼承；遺 傳算子僅僅利用適應值度量作為運算指標進行隨機操作，降低了般啟發(fā)式算 法在搜索過程中對人機交互的依賴。 幾乎每個重要的現(xiàn)實中的決策問題都要在考慮不同約束的同時處理若干相 互沖突的目標。最優(yōu)化處理的是在一堆可能的選擇中搜索對于某些目標來說是 最優(yōu)解的問題。如果存在的目標超過一個并需要同時處理，就成為多目標優(yōu)化 問題。由于多目標優(yōu)化問題的廣泛存在性與求解的困難性，該問題一宣是富有 吸引力和挑戰(zhàn)性的。 自2 0 世紀6 0 年代以來多耳標優(yōu)化問題就受到研究人員越來越多的關注。 在多目標優(yōu)化問題中，多個目標函數(shù)需要同時進行優(yōu)化。由于目標之間的無法 比較和矛盾等現(xiàn)象，導致不定存在所有目標上都是最優(yōu)的解。某個解可能在 一個目標上是最優(yōu)的但在另一個上是最差的。因此，多目標問題通常存在一個 解的集合，它們之間不能簡單地進行比較好壞。對這種解來說，不可能使得在 任何目標函數(shù)上的改進不損害至少一個其他目標函數(shù)，這種解稱作非支配解和 p a r e t o 最優(yōu)解。 九十年代開始的進化計算為求解多目標優(yōu)化問題提供了有力的工具。遺傳 算法【2 】作為一種超啟發(fā)式算法，可以靈活地將傳統(tǒng)方法結合進其主框架，因此可 以利用遺傳算法和傳統(tǒng)方法兩方面的優(yōu)勢來建立對問題更有效的求解方法。遺 傳算法內在的特征說明了為何遺傳搜索適合用于多目標優(yōu)化問題。遺傳算法的 基本特征是通過在代與代之閱維持由潛在解組成的種群來實現(xiàn)多向性和全局搜 索，帶有潛在解的種群因此能夠一代一代維持下來。在遺傳多目標優(yōu)化中，這 種從種群到種群的方法在搜索p a r e t o 解時是高效的。在具體問題上，遺傳算法 與多目標優(yōu)化問題的結合中最關鍵的是如何在種群中通過多個目標來評價個體 的好壞，即如何根據多個目標來確定個體的適應值。 在過去的幾年中，將遺傳算法應用于多目標優(yōu)化問題成為研究熱點，這種 算法通常稱作進化多目標優(yōu)化或遺傳多目標優(yōu)化。本文主要研究用于解決多目 標優(yōu)化問題的遺傳算法，同時將遺傳算法和多目標優(yōu)化引入t s p 和j o b - s h o p 調度問題中，重點研究遺傳算法的優(yōu)化作用，利用遺傳算法和多目標優(yōu)化技術 增強優(yōu)化智能。 1 2 遺傳算法的發(fā)展及研究現(xiàn)狀 1 2 1 遺傳算法的發(fā)展過程 早在2 0 世紀5 0 年代和6 0 年代，就有計算機學者開始研究“人工進化系統(tǒng)”， 將進化的思想發(fā)展成為許多工程闖題的優(yōu)化工具。早期的研究形成了遺傳算法 的雛形【3 ”，大多數(shù)系統(tǒng)都遵循“適者生存”的仿自然法則。6 0 年代初期，柏 林工業(yè)大學的i r e c h e n b e r g 和h p s c h w e f e l 在風洞實驗中利用了隨機變異的 思想，并且在對這種方法研究的基礎上，形成了進化計算的另一個分支一一進 化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 。l j f o g e l 等人在設計有限態(tài)自動機 ( f i n i t es t a t em a c h i n e ，f s m ) 時提出了進化規(guī)劃( e v o l u t i o n a r yp r o g r a m m i n g 。 e p ) 。2 0 世紀6 0 年代中期，美國m i c h i g a n 大學的h o l l a n d 教授在a s f r a s e r 和h j b r e m e r m a n n 等人工作的基礎上，提出了位串編碼技術。隨后，h o l l a n d 將該算法用于自然和人工系統(tǒng)的自適應行為的研究中，并于1 9 7 5 年發(fā)表了自 然系統(tǒng)和人工系統(tǒng)中的適應問題( “a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ”) 一書1 6 】，該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，為其奠定 了數(shù)學基礎，提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論 ( s c h e m a t at h e o r y ) 該理論首次確認了結構重組遺傳操作對于獲得隱并行性的 重要性。該書的出版標志著遺傳算法的誕生。h o l l a n d 等人在以后的應用研究 中，將遺傳算法推廣到優(yōu)化以及機器學習等問題的應用中，遺傳算法的通用編 碼技術和簡單有效的遺傳操作為其成功地廣泛應用莫定了基礎 h o l l a n d 在這本著作中指出，在自然界和人們生活中存在著一類優(yōu)化問 題，這類優(yōu)化問題具有如下特點：搜索空間足夠復雜，而且搜索開始時關于問 題的知識的不確定性很大，即對問題本身的了解很少；只有通過不斷試探解 獲得新的信息，才能減少這種不確定性：在獲得新信息的同時，還要利用這 些新信息，從而使試探解的平均性能隨著獲取信息量的增加而改善。 求解這類問題時面臨兩個難題：要獲得有關問題的新信息，就要實驗以前沒 有實驗過的搜索空闖的點；然而要提高試探解的平均性能，就要重復地實驗那 些己經實驗過的，且性能超過平均值的個體。也就是說，如果要使獲取信息的 速度最大，則所獲取的信息無法利用：反之，如果要最大限度地利用已經獲取 的信息，則很難再去探測新的信息。 h o l l a n d 將這類優(yōu)化問題稱為。適應性問題”( p r o b l e mo fa d a p t a t i o n ) ， 因為這與生物種群在適應環(huán)境時面i i 缶的狀況相似：生物對環(huán)境的適應程度也很 難用函數(shù)來表示，只能用生物種群中的每一個個體的體驗來獲得，進化的目標 是使生物種群( 而不是某個生物個體) 適應環(huán)境的能力最大。 由于這類問題的目標函數(shù)是未知的或沒有解析的數(shù)學表達式，因而傳統(tǒng)的 基于導數(shù)或解析的優(yōu)化方法是不可用的；從理論上說，窮舉法可以找到全局最 優(yōu)點，且實現(xiàn)起來簡單，但由于這類問題的搜索空間太大，利用這種方法求解 時，會因求解時間太長而無法忍受，有時甚至無法完成搜索。這是因為，窮舉 法不能利用以前的實驗結果來縮小搜索空間，即搜索的順序不受以前測試結果 的影響。 因而求解此類問題的算法應該注意以下幾點： ( 1 ) 不能簡單地認為只要能產生適應環(huán)境的結構就好，還要保證求解問題 的時間處于合理的范圍； ( 2 ) 應該在保持窮舉法的通用性的基礎上提高效率； ( 3 ) 由于不了解環(huán)境，在算法中要有存儲和利用實驗結果，從中獲取信息 的手段。 由于適應性問題與生物在進化過程中遇到的問題類似，因此自然界的進化 過程就為解決適應性問題提供了思路。分析自然界的進化現(xiàn)象可以看到，進化 過程關鍵是通過群體搜索、編碼表示、遺傳操作來找到適合環(huán)境的最優(yōu)解，并 最終解決了兩難問題。這三者缺一不可。沒有群體就無法引入生存競爭，無法 選出優(yōu)良基因；不用編碼表示就無法存儲進化所得的成果，無法將某些優(yōu)良特 性與基因模式聯(lián)系起來，無法利用適應度來改善搜索：不用遺傳操作就無法根 據個體基因的適應度，搜索更適合環(huán)境的個體。 因而，h o l l a n d l 6 】提出了模仿自然界的進化機制來解決適應性問題的優(yōu)化算 法一一遺傳算法。由于他提出的遺傳算法簡單實用，因而己普遍被接受采納。 一般就認為這標志了遺傳算法的誕生。 鑒于g e n e t i ca l g o r i t h m 的特點與優(yōu)點，繼h o l l a n d 之后，越來越多的學 者開始致力于g a 的研究與應用，主要是探討g 的應用和在應用時遇到的問題。 其中有d ej o n g 7 】對g a 各種策略的性能和機理進行的大量而細致的實驗和分析， 在一定程度上是d ej o n g 的工作使人們開始看到了g a 的應用價值。在h o l l a n d 的書中還給出了一個自適應的規(guī)則學習系統(tǒng)( c l a s s i f i e rs y s t e m ) ，6 0 l d b e r g s 】 將它成功地應用于天然氣管道系統(tǒng)的控制規(guī)則的優(yōu)化問題上，這是g a 應用的一 個著名例子。b e t h k e 的博士論文提出了用w a l s h 函數(shù)來研究g a 的方法；a l b e r t 大學的b r i n d l e 在博士論文1 9 】中對選擇策略進行了研究。這一時期的研究成果 主要是回答了g a 到底有何意義，有何價值。鑒于他們的研究工作，很多人的注 意力逐漸轉向了g a 。1 9 8 5 年召開了第一屆g a 的國際會議，以后每隔一年舉行 一次。 自8 0 年代中期以來，是g a 的蓬勃發(fā)展期，研究者對遺傳算法的應用研究 不斷擴大和深入。有用于t s p 問題d o j l 】、調度問題【1 2 】、鍵盤構造問題、多關節(jié) 機械手軌跡規(guī)劃問題【”】、工程中的設計輔助問題、機器學習問題【h 】、囚徒困境 ( p r i s o n e r sd i l e m m a ) 問題、模式分類問題，神經網的基因綜合，神經網的輔 助設計、程序自動生成一一遺傳編碼。此外，遺傳算法還在預測控制等問題中 都有運用研究。目前g a 的研究己構成與神經網絡，模糊控制并駕齊驅的一大領 域。 1 2 2 遺傳算法的國內外研究現(xiàn)狀 g a 的研究熱潮有其自身的原因，首先它思想獨特，與傳統(tǒng)的一些優(yōu)化算 法有很大不同；其次就是g a 非常一般化，實現(xiàn)起來較簡單，什么問題都可以套 用，好象成了一把萬能鑰匙；第三就是它雖然操作簡單，但人們對它的性能卻 了解得不透，這就給研究者們留下了廣闊的探索空間。 人們目前主要研究g a 的以下三個方面 1 5 , 1 6 , 1 刀： ( 1 ) g a 的搜索。當進化到一定程度后，種群中的個體適應性往往會變得非 常接近，這樣，個體間的選擇概率就會變得非常接近，此時的選擇過程就變成 了一種接近純隨機的抽樣過程。另外，群體規(guī)模往往不可能取得很大，因此而 產生的一些漲落誤差會使實際抽樣結果與預期結果有差距，這就可能使一些好 的或比較好的個體落選。針對這樣的一些問題，研究者們提出了不同的選擇策 略和復制策略，還有一類改進是對種群中的適應度的分布進行變換，例如進行 線性尺度變換( l i n e a rs c a l i n g ) ，截取變換( s i g m at r u n c a t i o n ) ，窗口變挨 ( w i n d o ws c a l i n g ) ，基于分享函數(shù)( s h a r i n gf u n c t i o n s ) 的變換等。對g a 的行 為有實質影響的改進研究主要在這兩方面，此外還有與問題有關的g a 的變種。 ( 2 ) g a 的收斂性研究。主要結果是g a 不會收斂到全局最優(yōu)解，對于保留 耩英( e l i t i s i ns e l e c t i o n ) 的選擇策略，g a 能收斂到全局最優(yōu)。盡管這一結論 說明了改進的g a 最終能收斂到全局最優(yōu)解，但收斂到最優(yōu)解的時間會很長。 ( 3 ) g a 的性能研究，包括與其它算法的比較研究。到目前為止，還沒有什 么肯定的結論。它與同類算法相比，例如爬山法，模擬退火算法，t a b u 算法等， 往往是問題不一樣結論也不一樣，甚至對同一問題，不同人的研究結果也不一 樣。目前。g a 界的研究者們多用人為結構的問題，如皇家大道函數(shù)( r o y a lr o a d f u n c t i o n ) ，來研究g a 的表現(xiàn)，以期找出具有什么特性的問題適合或不適合g a 。 還有人用構造的w a l s h 多項式函數(shù)來研究g a 的行為，以及其它人為構造的函數(shù)。 g a 的優(yōu)越性是建立在積木塊假設的基礎上，但是有些函數(shù)不滿足這個假設，叫 做欺騙性函數(shù)( d e c e p t i v ef u n c t i o n s ) ，有關這個問題的論題包括什么樣的函數(shù) 具有欺騙性，欺騙現(xiàn)象的普遍性怎樣等i l 摹| 坤1 。 1 3 多目標遺傳算法的發(fā)展及研究現(xiàn)狀 1 3 1 多目標遺傳算法的發(fā)展過程 多目標優(yōu)化問題一直是科學和工程研究領域的一個難題和熱點問題，不僅 因為許多工程問題本身就是一個多目標優(yōu)化闖題，而且在多目標優(yōu)化領域內還 存在著許多尚未解決的難題。遺傳算法應用于單目標問題之后的2 0 多年以后， 多目標遺傳算法逐漸成為研究熱點。十幾年來出現(xiàn)了許多基于進化方法的多目 標優(yōu)化技術。 國際上一般認為多目標最優(yōu)化問題最早是由法國經濟學家v p a r e t o 在 1 8 9 6 年提出的1 9 6 7 年，r o s e n b e r g 在其博士論文中提出了在模擬單細胞有機 物的化學遺傳特性中采用多屬性研究方法，在r o s e n b e r g 的研究中雖然在他的 研究中最終只應用了單一屬性方法，正是他的研究開創(chuàng)了這個領域的研究。直 到1 9 8 5 年，s c a f f e r 提出了第一個基于向量評估的多目標遺傳算法( v e g a ) ， 從而開刨了用遺傳算法求解多目標規(guī)劃的先河。真正引起演化界重視的是1 9 9 0 年后，f o n s e c a 和f l e m i n g 提出基于排序選擇的多目標遺傳算法 ( m o g a ) ，s r i n i v a s 和d e b i ”】提出非劣分層遺傳算法( n s g a ) ，h o r n 和 n a f p l i o t i s 也提出了小組決勝遺傳算法( n p g a ) ，h o m 等人提出的基于小生鏡 ( n i c h e ) 技術f 2 l 】的“小生鏡p a r e t o 遺傳算法”。g o l d b e r g 等人提出了一種p a r e t o 排序算法，這些算法已成為遺傳多目標優(yōu)化算法研究的基石在此基礎上，人 們又提出可以在多目標算法中引入最優(yōu)保存策略和約束處理策略，并提出了實 現(xiàn)這些策略的不同的多目標進化算法。 遺傳算法的操作需要適應度值的信息，那么，對于多目標優(yōu)化問題來說最 直接的方法就是采用加、乘或其他算子將各個目標函數(shù)整合成一個單目標優(yōu)化 問題。但是，這種方法存在很多問題：首先我們必須提供目標函數(shù)空間的精確 的標量信息，以避免其中的一個目標函數(shù)支配其他目標函數(shù)。這就意味著必須 了解每一個目標函數(shù)的行為，而其計算量十分巨大，通常都是不可能實現(xiàn)的。 顯然，如果這種整合方法可以實現(xiàn)的話，那么它將是最簡單、有效的處理多目 標問題的方法。因為它不需要和決策者做任何交互就可以得出最優(yōu)解或至少是 近優(yōu)解。整合成的目標函數(shù)稱為和函數(shù)，翠期的多目標優(yōu)化中有很多這方面的 工作，比如線性加權法、變權重加權法等。線性加權法為每個目標函數(shù)采用不 同的權重因子，對所有的目標函數(shù)進行整合。這種方法是第一種用來求多目標 優(yōu)化問題的非劣解的方法，它是受k u h n 和t u c k e r 的數(shù)值優(yōu)化方法的啟發(fā)而演 變來的。線性加權法簡單、有效、實用。對它的研究和應用有很多。1 9 9 1 年 s y s v e r d a 和p a l m u c c i 就使用權重法和遺傳算法相結合來解決資源計劃問題。 目標規(guī)劃法中決策者必須確定理想中的每個目標函數(shù)所能達到的目標值， 然后將這些值作為附加的約束整合進闖題中，對其進行優(yōu)化就是最小化理想的 目標值和目標函數(shù)值之間的絕對偏差。此法適用于目標函數(shù)是線性的或者是部 分線性的情況，對于非線性的情況它可能不太適用。1 9 9 2 年w i e n k ee ta 1 使 用目標規(guī)劃法和遺傳算法結合來解決核物理學中的問題。 1 9 9 3 年w i l s o n 和m a c l e o d 采用目標滿意法和遺傳算法來設計濾波器。1 9 9 7 年q u a g l i a r e l l a 和v i c i n i 共同采用雜合遺傳算法解決多目標優(yōu)化問題。早期 的多目標遺傳算法一般都是遺傳算法和一些經典的多目標優(yōu)化技術的結合的產 物，他們普遍效率不高、局限往大、魯棒性差。之后出現(xiàn)了基于多種群的v e g a 、 基于字典序的方法、基于博弈論的方法等等，這些方法的特點是實用性差、解 的精度不高、不能保證求得最優(yōu)解。 1 3 2 多目標遺傳算法的研究現(xiàn)狀 目前多目標遺傳算法的研究熱點是采用p a r e t o 機制【2 2 】的多目標優(yōu)化技術， 包括：m o g a ，n s g a ，n p g a ，s p e a 等等。 m o g a 由f o n s e c a 和f 1 e m i n g 于1 9 9 3 年提出，主要思想是個體排序的序號 由當前種群中支配它的個體的數(shù)量來決定。m o g a 在多目標優(yōu)化領域得到了廣泛 的應用。c h e nt a n 和l i 于1 9 9 7 年成功地將其應用于u l t i c 控制器的優(yōu)化問題 中，得到了一組滿意的時域和頻域參數(shù)；c h i p p e r f i e l d 和f l e m i n g 于1 9 9 5 年 將其應用于噴氣發(fā)動機的多變量控制系統(tǒng)優(yōu)化問題中；o b a y a s h i 于1 9 9 7 年應 用p a r e t o 排序、表現(xiàn)型莢享和b e s t - n ( 從n 個父代個體和n 個子代個體中選擇 n 個最佳個體最為下一代種群) 選擇來設計空氣動力學中的壓縮機葉片形狀； r o d r g u e zv d z q u e ze ta 1 將m o g a 和遺傳規(guī)劃( g e n e t i cp r o g r a m m i n g ) 結合，形 成了啪g p ( m u l t i p l eo b j e c t i v eg e n e t i cp r o g r a m m i n g ) 算法；t o d d 和s e n 于 1 9 9 7 年采用改進的m o o 來解決大規(guī)模組合優(yōu)化問題一一集裝箱布局 ( c o n t a i n e r s h i pl a y o u t s ) 問題等等。 非支配排序遺傳算法一一n s g a 是由s r i n i v a s 和d e b 2 3 l 于1 9 9 3 年提出的。 算法是基于對個體的幾層分級實現(xiàn)的。n s g a 在現(xiàn)實問題的求解中得到了廣泛的 應用，p e r i 8 u xe ta 1 于1 9 9 7 年采用n s g a 最小化空氣動力學中的反射器的散 射；v e d a r a j a ne ta l ，于1 9 9 7 年采用n s g a 進行投資利潤的最優(yōu)化；m i c h i e l s s e n 和w e i l e 于1 9 9 5 年采用n s g a 設計電磁系統(tǒng)，并取得了較好的解。 h o r n 和n a f p l i o t i s 于1 9 9 3 年提出了一種基于p a r e t o 支配的聯(lián)賽選擇方法一 一n p g a ，該方法中聯(lián)賽規(guī)模不局限于兩個個體，而是由種群中的多個個體參與 來決定支配關系 一般在l o 個左右) 。當兩個個體之間沒有明顯的支配或被支配 關系時，通過適應度共享來決定聯(lián)賽選擇的結果。b e l e g u n d u e ta 1 于1 9 9 4 年應 用n p g a 設計多層復合陶瓷問題。s p e a 由e c k a r tz i t z l e r 于1 9 9 9 年提出，在他 的論文中解決了計算任務在不同體系結構的系統(tǒng)上的調度問題，并和其他算法 的解進行了詳盡的比較。 當前，遺傳多目標優(yōu)化算法作為一個優(yōu)化工具在解決智能決策問題研究中 越來越顯示出它的強大生命力，在生產系統(tǒng)中對生產計劃調度集成系統(tǒng)的優(yōu)化， 在金融證券和經濟預測系統(tǒng)中的模型優(yōu)化，在決策支持系統(tǒng)中解決模型結構選 擇和模型實例確定的問題等領域都取得了較顯著的成果。 1 4 論文主要內容與結構 論文的整體架構圖見圖1 1 。 圖1 1 論文結構圖 全文共分五章，各章主要內容分述如下： 第一章是緒論。說明了論文的選題背景、依據，對遺傳算法和多目標優(yōu)化 遺傳算法的國內外研究現(xiàn)狀進行了概述，給出全文的整體架構圖和各章的研究 內容。 第二章是遺傳算法的基本原理和方法首先對遺傳算法的基本框架進行了 概述，簡述了遺傳算法的編碼原理，初始種群的生成，適應度函數(shù)原理，參數(shù) 設定的方法，遺傳操作，模式定理及積木塊假說。最后介紹了遺傳算法的欺騙 問題，隱含并行性問題和收斂性分析。 第三章是遺傳算法的若干改進及其應用研究。首先在基本遺傳算法的基礎 上，針對其缺點，介紹了在遺傳算法的使用范圍，遺傳算法的參數(shù)、編碼，選 擇、交叉、變異等遺傳操作的若干改進。隨后成功地將遺傳算法應用到t s p 問 題中，提出一種改進的遺傳算法的優(yōu)化方案，進行仿真研究，給出實驗測試結 果。 第四章是遺傳多目標優(yōu)化的應用研究。首先對多目標遺傳算法的基本理論 進行了概述。隨后，介紹了多目標優(yōu)化和遺傳算法的融合、發(fā)展狀況及其分類。 針對多目標j s s p 問題的求解需求，使用改進的多目標遺傳算法對j s s p 問題進 行求解。利用國際案例庫中的數(shù)據對算法進行測試，實驗結果證明算法達到了 良好的效果 第五章是總結與展望。首先闡述總結遺傳算法操作的相關改進。接著對遺 傳算法的研究方向和未來趨勢進行介紹。最后對本文所作工作進行了展望。 第二章遺傳算法的基本原理和方法 遺傳算法t 1 ，2 3 】是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自 適應全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學的h o l l a n d 教授提出，起 源于2 0 世紀6 0 年代對自然和人工自適應的研究。7 0 年代d ej o n g 基于遺傳算法的 思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的 基礎上，8 0 年代由g o l d b e r g 進行歸納總結，形成了遺傳算法的基本框架。 2 1 遺傳算法的基本框架 遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。選擇 ( s e l e c t i o n ) ，交叉( c r o s s o v e r ) 和變異( m u r a t i o n ) 是遺傳算法的三個主要操作 算子。遺傳算法包括6 個基本要素：參數(shù)編碼、初始種群的設定、適應度函數(shù)的 設計、遺傳算子的設計、停止運行準則及結果的編碼、控制參數(shù)設定( 包括種群 規(guī)模、交叉概率、變異概率，停止運行準則的參數(shù)等) 。 2 1 1 遺傳算法的運算步驟 步驟1 ：初始化，設置進化代數(shù)計數(shù)器t o ，設置最大進化代數(shù)m 找g e n ，種 群規(guī)模n ，隨機產生n 個個體作為初始種群m o ； ， 步驟2 ：個體評價，計算種群m t 中各個體的適應度； 步驟3 ：選擇操作，將選擇算子作用于種群m t ； 步驟4 ：交叉操作，將交叉算子作用于種群m t ； 步驟5 ：變異操作，將變異算子作用于種群m t ；種群m t 經過選擇、交叉、 變異操作后得到下一代種群m t + ，； 步驟6 ：終止條件判斷，若t + l = m a x _ g e n ，則算法停；否則置f = f + l ，轉步 驟2 。 2 1 2 遺傳算法的基本框架 2 2 編碼 圖2 1 遺傳算法的基本流程圖 把問題空間中的參數(shù)或解轉化成遺傳空間中的染色體或個體，稱作編碼 ( e n c o d i n g ) ，相反過程稱為譯碼( d e c o d i n g ) 。由于遺傳算法通常不能直接處理 解空間的數(shù)據，所以必須通過編碼將它們表示成遺傳空間的基因型串結構數(shù)據。 編碼規(guī)則有： ( 1 ) 完備性( c o m p l e t e n e s s ) ：闖題空間中的所有點都成為編碼后空間中的 點； ( 2 ) 健全性( s o u n d n e s s ) ：編碼后空簡的點能對應原問題空間的所有點： ( 3 ) 非冗余性( n o n r e d u n d a n c y ) ：編碼后空間的點與原問題空間的點一一 對應； ( 4 ) 有意義積木塊編碼規(guī)則：應使用能易于產生與所求問題相關的底階， 短定義長度模式的編碼方案。 對于實際應用問題，必須對編碼方法、交叉操作方法、變異操作方法、解 碼方法等統(tǒng)一考慮，以尋求到一種對問題的描述最為方便、遺傳算法效率最高 的編碼方案編碼方法有很多，如：二進制編碼、格雷碼編碼、實數(shù)編碼、符 號編碼、多參數(shù)級聯(lián)編碼、多參數(shù)交叉編碼對不同問題，應選用合適的編碼 方法。 2 3 初始種群的生成 一定數(shù)量的個體組成了種群( p o p u l a t i o n ) ，種群中個體的數(shù)目稱為種群規(guī) 模( p o p u l a t i o ns i z e ) 。由于遺傳算法的種群型操作需要，所以必須為遺傳操作 準備一個由若干初始解組成的初始種群。初始種群的每個個體都是通過隨機方 法產生，它也稱為進化的初始代。種群規(guī)模是遺傳算法的控制參數(shù)之一，其選 取對遺傳算法效能的發(fā)揮有影響。一般種群規(guī)模在幾十到幾百之問取值，問題 越難，維數(shù)越高，種群規(guī)模越大。 初始種群的設定可采取以下策略： ( 1 ) 設法把握最優(yōu)解在整個問題空間的分布范圍，然后在此分布范圍內均 勻設定初始種群。 ( 2 ) 先隨機生成一定數(shù)目的個體，然后從中選出最好的個體加入到種群 中，不斷重復這一過程，直到達到種群規(guī)模。 2 4 適應度函數(shù) 各個體對環(huán)境的適應程度叫適應度( f i t n e s s ) 。遺傳算法在進化搜索過程中 一般不需要其它外部信息，僅用適應度來評估個體或解的優(yōu)劣，并作為以后遺 傳操作的依據。 ( 1 ) 評價個體適應度的一般過程是：對個體編碼串進行解碼處理后，可得 到個體的表現(xiàn)型，由個體的表現(xiàn)型可計算出對應個體的目標函數(shù)值，根據最優(yōu) 化問題的類型，由目標函數(shù)值按一定的轉換規(guī)則求出個體的適應度。 ( 2 ) 適應度尺度變換：在遺傳算法中，種群的進化過程是以種群中各個體 的適應度為依據，通過一個迭代過程，不斷地尋求出適應度較大的個體，最終 就可得到問題的最優(yōu)解或近似最優(yōu)解。在遺傳算法運行的不同階段還需要對個 體的適應度進行適當?shù)臄U大或縮小，這就是適應度尺度變換。在進化的初期， 為避免未成熟收斂，應縮小個體間的差異；在進化的最后階段，為了加快收斂， 應放大個體問的差異。常用的尺度變換有三種：線性尺度變換、乘冪尺度變換、 指數(shù)尺度變換 2 5 參數(shù)設定 遺傳算法中需要選擇的參數(shù)主要有串長，種群規(guī)模廳，交叉概率p c ，變異 概率l 等，這些參數(shù)對遺傳算法的性能影響比較大。在簡單遺傳算法( s g a ) 或 標準遺傳算法( c g a ) 中，這些參數(shù)是不變的。然而，許多學者意識到這些參數(shù)需 要隨著遺傳算法的進程而自適應變化，這種有組織性能的遺傳算法具有更高的 魯棒性、全局最優(yōu)性和效率，但會增加算法的復雜性和計算量等。還有一些參 數(shù)的改進方法，比如，模糊控制參數(shù)、模擬退火方法、基于均勻設計的參數(shù)設 定等。 2 6 遺傳操作 遺傳操作是模擬生物基因遺傳的操作。在遺傳算法中，通過編碼組成初始 群體后，遺傳操作的任務就是對群體的個體按照他們對環(huán)境適應的程度( 適應 度評估) 施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度 而言，遺傳操作可使問題的解，一代又一代地優(yōu)化，并逼近最優(yōu)解。遺傳算法 的遺傳操作包括以下三個基本遺傳算子( g e n e t i co p e r a t o r ) ：l 、選擇 ( s e l e c t i o n ) ，2 、交叉( c r o s s o v e r ) ，3 、變異( m u t a t i o n ) 。這三個遺傳算子有 如下特點： ( 1 ) 這三個遺傳算子的操作都是在隨機擾動情況下進行的。換句話說，遺 傳操作是隨機化操作，因此，群體中的個體向最優(yōu)解遷移的規(guī)則是隨機的。需 要強調的是，這種隨機化操作和傳統(tǒng)的隨機搜索方法是有區(qū)別的。遺傳操作進 行的是高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。 ( 2 ) 遺傳操作的效果和上述三個遺傳算子所取的操作概率、編碼方法、群 體大小、初始群體以及適應度函數(shù)的設定密切相關。 ( 3 ) 三個基本遺傳算子的操作方法或操作策略隨著具體求解問題的不同 而異。更具體而言，是和個體的編碼方式直接有關。由于目前二值編碼仍是最 常用的編碼方法，所以，以下的對遺傳算子的論述是以二值編碼為基礎的。 下面分別介紹三種遺傳算子中比較常用的幾種操作方法： 2 6 1 選擇算子 選擇操作就是用來確定如何從父代種群中按某種方法選取哪些個體遺傳到 下一代種群的遺傳運算。選擇操作建立在對個體的適應度進行評價的基礎上， 其主要目的是為了避免基因缺失，提高全局收斂和計算效率。 常用的選擇算子有：比例選擇、保留最佳個體選擇、期望值選擇、排序選擇、 隨機聯(lián)賽選擇。 1 適應度比例方法 適應度比例方法是目前遺傳算法中最基本的選擇方法。它也叫賭輪或蒙特 卡羅選擇。在該方法中，各個個體的選擇概率和其適應值成比例 設群體大小為 ，其中個體i 的適應度值為聲，則f 被選擇的概率l 為 p - - f i | 缸 i - 1 ( 2 1 ) 顯然，概率氣反映了個體珀適應度在整個群體的適應度總和中所占的比 例。個體適應度越大，其被選擇的概率就越高，反之亦然。按式2 1 計算出群體 中各個個體的選擇概率后，就可以決定哪些個體被選出。該思想可用以下的算 法描述； p r o c e d u r es e l e c t i o n b e g i n i = o s u m = o w h e e l p o s = r a n d o m 年f s u m w h il e