1、多目標(biāo)優(yōu)化方法 Multi-Objective Optimization,第一節(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í)期，并正式作為一個(gè)數(shù)學(xué)分支進(jìn)行系統(tǒng)的研究，是上世紀(jì)七十年代以后的事。,現(xiàn)在，對多目標(biāo)規(guī)劃方面的研究集中在以下幾個(gè)方面: 一、關(guān)于解的概念及其性質(zhì)的研究， 二、關(guān)于多目標(biāo)規(guī)劃的解法研究， 三、對偶問題的研究， 四、不可微多目標(biāo)規(guī)劃的研究， 五、多目標(biāo)規(guī)劃的應(yīng)用研究。,

2、到現(xiàn)在為止，多目標(biāo)優(yōu)化不僅在理論上取得許多重要成果，而且在應(yīng)用上其范圍也越來越廣泛，多目標(biāo)決策作為一個(gè)工具在解決工程技術(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需制造工時(shí)和裝配工時(shí)分別為1時(shí)和1.25時(shí)，每件產(chǎn)品B需制造工時(shí)和裝配工時(shí)分別為1時(shí)和0.75時(shí)，每月制造車間和裝配車間能夠提供的最多工時(shí)為200時(shí)，另外，每月市場對產(chǎn)品A需求量很大，而對產(chǎn)品B的最大需求量為150件，產(chǎn)品A和產(chǎn)品B的售價(jià)分別為4元和5元，問如何安排每月的生產(chǎn)，最大限度的滿足市場需求，并產(chǎn)值最大？,多目

3、標(biāo)優(yōu)化設(shè)計(jì)模型,示例2：如圖所示，設(shè)計(jì)一苦空心階梯懸臂梁，根據(jù)結(jié)構(gòu)要求，已確定梁的總長為1000mm，第一段外徑為80mm，第二段外經(jīng)為100mm，梁的端部受有集中力F12000N，梁的內(nèi)徑不得小于40mm，梁的許用彎曲應(yīng)力為180MPa，確定梁的內(nèi)徑和各段長度，使梁的體積和靜撓度最小。,多目標(biāo)優(yōu)化設(shè)計(jì)模型,在單目標(biāo)優(yōu)化問題中，任何兩個(gè)解都可以比較出其優(yōu)劣，這是因?yàn)閱文繕?biāo)優(yōu)化問題是完全有序的；而在多目標(biāo)優(yōu)化設(shè)計(jì)中，任何兩個(gè)解不一定都可以比較出其優(yōu)劣，這是因?yàn)槎嗄繕?biāo)優(yōu)化問題是半有序的。,2. 多目標(biāo)優(yōu)化問題解的特點(diǎn),第一類：轉(zhuǎn)化法。這類多目標(biāo)最優(yōu)化方法的基本思想是將多目標(biāo)問題轉(zhuǎn)化為一個(gè)或一系列的

4、單目標(biāo)優(yōu)化問題，通過求解一個(gè)或一系列單目標(biāo)優(yōu)化問題來完成多目標(biāo)優(yōu)化問題的求解。,3. 多目標(biāo)優(yōu)化方法分類,第二類：非劣解集法。這類多目標(biāo)最優(yōu)化方法的基本思想是求得多目標(biāo)問題的非劣解集，然后在非劣解集中進(jìn)行協(xié)調(diào)和選擇，確定出優(yōu)惠解。,第三類：交互協(xié)調(diào)法。這類多目標(biāo)最優(yōu)化方法的基本思想是通過在分析者與抉擇者間的不斷交互，逐漸搞清抉擇者的選擇意圖，獲得多目標(biāo)問題的優(yōu)惠解。,第二節(jié) 多目標(biāo)優(yōu)化設(shè)計(jì)理論,1. 多目標(biāo)優(yōu)化設(shè)計(jì)模型,簡記為,VOP,多目標(biāo)優(yōu)化問題(Multi-Objective Optimization Problem)又稱為向量優(yōu)化問題(Vector Optimization Probl

5、em) 。,2. 決策空間與目標(biāo)空間,以設(shè)計(jì)變量為坐標(biāo)的實(shí)空間Rn稱為決策空間。,以目標(biāo)函數(shù)為坐標(biāo)的實(shí)空間Rm稱為目標(biāo)空間。,決策空間可行域：,目標(biāo)空間可行域,示例1,示例2,3. 解的定義,（1） 理想解(ideal solution),在目標(biāo)空間內(nèi)，以單目標(biāo)最小值為分量而形成的點(diǎn)，稱為多目標(biāo)問題的理想解。,在多目標(biāo)優(yōu)化問題中，由于各個(gè)目標(biāo)間往往是矛盾的，所以一般不存在使各目標(biāo)皆達(dá)到各自最優(yōu)值的理想解。,（2） 非劣解（Noninferior Solution）或 Pareto 解,對于可行點(diǎn)XPD，若不存在另一個(gè)可行點(diǎn)XD，使,成立，則稱Xp為多目標(biāo)問題的非劣解。,向量不等式的含義為,（3

