離散變量的最優(yōu)化方法

關(guān)于離散變量的最優(yōu)化方法

鋼絲直徑、鋼板厚度、型鋼的型號也都應(yīng)符合金屬材料的供應(yīng)規(guī)范等等

在許多工程問題中，設(shè)計變量實際上不是連續(xù)變化的。

8.1引言齒輪的齒數(shù)只能是正整數(shù)．是整型變量；齒輪的模數(shù)應(yīng)按標(biāo)準(zhǔn)系列取用；

屬于這樣的一些必須取離散數(shù)值的設(shè)計變量均稱為離散變量。

第2頁,共43頁，2024年2月25日，星期天一、變量類型

工程實際問題中不是單一的連續(xù)變量，經(jīng)常是各種類型變量的混合。有：連續(xù)變量確定型整型變量離散變量隨機變量不確定型混合變量所以需要相應(yīng)的優(yōu)化方法。

8.1引言（續(xù)）第3頁,共43頁，2024年2月25日，星期天二、工程實際設(shè)計的需要例：決定修建一條防洪堤壩。根據(jù)歷年的水文資料，臺風(fēng)的年最大風(fēng)速：8.1引言（續(xù)）服從正態(tài)分布第4頁,共43頁，2024年2月25日，星期天

現(xiàn)在需要設(shè)計堤壩的截面尺寸

b

和h，在保證不受災(zāi)害的概率不低于99.9%，堤壩不受沖壓損壞的概率不低于99.0%

的要求下，使投資最小。8.1引言（續(xù)）第5頁,共43頁，2024年2月25日，星期天三、傳統(tǒng)方法的局限性

求離散問題的最優(yōu)解，傳統(tǒng)的方法是先用連續(xù)變量優(yōu)化設(shè)計方法求連續(xù)變量的最優(yōu)解，然后圓整到離散值上。弊?。嚎赡艿貌坏娇尚凶顑?yōu)解，或所得的解不是離散最優(yōu)解。8.1引言（續(xù)）第6頁,共43頁，2024年2月25日，星期天●x*●X(1)●X(2)●X(3)x(3)是離散最優(yōu)點。x10x28.1引言（續(xù)）

x*是連續(xù)變量的最優(yōu)點；x(1)是圓整后最近的離散點，但不可行；x(2)是最近的可行離散點，但不是離散最優(yōu)點；第7頁,共43頁，2024年2月25日，星期天一、離散設(shè)計空間1、一維離散設(shè)計空間qij-1

●qij

●qij+1

●Xi§7.2

離散變量優(yōu)化設(shè)計的基本概念

在一條表示變量的坐標(biāo)軸上的一些間隔點的集合，這些點的集合稱為離散設(shè)計空間；這些點的坐標(biāo)值是該變量可取的離散值，這些點稱為一維離散設(shè)計空間的離散點。

第8頁,共43頁，2024年2月25日，星期天

二維連續(xù)設(shè)計變量的設(shè)計空間是代表該兩個變量的兩條坐標(biāo)軸形成的平面；

這些點的坐標(biāo)值分別離散變量可取的離散值．稱為二維離散設(shè)計空間的離散點，二維離散設(shè)計空間則是上述平面上的某些點的集合；§7.2離散變量優(yōu)化設(shè)計的基本概念（續(xù)）2、二維離散設(shè)計空間第9頁,共43頁，2024年2月25日，星期天§7.2離散變量優(yōu)化設(shè)計的基本概念（續(xù)）

這些交點就是三維離散設(shè)計空間中的離散點。

對于三維離散變量，過每個變量離散值作該變量坐標(biāo)軸的垂直面．這些平面的交點的集合就是三維離散設(shè)計空間。3、三維離散設(shè)計空間第10頁,共43頁，2024年2月25日，星期天P個離散設(shè)計變量組成P維離散設(shè)計空間?！?.2

離散變量優(yōu)化設(shè)計的基本概念（續(xù)）4、P維離散設(shè)計空間

對于p維離散變量，過每個變量離散值作該變量坐標(biāo)軸的垂直面，這些超平面的交點的集合就是p維離散設(shè)計空間，用表示。而這些交點就是p維離散設(shè)計空間中的離散點，用表示。

第11頁,共43頁，2024年2月25日，星期天注：①因為離散變量是有限個,所以離散空間是有界的。②某個離散變量的取值不足l個，其余值可用預(yù)先規(guī)定的自然數(shù)補齊?！?.2

離散變量優(yōu)化設(shè)計的基本概念（續(xù)）p個離散變量全部可取的離散值的集合稱為p維離散變量的值域，可用一個p*l階的矩陣Q來表示l為各離散設(shè)計變量可取離散值個數(shù)中的最大值第12頁,共43頁，2024年2月25日，星期天§7.2

