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

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

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

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

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

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

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

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

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

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

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è)計(jì)方法求連續(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)點(diǎn)。x10x28.1引言（續(xù)）

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

●qij

●qij+1

●Xi§7.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

離散最優(yōu)解

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

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

一般情況下，設(shè)離散變量的維數(shù)為p，則UN(X)內(nèi)的離散點(diǎn)總數(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è)計(jì)空間中離散點(diǎn)X的離散坐標(biāo)鄰域UC(X)是指以X點(diǎn)為原點(diǎn)的坐標(biāo)軸線和離散單位鄰域UN（X）的交點(diǎn)的集合。圖示離散坐標(biāo)鄰域?yàn)椋?/p>

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

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

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

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

設(shè)當(dāng)前搜索到的最好點(diǎn)為x(k)，需要判斷其是否收斂。在x(k)的單位鄰域中查3n–1個(gè)點(diǎn)，若未查到比x(k)的目標(biāo)函數(shù)值更小的點(diǎn)，則收斂，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)點(diǎn)（稱為連續(xù)最優(yōu)點(diǎn)），然后再把該點(diǎn)的坐標(biāo)按相應(yīng)的設(shè)計(jì)規(guī)范和標(biāo)準(zhǔn)調(diào)整為與其最接近的整數(shù)值或離散值，作為離散變量優(yōu)化問題的最優(yōu)（稱為離散最優(yōu)點(diǎn)）的坐標(biāo)．這便構(gòu)成離散變量最優(yōu)化問題的湊整解法。第24頁,共43頁，2024年2月25日，星期天

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

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

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

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

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

將第q+1點(diǎn)朝著點(diǎn)X

(s)的方向移動(dòng)，新點(diǎn)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è)計(jì)空間搜索時(shí)，通常取初始離散復(fù)合形的頂點(diǎn)數(shù)為k=2n+1個(gè)。先給定一個(gè)初始離散點(diǎn)X(0)，X(0)必須滿足各離散變量值的邊界條件，即：、分別是第i個(gè)變量的下限值和上限值。1、初始離散點(diǎn)的確定第34頁,共43頁，2024年2月25日，星期天7.5離散復(fù)合形法（續(xù)）2、初始復(fù)合形各頂點(diǎn)的產(chǎn)生這樣有2n個(gè)頂點(diǎn)分別分布于n個(gè)設(shè)計(jì)變量的上下限約束邊界上。

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

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

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