多目標優(yōu)化方法PPT課件

1、第二部分第二部分 多目標優(yōu)化方法多目標優(yōu)化方法 Multi-Objective Optimization 第一節(jié)第一節(jié) 概述概述 第三節(jié)第三節(jié) 多目標優(yōu)化的第一類方法多目標優(yōu)化的第一類方法 第二節(jié)第二節(jié) 多目標優(yōu)化設計理論多目標優(yōu)化設計理論 第四節(jié)第四節(jié) 多目標優(yōu)化的第二類方法多目標優(yōu)化的第二類方法 第五節(jié)第五節(jié) 多目標優(yōu)化的第三類方法多目標優(yōu)化的第三類方法國際上通常認為多目標最優(yōu)化問題最早是在國際上通常認為多目標最優(yōu)化問題最早是在18861886年由法國經(jīng)年由法國經(jīng)濟學家濟學家ParetoPareto從政治經(jīng)濟學的角度提出的。多目標規(guī)劃的真從政治經(jīng)濟學的角度提出的。多目標規(guī)劃的真正發(fā)達時期，

2、并正式作為一個數(shù)學分支進行系統(tǒng)的研究，是正發(fā)達時期，并正式作為一個數(shù)學分支進行系統(tǒng)的研究，是上世紀七十年代以后的事。上世紀七十年代以后的事?，F(xiàn)在，對多目標規(guī)劃方面的研究集中在以下幾個方面現(xiàn)在，對多目標規(guī)劃方面的研究集中在以下幾個方面: : 一、關于解的概念及其性質的研究，一、關于解的概念及其性質的研究， 二、關于多目標規(guī)劃的解法研究，二、關于多目標規(guī)劃的解法研究， 三、對偶問題的研究，三、對偶問題的研究， 四、不可微多目標規(guī)劃的研究，四、不可微多目標規(guī)劃的研究， 五、多目標規(guī)劃的應用研究。五、多目標規(guī)劃的應用研究。到現(xiàn)在為止，多目標優(yōu)化不僅在理論上取得許多重要成果，到現(xiàn)在為止，多目標優(yōu)化不僅在

3、理論上取得許多重要成果，而且在應用上其范圍也越來越廣泛，多目標決策作為一個工而且在應用上其范圍也越來越廣泛，多目標決策作為一個工具在解決工程技術、經(jīng)濟、管理、軍事和系統(tǒng)工程等眾多方具在解決工程技術、經(jīng)濟、管理、軍事和系統(tǒng)工程等眾多方面的問題也越來越顯示出它強大的生命力。面的問題也越來越顯示出它強大的生命力。 第一節(jié)第一節(jié) 概述概述1. 1. 多目標優(yōu)化設計示例多目標優(yōu)化設計示例11221 max()45 max()f XxxfXx目標函數(shù)示例示例1 1：某工廠生產兩種產品：某工廠生產兩種產品A A和和B,B,每件產品每件產品A A需制造工時需制造工時和裝配工時分別為和裝配工時分別為1 1時和時

4、和1.251.25時，每件產品時，每件產品B B需制造工時和需制造工時和裝配工時分別為裝配工時分別為1 1時和時和0.750.75時，每月制造車間和裝配車間時，每月制造車間和裝配車間能夠提供的最多工時為能夠提供的最多工時為200200時，另外，每月市場對產品時，另外，每月市場對產品A A需需求量很大，而對產品求量很大，而對產品B B的最大需求量為的最大需求量為150150件，產品件，產品A A和產和產品品B B的售價分別為的售價分別為4 4元和元和5 5元，問如何安排每月的生產，最元，問如何安排每月的生產，最大限度的滿足市場需求，并產值最大？大限度的滿足市場需求，并產值最大？12ABxx設計變

5、量：產品 的件數(shù) ，產品 的件數(shù)0,1 . .*61 max* min21222122121xxxxt sxxxx示例示例2. 2. 用直徑為用直徑為1(1(單位長單位長) )的圓木制成截面為矩形的圓木制成截面為矩形的梁的梁, ,為使重量最輕為使重量最輕, ,而強度最大而強度最大, ,問截面的高與寬問截面的高與寬應取何尺寸應取何尺寸? ?解解: : 設矩形截面的高與寬分別設矩形截面的高與寬分別 為和為和 , , 這時這時梁的面積為梁的面積為 , ,它決定重量它決定重量, ,而梁的強度取而梁的強度取決于截面形決于截面形 。 1x2x21*xx221*61xx因此因此, ,容易列出容易列出 梁的數(shù)

