遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用張砦第一頁，共四十六頁。目錄一、遺傳算法概述二、多目標(biāo)優(yōu)化問題三、實(shí)例1——Rosenbrock函數(shù)最值問題四、實(shí)例2——智能組卷問題第二頁，共四十六頁。一、遺傳算法概述1.1遺傳算法的生物學(xué)基礎(chǔ)1.2遺傳算法搜索機(jī)制

1.3遺傳算法的發(fā)展1.4基本遺傳算法（SGA）1.5遺傳算法的特點(diǎn)1.6遺傳算法的收斂性分析1.7遺傳算法研究的主要問題1.8遺傳算法的應(yīng)用第三頁，共四十六頁。1.1遺傳算法的生物學(xué)基礎(chǔ)生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的自適應(yīng)能力。受其啟發(fā)，人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithms，簡稱GAs)所借鑒的生物學(xué)基礎(chǔ)是生物的遺傳和進(jìn)化。(1)生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀；(2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過程發(fā)生在染色體上；(3)生物的繁殖過程是由其基因的復(fù)制過程來完成的；(4)通過同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(5)對(duì)環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。第四頁，共四十六頁。1.2遺傳算法搜索機(jī)制

遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象（染色體的變化），將實(shí)際問題的解答描述成染色體的形式，進(jìn)行類似生物進(jìn)化現(xiàn)象的操作以求解。對(duì)每次迭代中保留的候選解，按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。第五頁，共四十六頁。1.3遺傳算法的發(fā)展

(1)萌芽期(50年代后期至70年代初期)?50年代后期，一些生物學(xué)家著手采用電子計(jì)算機(jī)模擬生物的遺傳系統(tǒng)，盡管這些工作純粹是研究生物現(xiàn)象，但其中已使用現(xiàn)代遺傳算法的一些標(biāo)識(shí)方式。?1965年，德國的L.Rechenberg等人正式提出進(jìn)化策略的方法，當(dāng)時(shí)的進(jìn)化策略只有一個(gè)個(gè)體，而且進(jìn)化操作也只有變異一種。?1965年，美國的L.j.Fogel正式提出進(jìn)化規(guī)劃，在計(jì)算中采用多個(gè)個(gè)體組成的群體，而且只運(yùn)用變異操作。?60年代期間，美國J.H.Holland在研究自適應(yīng)系統(tǒng)時(shí)，提出系統(tǒng)本身與外部環(huán)境相互協(xié)調(diào)的遺傳算法。1968年，J.H.Holland教授又提出模式理論，它成為遺傳算法的主要理論基礎(chǔ)。?1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（GeneticAlgorithm）”一詞。第六頁，共四十六頁。

(2)成長期(70年代中期至80年代末期)?1975年，J.H.Holland教授的專著《AdaptationinNaturalandArtificialSystem》正式出版，全面地介紹了遺傳算法，人們常常把這一事件視作遺傳算法問世的標(biāo)志，Holland也被視作遺傳算法的創(chuàng)始人。?1975年，De.Jong在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。?1987年，美國D.Lawrence總結(jié)人們長期從事遺傳算法的經(jīng)驗(yàn)，公開出版《GeneticAlgorithmandSimulatedAnnealing》一書，以論文集形式用大量實(shí)例介紹遺傳算法。?1985年，作為Holland的學(xué)生，D.E.Goldberg博士出版專著《GeneticAlgorithms——inSearch，OptimizationandMachineLearning》，全面、系統(tǒng)地介紹遺傳算法，使這一技術(shù)得到普及與推廣。該書被人們視為遺傳算法的教科書。?1985年，在美國舉行第一屆遺傳算法國際學(xué)術(shù)會(huì)議(InternationalConferenceonGeneticAlgorithms，簡稱ICGA），與會(huì)者交流運(yùn)用遺傳算法的經(jīng)驗(yàn)。隨后，每2年左右都舉行一次這種會(huì)議。第七頁，共四十六頁。(3)發(fā)展期(90年代以后)90年代，遺傳算法不斷地向廣度和深度發(fā)展。?1991年，D.Lawrence出版《HandbookofGeneticAlgorithms》一書，詳盡地介紹遺傳算法的工作細(xì)節(jié)。?1996年Z.Michalewicz的專著《遺傳算法+數(shù)據(jù)結(jié)構(gòu)=進(jìn)化程序》深入討論了遺傳算法的各種專門問題。同年，T.Back的專著《進(jìn)化算法的理論與實(shí)踐：進(jìn)化策略、進(jìn)化規(guī)劃、遺傳算法》深入闡明進(jìn)化算法的許多理論問題。?1992年，Koza出版專著《GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection》，該書全面介紹了遺傳規(guī)劃的原理及應(yīng)用實(shí)例，表明遺傳規(guī)劃己成為進(jìn)化算法的一個(gè)重要分支。?1994年，Koza又出版第二部專著《GeneticProgrammingⅡ:AutomaticDiscoveryofReusablePrograms》，提出自動(dòng)定義函數(shù)的新概念，在遺傳規(guī)劃中引入子程序的新技術(shù)。同年，K.E.Kinnear主編《AdvancesinGeneticProgramming》，匯集許多研究工作者有關(guān)應(yīng)用遺傳規(guī)劃的經(jīng)驗(yàn)和技術(shù)。第八頁，共四十六頁。1.4基本遺傳算法（SGA）1.4.1基本遺傳算法的構(gòu)成要素(1)染色體編碼方法基本遺傳算法使用固定長度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因由二值符號(hào)集{0，1}組成。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。如：1101101，就可表示一個(gè)個(gè)體，該個(gè)體的染色體長度是18。(2)個(gè)體適應(yīng)度評(píng)價(jià)基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。第九頁，共四十六頁。(3)遺傳算子基本遺傳算法使用下述三種遺傳算子：?選擇運(yùn)算：使用比例選擇算子；?交叉運(yùn)算：使用單點(diǎn)交叉算子；?變異運(yùn)算：使用基本位變異算子。

(4)基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：?M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取20-100。?T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取100-500?pc：交叉概率，一般取0.4-0.99?pm：變異概率，一般取0.0001-0.1說明:這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。第十頁，共四十六頁。1.4.2基本遺傳算法的形式化定義基本遺傳算法可定義為一個(gè)7元組：

GA＝(M,F,s,c,m,pc,pm)M——群體大小；F——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算子；c——交叉操作算子：m——變異操作算子；pc——交叉概率；pm——變異概率；第十一頁，共四十六頁。1.4.3基本遺傳算法的實(shí)現(xiàn)

（1）編碼與解碼假設(shè)某一參數(shù)的取值范圍是[umin,umax]，我們用長度為λ的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，則它總共能夠產(chǎn)生2λ種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：00000000…00000000＝0umin

00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2λ–1umax

其中，為二進(jìn)制編碼的編碼精度，其公式為：=umax

umin2λ

1第十二頁，共四十六頁。x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1假設(shè)某一個(gè)體的編碼是：

x：blbl-1bl-2……b2b1則對(duì)應(yīng)的解碼公式為：第十三頁，共四十六頁。[例]設(shè)-3.0≤x≤12.1,精度要求=1/10000，由公式：Umax

umin2l=+11/1000012.1+3.0+1==151001即：217

<151001<218

x需要18位{0/1}符號(hào)表示。如：1010000解碼：x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1=-0.3+70352(12.1+3)/(218-1)=1.052426=Umax

umin2l

1得：第十四頁，共四十六頁。（2）個(gè)體適應(yīng)度評(píng)價(jià)(1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(X)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)

(2)對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即：minf(X)＝max(-f(X))但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求。

第十五頁，共四十六頁。（3）選擇算子

作用：從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。

比例選擇算子：指個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。輪盤選擇：輪盤法的基本精神是：個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度，顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個(gè)體也有可能被選中，以便增加下一代群體的多樣性。第十六頁，共四十六頁。（4）交叉算子作用：通過交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新個(gè)體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。

單點(diǎn)交叉算子的具體計(jì)算過程如下：Ⅰ.對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。Ⅱ.每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。Ⅲ.對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。

單點(diǎn)交叉A；1011011100A’：1011011111B：0001110011B’：0001110000第十七頁，共四十六頁。（5）變異算子

基本位變異算子：最簡單和最基本的變異操作算子。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?，反之，若原有基因值為1，則變異操作將其變?yōu)?。

具體執(zhí)行過程：Ⅰ.對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。Ⅱ.對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。

A：1010101010A’：1010001010

變異點(diǎn)基本位變異第十八頁，共四十六頁。開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子j=0j=0j=0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個(gè)體添入新群體中將交叉后的兩個(gè)新個(gè)體添入新群體中將變異后的個(gè)體添入新群體中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm1.4.4算法流程圖第十九頁，共四十六頁。1.5遺傳算法的特點(diǎn)

（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。

遺傳算法的本質(zhì)：對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。第二十頁，共四十六頁。1.6遺傳算法的收斂性分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。第二十一頁，共四十六頁。(1)種群規(guī)模對(duì)收斂性的影響通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢。(2)選擇操作對(duì)收斂性的影響選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。第二十二頁，共四十六頁。(3)交叉概率對(duì)收斂性的影響交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。

(4)變異概率對(duì)收斂性的影響變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。

第二十三頁，共四十六頁。1.7遺傳算法研究的主要問題(1)局部最優(yōu)(2)收斂速度問題(3)正確性問題(4)算法的實(shí)現(xiàn)性問題改進(jìn)：編碼方式、遺傳算子、控制參數(shù)。第二十四頁，共四十六頁。1.8遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域：(1)函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，用遺傳算法可以方便地得到較好的結(jié)果。(2)組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問題，人們己意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。第二十五頁，共四十六頁。

(3)生產(chǎn)調(diào)度問題生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會(huì)因簡化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。而目前在現(xiàn)實(shí)生產(chǎn)中也主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。

(4)自動(dòng)控制在自動(dòng)控制領(lǐng)域中很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計(jì)空間交會(huì)控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。第二十六頁，共四十六頁。(5)機(jī)器人學(xué)機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。

(6)圖像處理圖像處理是計(jì)算機(jī)視覺中的一個(gè)重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面找到了用武之地，日前已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。(7)人工生命人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。第二十七頁，共四十六頁。雖然人工生命的研究尚處于啟蒙階段。但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個(gè)有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展。(8)遺傳編程Koza發(fā)展了遺傳編程的概念，他使用了以LISP語言所表示的編碼方法，基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作來自動(dòng)生成計(jì)算機(jī)程序。雖然遺傳編程的理論尚未成熟，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域。(9)機(jī)器學(xué)習(xí)學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一?；谶z傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù)，從而更好地改進(jìn)了模糊系統(tǒng)的性能；基于遺傳算法的機(jī)器學(xué)習(xí)可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)；分類器系統(tǒng)也在學(xué)習(xí)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。第二十八頁，共四十六頁。二、多目標(biāo)優(yōu)化問題描述1、工程問題大多是多目標(biāo)優(yōu)化問題；2、一般沒有絕對(duì)的最優(yōu)解，只有可行解；3、可行解有多種組合可能；4、多個(gè)目標(biāo)相互制約；5、求解需要充分了解約束之間的關(guān)系。第二十九頁，共四十六頁。三、實(shí)例1——Rosenbrock函數(shù)最值問題

