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

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