第二部分多目標優化方法

Multi-ObjectiveOptimization第一節概述第三節多目標優化的第一類方法第二節多目標優化設計理論第四節多目標優化的第二類方法第五節多目標優化的第三類方法國際上通常認為多目標最優化問題最早是在1886年由法國經濟學家Pareto從政治經濟學的角度提出的。多目標規劃的真正發達時期，并正式作為一個數學分支進行系統的研究，是上世紀七十年代以后的事。現在，對多目標規劃方面的研究集中在以下幾個方面:一、關于解的概念及其性質的研究，二、關于多目標規劃的解法研究，三、對偶問題的研究，四、不可微多目標規劃的研究，五、多目標規劃的應用研究。到現在為止，多目標優化不僅在理論上取得許多重要成果，而且在應用上其范圍也越來越廣泛，多目標決策作為一個工具在解決工程技術、經濟、管理、軍事和系統工程等眾多方面的問題也越來越顯示出它強大的生命力。第一節概述1.多目標優化設計示例示例1：某工廠生產兩種產品A和B,每件產品A需制造工時和裝配工時分別為1時和1.25時，每件產品B需制造工時和裝配工時分別為1時和0.75時，每月制造車間和裝配車間能夠提供的最多工時為200時，另外，每月市場對產品A需求量很大，而對產品B的最大需求量為150件，產品A和產品B的售價分別為4元和5元，問如何安排每月的生產，最大限度的滿足市場需求，并產值最大？示例2.用直徑為1(單位長)的圓木制成截面為矩形的梁,為使重量最輕,而強度最大,問截面的高與寬應取何尺寸?解:設矩形截面的高與寬分別為和,這時梁的面積為,它決定重量,而梁的強度取決于截面形。因此,容易列出梁的數學模型:示例3物資調運問題:某種物資寸放三個倉庫里,存放量分別為(單位:t);現要將這些物資運往四個銷售點。其需要量分別為且，已知到的距離和單位運價分別為(km)和(元),現要決定如何調運多少,才能使總的噸,公里數和總運費都盡量少?解:設變量表示由運往的貨物數,于是總噸公里數為,總運費為,問題優化設計模型為示例4：如圖所示，設計一苦空心階梯懸臂梁，根據結構要求，已確定梁的總長為1000mm，第一段外徑為80mm，第二段外經為100mm，梁的端部受有集中力F＝12000N，梁的內徑不得小于40mm，梁的許用彎曲應力為180MPa，確定梁的內徑和各段長度，使梁的體積和靜撓度最小。12D1=100D2=80L=1000x1x2F多目標優化設計模型

多目標最優化問題的一般形式為:S.t.或者記作:minD=其中:=()