離散變量優(yōu)化設(shè)計的基本概念(續(xù)）4、N-P維連續(xù)設(shè)計空間

N個設(shè)計變量中有P個離散變量，此外有N-P個連續(xù)變量。N-P維連續(xù)設(shè)計空間第13頁,共43頁，2024年2月25日，星期天§7.2

離散變量優(yōu)化設(shè)計的基本概念(續(xù)）4、N維設(shè)計空間若Rp為空集時，Rn為全連續(xù)變量設(shè)計問題；若Rn-p為空集時，Rn為全離散變量設(shè)計問題。

其中：離散設(shè)計空間為

連續(xù)設(shè)計空間為第14頁,共43頁，2024年2月25日，星期天

在機械優(yōu)化設(shè)計中．常見的約束非線性離散變量最優(yōu)化問題的數(shù)學(xué)模型為：§7.2

離散變量優(yōu)化設(shè)計的基本概念(續(xù)）N—設(shè)計變量維數(shù)；m—不等式約束條件個數(shù)P—離散變量的個數(shù)；XD—離散子空間；RD—離散變量子集；XC—連續(xù)子空間；RC—連續(xù)變量子集；第15頁,共43頁，2024年2月25日，星期天§7.2

離散變量優(yōu)化設(shè)計的基本概念(續(xù)）1、整型變量的離散

整型變量可看作為是離散間隔恒定為1的離散變量。是離散變量的特例。2、連續(xù)變量的離散化有時為了提高優(yōu)化設(shè)計計算效率，將連續(xù)變量轉(zhuǎn)化為擬離散變量。二、非均勻離散變量和連續(xù)變量的均勻離散化處理第16頁,共43頁，2024年2月25日，星期天§7.2

離散變量優(yōu)化設(shè)計的基本概念（續(xù)）3、連續(xù)變量離散化的方法第17頁,共43頁，2024年2月25日，星期天

由于離散設(shè)計空間的不連續(xù)性，離散變量最優(yōu)點與連續(xù)變量最優(yōu)點不是同一概念，必須重新定義。1．離散單位鄰域（UN(X))7.3

離散最優(yōu)解

在設(shè)計空間中，離散點X的單位鄰域UN(X)是指如下定義的集合。第18頁,共43頁，2024年2月25日，星期天圖示為二維設(shè)計空間中離散點X的離散單位鄰域7.3

離散最優(yōu)解（續(xù)）

一般情況下，設(shè)離散變量的維數(shù)為p，則UN(X)內(nèi)的離散點總數(shù)為N=3p(p次方）

x●

B●●GD●E●A●●FC●●

Hεiεi0x2第19頁,共43頁，2024年2月25日，星期天7.3

離散最優(yōu)解（續(xù)）

2、離散坐標(biāo)鄰域（UC(X))

在設(shè)計空間中離散點X的離散坐標(biāo)鄰域UC(X)是指以X點為原點的坐標(biāo)軸線和離散單位鄰域UN（X）的交點的集合。圖示離散坐標(biāo)鄰域為：

一般在p維離散變量情況下離散坐標(biāo)鄰域的離散點總數(shù)為N=2p+1。第20頁,共43頁，2024年2月25日，星期天3．離散局部最優(yōu)解7.3

離散最優(yōu)解（續(xù)）若，對所有恒有則稱X*是離散局部最優(yōu)點4、擬離散局部最優(yōu)解若，對所有恒有則稱X*是擬離散局部最優(yōu)點5、離散全域最優(yōu)解若，對所有恒有則稱X**是離散全域最優(yōu)點第21頁,共43頁，2024年2月25日，星期天

嚴(yán)格說來，離散優(yōu)化問題的最優(yōu)解應(yīng)是指離散全域最優(yōu)點而言，但它與一般的非線性優(yōu)化問題一樣，離散優(yōu)化方法所求得的最優(yōu)點一般是局部最優(yōu)點，這樣通常所說的最優(yōu)解均指局部最優(yōu)解。7.3

離散最優(yōu)解（續(xù)）第22頁,共43頁，2024年2月25日，星期天三、收斂準(zhǔn)則

設(shè)當(dāng)前搜索到的最好點為x(k)，需要判斷其是否收斂。在x(k)的單位鄰域中查3n–1個點，若未查到比x(k)的目標(biāo)函數(shù)值更小的點，則收斂，x*=x(k)。7.3

離散最優(yōu)解（續(xù)）第23頁,共43頁，2024年2月25日，星期天7.4湊整解法與網(wǎng)格法一、湊整解法

解決離散變量的優(yōu)化問題很容易考慮為；將離散變量全都權(quán)宜地視為連續(xù)變量，用一般連續(xù)變量最優(yōu)化方法求得最優(yōu)點（稱為連續(xù)最優(yōu)點），然后再把該點的坐標(biāo)按相應(yīng)的設(shè)計規(guī)范和標(biāo)準(zhǔn)調(diào)整為與其最接近的整數(shù)值或離散值，作為離散變量優(yōu)化問題的最優(yōu)（稱為離散最優(yōu)點）的坐標(biāo)．這便構(gòu)成離散變量最優(yōu)化問題的湊整解法。第24頁,共43頁，2024年2月25日，星期天

圖中A、B兩點分別表示二維離散變量優(yōu)化問題湊整法中的連續(xù)最優(yōu)點與離散最優(yōu)點。7.4湊整解法與網(wǎng)格法（續(xù)）第25頁,共43頁，2024年2月25日，星期天7.4湊整解法與網(wǎng)格法（續(xù)）

1、與連續(xù)最優(yōu)點A最接近的離散點B落在可行域外，不可以接受；湊整法可能出現(xiàn)的兩個問題：2、與連續(xù)最優(yōu)點A最接近的離散點B并非離散最優(yōu)點C，點B僅是一個工程實際可能接受的較好的設(shè)計方案。第26頁,共43頁，2024年2月25日，星期天改進：即在求得連續(xù)最優(yōu)點A并調(diào)整到最接近的離散點B以后，在B的離散單位鄰域UN（X）或離散坐標(biāo)鄰域UC（X)內(nèi)找出所有的離散點，逐個判斷其可行性并比較其函數(shù)值的大?。畯闹姓业诫x散局部最優(yōu)點或擬離散局部最優(yōu)點。湊整解或改進的湊整法都是基于離散最優(yōu)點就在連續(xù)最優(yōu)點的附近。但實際問題有時并非如此，如圖，真正的離散最優(yōu)點C離連續(xù)最優(yōu)點A很遠。第27頁,共43頁，2024年2月25日，星期天二、網(wǎng)格法網(wǎng)格法是解離散變量優(yōu)化問題的一種最原始的遍數(shù)法。7.4湊整解法與網(wǎng)格法（續(xù)）

在離散變量的值域內(nèi)，先按各變量的可取離散值在設(shè)計空間內(nèi)構(gòu)成全部離散網(wǎng)格點，全域最優(yōu)點X’”應(yīng)是可行域中諸網(wǎng)格點目標(biāo)函數(shù)值最小者．這就需要逐個檢查網(wǎng)格點是否可行和擇其最優(yōu)。第28頁,共43頁，2024年2月25日，星期天7.4湊整解法與網(wǎng)格法（續(xù)）點若不可行，則去掉；若可行，則計算目標(biāo)函數(shù)值f(X(k))，并與以前計算取得的可行最好點x(l)比較,若f(X(k))<f(X(l)),則將X(k)作為新的最好點

繼續(xù)檢查所有的全部離散點后，其最好點就是該優(yōu)化問題的最優(yōu)解X**。優(yōu)點：原理簡單缺點：設(shè)計變量維數(shù)n以及每個變量離散值數(shù)目很多時，計算量大。X(k)點第29頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法

離散復(fù)合形法是在求解連續(xù)變量復(fù)合形法的基礎(chǔ)上進行改造，使之能在離散空間中直接搜索離散點，從而滿足求解離散變量優(yōu)化問題的需要。通過對初始復(fù)合形調(diào)優(yōu)迭代．使新的復(fù)合形不斷向基本思想：最優(yōu)點移動和收縮，直至滿足一定的終止條件為止。特點：復(fù)合形頂點必須是可行的離散點。第30頁,共43頁，2024年2月25日，星期天

將第q+1點朝著點X

(s)的方向移動，新點X

(q+1)為：

X(q+1)=X(s)+0.5(X(q+1)—X(s))連續(xù)變量的復(fù)合形法第31頁,共43頁，2024年2月25日，星期天第32頁,共43頁，2024年2月25日，星期天反射系數(shù)的初值一般取第33頁,共43頁，2024年2月25日，星期天一、初始離散復(fù)合形的產(chǎn)生7.5離散復(fù)合形法（續(xù)）

用復(fù)合形法在n維離散設(shè)計空間搜索時，通常取初始離散復(fù)合形的頂點數(shù)為k=2n+1個。先給定一個初始離散點X(0)，X(0)必須滿足各離散變量值的邊界條件，即：、分別是第i個變量的下限值和上限值。1、初始離散點的確定第34頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）2、初始復(fù)合形各頂點的產(chǎn)生這樣有2n個頂點分別分布于n個設(shè)計變量的上下限約束邊界上。

二維問題產(chǎn)生的離散復(fù)合形的5個頂點第35頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）二、約束條件的處理

由于初始復(fù)合形頂點的產(chǎn)生未考慮約束條件，此時產(chǎn)生的初始復(fù)合形頂點可能會有部分甚至全部落在可行域的外面。

在調(diào)優(yōu)迭代運算中必須保持復(fù)合形各頂點的可行性，故如果有部分頂點落在可行域外面，則需將其移入可行域之內(nèi)。定義離散復(fù)合形的有效目標(biāo)函數(shù)為：第36頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）f(X)為原目標(biāo)函數(shù)；M為一個比f(X)值數(shù)量級大得多的常數(shù)；離散復(fù)合形的有效目標(biāo)函數(shù)為：第37頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）一維變量時的有效目標(biāo)函數(shù)1、在可行域以外，有效目標(biāo)函數(shù)的曲線象一個向可行域傾斜的漏斗;2、當(dāng)部分復(fù)合形頂點在可行域之外時，最壞的頂點X(H)一定位于可行域之外的一個離散點上；D第38頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）3、以最壞點X(H)為基點進行一維離散搜索，M在有效目標(biāo)函數(shù)中保持不變；4、隨搜索點離約束面的位置而變化離約束面越近，其值越??；反之，其值則越大求的極小值，當(dāng)其等于