6、） 滿意解（最佳協(xié)調(diào)解或優(yōu)惠解）,效用函數(shù)值的大小反映決策者對多目標(biāo)值的喜愛程度，一般來說，決策者希望效用函數(shù)的值越大越好。,效用函數(shù)：,決策者對多目標(biāo)函數(shù)優(yōu)化解進(jìn)行評價(jià)的函數(shù)，記為,使效用函數(shù)取最大值的非劣解稱為最佳協(xié)調(diào)解。,對于效用函數(shù)未知的情況，無法直接求得最佳協(xié)調(diào)解。我們把多目標(biāo)優(yōu)化過程滿意結(jié)束的解稱為優(yōu)惠解。,4 多目標(biāo)優(yōu)化問題的KT條件,對于多目標(biāo)優(yōu)化問題,VOP,1. 主目標(biāo)法,轉(zhuǎn)化為,第三節(jié) 多目標(biāo)優(yōu)化的第一類方法,主目標(biāo)法就是從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)作為主目標(biāo)，而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)優(yōu)化問題,主目標(biāo)法中約束目標(biāo)的約束值選取,2. 線性加權(quán)法,轉(zhuǎn)化為,線性

7、加權(quán)法就是將多目標(biāo)的加權(quán)和作為單目標(biāo)，即將多目標(biāo)優(yōu)化問題,(2）對權(quán)系數(shù)的要求,(3) 權(quán)系數(shù)的確定,老手法,線性加權(quán)法的有關(guān)說明：,（1) 線性加權(quán)之前，各目標(biāo)應(yīng)進(jìn)行無量綱化處理。,3. 極小極大法,轉(zhuǎn)化為,極小極大法就是求取多目標(biāo)函數(shù)中的最大值，然后使最大值函數(shù)在可行域內(nèi)極小化，即將多目標(biāo)優(yōu)化問題,(2)極小極大法也可以引入一個(gè)變量和m個(gè)約束，即,極小極大法的有關(guān)說明：,（1) 考慮到各目標(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)說明：,考慮到各目標(biāo)的重要

8、程度差別，可以對各目標(biāo)乘以權(quán)系數(shù)，即,權(quán)系數(shù)的選取可以參閱線性加權(quán)法。,5. 功效系數(shù)法,在多目標(biāo)優(yōu)化問題，各目標(biāo)的要求不全相同，有的要求極小化，有的要求極大化，有的要求有一個(gè)合適的數(shù)值。為了反映這些不同的要求，故引入如下的功效函數(shù)：,功效系數(shù)的確定：,1.直線法,2.折線法,3.指數(shù)法,6. 分層序列法,將多目標(biāo)優(yōu)化問題的各目標(biāo)分清主次，按其重要程度逐一排序，然后依次對各目標(biāo)函數(shù)求最優(yōu)解，但應(yīng)注意后一目標(biāo)應(yīng)在前一目標(biāo)的最優(yōu)解域內(nèi)進(jìn)行尋優(yōu)。,照此繼續(xù)下去，最后求得第m個(gè)目標(biāo)函數(shù)得最優(yōu)解，真?zhèn)€解即為多目標(biāo)優(yōu)化問題的最終解。,在分層序列法中，當(dāng)前面有某個(gè)目標(biāo)函數(shù)的最優(yōu)解唯一時(shí)，該方法就發(fā)生中斷現(xiàn)象