6、學模型梁的數(shù)學模型: :示例示例3 3 物資調運問題物資調運問題: : 某種物資寸放三個倉庫某種物資寸放三個倉庫 里里, ,存放量分別為存放量分別為 ( (單位單位:t);:t);現(xiàn)要將這些物資運往四個銷售現(xiàn)要將這些物資運往四個銷售點點 。其需要量分別為。其需要量分別為 且且 ，已知，已知 到到 的距離和單位的距離和單位運價分別為運價分別為 (km)(km)和和 ( (元元),),現(xiàn)要決定如何現(xiàn)要決定如何調運多少調運多少, ,才能使總的噸才能使總的噸, ,公里數(shù)和總運費都盡量少公里數(shù)和總運費都盡量少? ?123,A A A123,a a a1234,B B B B1234,b b b b34i

7、jijabiAjBijdijc解: 設變量 表示由 運往 的貨物數(shù),于是總噸公里數(shù)為 ,總運費為 ,問題優(yōu)化設計模型為11ijijijxd4 , 3 , 2 , 1; 3 , 2 , 1,jixijiAjB4 , 3 , 2 , 1; 3 , 2 , 1, 04 , 3 , 2 , 1,3 , 2 , 1, . . * min* min314131413141jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc示例示例4 4：如圖所示，設計一苦空心階梯懸臂梁，根據(jù)結構要如圖所示，設計一苦空心階梯懸臂梁，根據(jù)結構要求，已確定梁的總長為求，已確定梁的總長為

8、10001000mmmm，第一段外徑為，第一段外徑為8080mmmm，第二段外經(jīng)為第二段外經(jīng)為100100mmmm，梁的端部受有集中力，梁的端部受有集中力F F12000N12000N，梁的內徑不得小于梁的內徑不得小于4040mmmm，梁的許用彎曲應力為梁的許用彎曲應力為180MPa180MPa，確定梁的內徑和各段長度，使梁的體積和靜撓度最小。確定梁的內徑和各段長度，使梁的體積和靜撓度最小。1 12 2D1=100D1=100D2=80D2=80L=1000L=1000 x1x2F F 多目標優(yōu)化設計模型多目標優(yōu)化設計模型6117422232419.78 10 . . ()18004.096