2.多目標優化設計模型注意，這里以及之后的所有講述同時適合于線性和非線性的多目標優化多目標優化設計幾何描述在單目標標優化問問題中，，任何兩兩個解都都可以比比較出其其優劣，，這是因因為單目目標優化化問題是是完全有有序的；；而在多多目標優優化設計計中，任任何兩個個解不一一定都可可以比較較出其優優劣，這這是因為為多目標標優化問問題是半半有序的的。3.多多目標優優化問題題解的特特點213第一類：：轉化法法。這類類多目標標最優化化方法的的基本思思想是將將多目標標問題轉轉化為一一個或一一系列的的單目標標優化問問題，通通過求解解一個或或一系列列單目標標優化問問題來完完成多目目標優化化問題的的求解。。4.多多目標優優化方法法分類第二類：：非劣解解集法。。這類多多目標最最優化方方法的基基本思想想是求得得多目標標問題的的非劣解解集，然然后在非非劣解集集中進行行協調和和選擇，，確定出出優惠解解。第三類：：交互協協調法。。這類多多目標最最優化方方法的基基本思想想是通過過在分析析者與抉抉擇者間間的不斷斷交互，，逐漸搞搞清抉擇擇者的選選擇意圖圖，獲得得多目標標問題的的優惠解解。第二節多多目目標優化化設計理理論1.多多目標優優化設計計模型簡記為VOP多目標優優化問題題(Multi-ObjectiveOptimizationProblem)又稱為為向量優優化問題題(VectorOptimizationProblem)。2.決決策空間間與目標標空間以設計變變量為坐坐標的實實空間Rn稱為決策策空間。。以目標函函數為坐坐標的實實空間Rm稱為目標標空間。。決策空間間可行域域：目標空間間可行域域示例1決策空間可行域目標空間可行域示例2決策策空空間間可可行行域域目標標空空間間可可行行域域3.解解的的定定義義（1））理理想想解解(idealsolution)在目目標標空空間間內內，，以以單單目目標標最最小小值值為為分分量量而而形形成成的的點點，，稱稱為為多多目目標標問問題題的的理理想想解解。在多多目目標標優優化化問問題題中中，，由由于于各各個個目目標標間間往往往往是是矛矛盾盾的的，，所所以以一一般般不不存存在在使使各各目目標標皆皆達達到到各各自自最最優優值值的的理理想想解解。fxX(0)f1(0)f2(0)f1f2（2））非非劣劣解解（（NoninferiorSolution）或或Pareto解對于于可可行行點點XPD，，若不不存在在另另一一個個可可行行點點XD，使成立立，，則則稱稱Xp為多多目目標標問問題題的的非非劣劣解解。。向量量不不等等式式的的含含義義為為決策空間非劣解集目標空間非劣解集7.1模模型型舉舉例例例7.1.用用直直徑徑為為1(單單位位長長)的的圓圓木木制制成成截截面面為為矩矩形形的的梁梁,為為使使重重量量最最輕輕,而而強強度度最最大大,問問截截面面的的高高與與寬寬應應取取何何尺尺寸寸?解:設設矩矩形形截截面面的的高高與與寬寬分分別別為為和和,這這時時梁梁的的面面積積為為,它它決決定定重重量量,而而梁梁的的重重量量取取決決于于截截面面矩矩形形。。因此此,容容易易列列出出梁的的數數學學模模型型:例7.2物資資調調運運問問題題:某種種物物資資寸寸放放三三個個倉倉庫庫里里,存存放放量量分分別別為為(單單位位:t);現現要要將將這這些些物物資資運運往往四四個個銷銷售售點點.其其需需要要量量分分別別為為且，，已已知知到到的的距距離離和和單單位位運運價價分分別別為為(km)和和(元元),現現要要決決定定如如何何調調運運多多少少,才才能能使使總總的的噸噸,公公里里數數和和總總運運費費都都盡盡量量少少?解:設設變變量量表表示示由由運運往往的的貨貨物物數數,于于是是總總噸噸公公里里數數為為,總總運運費費為為,問問題題優優化化為為求求解解由于于求求最最大大都都可可以以轉轉化化為為求求最最小小,所所以以多多目目標標最最優優化化問問題題的的一一般般形形式式為為:S.t.或者者記記作作:minD=其中中:=()當P=1時時,(VP)就就是是非非線線性性規規劃劃,稱稱為為單單目目標標規規劃劃。。對于于單單目目標標問問題題Min,總總可可比比較較與的的大大小小.對于多目標標規劃(VP),對對于，，與與都都是P維向向量,如何何比較兩個個向量的大大小?可以看到：：多目標優化化的非劣解解集