9、，因此需要引入目標(biāo)容差。,7. 協(xié)調(diào)曲線法,協(xié)調(diào)曲線法主要用于求解兩個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化設(shè)計(jì)問題。,1. 變權(quán)系數(shù)法,對于非負(fù)的權(quán)系數(shù)，若線性加權(quán)函數(shù),在線性加權(quán)法中，系列地改變權(quán)系數(shù)值，可獲得大量的非劣解，形成非劣解集。,第四節(jié) 多目標(biāo)優(yōu)化的第二類方法,存在唯一的最優(yōu)解，則該最優(yōu)解是多目標(biāo)問題的非劣解。,2. 約束法,轉(zhuǎn)化為,從多目標(biāo)中依據(jù)重要程度選擇一個(gè)目標(biāo)作為主目標(biāo)，而將其它目標(biāo)轉(zhuǎn)化為約束，即將多目標(biāo)優(yōu)化問題,可以證明，對于一組值，若X*為約束問題的唯一最優(yōu)解，則其一定為多目標(biāo)問題的一個(gè)非劣解。,通過系列地改變值，可獲得大量的非劣解，形成非劣解集。,值應(yīng)大于各單目標(biāo)函數(shù)的最優(yōu)值，可依據(jù)

10、實(shí)際情況在下列范圍中變化：,約束法有關(guān)說明,1. 逐步法,在迭代過程中，分析者向決策者不斷提供試驗(yàn)解及其相應(yīng)的目標(biāo)函數(shù)值，請決策者指出哪一個(gè)目標(biāo)值可以增加，哪一個(gè)目標(biāo)值應(yīng)減少。分析者根據(jù)決策者的意圖，增添新的約束，求得新的試驗(yàn)解，進(jìn)入下一步迭代。直到求出使決策者滿意的優(yōu)惠解。,逐步法(Step Method)是1971年由Benayoun等人提出的求解線性多目標(biāo)優(yōu)化問題的一種交互式方法，此方法本質(zhì)是在某種范數(shù)下求距理想點(diǎn)最近的點(diǎn)。,第五節(jié) 多目標(biāo)優(yōu)化的第三類方法,對于線性多目標(biāo)優(yōu)化問題,定義,逐步法的計(jì)算步驟,（1）建立支付表,（2）求第k次迭代點(diǎn),（3）與決策者對話,將目標(biāo)函數(shù)值提供給決策者

11、，若決策者對所有目標(biāo)值皆滿意，則獲得優(yōu)惠解，停止計(jì)算；若決策者對所有目標(biāo)值皆不滿意，則計(jì)算失敗，停止計(jì)算；若決策者對部分目標(biāo)值滿意，對部分目標(biāo)值不滿意，則繼續(xù)計(jì)算。,在滿意的目標(biāo)中選一個(gè)目標(biāo)fj*，并給出一個(gè)可以犧牲的量fj*，意思是愿意讓目標(biāo)fj*增大fj*，以換取其它不滿意目標(biāo)值的減小。并進(jìn)行如下計(jì)算：,2.代替價(jià)值交換法,代替價(jià)值交換法(Surrogate Worth Trade-off Method)是1971年由Haimes等人提出的求解非線性多目標(biāo)優(yōu)化問題的一種交互式方法。,其約束問題為,對于多目標(biāo)優(yōu)化問題,約束問題的KT條件,可以證明，約束目標(biāo)函數(shù)對應(yīng)的Lagrange乘子,即約

12、束目標(biāo)函數(shù)對應(yīng)的Lagrange乘子wj是目標(biāo)fk對目標(biāo)fj的交換率。,分析者與決策者的交互,分析者求得一個(gè)非劣解（即約束問題的最優(yōu)解）X(k)，及其對應(yīng)的所有目標(biāo)函數(shù)值與約束目標(biāo)函數(shù)對應(yīng)的Lagrange乘子wj，向決策者提問：,在目標(biāo)值f1(X(k), fm(X(k)時(shí)，你愿意在其它目標(biāo)值保持不變的條件下，以目標(biāo)fj增大一個(gè)單位量，而換取目標(biāo)fj減小wj單位量嗎？,決策者通過給代替價(jià)值函數(shù)Skj賦值，回答上述問題。代替價(jià)值函數(shù)Skj賦值規(guī)律如下：,（1）若決策者同意上述交換，應(yīng)給Skj賦正值，其值越大表示越贊成； （2）若決策者同意反向交換，即贊成以目標(biāo)fj減小一個(gè)單位量，而換取目標(biāo)fj增大wj單位量，應(yīng)給Skj賦負(fù)值，其絕對值越大表示越贊成； （3）若決策者對上述兩種交換都不贊成，應(yīng)給Skj賦零值。,代替價(jià)值函數(shù)Skj賦值規(guī)律,Skj取值范圍是10到10之間的整數(shù)，其取值含義為：,代替價(jià)值交換法的計(jì)算步驟,（1）求各目標(biāo)的極大值和極小值,（2）求非劣解,得最優(yōu)解和約束目標(biāo)函數(shù)對應(yīng)的乘子。,求約束問