（運籌學(xué)與控制論專業(yè)論文）求解兩類特殊雙層規(guī)劃問題的遺傳算法.pdf

摘要 近年來，隨著科學(xué)技術(shù)的日益發(fā)展，決策變得越來越復(fù)雜、上下級的交互決 策越來越普遍，因此，雙層規(guī)劃在生活中得到廣泛的應(yīng)用，引起了人們的極大關(guān) 注。本文主要研究雙層規(guī)劃聞題的理論和算法。雙層規(guī)劃的n p 難性、j # 跫性和不 可微性給其數(shù)值求解帶來極大困難，特別是求解非線性雙層規(guī)劃問題的全局最優(yōu) 解就更加網(wǎng)難。遺傳算法是一種求解復(fù)雜非線性優(yōu)化問題的新型有效的現(xiàn)代智能 優(yōu)化方法，它酶優(yōu)點是不受目標(biāo)函數(shù)的凸性、霹微性、連續(xù)性等的限制，與傳統(tǒng) 優(yōu)化方法相比，特別對一些大型復(fù)雜優(yōu)化問題，具有獨特的優(yōu)越性。 本文主要考慮了雙層規(guī)劃的復(fù)雜性和遺傳算法的優(yōu)點，用遺傳算法來求解雙 層規(guī)劃問題。在利用遺傳算法來解決雙層規(guī)劃閩題時，充分考慮了雙層規(guī)劃問題 的結(jié)構(gòu)特點，通過適當(dāng)?shù)奶幚恚档途S數(shù)，縮小搜索空聞，使得用遺傳算法的求 解更加快速。 首先，對兩類特殊結(jié)構(gòu)的非線性雙層規(guī)劃問題，將下層的最優(yōu)解用上層的決 策變量或l a g 鼴l g e 乘子表示，并將下層的最優(yōu)解代入上層中，便可將雙層規(guī)劃閥 題轉(zhuǎn)化為含有上層決策變量l a g r a n g e 乘子的單層規(guī)劃問題。其次，分別設(shè)計了一 個改進的凸交叉算子和一個新的交叉算子，在此基礎(chǔ)上，分別設(shè)計了求解這兩類 特殊的非線性雙層規(guī)劃問題的遺傳算法。進一步，分析了算法的全局收斂性。最 后，對所提出的兩個算法進行了數(shù)值仿真，結(jié)果表明這兩個算法是有效的。 關(guān)鍵詞：雙層規(guī)劃二次規(guī)劃遺傳算法全局優(yōu)化 a b s t r a c t w i t ht h l ef a s td e v e l o p m e n to fs c i e n c oa n dt e c l l n o l o g yi nr e c e n ty c a r s ，m o r ea n dm o r e d e e i s i o nm a k i n gp b l e m sw i 也也e 撼e 斌c h i c a ls t 挪c t u f eh a v ea 戚s e ni n 璜a n y 蠡e l d s 。 髓l e s e 弘靜麟。氆s 蠡輪l l yb e c 凇e 毯i 棼v 囂lp 鼯g 怒撒黻i 器gp 街纛l e 趲sa l 薹蓮辯s u l 溆m o 瓣 d i f j f i c u l 夠硒rd e c i s i o nm a k e r s b i l e v e lp r o g r 鋤m i n gp r o b l e m sa r ew i d e l yu s e di no u r l i f e m u c ha 訛n t i o nh a sb e e np a i dt ot h i s6 e l di n c e n ty e a r s h o ，e v e r ，t h es o 】u t i o no f 毯k v e lp 鰳踟螨n gi sv e 磣d i 臻e u l 毫埝g e 鼉酶c a n s e 醴i l s 魏一e v e x i 鏇n p 囊a 通 e h a f a e t e 蝣s l i ca n dn o n d i 重琵r e n 毫主a 毯l i t y 酗p a n i c u l a 如i li sm o r e 崩掰c u l tt og e ti 量sg l o b a i o p t i m a ls o l u t i o n g e n e t i ca l g o r i t h m sa 心an e wk i n do fe f f e c t i v ea l g o r i t l l r l l sf o rc o m p l e x o p l i m i z a o 穩(wěn)p r o 琰鋤s ?； yh a v e 致om h e hf e s 城c l i o 璉o nr e l a l o d n e l i o n s ，s 獬羲8 s 蕊陵糯n 熏至豳i l i 移，e o 鑫v e x i 毋，e o 蛾i 鞠a 鼉主o n 勰ds oo n e 蹲撼越l y ，如r m el 皴鬈e s c 鑫酶 c o m p l e xn o n l i n e a ro p t 橢i z a t i o np r o b l e m s ，t h e ya r eu s u a n ys u p e d o rt ot r a d i t i o n a l o p t i m i z a t i o n8 p p r o a c h e s ， c 鰳s i d e 蠢耀氌e 硪箍e u l 磣o f 琰l 粼e lp 秘群猢m i 箍g 鞠d 落e 鬈蓮函煳鞠o f g e n e t i ea l g o r i t h 王l l ，g e n e t i ca l g o f i t 量1 m sa 1 ea p p l i e dt os o l v eb i l e v e lp r o g r a m l n i n g t h e s t m c t u r e 曲a r a c t e r i s t i co fb i l e v ep r o g 粉m m i n gi sf u l l yc o n s i d e r e di nt h ep r o c e s so f s o l v i n g 糯霉b i l e v e lp 糊g r 黼m i n gb ya d o p t i n gp 姻p e rs 甄l l s ，瓣婊a sd e e r e a s i n g 也e p b l e m 魏穩(wěn)e n s i 油s 鑫n 娃s e a 幽s p a e e a saf e s u l 鼉，鰳。s 揮e 蓮甜詆；g 蔽i c 采艫磚l h 搭 w i l lb em o r eq u i c k l y i nt h i st h e s i s ，蜀r s t ，f o rt 、約8 p e c i a le l a s s e s 靠n o n 】i n e a rb 譴e v e l p r o g r a m m i n g p 羚b | e 璐s ，婭礞l i 瓔a 差s o l 避i 濰o fl h el 鰳嘴r 1 e v e lp 羚b l e 瓔i s 閹筍e s e 蹴db yt k u p p e r l e v e lv a r i a b l e so rl a g r a n g em u l 邱玎e f s ，i e ，t h e1 0 w e e v e lv a r i a b l e sa r ea f u n c t i o no fu p p e r l e v e lv a r i a b l e s 1 e nt h eb i l e v e lp r o g r 咖m i n gp r o b l e mc a nb e 瓣n s 內(nèi)燃艇i 奶鑫 s i n g l e l e v e lo p t i m i z a l i 強p f o b l e me o n l a 赫罐 壤e嘲e r l e v e l v 碰曲l e s 黻l a 蓼孤g em 毛l l i p l i e f s 翻黔玨醇愆p l a c i 蜷l h el o 硪靜l e v e lv 描曲l e sb y 氌i s 如n c t i o n s e c o n d ，a 1 1i m l ) r 0 v e dc o n v e xc r o s s o v e ro p e r a t o ra 1 1 dan o v e lm u t a t i o no p e r a t o r a f ed e s i g n e d ，r e s p e c t i v e l y b a s e do n 搬e s e ，t w on e 、 ，g e n e t i ca l g o r i t l l m sa r ep r o p o s e df o r 毛& 辯翩e l a s s e so f 纛?？齦 i 黼囂黽i | e w lp r o g 勰m i 甥p b e 趣s 羚蹲e e 矗v e l y ，m 讎w 毛 t h eg l o b a l n v e 毽e n c e0 ft h ep r o p o s 砌a l g o r i t h m si sp r o v e d a tl a s t ，t h ee x p e r i m e n t a l s i m u l a t i o n sa r em a d e 蝴dt h er e s u l t si n d i c a t et h ep r o p o s e da l g o r i t h m sa r ee f f e c t i v e x 句惻。蝴s ：g 鍾e l i e 建l g o 確囊mb i l e v e lp r o g r 冀m 黼i 玨gq 毯矬d r 8 耄i ep 硒g 薹i 建搬m 泌g g l o b a lo p t i m i z a t i o n 剖薪性聲明 本人聲明所呈交的論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究 成果。盡我所知，除了文中特裂煙以標(biāo)注和致謝中所羅列靜蠹容以外，論文中不 包含其他入已經(jīng)發(fā)表或撰寫過靜研究成果；也不包禽為獲得囂安電子科技大學(xué)或 其它教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做 的任何貢獻均已在論文中做了明確的說明并表示了謝意。 孛請學(xué)位論文與資瓣若喜不實之處，本人丞撾切相關(guān)責(zé)證。 本人簽名：匿糕；略| 2t 落。 關(guān)于論文使用授權(quán)的說明 本人完全了解囂安魄子辯技大學(xué)霄關(guān)僳鍪幫餿臃學(xué)位論文的溉定，霹：研究 生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學(xué)。本人保證畢 業(yè)離校后，發(fā)表論文或使用論文工作成果時署名單位仍然為西安電子科技大學(xué)。 學(xué)校有權(quán)保整送交論文的復(fù)印件，允許查閱和借闋論文；學(xué)?？梢怨颊撐呐稳?部或部分蠹容，可以兔誨采霜影霹、縮竄或其它復(fù)制手段保存論文。( 保密麴論 文在解密后遵守此規(guī)定) 本人簽名： 導(dǎo)師簽名： 爨期： 蹬斕：蘭翌盤：z 星：星笸 第一章緒論 第一章緒論 1 1 引言 本文主要是應(yīng)用現(xiàn)代智能優(yōu)化算法一遺傳算法( g e n e t i ca l g o r i t h m ，g a ) 來求解 兩類復(fù)雜優(yōu)化問題一雙層規(guī)劃問題( b i l e v e lp r o g r a m m i n gp r o b l e m ) 。 雙層規(guī)劃問題是一種具有兩級遞階結(jié)構(gòu)的復(fù)雜系統(tǒng)，結(jié)構(gòu)分為上下兩層，即 上層規(guī)劃和下層規(guī)劃。上層規(guī)劃問題的目標(biāo)函數(shù)和約束條件不僅與上層決策變量 有關(guān)，而且還依賴于下層規(guī)劃的最優(yōu)解，而下層規(guī)劃的最優(yōu)解又受上層決策變量 的影響。它具有層次性，上層規(guī)劃首先做出決策，確定上層決策變量，然后下層規(guī) 劃在上層規(guī)劃確定上層決策變量的基礎(chǔ)上，做出自己的決策，求出下層規(guī)劃的最 優(yōu)解，然后將該最優(yōu)決策反饋給上層，下層的決策也影響上層規(guī)劃的目標(biāo)函數(shù)和 可行域。上層規(guī)劃根據(jù)下層規(guī)劃的決策，再對其決策進行調(diào)整，最終找到使上層 目標(biāo)函數(shù)達到最優(yōu)的決策。雙層規(guī)劃分為兩類：一類是不合作的雙層規(guī)劃，即上 層規(guī)劃在確定自己的最優(yōu)值時，完全不考慮下層規(guī)劃的最優(yōu)值；另一類是合作的 雙層規(guī)劃，上層規(guī)劃在做出決策時，考慮下層規(guī)劃的最優(yōu)值。雙層規(guī)劃問題比熟 知的單層數(shù)學(xué)規(guī)劃復(fù)雜得多，主要表現(xiàn)在：( 1 ) 約束的嵌套本性；在雙層規(guī)劃中， 因為下層問題的介入，由其隱含的互補條件決定了約束的嵌套本性。( 2 ) 非凸性； 可行集一般不具備凸性和閉性，有上層約束有時還可能不連通。( 3 ) 內(nèi)在的非光滑 性；( 4 ) 計算復(fù)雜性；雙層規(guī)劃是一種n p 難問題。由于雙層規(guī)劃問題的嵌套性， 非凸性，非光滑性，n p 難等，造成了用傳統(tǒng)優(yōu)化方法求解雙層規(guī)劃問題比較困難， 求其全局最優(yōu)解更就加困難。 遺傳算法是模擬生物界的進化過程而產(chǎn)生的一種現(xiàn)代智能優(yōu)化方法，它使用 隨機概率搜索技術(shù)，具有操作簡單、通用性強、魯棒性強和便于并行處理等特點， 被廣泛應(yīng)用于眾多領(lǐng)域。遺傳算法將問題的所有可行解集看作解空間，從代表問 題的潛在可行解的一個初始種群開始，通過對種群( 潛在可行解的子集) 施加選擇、 交叉和變異等一系列遺傳操作，從而產(chǎn)生新的解集( 潛在可行解的新子集) ，并逐 漸使種群進化到問題的最優(yōu)解狀態(tài)。遺傳算法在整個進化過程中，它是直接以目 標(biāo)函數(shù)值作為搜索信息，它僅需要目標(biāo)函數(shù)，不像傳統(tǒng)優(yōu)化方法，往往需要目標(biāo) 函數(shù)的導(dǎo)數(shù)值或梯度，而遺傳算法在求解的過程中不受目標(biāo)函數(shù)的連續(xù)或可微， 多峰等性質(zhì)的限制。因此遺傳算法特別對于求解一些離散的、大規(guī)模的、n p 難的、 高維的、非光滑的、不具有凸性和可微性的函數(shù)，多峰函數(shù)，復(fù)雜非線性系統(tǒng)等 問題，具有比其他傳統(tǒng)優(yōu)化算法更加獨特的優(yōu)越性。遺傳算在使用時具有很大的 靈活性，在實際應(yīng)用中，靈活使用和設(shè)計遺傳算子( 選擇，交叉，變異) 對解決問題 2 求解兩類特殊雙層規(guī)劃問題的遺傳算法 有很大的影響。 本文鑒于雙層規(guī)劃問題有嵌套型、非凸性、n p 難性、而且往往不連續(xù)或約束 不連通、非光滑等復(fù)雜性，用傳統(tǒng)優(yōu)化方法求其全局最優(yōu)解有很大困難，而現(xiàn)代 優(yōu)化方法遺傳算法具有不受非凸性、不連續(xù)，菲光滑等限制，它采用全局隨機搜 索，可求得全局最好解。這樣，應(yīng)用遺傳算法對雙層規(guī)劃問題進行求解，可以克 服傳統(tǒng)優(yōu)化的缺點，可求得雙層規(guī)劃的全局最優(yōu)解。因此，本文用遺傳算法求解 雙層規(guī)劃問題。 1 2 雙層規(guī)劃的研究概況 l 。2 1 雙層規(guī)劃的背景和應(yīng)用 隨著經(jīng)濟、科技和社會的不斷發(fā)展，人們在實際生活中遴到問題的規(guī)模越來 越大，結(jié)構(gòu)越來越復(fù)雜，也逐漸顯示出了層次性。在經(jīng)濟全球化的今天，競爭越 來越激烈，決策問題顯得越來越重要，它影響著企業(yè)的經(jīng)濟效益和競爭力，在社 會經(jīng)濟、社會管理、企業(yè)管理，工程技術(shù)、工業(yè)設(shè)計、制造業(yè)、經(jīng)濟決策、系統(tǒng) 管理、政策制定、交通旒劃、軍事指揮等眾多領(lǐng)域中存在著各種形式的具有遞階 特征的層次系統(tǒng)優(yōu)化問題，其中最麓單的多層優(yōu)化問題雙層規(guī)劃，存在于我們的 日常生活中，例如資源分配問題，它是類比較復(fù)雜的管理問題，上層部門將資 源分配給多個下層部門，下層部門根據(jù)分配到的資源組織生產(chǎn)，使自己的利益最 大。由予上層部門擁有有限的資源，各部門的生產(chǎn)效益又不同，如何使用有限的 資源產(chǎn)生最大的效益是上層部門面臨的最大問題；許多跨國公司和它的許多子公 司之間的決策問題；在管理機構(gòu)中的上下級關(guān)系；經(jīng)濟活動中的供銷關(guān)系；企業(yè) 中的總公司與分公司關(guān)系等；企業(yè)和市場之間的價格決策關(guān)系；總批發(fā)商和代理 商，對這種遞階結(jié)構(gòu)的決策問題進行數(shù)學(xué)抽象和數(shù)學(xué)建模，得到的數(shù)學(xué)模型就是 雙層規(guī)劃問題。雙層規(guī)劃在生活中的廣泛應(yīng)用，影響著人們的生產(chǎn)和生活，促使 了人們最它的研究和探索。 1 9 7 3 年，b 豫e l ( e n 和m e g i l l 提出了雙層規(guī)劃問題的模型n 3 ，1 9 7 7 年，c 蠲d l e f 和 n o n o n 首次在報告中首次提出了雙層規(guī)劃和多層規(guī)劃的概念瞻】。s 妣k e l b e f g 研究市 場經(jīng)濟建立了s t a c k e l b e r g 博弈模型，該模型在經(jīng)濟中得到廣泛的應(yīng)用，使得雙層規(guī) 劃得到了人們的充分的重視。近年來，雙層規(guī)劃受到了應(yīng)用數(shù)學(xué)、運籌學(xué)、管理 科學(xué)、決策科學(xué)、系統(tǒng)科學(xué)、經(jīng)濟學(xué)等眾多領(lǐng)域的廣泛關(guān)注，從瑟也罨| 起了許多 學(xué)者的研究興趣，許多學(xué)者對雙層規(guī)劃和多層規(guī)劃問題深入了研究，使用不同的 思想和方法提出了許多有效的算法，為人們的生活做出了巨大的貢獻。 第一章緒論 1 2 2 雙層規(guī)劃問題基本模型： 雙層規(guī)劃的基本模型： ( b l p ) m i n f ( x ，y ) 一g 哆亍o ( 1 1 ) m i n 廠( x ，y ) 、 s jg ( x ，y ) s o 其中：x r ”，y r ”分別稱為上層規(guī)劃問題和下層規(guī)劃問題的決策變量， f ，廠： 月腫”專尼，g ：r 腫”專r 尸， g ：r ”腳專r 9 。 從上面的模型中可以看出作為兩層決策問題的雙層規(guī)劃是一種具有兩層遞階 結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，并且上層規(guī)劃問題和下層規(guī)劃問題都有各自的目標(biāo)函數(shù)和 約束條件，上層規(guī)劃問題的目標(biāo)函數(shù)和約束條件不僅與上層規(guī)劃問題的決策變量 有關(guān)，而且還依賴于下層規(guī)劃問題的最優(yōu)解，而下層規(guī)劃問題的最優(yōu)解又受上層 決策變量的影響 1 2 3 雙層規(guī)劃的定義及其概念： 對于問題( b l p ) 定義如下概念： 問題( b l p ) 的容許集：q = ( x ，j ，) x 】，l g ( x ，y ) s 0 ，g ( x ，y ) 0 ) 對于上層給定的x x ，下層規(guī)劃問題的約束域：q ( x ) = 抄ig ( x ，y ) 0 ) q 在上層決策空間的投影：元= x i j y ，使得( x ，y ) q 對給定的x 叉，下層規(guī)劃的合理反應(yīng)集： m ( x ) = yiy a r gm i n 廠( x ，y ) ly q ( x ) ) 下層合理反應(yīng)集是隱映射，它表示下層規(guī)劃對上層決策的反應(yīng)。有時對于上層 的某些x x ，下層可能有多個反應(yīng)j ，與之對應(yīng)，即下層規(guī)劃問題的最優(yōu)解不唯一， 有時對于某些x x ，下層問題可能是不可行，因此，有時對于一些x ，下層合理反 應(yīng)集是空集。 對于任意給定的x 和相應(yīng)的y m ( x ) ，問題( b l p ) 的下層規(guī)劃問題的最優(yōu)值： 1 ，( x ) = ( x ，y ) 。 4 求解兩類特殊雙層規(guī)劃問題的遮傳算法 對給定的x 賈，問題( b l p ) 的誘導(dǎo)域：緩【( 麓y ) | x z 羅掰( 曲 則問題 ( b l p ) 就轉(zhuǎn)化為如下形式的優(yōu)化問題：睜 f o ，j ，) l ( x ，j ，) 皿 。 定義1 1 ：如果( 為少) 豫，則稱點( 墨力為雙層規(guī)劃問題( b l p ) 的可行解。 定義1 2 ：如果存在( f ，) 豫，對于任意0 ，y ) 豫有f ( 0 ，) f ( x ，y ) ，則稱 點( x + ，y 。) 為雙層規(guī)劃問題( b l p ) 的最優(yōu)解。 1 2 4 約束優(yōu)化的最優(yōu)性條件 全局最優(yōu)解嘲：設(shè)，：掣一定為毯標(biāo)函數(shù)，s 簍美”為可行域，i s 。 ( 1 ) 對于一切x s ，都有廠( i ) 墨( x ) ，則稱i 為廠( x ) 在s 上的全局最優(yōu)解( 極 小化問題) 。 ( 2 ) 若對于一切x s 但x i ，都有，( 西 八x ) ，則稱；為( x ) 在s 主的嚴(yán)格 全局最優(yōu)解。 1 等式約束優(yōu)化問題： 仨萵) ”地， ( 1 2 ) i j j 辦，( x ) = o = 1 ，2 ， 、 其中，：露”一震，恐：定4 一定，歹= l ，2 ，。 定理1 1 嘲：設(shè)廠：r ”一r 在i 鼴r ”處可微，_ ：r “_ 尺( ，= l ，2 ，z ) 在點i 處 具有一階連續(xù)偏導(dǎo)數(shù)，向量組v 盔( i ) ，v 魄( ；) ，v 趣( ；) 線性無關(guān)。若i 是問題 ( 卜2 ) 的局部極小點，則存在實數(shù)e ，= l ，2 ，使得， ， 夥( i ) 一e v 哆( ；) = o ( 1 - 3 ) l 定理1 2 陵：對于悶題( 卜2 ) 中，是凸函數(shù)，哆( 歹= l ，2 ，) 是線性函數(shù)，i 可行點，并且在點茹可微，若i 是問題( 卜2 ) 的局部極小點，則；是問題( 卜2 ) 的 全局極小點，廠( 動為闖題( 1 2 ) 的全局極小值。 2 不等式約束優(yōu)化問題： 第一幫緒論 陋纛，茗) ( 1 嘞 l s 0 舅( x ) o = l ，2 ，磁 其中：( x ) ：火”嶺r ，呂( 搿) ：尺”一r ，( f = l ，2 ，聊) 。 k u 婦t 玨e k f 條件： 用，( i ) 表示在可行點茹處起作用約束的指標(biāo)集，即 z 6 一 f l 臻( 動= o ，f = l ，2 ，搬 定理羔。3 讎：設(shè)i 是閽題( 董一4 ) 的可行點，秘藏( i 芒f ( i ) ) 在點；處可微， 蕊( 彗j 動) 在點；處連續(xù)，并且魄( ；) ( 芒j ( ；) ) 線性無關(guān)。若；是隨題( p 4 ) 熬局 部極小點，則存在菲負(fù)數(shù)麓( 建j ( ；) ) ，使得 叭；) 一m 魄( i ) = o 挺艇 如果g ( 堙，( 動) 在點；處也可微，則存在咎o ( = l ，2 ，磁) ，使得 l 蹦動一萋輯吲動一s ) ，。lti 一 ， i 夠愛并) 一執(zhí)江l ，2 ，掰 稱i 為問題( 卜4 ) 的k - t 點。 定理蔓。唾瀚：設(shè)在潤題( 卜毒) 中，秘一警，f = | ，2 ，搬) 是瑟齲數(shù)，i 是霹符 點，并且，和畿( 堙歹；) ) 在點；處可微，若蔓是闋題( 卜4 ) 的k t 點，測i 為悶題 ( 卜4 ) 的全局極小點。 l 。2 。s 雙瑟規(guī)劃酶主要特點： ( 1 ) 層次??；雙層規(guī)劃分為兩層，瑟上層規(guī)劃和下層規(guī)劃，下層服從主層，僵 有一定的是主權(quán)，下層規(guī)劃在上層決策變量的基礎(chǔ)土，來優(yōu)化爨邑的目標(biāo)函數(shù)， 求其全局最優(yōu)解。 ( 2 ) 獨立性：上層和下層分別控制著自己的決策變量，獨自優(yōu)化自己的目標(biāo)函 數(shù)值，確定其決策變量。 ( 3 優(yōu)先性：上層規(guī)劃苔先優(yōu)化照己的醬標(biāo)蘧數(shù)，確定上層決策變量，然麓下 層規(guī)劃根據(jù)上層給出的決策變量，優(yōu)化目標(biāo)函數(shù)，求其最優(yōu)解。 ( 4 ) 沖突性：由于上層規(guī)劃首先做出決策，然后下層規(guī)劃做躦決策，再反饋給 6 求解兩類特殊雙層規(guī)劃問題的遺傳算法 上層規(guī)劃，然麗這些嗣挺往往是相互沖突的。 ( 5 ) 良主性：上層麓決策可能影螭下層鮑決策，宅只是部分的影響，下屢規(guī)劃 可以在上層規(guī)劃給出的決策變量的基礎(chǔ)上可以優(yōu)化自己的目標(biāo)函數(shù)值。 ( 6 ) 制約性：下層規(guī)劃不但可以優(yōu)化自融的網(wǎng)標(biāo)函數(shù)值，而且做出的決策反饋 給上層覯劃爵，影響上瑩酶西赫醋數(shù)值，因就，上層篾劃在徽惠決策時，也要考 慮下層的決策對翻己的影響。 ( 7 ) 依賴性：由上面的定義可以看出，約束域般是不可分離的，形成個相 關(guān)的整體。 1 2 6 酲前求解雙層規(guī)劃的主要算法融3 ： 雙層規(guī)劃是多層次規(guī)劃中最簡單一種，輟然雙層規(guī)劃從模型和概念的提出到 現(xiàn)在僅3 e 多年發(fā)展煎歷史，綴是它褥到了重視，嚷雩| 了人稍斡興趣，人們徽了大 量的研究，從而提出了許多有效的算法，大致有：極點搜索法、分枝定界算法、 互補旋轉(zhuǎn)法、下降方向法、罰函數(shù)法、模糊數(shù)法、k 。k - t 法、遺傳算法和其他一些 饒純方法等。 ( 王) 極點搜索法 極點搜索算法最早、由b a r d 等人瞄1 在約束集有界的假設(shè)下，證明了線性雙層規(guī) 劃最優(yōu)解豹個數(shù)為有限個，在約束集的極點處，至少存在一個極點是最優(yōu)解，于是 基于這個牲覆，提掰了授點搜索法。其中比較著名的極點接索法有k 次最好法幫播 搜索法。s h ic h e n g g e n 和z h a n gg u a n g q u a i l 陽3 在新定義雙層線性規(guī)劃的基礎(chǔ)上，提出 了推廣的k 次最好法求解雙層線性規(guī)劃問題，而且還提出了求解下層具有多個決策 者的雙層線性規(guī)劃潤題麴k 次最好法。極點算法主要簿決雙層線性規(guī)劃，其基本愚 路是，線性雙層規(guī)劃問題的任何解都出現(xiàn)在下層規(guī)劃的約束集合的極點處，首先 可以利用各種方法來找到約束空間的極點，然后從中找出雙層規(guī)劃問題的局部最 優(yōu)解或全麓最貔解。 ( 2 ) 分被定界法 分枝定界法在數(shù)學(xué)規(guī)劃中被廣泛的應(yīng)用，它般可以收斂到全局最優(yōu)解，主 要用于求解整數(shù)規(guī)劃，也被廣泛應(yīng)用于求解雙層問題中。f o m m y a m a tm c c 甜1 1 首 先把雙層二次撬劃藏題轉(zhuǎn)純勢單層混合整數(shù)的二次規(guī)翔闐題，然蜃蹋分授定秀求 解，來求得全局最優(yōu)解；b a r d 和囂d m u n d s 等秘提出了求解二次雙層規(guī)劃的分枝定界 法和求解整數(shù)線性雙層規(guī)劃的分枝定界法，w e n 和y a n g 等阻3 提出了求解整數(shù)線性二 層規(guī)矧的分技定賽法。分枝定賽法主要應(yīng)翔予求解雙層整數(shù)援劃當(dāng)中，分技定界法 的基本思路是報據(jù)事先選定的分棱準(zhǔn)則，將所求解的聞題分成一系列子閼題，并 從中選取個子問題進行檢驗，決定其取舍。分枝定界法計算量很大，但它能求 篇一章緒論 7 得全局最傀解。 3 ) 互孝 旋轉(zhuǎn)法 b i a l a s 等h 們最早提出了互補旋轉(zhuǎn)法來求解線性雙層規(guī)劃。此算法可以看作是下 層最優(yōu)基的隱迭代，并且算法的所有計算像單純形表的框架中進行。后來b i a l a s 和 k 鑫測- 鼴n 蝣指露這種互補旋轉(zhuǎn)法不麓求凄全局最優(yōu)解，后來由j u d i e 尊和f 勰s l i 瀚稚磚改 進了互補旋轉(zhuǎn)法，使得能夠得到全髑簸優(yōu)的互補旋轉(zhuǎn)法，提出了序列線性囂補算 法，求得線性雙層規(guī)劃和線性二次雙層規(guī)劃的s 全局最優(yōu)解。豆補旋轉(zhuǎn)法主要思想 是將閉題轉(zhuǎn)化為一個帶參數(shù)酶線性互補闖題，然蜃耀受限基算法，也就是帶參數(shù) 熬互替主元算法進行求解。該方法是種瘧發(fā)式算法，有時不畿確保牧斂于全焉 最優(yōu)解。后來對此算法進行修正，提出了連續(xù)線性互補旋轉(zhuǎn)算法，確保了算法的 全局收斂性。 4 ) 下降方向法 下降方向法有主要有三種：第一種算法是最速下降方向法，s a v 莉軸用最速下 降來求解雙層非線性規(guī)劃。v i c e n t e 等n 削針對雙層嚴(yán)凸二次規(guī)劃和凸二次規(guī)劃，這 特殊的結(jié)構(gòu)提出了兩張下降算法，釋基于旋轉(zhuǎn)尺度下降方法，但是它不麓保證 鼴幫最鍵。第二釋是改良的最速下降滋，在其中學(xué)| 入了計算精確步靜薪規(guī)則，并 且提出了結(jié)合這兩種策略的混合方法，但這種方法缺乏收斂性。后來我國數(shù)學(xué)學(xué) 者韓繼業(yè)，劃豳山和汪壽陽n 硼提出了一祧具有收斂性的新的下降算法，可以用來求 解雙層二次規(guī)劃和線髏二次雙層規(guī)劃瓣題。第三釋方法是k o l s 灝幫勰蓮微騶硝提箍 的下降算法來求解非線性雙層規(guī)劃。 ( 5 ) k k 。t 法 k 矗法黧基本思路是褥雙層規(guī)劃閼題中的下層援劃用k ，k 曩條彳譬代瞽，姨囂 將雙層規(guī)劃閥題純秀單層菲線性規(guī)剿閥遂求解，這種算法僅對于下層是凸勰鯔有 效，但是它的決策變量較多和約束較多時，計算量也較大。 ( 6 ) 罰函數(shù)方法 囂溺數(shù)法是數(shù)學(xué)瓶劃中常靂的一種方法。a 鼗鑫蕊遘采赫窯8 越靼w 歉i 絕翻提斑了對偶 間隙作為懲罰項的罰函數(shù)方法。y l vn 硝等提出了求解弱價格控制問題的罰函數(shù)方 法和基于k u h n t u c k e r 條件求解雙層線性規(guī)劃的罰函數(shù)方法n 9 1 。l i u 等咖1 為凸雙層規(guī) 劃提出了一耱薪的約寨掇格，在此約柬規(guī)格下給蹴了凸雙層規(guī)劃閽題的局部和全 局的一階精確弱蠡數(shù)法。萬締平和溺樹民疆璉把罰函數(shù)法和近似雙層規(guī)劃結(jié)合起來 提出了近似罰函數(shù)法來求解帶有線性約束的雙層規(guī)劃問題，并得到了收斂的罰函 數(shù)方法。罰霸數(shù)方法主要應(yīng)用非線憔規(guī)劃理論中的蹯函數(shù)原理，利用各種不同形 式麓懲罰頊，把下層瓣題轉(zhuǎn)純?yōu)橐粋€禿約束數(shù)學(xué)規(guī)劃翔題，然蜃援懲囂頊加別主 層目標(biāo)函數(shù)中，將問題轉(zhuǎn)化為一個帶懲罰參數(shù)的單層問題，稃通過求解系列非 線性規(guī)劃來求得問題的全局最優(yōu)解。 8 求解兩類特殊雙層規(guī)劃問題的遺傳算法 ( 7 ) 模糊數(shù)學(xué)算法 裴崢、黃天民疆2 針對上層有約束條件、下層有n 個獨立的決策單元的線嬖耋雙層 規(guī)劃問題，提出了一種模糊數(shù)學(xué)解法。劉新旺、達慶利盤3 1 針對多人遞階資源分配 問題提出了對決策者模糊滿意度進行兩步折衷的求解算法。其基本思路是充分利 用模糊數(shù)學(xué)中隸屬函數(shù)及模糊算子的概念和性質(zhì)，分別建立土層決策變量的隸屬 函數(shù)和上、下層決策者目標(biāo)函數(shù)的偏好隸屬函數(shù)，將雙層規(guī)劃問題轉(zhuǎn)化為單層規(guī) 劃問題，分別對各單層規(guī)劃的解進行討論，最終把雙層規(guī)劃問題轉(zhuǎn)化為求解單層 規(guī)劃問題，求得兩層決策聞題的滿意解。 ( 8 ) 遺傳算法方法 m a t h i e u 等嘲1 提出了解線性雙層規(guī)劃問題的遺傳算法，將上層的決策變量隨機 生成，然后通過求解一個線性規(guī)劃得到下層的反應(yīng)，而且在其遺傳算法中僅使用了 變異算予，然而在該方法中由于每一個霹行的個體不一定代表一個極值點，焉是代 表一個可達的解，這樣擴大了搜索空間。因此，h e j a z i 等洶提出了一種遺傳算法， 在該算法中每個可行個體代表可行域的一個頂點，因而大大減小了搜索空間，l i u 啪 提出了求解多層規(guī)劃s t a c 憊e l b e r g - n a s h 平衡的遺傳算法。n i w a 等3 應(yīng)用二進制編碼 的遺傳算法來求解分布式雙層o l 規(guī)劃問題。0 d u g u w a 和r o y 洶1 提出了一種求解雙 層規(guī)劃遺傳算法，通過兩個參與者之間有限的非對稱合作從而在單一框架中來求 解不同類型的雙層規(guī)劃問題。其基本思想是通過對決策變量進行編碼，然后利用 遺傳算法的隨機全蜀搜索，來褥到潤題的全局最鐃解。 此外，還有模擬退火、粒子群算法、割平面方法、禁忌搜索算法、信賴域算 法，同倫算法等求解雙層規(guī)劃的方法。 以上是入們提出的一些算法，其實也有不少學(xué)者積極研究雙層規(guī)劃悶題的最 優(yōu)性條件?？傮w上人們主要通過各種不同的方法，將雙層規(guī)翊轉(zhuǎn)化為單層規(guī)劃聞 題來研究。 l 。3 本文的主要工作與內(nèi)容安排 本文主要研究了兩類具有特殊結(jié)構(gòu)的雙層規(guī)劃問題，并針對這兩類特殊雙層 規(guī)劃，設(shè)計遺傳算法進行求解，并進行數(shù)值試驗，實驗結(jié)果表明了遺傳算法的有 效性。全文共分為四章，具體安排如下： 第一章為緒論部分，主要簡單的介紹了雙層規(guī)劃問題的基本概念和基礎(chǔ)知識， 以及研究現(xiàn)狀。 第二章較為詳細(xì)的籬紹了遺傳算法的基本概念、主要特點、基本框架及其廣 泛的應(yīng)用。 第三章深入研究了上層規(guī)劃的目標(biāo)函數(shù)和約束沒有凸性和可微性要求，下層 第一章緒論9 規(guī)劃為關(guān)于下層決策變量為正定二次規(guī)劃的這一特殊結(jié)構(gòu)的雙層規(guī)劃問題?；?思想為首先利用k k t 條件對下層規(guī)劃問題進行求解，將下層規(guī)劃的最優(yōu)解表示為 關(guān)于上層決策變量和l a 黟a n g e 乘子五的表達式，針對問題的特點設(shè)計了一個改進的 凸交叉算子，并應(yīng)用遺傳算法對這類雙層規(guī)劃進行求解，證明了算法的收斂性，最 后進行數(shù)值實驗取得了良好的效果。 第四章主要研究了對上層規(guī)劃的目標(biāo)函數(shù)和約束沒有凸性和可微性要求，下 層規(guī)劃為關(guān)于下層決策變量為帶有線性等式約束的正定二次規(guī)劃的這一特殊結(jié)構(gòu) 的雙層規(guī)劃。其基本思想為先應(yīng)用k k t 條件對下層規(guī)劃進行求解，將下層規(guī)劃的 最優(yōu)解表示為僅關(guān)于上層決策變量的表達式，然后將下該最優(yōu)解代入上層規(guī)劃， 使雙層規(guī)劃轉(zhuǎn)化為僅關(guān)于上層決策變量的單層規(guī)劃，從而降低了搜索的維數(shù)，最 后，設(shè)計一個新的交叉算子，應(yīng)用新的遺傳算法對這類雙層規(guī)劃進行快速求解， 最后證明算法的收斂性，并進行數(shù)值實驗，驗證了算法的有效性。 第二章遺傳算法簡介 第二章遺傳算法簡介 2 1 遺傳算法概述 遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種概率搜索 算法。它以達爾文自然進化論“物競天擇，適者生存”和孟德爾的生物遺傳變異 理論為基礎(chǔ)，借鑒生物界自然選擇和自然遺傳機制，以概率為基礎(chǔ)，在解空間中 進行隨機搜索，最終找到問題全局最優(yōu)解。2 0 世紀(jì)6 0 年代，美國m i c h i g a n 大學(xué)的 h o l l a n d 教授提出了遺傳算法，它起源于6 0 年代對生物系統(tǒng)所進行的計算機模擬的 研究。7 0 年代h o l l a n d 教授提出了遺傳算法的基本定理一模式定理，從而奠定了遺傳 算法的理論基礎(chǔ)；同時d ej o n g 基于遺傳算法的思想在計算機上進行了大量的純數(shù) 值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎(chǔ)上，g o l d b e r g 進行歸納總結(jié)，形成 了遺傳算法的基本框架，并出版專著搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳算法( g e n e t i c a l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a m i n g ) 啪1 ，從此遺傳算法受到了 人們的關(guān)注，并使它得到迅速的發(fā)展，逐漸發(fā)展成了計算智能的一個重要的方向， 并應(yīng)用于科研和工程等眾多領(lǐng)域。 2 2 遺傳算法的基礎(chǔ)理論研究概述 遺傳算法是一種群體型操作，它以種群中的所有個體為操作對象。遺傳算法 主要使用選擇、交叉和變異三個基本遺傳算子。遺傳算法包括6 個基本因素：( 1 ) 參數(shù)的編碼；( 2 ) 初始種群的設(shè)定；( 3 ) 適應(yīng)度函數(shù)的設(shè)計；( 4 ) 遺傳算子的設(shè)計； ( 5 ) 停止運行準(zhǔn)則及結(jié)果的解碼；( 6 ) 控制參數(shù)設(shè)定，包括群體規(guī)模，交叉概率、 變異概率，停止運行準(zhǔn)則的參數(shù)等。 2 2 1 遺傳編碼 在使用遺傳算法求解實際問題時，由于遺傳算法不能直接處理解空問的數(shù)據(jù) 上，所以必須在實際問題的解空間與遺傳算法的編碼空間的點之間建立一個對應(yīng) 關(guān)系，將實際問題中解的形式轉(zhuǎn)換為遺傳算法能夠處理的解的表達形式，即進行 編碼運算，把問題空間中的解轉(zhuǎn)換成遺傳空間中的染色體或個體，稱作編碼；與 其相逆的過程為譯碼運算。遺傳算法的編碼可以根據(jù)問題靈活設(shè)計，但編碼對遺 傳算法的搜索效果和效率產(chǎn)生非常重要的影響。對特定的問題確定合適的編碼是 非常重要的，所以問題的編碼一般應(yīng)滿足如下3 個原則： ( 1 ) 完備性( c o m p l e t e n e s s ) ：問題空間中的所有點都能成為編碼后空間中的點。 1 2 求解兩類特殊雙藤規(guī)劃問題的遺傳算法 2 ) 健全性s o u n d 懿e s 站：編瑪詹空間的點能對成原闖題空間的所有點。 ( 3 囂冗余性爨蟄融e d 黼d a 辯勢：編碼矮空瓣的點與霖囊題空間瓣點一一對應(yīng)。 d e j o n 甓提出了以下兩條操作性較強的使用編褥原則： ( a ) 有意義積木塊編媽規(guī)則：應(yīng)使用能易于產(chǎn)生與所求闋越棚關(guān)的具有低階、 短定義長度模式豹編碼方案。 ( b ) 最小字符集編碼規(guī)娜：應(yīng)使用能使聞邀褥戮自然、簡肇表示和描述的鼴有 最小字符集酶編碼方案。 編碼熬優(yōu)劣程度對遺傳算子設(shè)計的難易和潤趲的求解效攀產(chǎn)生菲鬻重癸的影 響，所以在實際應(yīng)用遺傳算法求耨闖題時，登須瓣編碼方法、交叉算子的設(shè)詩、 變異算子的設(shè)計、譯碼方法等統(tǒng)一考慮，來尋求種對問題的描述最為簡葷、且 使遺傳算法求解效率最寒的編碼方案。 在實際巍耀孛，壺于的闌題麴不固或者瓣予圈闖題都有各種不弱的編碼方 式，常用的編碼方式有：二進制編碼、實數(shù)編碼、格雷編碼、符號編碼、序列編 碼、樹編碼、自適應(yīng)編碼、多參數(shù)聯(lián)編碼、多參數(shù)交叉編碼等。 2 。2 2 初始群體蘸壘藏 一定數(shù)量朐個體綴戲了種群，群體巾個體麴數(shù)謦稱鴦種群艘模。盤于遺贊算法 的群體性操作的需要，所以在執(zhí)行遺傳操作之前，必須已經(jīng)有個由若干的鋼始 解綴藏的初始種群。由乎實際闋題的復(fù)雜性，往往并不具有關(guān)予閼題解空聞的先 驗舞識，所毅穰難確定最撬辯酶數(shù)量及箕在蜀行解空闖中韻分蠢。霞就我翻一般 希望生成一定數(shù)盡的個體( 個體數(shù)強等于種群規(guī)模) ，使得這些個體所對應(yīng)的解在 解空間均勻分靠。初始種群中的每個個體一般都是通過隨機方法產(chǎn)生，也稱為進 純懿裙始代。耱群規(guī)模怒遺傳算法的控翎參數(shù)之一，其選取對遺傳算法酶效率霸 速度有影蛹。一般群體溉模在死十到凡囂之聞取毽，根據(jù)潤題的復(fù)雜程度不麗而 取值不同，悶題越難，維數(shù)越高，種群規(guī)模應(yīng)越大，反之則小。 初貽群體的設(shè)定一般霹袋敢翔下方法： ( 1 ) 設(shè)法確定最優(yōu)篇在整個舞題空闋酶分布范圍，然螽在就范圍蠹產(chǎn)生均勻分 布的初始種群。 ( 2 ) 先髓規(guī)生成定數(shù)目的個體，然后從中選出最好的個體加入種群中，不斷 重簸這一過程，直剿達到耱群巍摸。男辨，對于帶約束翡褥題，還需要考慮戮隨 機初始純酶點是否在可符區(qū)域中，如果不在麓趲韻可行域中，霹戩使熏與間題相 關(guān)的領(lǐng)域的知識對其修j 琶使其至少對戚所求問題的一個可行解。 2 。2 。3 適應(yīng)發(fā)遺數(shù)； 種群中個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度。為了執(zhí)行適者生存的原則，遺傳 算法必須對個體的適應(yīng)性進行評價。因此，需要度量個體的適應(yīng)度，度量個體適 第二章遺傳算法簡介 應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。遺傳算法在搜索進化過程中一般不需要其他外部信 息，只根據(jù)個體適應(yīng)度，就可以決定它在此環(huán)境下的生存能力。好的個體具有較 高的適應(yīng)度函數(shù)值，具有較好的生存能力。差的個體一般適應(yīng)度函數(shù)值較小，所 以生存能力相對弱。由于適應(yīng)度是群體中個體生存機會選擇的唯一確定性指標(biāo)， 所以適應(yīng)函數(shù)的形式直接決定著群體的進化行為。為了能夠直接將適應(yīng)度函數(shù)與 群體中的個體優(yōu)劣度量相聯(lián)系，在遺傳算法中規(guī)定適應(yīng)度為非負(fù)，并且在任何情 況下總是希望越大越好。一般而言，適應(yīng)度函數(shù)是通過對目標(biāo)函數(shù)的轉(zhuǎn)化而形成 的。 ( 1 ) 評價個體適應(yīng)度的一般過程是： ( a ) 對個體編碼串進行解碼處理后，可得到個體的表現(xiàn)型； ( b ) 由個體的表現(xiàn)型可計算出對應(yīng)個體的目標(biāo)函數(shù)值； ( c ) 根據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個體的適應(yīng) 度； ( 2 ) 適應(yīng)度函數(shù)的設(shè)計一般主要滿足以下條件： ( a ) 函數(shù)性質(zhì)：單值、連續(xù)、非負(fù)； ( b ) 合理性、一致性：要求適應(yīng)度函數(shù)值能夠反映出對應(yīng)解的優(yōu)劣程度； ( c ) 計算量小：要求適應(yīng)函數(shù)設(shè)計應(yīng)盡可能簡單； ( d ) 通用性強：適應(yīng)函數(shù)對某一類具體問題，應(yīng)盡可能通用； 在實際應(yīng)用中，根據(jù)問題的不同和特殊性，可以設(shè)計特殊的遺傳算法，可以 不必完全遵守上述規(guī)則。 2 2 4 適應(yīng)度尺度變換： 遺傳算法中，在進化過程是以種群中各個個體的適應(yīng)度為依據(jù)，各個個體被 遺傳到下一代群體中的概率是由個體的適應(yīng)度來確定的，通過一個迭代過程，不 斷的尋求出適應(yīng)度較大的個體，最終就可得到問題的最優(yōu)解或近似最優(yōu)解。在進 化的初期，為避免早熟收斂，應(yīng)縮小個體間差異，從而限制其選擇數(shù)量，從而， 維護了種群的多樣性；在進化的最后階段，為了加快收斂，應(yīng)放大個體間的差異， 因此，在遺傳算法運行的不同階段還需要對個體的適應(yīng)度進行適當(dāng)?shù)財U大或縮小， 這種對個體適應(yīng)度所做的擴大或縮小的變換稱為適應(yīng)度尺度變換。適應(yīng)函數(shù)的常 用尺度變換法有如下幾種：線形尺度變換法、冪尺度變換法、指數(shù)尺度變換法。 ( 1 ) 線性變換： 線性尺度變換公式：，= 卵+ 6 式中，為原適應(yīng)度；f 是經(jīng)尺度變換的后的適應(yīng)度；口，6 是系數(shù)。 ( 2 ) 乘冪尺度變換： 乘冪變換公式：，= f 1 4 求解兩類特殊雙層規(guī)劃問題的遺傳算法 即新的適應(yīng)度是原有適應(yīng)度的某個指定乘冪。冪指數(shù)七與所求解的問題有關(guān)，并 在算法的執(zhí)行過程中霈不斷對其進行修正菇1 能使尺度變換滿足一定的伸縮要求。 ( 3 ) 指數(shù)尺度變換： 指數(shù)尺度換公式為：，= e x p ( 一，) ，式中系數(shù)決定了選擇的強制性，越 小，原有適應(yīng)度較高的個體與其德的新適應(yīng)度相差較大，也即越增加了選擇個體， 的強制性。 2 2 5 遺傳算法的基本遺傳算子跚啪1 ： 遺傳算法是模擬生物進化過程的仿生算法，它主要有三個遺傳算子分別是： 選擇算子；交叉算子；變異算子； ( 1 ) 選擇算子 選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下 一代群體的遺傳運算。它是根據(jù)適瘴度函數(shù)值選擇適應(yīng)值高的個體以形成交配池 的過程。在被選種群中按照一定的選擇概率進行操作，這個概率取決于種群中個 體的適應(yīng)度及其分布。其主要作用是避免基因缺失，提高全局收斂性和計算效率。 愛前常用的選擇方法主要有：賭輪選擇、最饒保存策略選擇、捧序選擇、聯(lián) 賽選擇、精英選擇、穩(wěn)態(tài)選擇、確定式采樣選擇、無放回隨機選擇、無放回余數(shù) 選擇、期望值選擇等方法。 ( 2 ) 交叉算子 遺傳算法交叉算子是模仿自然界有性繁殖，兩個同源染色體通過交配兩重組， 形成新的染色體，從而產(chǎn)生出新的個體或物種。對兩個父代個體進行基因操作， 其作用在于把原有優(yōu)良基因遺傳給下一代個體，并生成包含更復(fù)雜基因結(jié)構(gòu)的新 個體。交叉運算是指對兩個相互配對的染色體按某種方式相互交換其部分基因， 從而形成兩個新的個體。 目前，一般經(jīng)常使用的交叉算子有：單點交叉、兩點交叉、多點交叉、一致 交叉、算術(shù)交叉等形式。針對特定的問題，還可以設(shè)計其他類型的交叉算予，而 且對于不同的編碼方式，交叉算子也不同。 交叉算子是遺傳算法運行過程中的一個重要的操作，交叉算子的設(shè)計一般主 要考慮以下兩個原則： ( a ) 必須保涯優(yōu)良基因能夠在下一代中有一定的遺傳和繼承的祝會； ( b ) 必須通過交叉操作有一定的生成優(yōu)良基因的機會； 交叉方式的設(shè)計與問題編碼緊密有關(guān)，必須結(jié)合編碼位串的結(jié)構(gòu)來設(shè)計高效 的交叉算子。在實際應(yīng)用時，可根據(jù)問題的特殊性應(yīng)靈活設(shè)計和應(yīng)用交叉算子， 可以大大提高遺傳算法求解的效率。 ( 3 ) 變異算予 第二章遺傳算法簡介 1 5 變異操作是模擬自然界生物進化中染色體上某位基因發(fā)生突變現(xiàn)象，從而改 變?nèi)旧w的結(jié)構(gòu)和物理性狀。在遺傳算法中，變異運算是指將個體染色體編碼串 中的某些基因座上的基因值用基因座的其他等位基因來替換，從而形成一個新個 體。變異算子通過變異概率p 。隨機對個體染色體中的基因進行突變來實現(xiàn)。遺傳 算法中使用變異算子的作用主要為了改善遺傳算法的局部搜索能力和維持群體的 多樣性，抑制了出現(xiàn)早熟的現(xiàn)象。為了保證個體變異后不會與其父體產(chǎn)生太大差 異，變異概率p 。一般取值較小值，以保證種群發(fā)展得穩(wěn)定性。交叉操作是產(chǎn)生新 個體的主要方法，它決定了遺傳算法的全局搜索能力；而變異操作只是產(chǎn)生新個 體的輔助方法，它決定遺傳算法的局部搜索能力，使用變異算子可以維持群體的 多樣性，防止出現(xiàn)早熟現(xiàn)象和提高算法的局部搜索效率。 目前一般常用的變異算子有：基本位變異、均勻變異、邊界變異、非均勻變 異、插入變異、對換變異、高斯變異等。 2 2 6 遺傳算法的參數(shù)設(shè)定口們 在遺傳算法的運行過程中，存在對其性能產(chǎn)生重大影響的一組參數(shù)。這組參 數(shù)在初始化階段或群體進化過程中如果能有合理的選擇和控制，就能使遺傳算法 將能夠發(fā)揮最佳作用，在隨機搜索中迅速達到最優(yōu)解。主要參數(shù)包括染色體長度 ，群體規(guī)模，交叉概率p r ，以及變異概率p 。在經(jīng)典遺傳算法和一些簡單遺 傳算法中，這些參數(shù)是不變的。然而，隨著研究的深入和經(jīng)驗的積累，許多學(xué)者 發(fā)現(xiàn)如果這些參數(shù)能夠隨著遺傳算法進程而變化，這種有自適應(yīng)性能的遺傳算法 具有更高的魯棒性、全局最優(yōu)性，但其缺點在于將增加算法復(fù)雜性和計算量等。 還有一些參數(shù)的改進方法，比如，模糊控制參數(shù)法、基于均勻設(shè)計的參