Noninferiorsolutionforthemodel例如：A,B點屬于于非劣解，，因為不滿足定義義條件②（3）滿滿意解（最最佳協調解解或優惠解）效用函數值值的大小反反映決策者者對多目標標值的喜愛愛程度，一一般來說，，決策者希希望效用函函數的值越越大越好。。效用函數：：決策者對多多目標函數數優化解進進行評價的的函數，記記為使效用函數數取最大值值的非劣解解稱為最佳佳協調解。。對于效用函函數未知的的情況，無無法直接求求得最佳協協調解。我我們把多目目標優化過過程滿意結結束的解稱稱為優惠解解。滿意解4多目目標優化問問題的K－－T條件對于多目標標優化問題題VOP7.4求求解多多目標規劃劃的評價函函數法盡管多目標標優化問題題有各種意意義下的最最優解.但但在應用中中,需要的的還是有效效解和弱有有效解.本本節介紹求求有效解和和弱有效解解最基本的的方法-----評評價函數法法.評價函數法法的基本思思想是:借借助于幾何何或應用中中的直觀效效果.構造造所謂的評評價函數.從而將多多目標優化化問題轉化化為單目標標優化問題題.然后利利用單目標標優化問題題的求解方方法求出最最優解.并并把這種最最優解當作作多目標優優化問題的的最優解.這里關鍵鍵的問題是是轉化后的的單目標優優化問題的的最優解必必須是多目目標問題的的有效解和和弱有效解解.否則是是不能接受受的.所謂評價函函數,是利利用(VP)的目標標函數,構造造一個復合合函數.然后在(VP)的的約束集D上極小化化,的的構造必須須保證在一一定條件下下,min的的最優解解是(VP)的有效效解或弱有有效解.下面先討論論在什么條條件下,min的的最優解解才能是(VP)min的的有效效解or弱弱有效解.定義6.設設:1.若,總有,則稱稱為為的的嚴格格單增函數數.2若時時,總總有,則稱為為的的單單增函數.定理1.設：：:,又設，，是問問題min的的極小點,那么:若為為Z的嚴嚴格單增函函數,則是是min有有效效解.若為為Z的單單增函數,則是是min的的弱弱有效解.重要定理幾種常用的的構造評價價函數的方方法一.理理想點法:在(VP)中,先求求解P個單單目標問題題j=1，2，，px∈D設其最優值值為,我我們稱為值域中的的一個理想想點。因為一般很很難達到它它,這樣,就期望在在某種等量量下,尋求求距最近的的f作為近近似值,一一種最直接接的想法是是構造評價價函數=（7.2））然后極小化化即求解：：并將它的最最優解作作為為(VP)在這種意意義下的“最優解””,由于,因此由由7.2構構造的是嚴格單增增的,從而而是是(VP)的有效解解.二.線線性加權和和法.在具有多個個指標的問問題中,人人們總希望望對那些相對重要要的指標給給予較大的的權系數,基于這種種現實,自然然如下的構構造評價函函數,令稱之為權向向量集,令令再求解而將它的最最優解,作作為(VP)在該意意義下的最最優解.三.極大大極小法在決策時，，采取保守守策略是穩穩妥的。即即在最壞的的情況下，，尋求最好好的結果。。按照這種種想法，可可以構造如如下評價函函數然后求解并將它的最最優解作作為為（VP））在這種意意義下的最最優解。1.主目目標法轉化為第三節多多目標優優化的第一一類方法主目標法就就是從多目目標中依據據重要程度度選擇一個個目標作為為主目標，，而將其它它目標轉化化為約束，，即將多目目標優化問問題主目標法中中約束目標標的約束值值選取2.線性性加權法轉化為線性加權法法就是將多多目標的加加權和作為為單目標，，即將多目目標優化問問題(2）對權權系數的要要求(3)權權系數的確確定老手法線性加權權法的有有關說明明：（1)線線性加加權之前前，各目目標應進進行無量量綱化處處理。3.極極小極大大法轉化為極小極大大法就是是求取多多目標函函數中的的最大值值，然后后使最大大值函數數在可行行域內極極小化，，即將多多目標優優化問題題(2)極極小極大大法也可可以引入入一個變變量和m個約束，，即極小極大大法的有有關說明明：（1)考考慮到到各目標標的重要要程度差差別，可可以對各各目標乘乘以權系系數，然然后再求求最大值值函數，，即4.理理想點法法轉化為理想點法法就是將將距理想想點最近近的點作作為多目目標問題題的優惠惠解，即即將多目目標優化化問題理想點法法的有關關說明：：考慮到各各目標的的重要程程度差別別，可以以對各目目標乘以以權系數數，即權系數的的選取可可以參閱閱線性加加權法。。5.功功效系數數法在多目標標優化問問題，各各目標的的要求不不全相同同，有的的要求極極小化，，有的要要求極大大化，有有的要求求有一個個合適的的數值。。為了反反映這些些不同的的要求，，故引入入如下的的功效函函數：功效系數數的確定定：1.直線線法2.折線線法3.指數數法6.分分層序列列法將多目標標優化問問題的各各目標分分清主次次，按其其重要程程度逐一一排序，，然后依依次對各各目標函函數求最最優解，，但應注注意后一一目標應應在前一一目標的的最優解解域內進進行尋優優。照此繼續續下去，，最后求求得第m個目標標函數得得最優解解，真個個解即為為多目標標優化問問題的最最終解。。在分層序序列法中中，當前前面有某某個目標標函數的的最優解解唯一時時，該方方法就發發生中斷斷現象，，因此需需要引入入目標容容差。7.協協調曲線線法協調曲線線法主要要用于求求解兩個個目標函函數的多多目標優優化設計計問題。。目標規劃劃法GoalAttainmentMethod引入目標標概念：：F*，令非劣劣解集到到目標的的距離（（或稱范范數）最最小，選選出一個個非劣解解。Wiγ引入了一一個松弛弛度的概概念，松松弛度最最小的一一個非劣劣解就是是對于目目標F*的最可行行解。優點：不不漏解，，目標明明確，計計算量小小。缺點：對對于非線線性規劃劃設計：：①運用連續續二次形形規劃(SQP-sequentialquadraticprogramming)，線性性的權值值松弛在在局部搜搜索范圍圍內，會會導致拒拒絕可大大幅改進進總體目目標的小小步搜索索。②只針對對連續問問題，可可能只能能給出局局部最優優解。改進：閱閱讀MatlabOptimizationToolbox3.0.1User‘sGuide中中AlgorithmImprovementsforGoalAttainmentMethod一節節內容。。1.變變權系數數法對于非負負的權系系數，若若線性加加權函數數在線性加加權法中中，系列列地改變變權系數數值，可可獲得大大量的非非劣解，，形成非非劣解集集。第四節多多目目標優化化的第二二類方法法存在唯一一的最優優解，則則該最優優解是多多目標問問題的非非劣解。。2.－約束法轉化為從多目標標中依據據重要程程度選擇擇一個目目標作為為主目標標，而將將其它目目標轉化化為約束束，即將將多目標標優化問問題可以證明明，對于于一組值，若X*為－約束問題題的唯一一最優解解，則其其一定為為多目標標問題的的一個非非劣解。。通過系列列地改變變值，可獲得得大量的的非劣解解，形成成非劣解解集。值應大大于各單目標標函數的的最優值值，可依依據實際際情況在在下列范范圍中變變化：－約束法有有關說明明1.逐逐步法在迭代過過程中，，分析者者向決策策者不斷斷提供試試驗解及及其相應應的目標標函數值值，請決決策者指指出哪一一個目標標值可以以增加，，哪一個個目標值值應減少少。分析析者根據據決策者者的意圖圖，增添添新的約約束，求求得新的的試驗解解，進入入下一步步迭代。。直到求求出使決決策者滿滿意的優優惠解。。逐步法(StepMethod)是1971年年由Benayoun等人提提出的求求解線性性多目標標優化問問題的一一種交互互式方法法，此方方法本質質是在某某種范數數下求距距理想點點最近的的點。第五節多多目目標優化化的第三三類方法法對于線性性多目標標優化問問題定義逐步法的的計算步步驟（1）建建立支付付表f1f2…fm1

2

m

……（2）求求第k次迭代點點（3）與與決策者者對話將目標函函數值提提供給決決策者，，若決策策者對所所有目標標值皆滿滿意，則則獲得優優惠解，，停止計計算；若若決策者者對所有有目標值值皆不滿滿意，則則計算失失敗，停停止計算算；若決決策者對對部分目目標值滿滿意，對對部分目目標值不不滿意，，則繼續續計算。。在滿意的的目標中中選一個個目標fj*，并給出出一個可可以犧牲牲的量fj*，意思是是愿意讓讓目標fj*增大fj*，以換取取其它不滿滿意目標標值的減減小。并并進行如如下計算算：2.代替替價值交交換法代替價值值交換法法(SurrogateWorthTrade-offMethod)是1971年年由Haimes等人人提出的的求解非非線性多多目標優優化問題題的一種種交互式式方法。。其－約束問題題為對于多目目標優化化問題－約束問題題的K－－T條件件可以證明明，約束束目標函函數對應應的Lagrange乘子即約束目目標函數數對應的的Lagrange乘乘子wj是目標fk對目標fj的交換率率。分析者與與決策者者的交互互分析者求求得一個個非劣解解（即－約束問題題的最優優解）X(k