系統(tǒng)工程第章系統(tǒng)優(yōu)化

IntroductiontoSystemsEngineering

石英

武漢理工大學自動化學院E-mail:系統(tǒng)工程概論教學內(nèi)容第一章

緒論

（1學時）

第二章系統(tǒng)分析與系統(tǒng)建模（3學時）

第三章最優(yōu)化技術(shù)（24學時）

第四章

系統(tǒng)優(yōu)化（2學時）

第五章

決策分析（2學時）

系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:武漢理工大學自動化學院石英§4-1系統(tǒng)優(yōu)化方法概述系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法系統(tǒng)優(yōu)化問題的應用場合：工程設計中參數(shù)的選擇（既滿足設計要求，又能降低成本）生產(chǎn)計劃安排（采用合理的方案，提高產(chǎn)值和利潤）城市建設規(guī)劃（工廠、學校、醫(yī)院、機關(guān)、商店、住宅和其他公共設施的安排，方便群眾）系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法傳統(tǒng)優(yōu)化算法：必須定義被優(yōu)化系統(tǒng)的性能指標和約束條件；必須選擇代表優(yōu)化因素的獨立變量；寫出表示個變量之間關(guān)系的數(shù)學模型。現(xiàn)代優(yōu)化算法：用來解決優(yōu)化問題中的難解問題，對系統(tǒng)模型復雜而無法用明確解析方程來描述的問題有效。系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英系統(tǒng)優(yōu)化方法概述概述遺傳算法現(xiàn)代優(yōu)化算法：是20世紀80年代初興起的啟發(fā)式算法，這些算法包括禁忌搜索(tabusearch)、模擬退火(simulatedannealing)、遺傳算法(geneticalgorithms)、人工神經(jīng)網(wǎng)絡(neuralnetworks)。啟發(fā)式算法是這樣一種技術(shù)，它在可接受的計算代價內(nèi)去尋找最好的解，但不能保證所得的解是最優(yōu)的，所以有必要對算法進行評價。系統(tǒng)工程概論第四章系統(tǒng)優(yōu)化§4-1系統(tǒng)優(yōu)化方法概述

§4-2遺傳算法E-mail:武漢理工大學自動化學院石英系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英遺傳算法概述遺傳算法一．遺傳算法中相關(guān)的遺傳學基礎二．遺傳算法的原理和特點三．遺傳算法的基本操作四．簡單遺傳算法的算法描述五．簡單遺傳算法舉例§4-2遺傳算法系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英遺傳算法概述遺傳算法§4-2遺傳算法一．遺傳算法中相關(guān)的遺傳學基礎

遺傳算法是根據(jù)生物進化的模型提出的一種優(yōu)化算法。

根據(jù)達爾文的進化論，生物的發(fā)展進化主要有三個原因：遺傳、變異和選擇。

遺傳：指子代總是和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把它的特性、性狀傳給后代。遺傳是生物進化的基礎。

系統(tǒng)工程概論E-mail:武漢理工大學自動化學院石英遺傳算法概述遺傳算法選擇：指具有精選的能力，它決定生物進化的方向。進化過程中，有的要保留，有的要被淘汰，即適者生存，優(yōu)勝劣汰。

生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發(fā)展和進化。變異：指子代和親代有某些不相似的現(xiàn)象，即子代不會和親代完全一樣。它是生物個體之間區(qū)別的基礎。生物的變異性為生物的進化和發(fā)展創(chuàng)造了條件。

