多目標(biāo)優(yōu)化方法

第二部分多目標(biāo)優(yōu)化方法

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

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

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

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

2

m

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