9、10()75.20()400()0 xstg XxgXxgXxgXx12xx設計變量：第一段梁的長度 ，梁的內徑22221122112 ()()()()4f Xx DxLxDx33214444442212126411 ()()3LfXxEDxDxDx12min()(),) (TF Xf XfX 多目標最優(yōu)化問題的一般形式為多目標最優(yōu)化問題的一般形式為: : S.t. 或者記作:min D= 12min( (),(),( )mf xf xfx( )0,1,2.,( )0,1,2,ijg xiph xjq( )f x |( )0, ( )0nxEg xh x xD 其中: =( ) ( )f x

10、1( ),( )mf xfx1( )( )( )pg xg xgx1( )( ( )( )qh xh xh x 2. 2. 多目標優(yōu)化設計模型多目標優(yōu)化設計模型iGxFy為滿足所有目標的參數(shù) 組成的參數(shù)空間為根據(jù) 按照目標函數(shù) 映射的組成的目標函數(shù)空間注意，這里以及注意，這里以及之后的所有講述之后的所有講述同時同時適合于線性適合于線性和非線性的多目和非線性的多目標優(yōu)化標優(yōu)化多目標優(yōu)化設計幾何描述多目標優(yōu)化設計幾何描述在單目標優(yōu)化問題中，任何兩個解都可以比較出其優(yōu)劣，這是在單目標優(yōu)化問題中，任何兩個解都可以比較出其優(yōu)劣，這是因為單目標優(yōu)化問題是完全有序的；而在多目標優(yōu)化設計中，因為單目標優(yōu)化問題

11、是完全有序的；而在多目標優(yōu)化設計中，任何兩個解不一定都可以比較出其優(yōu)劣，這是因為多目標優(yōu)化任何兩個解不一定都可以比較出其優(yōu)劣，這是因為多目標優(yōu)化問題是半有序的。問題是半有序的。3. 3. 多目標優(yōu)化問題解的特點多目標優(yōu)化問題解的特點T(1)(1)(1(1)(1)()(1)12T(2)(2)(2)(2)12(1)(2)(1)(21)( )2()(),(),() ()(),(),(), ()() (1,2,)mmllF Xf XfXfXF Xf Xff XfXfXXXlmXXXXX設為多目標優(yōu)化問題的兩個可行解，其對應若對于每一個分量，都則顯然，優(yōu)的目標函數(shù)于，記為有為(1)(2)(1)(2)(2

12、)(1)(2)(1)(2)()() ()() ()()() jjllF XF XfXfXF Xf Xf XXX大多數(shù)情況下，的某幾個分量小于的對應分量，但另外幾個分量大于的對應分量 則顯然，與無法比較優(yōu)劣。1f2f213第一類：轉化法。這類多目標最優(yōu)化方法的基本思想是將多目標第一類：轉化法。這類多目標最優(yōu)化方法的基本思想是將多目標問題轉化為一個或一系列的單目標優(yōu)化問題，通過求解一個或一問題轉化為一個或一系列的單目標優(yōu)化問題，通過求解一個或一系列單目標優(yōu)化問題來完成多目標優(yōu)化問題的求解。系列單目標優(yōu)化問題來完成多目標優(yōu)化問題的求解。4. 4. 多目標優(yōu)化方法分類多目標優(yōu)化方法分類第二類：非劣解集

13、法。這類多目標最優(yōu)化方法的基本思想是求第二類：非劣解集法。這類多目標最優(yōu)化方法的基本思想是求得多目標問題的非劣解集，然后在非劣解集中進行協(xié)調和選擇，得多目標問題的非劣解集，然后在非劣解集中進行協(xié)調和選擇，確定出優(yōu)惠解。確定出優(yōu)惠解。第三類：交互協(xié)調法。這類多目標最優(yōu)化方法的基本思想是通第三類：交互協(xié)調法。這類多目標最優(yōu)化方法的基本思想是通過在分析者與抉擇者間的不斷交互，逐漸搞清抉擇者的選擇意過在分析者與抉擇者間的不斷交互，逐漸搞清抉擇者的選擇意圖，獲得多目標問題的優(yōu)惠解。圖，獲得多目標問題的優(yōu)惠解。 第二節(jié)第二節(jié) 多目標優(yōu)化設計理論多目標優(yōu)化設計理論 1. 1. 多目標優(yōu)化設計模型多目標優(yōu)化設

14、計模型 . . ()0 1,2,()0 1,2,uvstgXuph Xvq 簡記為簡記為 VOP多目標優(yōu)化問題多目標優(yōu)化問題( (Multi-Objective Optimization Problem) )又稱為向量優(yōu)化問題又稱為向量優(yōu)化問題( (Vector Optimization Problem) ) 。12min()(),(),()TmF Xf XfXfX() V-mi nnF XXDR 2. 2. 決策空間與目標空間決策空間與目標空間() 0 1,2,() 0 1,2, =uvngXupXhXvqDXR 以設計變量為坐標的實空間以設計變量為坐標的實空間Rn稱為決策空間。稱為決策空間

15、。 以目標函數(shù)為坐標的實空間以目標函數(shù)為坐標的實空間Rm稱為目標空間。稱為目標空間。決策空間可行域：決策空間可行域：目標空間可行域目標空間可行域12=(),(), ,() ,mTFmXDFRFfXfXfXXD 示例示例1 1112212324152 . . ()2000()200 1.250.750()1500()0()0stg XxxgXxxgXxgXxgXx決策空間決策空間可行域可行域目標空間目標空間可行域可行域T121max F()45 Xxxx， 示例示例2 26117422232419.78 10 . . ()18004.096 10()75.20()400()0 xstg XxgX

16、xgXxgXx22221122112 ()()()()4f Xx DxLxDx決策空間決策空間可行域可行域目標空間目標空間可行域可行域12min()(),()TF Xf XfX33214444442212126411()()3LfXxEDxDxDx3. 3. 解的定義解的定義（1 1） 理想解理想解(ideal solution)000012,TmFfff在目標空間內，以單目標最小值為分量而形成的點，在目標空間內，以單目標最小值為分量而形成的點，稱為多目標問題的理想解稱為多目標問題的理想解。0min()njjffXXDR其中 在多目標優(yōu)化問題中，在多目標優(yōu)化問題中，由于各個目標間往往是由于各個

17、目標間往往是矛盾的，所以一般不存矛盾的，所以一般不存在使各目標皆達到各自在使各目標皆達到各自最優(yōu)值的理想解最優(yōu)值的理想解。fxX(0)f1(0)f2(0)f1f2（2 2） 非劣解（非劣解（Noninferior Solution）或）或 Pareto 解解()()pF XF X對于可行點對于可行點XP D，若不若不存在另一個可行點存在另一個可行點X D，使使()() 1,2,()()ppjjllfXfXjmfXfX 但至少有一個 成立，則稱成立，則稱Xp為多目標問題的非劣解。為多目標問題的非劣解。向量不等式的含義為向量不等式的含義為決策空間決策空間非劣解集非劣解集目標空間目標空間非劣解集非劣

18、解集7.1 模型舉例0,1 . .*61 max* min21222122121xxxxt sxxxx例7.1. 用直徑為1(單位長)的圓木制成截面為矩形的梁,為使重量最輕,而強度最大,問截面的高與寬應取何尺寸?解: 設矩形截面的高與寬分別 為和 , 這時梁的面積為 ,它決定重量,而梁的重量取決于截面矩形 。 1x2x21*xx221*61xx因此,容易列出 梁的數(shù)學模型:例7.2 物資調運問題: 某種物資寸放三個倉庫 里,存放量分別為 (單位:t);現(xiàn)要將這些物資運往四個銷售點 .其需要量分別為 且 ，已知 到 的距離和單位運價分別為 (km)和 (元),現(xiàn)要決定如何調運多少,才能使總的噸,

19、公里數(shù)和總運費都盡量少?123,A A A123,a a a1234,B B B B1234,b b b b34ijijabiAjBijdijc解: 設變量 表示由 運往 的貨物數(shù),于是總噸公里數(shù)為 ,總運費為 ,問題優(yōu)化為求解11ijijijxd4 , 3 , 2 , 1; 3 , 2 , 1,jixijiAjB4 , 3 , 2 , 1; 3 , 2 , 1, 04 , 3 , 2 , 1,3 , 2 , 1, . . * min* min314131413141jixjbxiaxtsxcxdijijijiiijijijijijijij11ijijijxc由于求最大都可以轉化為求最小由于求

20、最大都可以轉化為求最小,所以多目標最優(yōu)化問所以多目標最優(yōu)化問題的一般形式為題的一般形式為: S.t. 或者記作:min D= 12min( (),(),( )pf xf xfxljxhmixgji, 2 , 1, 0)(,. 2 , 1, 0)( )f x |( )0, ( )0pxEg xh x xD 其中: =( ) ( )f x 1( ),( )pf xfx1( )( )( )mg xg xgx1( )( ( )( )mh xh xhx 當P=1時,(VP)就是非線性規(guī)劃, 稱為單目標規(guī)劃。對于單目標問題Min , 總可比較 與 的大小.對于多目標規(guī)劃(VP),對于 ， 與 都是P 維向

21、量,如何比較兩個向量的大小?( )f x 12,x xD1()f x2()f x12,x xD1()f x2()f x可以看到：可以看到：多目標優(yōu)化的非劣解集Noninferior solution for the model*xxx(xx)x若，且對于 不存在，使得：與能同時成立，那么則定義 為多目標優(yōu)化問題的非劣解。例如：A,B點屬于非劣解，因為不滿足定義條件（3 3） 滿意解（最佳協(xié)調解或優(yōu)惠滿意解（最佳協(xié)調解或優(yōu)惠解）解）11(),(),()mUU f Xf XfX效用函數(shù)值的大小反映決策者對多目標值的喜愛程度，效用函數(shù)值的大小反映決策者對多目標值的喜愛程度，一般來說，決策者希望效用函

22、數(shù)的值越大越好。一般來說，決策者希望效用函數(shù)的值越大越好。效用函數(shù)：效用函數(shù)：決策者對多目標函數(shù)優(yōu)化解進行評價的函數(shù)，記為決策者對多目標函數(shù)優(yōu)化解進行評價的函數(shù)，記為使效用函數(shù)取最大值的非劣解稱為最佳協(xié)調解。使效用函數(shù)取最大值的非劣解稱為最佳協(xié)調解。對于效用函數(shù)未知對于效用函數(shù)未知的情況，無法直接的情況，無法直接求得最佳協(xié)調解。求得最佳協(xié)調解。我們把多目標優(yōu)化我們把多目標優(yōu)化過程滿意結束的解過程滿意結束的解稱為優(yōu)惠解。稱為優(yōu)惠解。滿意解滿意解4 4 多目標優(yōu)化問題的多目標優(yōu)化問題的K KT T條件條件對于多目標優(yōu)化問題對于多目標優(yōu)化問題 . . ()0 1,2,()0 1,2,uvstgXup

23、h Xvq VOP(),1,2,;(),1,2, ;(),1,2, ;juvfXjm gXup h Xvq設 *VOPjuvXXw皆為連續(xù)可微函數(shù)，為可行點，則為（）的非劣解的必要條件為：存在、與使*1*1()()()02()01,2,301,2,401,2,pqmjjuuvvjuvuuujwfXgXh XgX up up w jm （ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）12min()(),(),()TmF Xf XfXfX7.4 求解多目標規(guī)劃的評價函數(shù)法求解多目標規(guī)劃的評價函數(shù)法 盡管多目標優(yōu)化問題有各種意義下的最優(yōu)解.但在應用中,需要的還是有效解和弱有效解.本節(jié)介紹求有效解和弱

24、有效解最基本的方法-評價函數(shù)法. 評價函數(shù)法的基本思想是:借助于幾何或應用中的直觀效果.構造所謂的評價函數(shù).從而將多目標優(yōu)化問題轉化為單目標優(yōu)化問題.然后利用單目標優(yōu)化問題的求解方法求出最優(yōu)解.并把這種最優(yōu)解當作多目標優(yōu)化問題的最優(yōu)解.這里關鍵的問題是轉化后的單目標優(yōu)化問題的最優(yōu)解必須是多目標問題的有效解和弱有效解.否則是不能接受的. 所謂評價函數(shù),是利用(VP)的目標函數(shù) ,構造一個復合函數(shù) .然后在(VP)的約束集D上極小化 , 的構造必須保證在一定條件下, min 的最優(yōu)解是(VP)的有效解或弱有效解. 下面先討論在什么條件下, min 的最優(yōu)解才能是(VP) min 的有效解or弱有效

25、解. ( )f x( ( )f x( ( )f x( ( )f x( ( )f x()f x定義6. 設 : 1.若 ,總有 ,則稱 為 的嚴格單增函數(shù). 2 若 時,總有 ,則稱 為 的單增函數(shù).,:pnPEEfDEE12ZZ12()()ZZ( )ZZ12ZZ12()()ZZ( )ZZ定理1 . 設：: ,又設 ，是問題min 的極小點,那么: 若 為Z的嚴格單增函數(shù),則 是min 有效解. 若 為Z的單增函數(shù),則 是min 的弱有效解.pEE:nPfDEE*x( ( )f x*x*x( )f x( )f x重要定理幾種常用的構造評價函數(shù)的方法一. 理想點法: 在(VP)中,先求解P個單目標

26、問題 j=1，2，p xD 設其最優(yōu)值為 ,我們稱 為值域中的一個理想點 。min( )jfx*jf*12(,)Tpffff 因為一般很難達到它,這樣,就期望在某種等量下,尋求距最近的f作為近似值,一種最直接的想法是構造評價函數(shù) = （7.2） ( )Z2*1()piiiZf 然后極小化即求解：并將它的最優(yōu)解 作為(VP)在這種意義下的“最優(yōu)解”,由于 ,因此由7.2構造的 是嚴格單增的,從而 是(VP)的有效解.* 21min( )( )piiif xf xf*x*( )iiiZf xf( )Z*x二. 線性加權和法. 在具有多個指標的問題中,人們總希望對那些相對重要的指標給予較大的權系數(shù),

27、基于這種現(xiàn)實,自然如下的構造評價函數(shù),令 12,1(,) |01pTpiii 且12,1(,) |01pTpiii 且稱之為權向量集,令 再求解而將它的最優(yōu)解, 作為(VP)在該意義下的最優(yōu)解.1( )*,pTiiiP ZZZormin ( ( )*( )Tf xf x*x三. 極大極小法 在決策時，采取保守策略是穩(wěn)妥的。即在最壞的情況下，尋求最好的結果。按照這種想法，可以構造如下評價函數(shù) 然后求解 并將它的最優(yōu)解 作為（VP）在這種意義下的最優(yōu)解。ipizz1max)()(maxmin)(min1xfxfipiDxDxx 1. 1. 主目標法主目標法 轉化為轉化為 第三節(jié)第三節(jié) 多目標優(yōu)化的

28、第一類方法多目標優(yōu)化的第一類方法主目標法就是從多目標中依據(jù)重要程度選擇一個目標主目標法就是從多目標中依據(jù)重要程度選擇一個目標作為主目標，而將其它目標轉化為約束，即將多目標作為主目標，而將其它目標轉化為約束，即將多目標優(yōu)化問題優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvq0min () s.t. ()01,2, ()01,2, ()1,2,kuvllfXgXuph Xvqf Xflm lk主目標法中約束目標的約束值選取主目標法中約束目標的約束值選取0* 1,2,lllfflm lk* () min() 1,2,Xll

29、llXDff Xff Xlm lk式中為目標函數(shù)的單目標極小值， 即 * () 0.010.02) 1, ,2,llllf Xflm lk式中為對目標函數(shù)的單目標極小值的放大值，一般可取 （ 2. 2. 線性加權法線性加權法 轉化為轉化為線性加權法就是將多目標的加權和作為單目標，即將線性加權法就是將多目標的加權和作為單目標，即將多目標優(yōu)化問題多目標優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvqmin()() s.t. ()01,2, ()01,2, mllluvF Xw f XgXuph Xvq(2(2）對權系數(shù)的

30、要求）對權系數(shù)的要求 (3) (3) 權系數(shù)的確定權系數(shù)的確定 0 1,2,lwlm非負要求1 1mllw歸一化要求 老手法老手法*1 min()lllXDlwff Xf線性加權法的有關說明：線性加權法的有關說明：（1) 1) 線性加權之前，各目標應進行無量綱化處理。線性加權之前，各目標應進行無量綱化處理。 3. 3. 極小極大法極小極大法 轉化為轉化為極小極大法就是求取多目標函數(shù)中的最大值，然后使極小極大法就是求取多目標函數(shù)中的最大值，然后使最大值函數(shù)在可行域內極小化，即將多目標優(yōu)化問題最大值函數(shù)在可行域內極小化，即將多目標優(yōu)化問題12min()(),(),() s.t. ()01,2, (

31、)01 ,2,TmuvF Xf XfXfXgXuph Xvq1min max () s.t. ()01,2, ()01,2, ll muvf XgXuph Xvq (2) (2)極小極大法也可以引入一個變量極小極大法也可以引入一個變量 和和m個約束，即個約束，即極小極大法的有關說明：極小極大法的有關說明：（1) 1) 考慮到各目標的重要程度差別，可以對各目標考慮到各目標的重要程度差別，可以對各目標乘以權系數(shù)，然后再求最大值函數(shù)，即乘以權系數(shù)，然后再求最大值函數(shù)，即1min max () s.t. ()01,2, ()01,2, lll muvw f XgXuph Xvq min s.t. ()

32、01,2, ()01,2, () 1,2,uvllgXuph Xvqw f Xjm 4. 4. 理想點法理想點法 轉化為轉化為理想點法就是將距理想點最近的點作為多目標問題的理想點法就是將距理想點最近的點作為多目標問題的優(yōu)惠解，即將多目標優(yōu)化問題優(yōu)惠解，即將多目標優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01 ,2,TmuvF Xf XfXfXgXuph Xvq200()min() s.t. ()01,2, ()01,2,mlllluvf XfU XfgXuph Xvq00012mfff其中，為多目標問題在目標空間中的理想點。理想點法的有關說明：理想點法的有關說明：考

33、慮到各目標的重要程度差別，可以對各目標乘以權考慮到各目標的重要程度差別，可以對各目標乘以權系數(shù)，即系數(shù)，即權系數(shù)的選取可以參閱線性加權法。權系數(shù)的選取可以參閱線性加權法。200()min() s.t. ()01,2, ()01,2,mllllluvf XfU XwfgXuph Xvq 5. 5. 功效系數(shù)法功效系數(shù)法在多目標優(yōu)化問題，各目標的要求不全相同，有的要在多目標優(yōu)化問題，各目標的要求不全相同，有的要求極小化，有的要求極大化，有的要求有一個合適的求極小化，有的要求極大化，有的要求有一個合適的數(shù)值。為了反映這些不同的要求，故引入如下的功效數(shù)值。為了反映這些不同的要求，故引入如下的功效函數(shù)：

34、函數(shù)： 0110jjjjjccfcf的取值為 ， 表示目標 的值最滿意； 表示目標 的值最不滿意。() 1,2,jjcF fjm1 2 maxUjmmcc cc取所有 的幾何平均值為多目標問題的評價函數(shù)，即功效系數(shù)的確定：功效系數(shù)的確定：1.1.直線法直線法 2.2.折線法折線法 3.3.指數(shù)法指數(shù)法 6. 6. 分層序列法分層序列法將多目標優(yōu)化問題的各目標分清主次，按其重要程度將多目標優(yōu)化問題的各目標分清主次，按其重要程度逐一排序，然后依次對各目標函數(shù)求最優(yōu)解，但應注逐一排序，然后依次對各目標函數(shù)求最優(yōu)解，但應注意后一目標應在前一目標的最優(yōu)解域內進行尋優(yōu)。意后一目標應在前一目標的最優(yōu)解域內進

35、行尋優(yōu)。() 1,2 ,jfXjm設目標函數(shù)的重要程度排序為*11 min() f XfXD首先對第一個目標函數(shù)求最優(yōu)值*22*11 min() ()fXfXDX f Xf在第一個目標函數(shù)的最優(yōu)解域中，求第二個目標函數(shù)的最優(yōu)解，即照此繼續(xù)下去，最后求得第照此繼續(xù)下去，最后求得第mm個目標函數(shù)得最優(yōu)解，個目標函數(shù)得最優(yōu)解，真?zhèn)€解即為多目標優(yōu)化問題的最終解。真?zhèn)€解即為多目標優(yōu)化問題的最終解。在分層序列法中，當前面有某個目標函數(shù)的最優(yōu)解唯一在分層序列法中，當前面有某個目標函數(shù)的最優(yōu)解唯一時，該方法就發(fā)生中斷現(xiàn)象，因此需要引入目標容差。時，該方法就發(fā)生中斷現(xiàn)象，因此需要引入目標容差。*11 min()

36、 f XfXD首先對第一個目標函數(shù)求最優(yōu)值*22*111 min() ()fXfXDX f Xf在第一個目標函數(shù)的最優(yōu)解容差域中，求第二個目標函數(shù)的最優(yōu)解，即 7. 7. 協(xié)調曲線法協(xié)調曲線法協(xié)調曲線法主要用于求解兩個目標函數(shù)的多目標優(yōu)協(xié)調曲線法主要用于求解兩個目標函數(shù)的多目標優(yōu)化設計問題。化設計問題。目標規(guī)劃法目標規(guī)劃法Goal Attainment Method 引入目標概念：引入目標概念：F*，令非劣解集到目標的，令非劣解集到目標的距離（或稱范數(shù)）最小，選出一個非劣解。距離（或稱范數(shù)）最小，選出一個非劣解。Wi引入了一個松弛度的概念，松弛度最小引入了一個松弛度的概念，松弛度最小的一個非劣

37、解就是對于目標的一個非劣解就是對于目標F*的最可行解。的最可行解。優(yōu)點：不漏解，目標明確，計算量小。優(yōu)點：不漏解，目標明確，計算量小。缺點：對于非線性規(guī)劃設計：缺點：對于非線性規(guī)劃設計：運用連續(xù)運用連續(xù)二次形規(guī)劃二次形規(guī)劃(SQP - sequential quadratic programming)，線性的權值松弛在局部，線性的權值松弛在局部搜索范圍內，會導致拒絕可大幅改進總體搜索范圍內，會導致拒絕可大幅改進總體目標的小步搜索。目標的小步搜索。只針對連續(xù)問題，可只針對連續(xù)問題，可能只能給出局部最優(yōu)解。能只能給出局部最優(yōu)解。改進：閱讀改進：閱讀Matlab Optimization Toolb

38、ox 3.0.1 Users Guide中中Algorithm Improvements for Goal Attainment Method一節(jié)內容。一節(jié)內容。 1. 1. 變權系數(shù)法變權系數(shù)法 對于非負的權系數(shù)，若線性加權函數(shù)對于非負的權系數(shù)，若線性加權函數(shù)在線性加權法中，系列地改變權系數(shù)值，可獲得大量在線性加權法中，系列地改變權系數(shù)值，可獲得大量的非劣解，形成非劣解集。的非劣解，形成非劣解集。 第四節(jié)第四節(jié) 多目標優(yōu)化的第二類方法多目標優(yōu)化的第二類方法存在唯一的最優(yōu)解，則該最優(yōu)解是多目標問題的存在唯一的最優(yōu)解，則該最優(yōu)解是多目標問題的非劣解。非劣解。min()() s.t. ()01,2

39、, ()01,2, mllluvF Xw f XgXuph Xvq 2. 2. 約束法約束法 轉化為轉化為從多目標中依據(jù)重要程度選擇一個目標作為主目標，從多目標中依據(jù)重要程度選擇一個目標作為主目標，而將其它目標轉化為約束，即將多目標優(yōu)化問題而將其它目標轉化為約束，即將多目標優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01,2,TmuvF Xf XfXfXgXuph Xvqmin () s.t. ()01,2, ()01,2, ()1,2, kuvllfXgXuph Xvqf Xlm lk可以證明，對于一組可以證明，對于一組 值，值，若若X*為為 約束問題的約束問題的唯

40、一最優(yōu)解，則其一定為多目標問題的一個非劣唯一最優(yōu)解，則其一定為多目標問題的一個非劣解。解。通過系列地改變通過系列地改變 值值，可獲得大量的非劣解，形成非，可獲得大量的非劣解，形成非劣解集。劣解集。 值應大于值應大于各單目標函數(shù)的最優(yōu)值，可依據(jù)實際情況各單目標函數(shù)的最優(yōu)值，可依據(jù)實際情況在下列范圍中變化：在下列范圍中變化： 約束法有關說明約束法有關說明00(0.001 0.01) 1,2,jjjffjm jk 1. 1. 逐步法逐步法在迭代過程中，分析者向決策者不斷提供試驗解及在迭代過程中，分析者向決策者不斷提供試驗解及其相應的目標函數(shù)值，請決策者指出哪一個目標值其相應的目標函數(shù)值，請決策者指出

41、哪一個目標值可以增加，哪一個目標值應減少。分析者根據(jù)決策可以增加，哪一個目標值應減少。分析者根據(jù)決策者的意圖，增添新的約束，求得新的試驗解，進入者的意圖，增添新的約束，求得新的試驗解，進入下一步迭代。直到求出使決策者滿意的優(yōu)惠解。下一步迭代。直到求出使決策者滿意的優(yōu)惠解。逐步法逐步法(Step Method)是是1971年由年由Benayoun等人提出的等人提出的求解線性多目標優(yōu)化問題的一種交互式方法，此方法求解線性多目標優(yōu)化問題的一種交互式方法，此方法本質是在某種范數(shù)下求距理想點最近的點。本質是在某種范數(shù)下求距理想點最近的點。 第五節(jié)第五節(jié) 多目標優(yōu)化的第三類方法多目標優(yōu)化的第三類方法 對于

42、線性多目標優(yōu)化問題對于線性多目標優(yōu)化問題 定義定義1211min()(),(),() s.t. 1,2, 01,2, () 1,2, TmnuiiiiinjjiiiF Xf XfXfXa xbupxinfXc x jm其中12121,12 , max,mmwjjjjmmFfffPp ppFPwfpWw ww兩點和間的距離為 其中為給定非負的權系數(shù)。 逐步法的計算步驟逐步法的計算步驟 （1 1）建立支付表）建立支付表 min() ,1,2,jjfXXDXjm求解得每個單目標的極小點f1 f2 fm 1 2 m 11()f X12()fX1()mfX1()mf X2()mfX()mmfX21()f

43、 X22()fX2()mfX1,min(),1,2,ijjimmfXjm各列的最小值為，為理想點。(1)1,max(),1,2,;,12ijjimMfXjm DD k各列的最大值為轉（ ）。 （2 2）求第）求第k次迭代點次迭代點( )1,( )( ) min max() (),1,2,kjjjXjmkkjwfXmXDXfXjm求解得每個單目標的極小點和相應的目標函數(shù)值1/,1, 2,mjjllwjm這 里12211221,0,0mjjjljljjmjjjljljMmcMMmMcMm當其中 當 （3 3）與決策者對話）與決策者對話將目標函數(shù)值提供給決策者，若決策者對所有目標將目標函數(shù)值提供給決

44、策者，若決策者對所有目標值皆滿意，則獲得優(yōu)惠解，停止計算；若決策者對值皆滿意，則獲得優(yōu)惠解，停止計算；若決策者對所有目標值皆不滿意，則計算失敗，停止計算；若所有目標值皆不滿意，則計算失敗，停止計算；若決策者對部分目標值滿意，對部分目標值不滿意，決策者對部分目標值滿意，對部分目標值不滿意，則繼續(xù)計算。則繼續(xù)計算。在滿意的目標中選一個目標在滿意的目標中選一個目標fj*，并給出一個可以犧牲，并給出一個可以犧牲的量的量 fj*，意思是愿意讓，意思是愿意讓目標目標fj*增大增大 fj*，以換取，以換取其它其它不滿意目標值的減小。并進行如下計算：不滿意目標值的減小。并進行如下計算：*(1)( )( )(

45、)*(), (),1,2, kkkjjjkjjDXDffXfffXjm jj* 0,1,jkkkm令若此法失??；否則轉(2). 2. 2.代替價值交換法代替價值交換法代替價值交換法代替價值交換法(Surrogate Worth Trade-off Method)是是1971年由年由Haimes等人提出的求解非線性多目標優(yōu)化問等人提出的求解非線性多目標優(yōu)化問題的一種交互式方法。題的一種交互式方法。其其 約束問題為約束問題為對于多目標優(yōu)化問題對于多目標優(yōu)化問題12min()(),(),() s.t. ()01,2, ()01 ,2,TmuvF Xf XfXfXgXuph Xvqmin () s.t. ()01,2, ()01,2, ()1,2, kuvllfXgXuph Xvqf Xlm lk 約束問題的約束問題的K KT T條件條件 可以證明，約束目標函數(shù)對應的可以證明，約束目標函數(shù)對應的LagrangeLagrange乘子乘子pqmkjjuuvvjj kuvjjjjuuufXwfXgXh XwfX w jm jk gX up*1,*1()()()()02()001,2,3(