求Rosenbrock函數(shù)的全局最大值計(jì)算。

maxf(x1,x2)=100(x12-x22)2+(1-x1)2s.t.-2.048≤xi≤2.048(xi=1,2)如圖所示：該函數(shù)有兩個(gè)局部極大點(diǎn)，分別是:f(2.048,-2048)=3897.7342和f(-2.048,-2.0048)=3905.9262其中后者為全局最大點(diǎn)。第三十頁，共四十六頁。下面介紹求解該問題的遺傳算法的構(gòu)造過程：第一步：確定決策變量及其約束條件。

s.t.-2.048≤xi≤2.048(xi=1,2)第二步：確定適應(yīng)度函數(shù)。maxf(x1,x2)=100(x12-x22)2+(1-x1)2第三步：確定編碼方法。用長度為l0位的二進(jìn)制編碼串來分別表示二個(gè)決策變量x1,x2。lO位二進(jìn)制編碼串可以表示從0到1023之間的1024個(gè)不同的數(shù)，故將x1,x2的定義域離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。從離散點(diǎn)-2.048到離散點(diǎn)2.048，依次讓它們分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示x1和x2的二個(gè)10位長的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體編碼方法。例如X：00001101111101110001就表示一個(gè)個(gè)體的基因型。第三十一頁，共四十六頁。第四步：確定解碼方法。

解碼時(shí)先將20位長的二進(jìn)制編碼串切斷為二個(gè)10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。依據(jù)前述個(gè)體編碼方法相對(duì)定義域的離散化方法可知，將代碼yi轉(zhuǎn)換為變量xi的解碼公式為：例如，對(duì)前述個(gè)體X：00001101111101110001它由這樣的兩個(gè)代碼所組成：y1=55y2=881經(jīng)上式的解碼處理后，得到：x1=-1.828x2=1.476xi=4.096yi

1023

2.048(i=1,2)第三十二頁，共四十六頁。

第五步：確定個(gè)體評(píng)價(jià)方法。由式f(x1,x2)=100(x12-x22)2+(1-x1)2可知，Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，并且不再對(duì)它作其他變換處理，即有：F(x)=f(x1,x2)第六步：設(shè)計(jì)遺傳算子。選擇運(yùn)算使用比例選擇算子；交叉運(yùn)算使用單點(diǎn)交叉算子；變異運(yùn)算使用基本位變異算子。第七步：確定遺傳算法的運(yùn)行參數(shù)。對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下：群體大