系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法二．遺傳傳算法的的原理和和特點遺傳算法法的基本本思想：：首先將需需要優(yōu)化化的參數(shù)數(shù)進行編編碼，組組成一個個種群;按照一定定的適值值函數(shù)和和一系列列遺傳操操作對種種群中的的各個個個體進行行篩選，，使適值值(fitness也叫適應應度)高的個體體被保留留，組成成新的種種群，新種群包包含了上上一代的的大量信信息，并并且引入入了新的的優(yōu)于上上一代的的個體。。這樣周而而復始，，種群中中個體的的適值不不斷提高高，直至至滿足一一定的極極限條件件。此時時，種群群中適值值最高的的個體即即為需要要優(yōu)化參參數(shù)的最最優(yōu)解。。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法由于遺傳傳算法獨獨具特色色的工作作原理，，使它能能夠在復復雜空間間進行全全局優(yōu)化化搜索，，并且具具有較強強的魯棒棒性。同常規(guī)優(yōu)優(yōu)化算法法比較，，遺傳算算法有以以下優(yōu)點：1．遺傳算算法是對對參數(shù)的的編碼進進行操作作，而非非參數(shù)本本身。這這樣算法法的操作作信息量量大，優(yōu)優(yōu)化效果果好。2．遺傳算算法是從從許多點點開始并并行操作作，可以以有效防防止搜索索過程收收斂于局局部最優(yōu)優(yōu)解問題題。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法4．遺傳算算法的尋尋優(yōu)規(guī)則則是由概概率決定定的，而而非確定定性的。。5．遺傳算算法在解解空間進進行高效效啟發(fā)式式搜索，，而不是是盲目地地窮舉或或完全隨隨機搜索索。6．遺傳算算法具有有并行計計算的特特點，可可以借助助大規(guī)模模并行計計算來提提高計算算速度。。3．遺傳算算法對所所要解決決的優(yōu)化化問題沒沒有太多多的數(shù)學學要求。。它通過過目標函函數(shù)來計計算適值值，并不不需要其其它推導導和附加加信息，，因此對對問題的的依賴性性較小。。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法三．遺傳傳算法的的基本操操作一般的遺遺傳算法法都包含含三個基基本操作作：復制制、交叉叉和變異異。1．復制（（Reproduction）復制又稱稱繁殖，，也叫選選擇（selection），它是從一一個舊種種群中選選擇生命命力強的的個體位位串，產(chǎn)產(chǎn)生新種種群的過過程。也就是說說，復制制是個體體位串根根據(jù)目標標函數(shù)（（適值函函數(shù)）計計算適值值，按照照適值進進行復制制，具有有較高適適值的位位串出現(xiàn)現(xiàn)在下一一代種群群中的可可能性就就大。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法例如，設設有一個個優(yōu)化問問題，在在整數(shù)空空間[0,31]上求函數(shù)數(shù)f(x)=x2的最大值值。首先把參參數(shù)x編碼為有有限長度度的字符符串，一一般使用用二進制制數(shù)串，，設參數(shù)數(shù)x的編碼長長度為5。則有：“00000”代表參參數(shù)0，“11111”代表參參數(shù)31，區(qū)間[0,31]上的數(shù)與與編碼之之間采用用線性映映射方法法。隨機產(chǎn)生生復制操操作的初初始種群群。例如隨機機生成的的有4個數(shù)的初初始種群群如下：：系統(tǒng)工程程概論遺傳傳算算法法概述述遺傳算法法將初始種種群中的的個體視視為長度度為5位的無符符號二進進制數(shù)，，每個位位串可解解碼為一一個十進進制數(shù)：：位串1：：0110113位位串2：：1100024位位串3：：010008位串4：1001119對種群的的各位串串根據(jù)目目標函數(shù)數(shù)f(x)=x2計算相應應的適值值和比例例，結(jié)果果如表所所示。系統(tǒng)工程程概論遺傳傳算算法法概述述遺傳算法法復制操作作可以用用多種算算法實現(xiàn)現(xiàn)，其中中最簡單單的方法法是轉(zhuǎn)輪輪法。轉(zhuǎn)輪法：將種群群中所有有個體位位串的適適值的總總和看作作一個輪輪子的圓圓周，每每個位串串按照它它的適值值在總和和中所占占的比例例，在圓圓周中用用一個扇扇區(qū)表示示。按照上表表畫出的的轉(zhuǎn)輪如如圖所示示。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法由于初始始種群中中的每個個位串的的適值不不同，所所占總數(shù)數(shù)的百分分比不一一樣，因因此在轉(zhuǎn)轉(zhuǎn)輪旋轉(zhuǎn)轉(zhuǎn)時，被被選中的的概率就就不一樣樣。例如，本本次產(chǎn)生生的4個位串中中，原初初始種群群中，有有的位串串被選中中一次，，有的被被選中多多次，而而有的一一次也沒沒有選中中，即該該位串被被淘汰。。因此，，適值最最好的位位串在新新種群中中就有較較多的拷拷貝。產(chǎn)生的新新種群的的情況如如下表所所示。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法2．交叉（（Crossover）遺傳算法法的有效效性主要要來自復復制和交交叉操作作。復制制操操作作雖雖然然能能夠夠從從舊舊種種群群中中選選擇擇出出優(yōu)優(yōu)秀秀者者，，但但不不能能創(chuàng)創(chuàng)造造出出新新的的個個體體；；交叉叉操操作作模模擬擬了了生生物物進進化化過過程程中中的的繁繁殖殖現(xiàn)現(xiàn)象象，，通通過過兩兩個個個個體體的的交交換換組組合合，，來來創(chuàng)創(chuàng)造造出出新新的的優(yōu)優(yōu)良良個個體體。。簡單單的的交交叉叉分分兩兩步步實實現(xiàn)現(xiàn)：：（1）將將新新復復制制產(chǎn)產(chǎn)生生的的位位串串個個體體隨隨機機進進行行兩兩兩兩配配對對；；（2）隨隨機機選選擇擇交交叉叉點點，，對對匹匹配配的的位位串串進進行行交交叉叉繁繁殖殖，，產(chǎn)產(chǎn)生生一一對對新新的的位位串串。。系統(tǒng)統(tǒng)工工程程概概論論武漢漢理理工工大大學學自自動動化化學學院院石石英英遺傳傳算算法法概述述遺傳傳算算法法下面面舉舉例例說說明明交交叉叉實實現(xiàn)現(xiàn)過過程程。。設位位串串的的字字符符長長度度為為l，在[1,l－1]的范范圍圍內(nèi)內(nèi)，，隨隨機機選選取取一一個個整整數(shù)數(shù)值值k作為為交交叉叉點點。。將將兩兩個個位位串串的的第第k位右右邊邊部部分分的的所所有有字字符符進進行行交交換換，，從從而而生生成成兩兩個個新新的的位位串串。。b1b2b3b4b5a1a2a3a4a5b1b2b3a4a5a1a2a3b4b5新串1新串2交叉前交叉后例如如，，在在前前述述表表1中，，l＝5，對兩兩個個隨隨機機配配對對的的位位串串個個體體A1和A2，隨機機選選取取k＝4，經(jīng)過過交交叉叉后后產(chǎn)產(chǎn)生生的的新新串串為為A’’1和A’’2。系統(tǒng)統(tǒng)工工程程概概論論武漢漢理理工工大大學學自自動動化化學學院院石石英英遺傳傳算算法法概述述遺傳傳算算法法A1=01101A2=11000A’1=01100A’2=11001對兩兩個個隨隨機機配配對對的的位位串串個個體體A3和A4，隨機機選選取取交交叉叉點點k＝2，經(jīng)過過交交叉叉后后產(chǎn)產(chǎn)生生的的新新串串為為A’’3、和A’’4。A3=11000A4=10011A’3=11011A’4=10000經(jīng)過過交交叉叉后后的的結(jié)結(jié)果果數(shù)數(shù)據(jù)據(jù)如如下下表表所所示示。。系統(tǒng)統(tǒng)工工程程概概論論遺傳傳算算法法概述述遺傳傳算算法法在進進行行交交叉叉時時，，如如果果交交叉叉的的位位置置只只有有一一個個稱稱為為單單點點交交叉叉，，對對于于位位串串長長度度為為l的種種群群，，單單點點交交叉叉可可能能有有l(wèi)－1個不不同同的的交交叉叉。。交叉時也可以以選擇多點交交叉，也稱為為復點交叉，，即允許個體體的切斷點有有多個，每個個切斷點在兩兩個個體間進進行個體的交交叉，生成兩兩個新個體。。系統(tǒng)工程概論論武漢理工大學學自動化學院院石英遺傳算算法概述遺傳算法3．變異（Mutation）變異也叫突變變，盡管在遺遺傳算法中，，復制和交叉叉操作是最重重要的，但它它不能保證不不會遺漏一些些重要的遺傳傳信息。在簡單遺傳算算法中，變異異就是指某個個字符串中某某一位的值偶偶然的（概率率很小的）隨隨機的改變，，也就是說在在某些特定位位置上簡單地地把1變?yōu)?，或把0變變?yōu)?。當有限制地將將變異和交叉叉一起使用時時，可以防止止一些重要的的遺漏。例如，對于上上述例子，如如果隨機產(chǎn)生生的種群為：：系統(tǒng)工程概論論武漢理工大學學自動化學院院石英遺傳算算法概述遺傳算法在交叉過程中中，無論如何何在第4位上都不可能能得到有1的位串。因此此最終所得到到的解只能是是局部最優(yōu)解解。但結(jié)合變變異操作就可可以解決這個個問題。變異運算是用用來模擬生物物在自然的遺遺傳環(huán)境中由由于各種偶然然因素引起的的基因突變，，它以很小的的概率隨機改改變位串個體體中的某一位位的值。從上面的簡單單例子分析中中可以看出，，雖然只進行行了一代遺傳傳操作，但所所獲得的新種種群的適值的的平均值和最最大值卻比初初始種群有了了很大的提高高，平均值由由293增到了439，最大值由576增加到729。這說明隨著著遺傳運算的的進行，種群群正向著優(yōu)化化的方向發(fā)展展。系統(tǒng)工程概論論武漢理工大學學自動化學院院石英遺傳算算法概述遺傳算法四．簡單遺傳傳算法的算法法描述簡單遺傳算法法只使用了復復制算子（選選擇算子）、、交叉算子和和變異算子這這三種基本遺遺傳算子，其其遺傳進化操操作過程簡單單，容易理解解．是其他一一些遺傳算法法的雛形和基基礎，它不僅僅給各種遺傳傳算法提供了了一個基本框框架，同時也也具有一定的的應用價值。。系統(tǒng)工程概論論武漢理工大學學自動化學院院石英遺傳算算法概述遺傳算法1．簡單遺傳算算法的構(gòu)成要要素(1)染色體編碼方方法簡單遺傳算法法使用固定長長度的二址制制位串來表示示種群中的個個體，初始種種群中各個個個體的位串值值可用均勻分分布的隨機數(shù)數(shù)來生成。如：這個個體的染染色體長度為為n＝18。系統(tǒng)工工程概概論武漢理理工大大學自自動化化學院院石石英英遺傳傳算算法法概述述遺傳算算法(2)個體適適應度度評價價―――適值值（fitness）基本遺遺傳算算法按按照與與個體體適值值正比比的概概率，，來決決定當當前種種群中中每個個個體體遺傳傳到下下一代代的機機會的的大小小。為了正正確計計算這這個概概率，，要求求所有有個體體的適適應度度必須須為正正數(shù)或或零。。這樣樣，根根據(jù)不不同種種類的的問題題．必必須預預先確確定好好由目目標函函數(shù)值值到個個體適適應度度之間間的轉(zhuǎn)轉(zhuǎn)換規(guī)規(guī)則，，特別別是要要預先先確定定好當當目標標函數(shù)數(shù)值為為負數(shù)數(shù)時的的處理理方法法。系統(tǒng)工工程概概論武漢理理工大大學自自動化化學院院石石英英遺傳傳算算法法概述述遺傳算算法(3)遺傳算算子簡單遺遺傳算算法使使用三三種遺遺傳算算子：：●復制制運算算使用用復制制算子子；●交叉叉運算算使用用單點點交叉叉算子子；●變異運運算使使用基基本位位變異異算子子或均均勻變變異算算子。。系統(tǒng)工工程概概論武漢理理工大大學自自動化化學院院石石英英遺傳傳算算法法概述述遺傳算算法(4)簡單遺遺傳算算法的的運行行參數(shù)數(shù)簡單遺遺傳算算法有有以下下4個運行行參數(shù)數(shù)需要要提前前設定定：●M：種群大大小，，即種種群中中所含含個體體的數(shù)數(shù)量，，一般般取為為20～100。●T：遺傳運運算的的終止止進化化代數(shù)數(shù)，一一般取取為100～500?！馪c：：交叉概概率，，一般般取為為0.4～～0.99?！馪m：變異概概率，，一般般取為為0.0001～0.1。這4個運行行參數(shù)數(shù)對遺遺傳算算法的的求解解結(jié)果果和求求解效效率都都有一一定的的影響響，但但目前前還沒沒有合合理選選擇它它們的的理論論依據(jù)據(jù)。在在遺傳傳算法法的實實際應應用中中，往往往需需要經(jīng)經(jīng)過多多次試試算后后，才才能確確定出出這些些參數(shù)數(shù)合理理的取取值大大小或或取值值范圍圍。系統(tǒng)統(tǒng)工工程程概概論論遺傳傳算算法法概述述遺傳傳算算法法2．簡簡單單遺遺傳傳算算法法描描述述下面面給給出出簡簡單單遺遺傳傳算算法法的的偽偽代代碼碼描描述述。。簡單單遺遺傳傳算算法法可可定定義義為為一一個個8元元組組：：SGA＝＝(C，，E，，P0，M，，Φ,гг,ψψ，T)式中中:C--個體體的的編編碼碼方方法法；；E--個體體適適值值評評價價函函數(shù)數(shù)；；P0--初始始種種群群；；M--種群群大大小小;Φ--復制制算算子子；；г——交叉叉算算子子；；ψ——變異異算算子子；；T——遺傳傳運運算算終終止止條條件件。。系統(tǒng)統(tǒng)工工程程概概論論遺傳傳算算法法概述述遺傳傳算算法法ProcedureSGABeginInitializeP(0);t=0;while(t≤T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoReproductionoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endfor系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法fori=1toMdoP(t+1)=P(t)endfort=t+1endwhileend系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法五．簡單單遺傳算算法舉例例簡單遺傳傳算法是是一個迭迭代過程程，它模模仿生物物在自然然環(huán)境中中的遺傳傳和進化化機理，，反復將將復制算算子、交交叉算子子子、變變異算子子作用于于種群，，最終可可得到問問題的最最優(yōu)解或或近似最最優(yōu)解。。1．遺傳算算法的應應用步驟驟遺傳算法法提供了了一種求求解復雜雜系統(tǒng)優(yōu)優(yōu)化問題題的通用用框架，，它不依依賴于問問題的領(lǐng)領(lǐng)域和種種類。對一個需需要進行行優(yōu)化計計算的實實際應用用問題，，一般可可按以下下步驟來來構(gòu)造求求解該問問題的遺遺傳算法法。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法第一步：：確定決決策變量量及其各各種約束束條件，，即確定定出個體體的表現(xiàn)現(xiàn)型x和問題的的解空間間。第二步：：建立優(yōu)優(yōu)化模型型，即確確定出目目標函數(shù)數(shù)的類型型(是求目標標函數(shù)的的最大值值還是求求目標函函數(shù)的最最小值?)及其數(shù)學學描述形形式或量量化方法法。第三步：：確定表表示可行行的個體體編碼方方法，也也就是確確定出個個體的位位串x及遺傳算算法的搜搜索空間間。第四步：：確定解解碼方法法，也就就是確定定出由個個體位串串x到個體表表現(xiàn)型x的對應關(guān)關(guān)系或轉(zhuǎn)轉(zhuǎn)換方法法。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法第五步；；確定個個體適值值的量化化評價方方法，也也就是確確定出由由目標函函數(shù)值g(x)到個體適適應度f(x)的轉(zhuǎn)換規(guī)規(guī)則。第六步：：設計遺遺傳算子子，即確確定出復復制運算算、交叉叉運算、、變異運運算等遺遺傳算子子的具體體操作方方法。第七步：：確定遺遺傳算法法的有關(guān)關(guān)運行參參數(shù)，即即確定出出遺傳算算法的M、T、Pc、Pm等參數(shù)。。下圖是應應用遺傳傳算法解解決實際際問題的的流程。。系統(tǒng)工程程概論遺傳傳算算法法概述述遺傳算法法實際問題參數(shù)集編碼成位串形式種群1計算適值選擇和遺傳統(tǒng)計結(jié)果種群2經(jīng)過優(yōu)化的一個或多個參數(shù)值改善或解決實際問題隨機算子種群1<-種群2復制.交叉.變異系統(tǒng)工程程概論遺傳傳算算法法概述述遺傳算法法2．簡單遺遺傳算法法在函數(shù)數(shù)優(yōu)化中中的應用用舉例例用簡單遺遺傳算法法求解Rosenbrock函數(shù)的全全局最大大值。f(x1,x2)＝100(x12－x2)2＋(1-x1)2（6-1-1）-2.048<xi<2.048(i=1,2)（6-1-2）系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法如圖所示示，該函函數(shù)有兩兩個局部部極大點點，分別別是f(2.048,-2.048)=3897.7342和f(-2.048,-2.048)=3905.9296，其中后者者為全局局最大點點。系統(tǒng)工程程概論武漢理工工大學自自動化學學院石石英遺傳傳算算法法概述述遺傳算法法下面討論論求解該該問題的的遺傳算算法的構(gòu)構(gòu)造過程程.第一步：：確定決策策變量和和約束條條件。式（6-1-2）就是該該問題的的決策變變量和約約束條件件。第二步：建立優(yōu)化模型型。式（6-1-1）就是該問題題的數(shù)學模型型。第三步：確定編碼方法法。用長度為10位的二進制位位串來分別表表示二個決策策變量x1和x2。10位編碼可以表表示從0～1023之間的1024個不同的數(shù)。。系統(tǒng)工程概論論武漢理工大學學自動化學院院石英遺傳算算法概述遺傳算法將x1和x2的定義域(-2.048~2.048)離散化為1023個均等的區(qū)域域，包括兩個個端點在內(nèi)共共有1024個不同的離散散點。依次讓讓它們對應于于從0000000000(0)到1111111111(1023)之間的二進制制編碼。再將分別表示示x1和x2的二個10位長的編碼串串連接在一起起，組成一個個20位長的編碼，，它就構(gòu)成了了這個函數(shù)優(yōu)優(yōu)化問題的染染色體（個體體）編碼方法法。系統(tǒng)工程概論論遺傳算算法概述遺傳算法第四步：確定解碼方法法。解碼時需要先先將20位長的位串分分割成二個10位長的位串，，然后將它們們分別轉(zhuǎn)換為為對應的十進進制整數(shù)代碼碼，分別記為為y1和y2。根據(jù)前面介紹紹的個體