控制系統(tǒng)參數(shù)優(yōu)化及仿真.ppt

,第六章 控制系統(tǒng)參數(shù)優(yōu)化及仿真,仿真是將已知系統(tǒng)在計(jì)算機(jī)上進(jìn)行復(fù)現(xiàn)，它是分析，設(shè)計(jì)系統(tǒng)的一種重要實(shí)驗(yàn)手段。怎樣才能使設(shè)計(jì)出來的系統(tǒng)在滿足一定的約束條件下，使某個(gè)指標(biāo)函數(shù)達(dá)到極值，這就需要優(yōu)化的仿真實(shí)驗(yàn)。所以仿真技術(shù)與優(yōu)化技術(shù)兩者關(guān)系十分密切。,第六章 控制系統(tǒng)參數(shù)優(yōu)化及仿真,優(yōu)化技術(shù)包括內(nèi)容很多，本章主要介紹與系統(tǒng)最優(yōu)化技術(shù)有關(guān)的參數(shù)優(yōu)化技術(shù)方法。 第一節(jié)首先對(duì)控制系統(tǒng)常用的優(yōu)化技術(shù)做一概括性的敘述。 第二節(jié)介紹單變量技術(shù)的分割法和插值法。 第三節(jié)為多變量尋優(yōu)技術(shù)，介紹工程中常用的最速下降法，共軛梯法和單純形法。 第四節(jié)為隨機(jī)尋優(yōu)法。 第五節(jié)簡(jiǎn)單介紹具有約束條件的尋優(yōu)方法。 第六節(jié)介紹含函數(shù)尋優(yōu)的基本方法。 最后向讀者介紹了Matlab優(yōu)化工具箱的使用方法。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,優(yōu)化技術(shù)是系統(tǒng)設(shè)計(jì)中帶有普遍意義的一項(xiàng)技術(shù),本節(jié)首先討論優(yōu)化技術(shù)中的一些基本定義和問題. 一、優(yōu)化問題數(shù)學(xué)模型的建立 用優(yōu)化方法解決實(shí)際問題一般分三步進(jìn)行： (1) 提出優(yōu)化問題，建立問題的數(shù)學(xué)模型。 (2)分析模型，選擇合適的求解方法。 (3)用計(jì)算機(jī)求解，并對(duì)算法，誤差，結(jié)果進(jìn)行 評(píng)價(jià)。 顯然，提出問題，確定目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式是優(yōu)化問題的第一步，在某種意義上講也是最困難的一步。以下分別說明變量，約束和目標(biāo)函數(shù)的確定。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,(1) 變量的確定 變量一般指優(yōu)化問題或系統(tǒng)中待確定的某些量。例如，在電機(jī)的優(yōu)化設(shè)計(jì)中，變量可能為電流密度J,磁通密度 B，軸的長(zhǎng)度，直徑以及其他幾何尺寸等。電路的優(yōu)化設(shè)計(jì)中要確定的變量主要是電路元件(R,L,C)的數(shù)值。對(duì)產(chǎn)品設(shè)計(jì)問題來說，一般變量數(shù)較少(例如，幾個(gè)到幾十個(gè))。變量數(shù)的多少以及約束的多少表示一個(gè)優(yōu)化問題的規(guī)模大小。因此，工程上最優(yōu)設(shè)計(jì)問題屬于中小規(guī)模的優(yōu)化問題，而生產(chǎn)計(jì)劃，調(diào)度問題中變量數(shù)可達(dá)幾百個(gè)幾千個(gè)，屬于大規(guī)模優(yōu)化問題。變量用X表示,，磁通密度,表示，,。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,(2) 約束條件 求目標(biāo)函數(shù)極值時(shí)的某些限制稱為約束。例如，要求變量為非負(fù)或?yàn)檎麛?shù)值，這是一種限制；可用的資源常常是有限的(資源泛指人力，設(shè)備，原料，經(jīng)費(fèi)，時(shí)間等等)；問題的求解應(yīng)滿足一定技術(shù)要求，這也是一種限制(如產(chǎn)品設(shè)計(jì)中規(guī)定產(chǎn)品性能必須達(dá)到的某些指標(biāo))。此外，還應(yīng)滿足物理系統(tǒng)基本方程和性能方程(如電路設(shè)計(jì)必須服從電路基本定律KCL和KVL)?？刂葡到y(tǒng)優(yōu)化設(shè)計(jì)則用狀態(tài)方程和高階微分和差分方程來描述其物理性質(zhì)。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,如果列寫出來的約束式，越接近實(shí)際系統(tǒng)，則所求得的優(yōu)化問題的解，也越接近于實(shí)際的最優(yōu)解。 等式約束 ： 不等式約束：,或,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,(3) 目標(biāo)函數(shù) 優(yōu)化有一定的標(biāo)準(zhǔn)和評(píng)價(jià)方法，目標(biāo)函數(shù) 是這 種標(biāo)準(zhǔn)的數(shù)學(xué)描述。目標(biāo)函數(shù)可以是效果函數(shù)或費(fèi) 用函數(shù)， 。用效果作為目標(biāo)函 數(shù)時(shí)，優(yōu)化問題是要求極大值，而費(fèi)用函數(shù)不得超 過某個(gè)上界成為這個(gè)優(yōu)化問題的約束；反之，最優(yōu) 函數(shù)是費(fèi)用函數(shù)時(shí)，問題變成了求極小值，而效果 函數(shù)不得小于某個(gè)下界就成為這個(gè)極小值問題的約 束了，這是對(duì)偶關(guān)系。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,費(fèi)用和效果都是廣義的，如費(fèi)用可以是經(jīng)費(fèi)，也可以是時(shí)間、人力、功率、能量、材料、占地面積或其他資源。而效果可以是性能指標(biāo)、利潤(rùn)、效益、精確度、靈敏度等等。也可以將效果與費(fèi)用函數(shù)統(tǒng)一起來，以單位費(fèi)用的效果函數(shù)或單位效果的費(fèi)用函數(shù)為目標(biāo)函數(shù)，前者是求極大值，后者是求極小值。 求極大值和極小值問題實(shí)際上沒有什么原則的區(qū)別。因?yàn)榍?的極小值相當(dāng)于求- 的極大值，即 。 兩者的最優(yōu)值均當(dāng) 時(shí)得到。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,綜上所述，優(yōu)化問題的數(shù)學(xué)模型可以表示成如下形式：,(6.1.1),約束條件,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,二、優(yōu)化問題的分類 優(yōu)化問題可以按下述情況分類： (1)有沒有約束？有約束的話是等式約束還是不等式約束？ (2)所提問題是確定性的還是隨機(jī)性的？ (3)目標(biāo)函數(shù)和約束式是線性的還是非線性的？ (4)是參數(shù)最優(yōu)還是函數(shù)最優(yōu)，即變量是不是時(shí)間的函數(shù)？ (5)問題的模型是用數(shù)學(xué)解析公式表示還是用網(wǎng)絡(luò)圖表示？在網(wǎng)絡(luò)上的尋優(yōu)稱為網(wǎng)絡(luò)優(yōu)化。 限于本書的內(nèi)容要求，在此只介紹參數(shù)優(yōu)化和函數(shù)優(yōu)化。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,(1) 參數(shù)優(yōu)化 在控制對(duì)象已知，控制器的結(jié)構(gòu)、形式已確定的情況下，通過調(diào)整控制器的某些參數(shù)，使得某個(gè)目標(biāo)函數(shù)最優(yōu)，這就是參數(shù)優(yōu)化問題。 例如，圖6.1.1所示的控制系統(tǒng)，在某個(gè)給定函數(shù) 的作用下，測(cè)量給定 與輸出量 之間的偏差 ，用 作為指標(biāo)函數(shù)，要求調(diào)整控制器的參數(shù)，使得該指標(biāo)函數(shù)達(dá)到最小。,圖6.1.1 控制器參數(shù)的調(diào)整,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,假定控制器有 個(gè)可調(diào)整參數(shù) 顯然上述指標(biāo)是這些參數(shù)的函數(shù)，即 (6.1.2) 現(xiàn)在的問題就是要尋求使 達(dá)到極小值的 ，其中 是一個(gè)向量。 從數(shù)學(xué)上講，參數(shù)優(yōu)化問題是屬于普通極值問題。尋找的最優(yōu)參數(shù)不隨時(shí)間變化，故也屬于靜態(tài)尋優(yōu)問題。其一般問題形式是： 有一個(gè)物理系統(tǒng)，它的數(shù)學(xué)模型為 ，其中 為 維狀態(tài)向量； 為 維被尋優(yōu)參數(shù)的向量； 為 維系統(tǒng)運(yùn)動(dòng)方程結(jié)構(gòu)向量。要求在滿足下列條件下：,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,不等式限制 q維 等式限制 p維 等式終端限制 維(是終端時(shí)間) 找到一組參數(shù) ， 使指標(biāo)函數(shù) (2) 函數(shù)優(yōu)化 函數(shù)優(yōu)化是控制對(duì)象已知，要找最優(yōu)控制作用 ，以使某個(gè)函數(shù)指標(biāo)達(dá)到最小，也包括要尋找最優(yōu)控制器的結(jié)構(gòu)、形式和參數(shù)。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,由于最優(yōu)控制作用 為時(shí)間函數(shù)，所以這類問題稱為函數(shù)優(yōu)化問題，在數(shù)學(xué)上稱為泛函極值問題，這類問題的一般形式是： 有一個(gè)物理系統(tǒng)，它的數(shù)學(xué)模型為 ，其中 為 維狀態(tài)向量； 為 維被尋優(yōu)參數(shù)的向量； 為 維系統(tǒng)運(yùn)動(dòng)方程結(jié)構(gòu)向量。要求在滿足條件下： 不等式限制 q維 等式限制 p維 等式終端限制 維 找到m維函數(shù) 使指標(biāo)函數(shù),6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,函數(shù)優(yōu)化問題從理論上講可以用變分或極大值原理或動(dòng)態(tài)規(guī)劃求解。但是在仿真研究中，由于采用的是數(shù)值求解，所以通常將其轉(zhuǎn)化為參數(shù)優(yōu)化問題加以解決。出于以上原因，本章的重點(diǎn)主要討論參數(shù)優(yōu)化問題。 三、參數(shù)優(yōu)化方法 系統(tǒng)的參數(shù)優(yōu)化問題求解方法，按其求解方式可分為兩類：間接尋優(yōu)和直接尋優(yōu)。 (1) 間接尋優(yōu) 間接尋優(yōu)就是把一個(gè)優(yōu)化問題用數(shù)學(xué)方程描述出來，然后按照優(yōu)化的充分必要條件用數(shù)學(xué)分析的方法求出解析解，故又稱其為解析法。,6.1 參數(shù)優(yōu)化與函數(shù)優(yōu)化,數(shù)學(xué)中的變分法，拉格朗日乘子法和最大值原理，動(dòng)態(tài)規(guī)劃等都是解析法，所以也都是間接尋優(yōu)法。由于在大部分控制系統(tǒng)中目標(biāo)函數(shù)J一般很難寫出解析式，而只能在計(jì)算動(dòng)態(tài)相應(yīng)過程中計(jì)算出來，所以仿真中一般較少采用間接尋優(yōu)方法。 (2) 直接尋優(yōu)法 直接尋優(yōu)法就是直接在變量空間搜索一組最佳控制變量(又稱決策變量，設(shè)計(jì)變量)。這是一種數(shù)值方法，具體辦法是，利用目標(biāo)函數(shù)在一局部區(qū)域初始狀態(tài)的性質(zhì)和已知數(shù)值，來確定下一步計(jì)算的點(diǎn)，這樣一步步搜索逼近，最后接近最優(yōu)點(diǎn)。,6.2 單變量尋優(yōu)技術(shù),單變量尋優(yōu)技術(shù)是多變量尋優(yōu)技術(shù)的基礎(chǔ)，多變量參數(shù)尋優(yōu)的算法中常常要用到它，因此單變量的尋優(yōu)方法是解決多變量?jī)?yōu)化問題的基本方法。本節(jié)主要介紹常用的兩種單變量尋優(yōu)方法：分割法和插值法。,6.2 單變量尋優(yōu)技術(shù),6.2.1 黃金分割法( 法) 分割法是單變量函數(shù)無約束極值較為有效的一種直接搜索法。這種方法實(shí)質(zhì)上是在搜索過程中不斷縮小最優(yōu)點(diǎn)存在的區(qū)域，即通過搜索區(qū)間的逐步隨小來確定最優(yōu)點(diǎn)。對(duì)多變量函數(shù)來說，分割法不十分有效，因?yàn)檫@時(shí)消去的不是線段，而是平面、立體或多維空間的一部分。黃金分割法是分割法中的一種有效方法。 假定目標(biāo)函數(shù) ，已知它在區(qū)間 有一極小值存在，如圖6.2.1(a)所示。為了找到這個(gè)極小點(diǎn) ，可以在距 各 處找兩點(diǎn) ，然后比較它們的目標(biāo)函數(shù)值，如果 ，則令 ，形成新區(qū)間 ，然后對(duì)這個(gè)新區(qū)間在距 各 處找兩點(diǎn)。由于每次分割區(qū)間縮小為原來的 倍( )，若原來區(qū)間 為 ，而經(jīng)過n次分割后區(qū)間為 。,6.2 單變量尋優(yōu)技術(shù),那么 。,選多大適合呢？如果要求 應(yīng)該是 的對(duì)稱點(diǎn)，即 ，如圖6.2.1(b)所示，則也可以寫成下面關(guān)系式：,圖6.2.1 黃金分割圖,6.2 單變量尋優(yōu)技術(shù),且希望經(jīng)過分割后其保留點(diǎn)仍處于留下區(qū)間的相應(yīng)位置上，即 在 中的位置與 在 中相仿,且比值相等 (6.2.2) 故: , , 因此可以得到： = (6.2.3) 取正值 =0.6180339 這樣，若計(jì)算分割后的函數(shù)值，則由計(jì)算兩個(gè)點(diǎn)的函數(shù)值變?yōu)橛?jì)算一個(gè)點(diǎn)的函數(shù)值，在一定分割次數(shù)內(nèi)，減少了計(jì)算函數(shù)的次數(shù)。這種分割方法稱為黃金分割法。,6.2 單變量尋優(yōu)技術(shù),圖6.2.2表示了黃金分割法程序框圖。,6.2 單變量尋優(yōu)技術(shù),例6.2.1 求目標(biāo)函數(shù) 的最小值，區(qū)間縮短的精度 。 使用符號(hào)：A：初始區(qū)間的起點(diǎn)， ； B：初始區(qū)間的終點(diǎn)， ； E：允許的精度， 用C語言編寫的計(jì)算程序清單如下： #include “math.h” #include “stdio.h” main( ),6.2 單變量尋優(yōu)技術(shù),float x0, x1, x2, x3, x4, e1, e2, q1, q2, q3, q4, q5, m, h0, h, c1, c2; int n; printf(“intput x0, H0,E1, E2, M”); scanf(“%f, %f, %f, %f, %f ”,6.2 單變量尋優(yōu)技術(shù),p1: x1=x2; q1=q2; x2=x3; q2=q3; x3=x2+h; q3=x3*x3 -10x3+36; if(q2q3) h=h+h; n=n+1; go to p1; else if(n0) x4=0.5*(x2+x3); q4=x4*x4 10*x4+36; if(q4q2) x3=x4; q3=q4; elsex1=x2; q1=q2; x2=x4; q2=q4; c1=(q3-q1)/(x3-x1) c2=(q2-q1)/(x2-x1)-c1)/(x2-x3);,6.2 單變量尋優(yōu)技術(shù),if(fabs(c2)e1) if(q4q2) x1=x2; q1=q2; elsex1=x4; q1=q4; h0=m*h0; go to p2;,6.2 單變量尋優(yōu)技術(shù),printf(“OPTIM X=%fn”,x4); printf(“OBJ.FUNC=%f”,q4); 計(jì)算結(jié)果： Q=11, x1=5.000 67, A=5.007 5, B=5.000 63。,6.2 單變量尋優(yōu)技術(shù),6.2.2 二次插值法 二次插值法是多項(xiàng)式近似法的一種，即用二次的插值多項(xiàng)式擬合目標(biāo)函數(shù)，并用這個(gè)多項(xiàng)式的極小點(diǎn)作為目標(biāo)函數(shù)極值的近似。 1二次插值法的計(jì)算公式 假設(shè)目標(biāo)函數(shù) 在三個(gè)點(diǎn) 的函數(shù)值分別為 。可以利用這三個(gè)點(diǎn)及相應(yīng)的函數(shù)值作為二次插值公式，令 (6.2.4) 為所求的插值多項(xiàng)式，它應(yīng)滿足條件,(6.2.5),6.2 單變量尋優(yōu)技術(shù),對(duì)多項(xiàng)式(6.2.4)式求導(dǎo)數(shù)，并令其為零，得 (6.2.6) (6.2.7) (6.2.7)式就是計(jì)算近似極小點(diǎn)的公式。為了確定這個(gè)極小點(diǎn)只需算出a1和a2，其算法如下。 從(6.2.5)可求出 (6.2.8),6.2 單變量尋優(yōu)技術(shù),如果設(shè)三個(gè)點(diǎn)等距離，即 則式(6.2.8)又可寫為 (6.2.9) 設(shè) 為坐標(biāo)原點(diǎn)，則 (6.2.10),6.2 單變量尋優(yōu)技術(shù),2. 用外推法求尋優(yōu)區(qū)間 外推法是一種尋優(yōu)極點(diǎn)范圍的方法。用二次插值法巡優(yōu)，有時(shí)其最優(yōu)點(diǎn)存在的范圍事先沒有給出，因此作為尋優(yōu)的第一步，首先就是確定尋優(yōu)區(qū)間。其方法如下： 設(shè)從某點(diǎn) 開始，原始步長(zhǎng)為 ，則 , 求目標(biāo)函數(shù) 和 并進(jìn)行比較。 若 ,則將步長(zhǎng)加倍，求在, , ,等點(diǎn)處目標(biāo)函數(shù) 的值,直至函數(shù)值增加為止，如圖6.2.3(a)所示。,6.2 單變量尋優(yōu)技術(shù),若 ,則求在 , , ,等點(diǎn)處的的值，直至函數(shù)值增加為止，如圖.2.3(b) 對(duì)凸函數(shù)來說，最小點(diǎn)必落在 之間，即 , 而且有 (6.2.11),圖6.2.3 外推法圖示,6.2 單變量尋優(yōu)技術(shù),此時(shí)，若在 與 之間的中點(diǎn)進(jìn)行第k+1點(diǎn)的計(jì)算，即取 (6.2.12) 這樣共得四個(gè)等間距的點(diǎn) ,它們之間的間距為 當(dāng) 時(shí) ,;當(dāng) 時(shí) ， 。比較這四個(gè)點(diǎn)的函數(shù)值，取函數(shù)值最小的 ,則 ，這樣就可以得三點(diǎn) ，以便于構(gòu)成二次插值函數(shù)，并且可以判定 一定在 和 之間。,6.2 單變量尋優(yōu)技術(shù),3外推二次插值法的程序框圖 為便于分析將圖6.2.4所示的框圖分為三部分。其中，圖6.2.4(a)為外推法最優(yōu)點(diǎn)存在的區(qū)間；圖6.2.4(b)為二次插值法求近似的最有點(diǎn)；圖6.2.4(c)是比較 與 ，其比較小者為新的起點(diǎn)，同時(shí)縮短步長(zhǎng) ，再重復(fù)圖6.2.4(a)及(b)兩部分。 例6.2.2 求目標(biāo)函數(shù) 的最小值。 用C語言編寫的程序清單如下： #include “math.h” #include “stdio.h”,6.2 單變量尋優(yōu)技術(shù),main( ) float x0, x1, x2, x3, x4, e1, e2, q1, q2, q3, q4, q5, m, h0, h, c1, c2; int n; printf(“input x0, H0, E1, E2, M”)； scanf(“%f, %f, %f, %f, %f”,6.2 單變量尋優(yōu)技術(shù),p1: x1=x2; q1+q2; x2=x3; q2=q3; x3=x2+h; q3=x3*x3-10*x3+36; if(q2q3) h=h+h; n=n+1; go to p1; else if(n0) x4=0.5*(x2+x3); q4=x4*x4-10*x4+36; if(q4q2) x3=x4; q3=q4; elsex1=x2; q1=q2; x2=x4;q2=q4; c1=(q3-q1)/(x3-x1); c2=(q2-q1)/(x2-x1)-c1)/(x2-x3,6.2 單變量尋優(yōu)技術(shù),if(fabs(c2)e1) x1=x2; q1=q2; h0=m*h0; go to p2; elsex4=0.5*(x1+x3-c1/c2); q4=x4*x4-10*x4+36; if(q2e2) q5=e2 else q5=q2;,6.2 單變量尋優(yōu)技術(shù),if(fabs(q4-q2)/q5=e1) if(q4q2) x1=x2; q1=q2; elsex1=x4;q1=q4; h0=m*h0; go to p2; printf(“OPTIM X=%fn”, x4); printf(“OBJ.FUNC=%f ”,q4); ,圖6.2.4 外推二次插值法的程序框圖,當(dāng) x0=0.5, h0=1, 0, e1=0.001, e2=1, m=0.1 時(shí)， 計(jì)算結(jié)果： optim x=5.0, obj.fucn=11.0,6.3 多變量尋優(yōu)技術(shù),單變量尋優(yōu)技術(shù)，由于只有一個(gè)變量，因此只要在一條線上搜索最優(yōu)參數(shù)就可以了。在變量超過一個(gè)以后，就要在多維空間搜索一組最優(yōu)參數(shù)，因此確定尋優(yōu)方向及尋優(yōu)步長(zhǎng)的問題就比較突出了。根據(jù)尋優(yōu)方向及尋優(yōu)步長(zhǎng)的不同，就有不同的尋優(yōu)方法。本節(jié)將介紹三種方法：最速下降法，共軛梯度法和單純形法。,6.3 多變量尋優(yōu)技術(shù),.3.1 最速下降法 一、最速下降法的基本思想 為了弄清這種尋優(yōu)方法的基本思想，可以舉一個(gè)盲人下山的例子。當(dāng)盲人下山時(shí)，眼睛看不見山谷的方位，如何能沿最短路線迅速下降呢？一般盲人只好靠手前后探索試探著前進(jìn)的方向，哪兒最陡？一定下降的最快，這種尋求最速下降的方向作為搜索的方向，一步步逼近最低點(diǎn)就是最速下降的基本思想。 要求多變量函數(shù) 的極小點(diǎn) ，其中 為 維方向，首先從給定的起始點(diǎn) 出發(fā)，沿某個(gè)有利的方向 進(jìn)行一維搜索，求得 在方向 上的極小點(diǎn) ，然后再從 出發(fā)，沿某個(gè)新的有利方向 進(jìn)行搜索，求得 在 方向上的近似極小點(diǎn) 。如此繼續(xù)，直至滿足給定的精度為止。,6.3 多變量尋優(yōu)技術(shù),二、最速下降法的計(jì)算方法 設(shè)目標(biāo)函數(shù) ，求使目標(biāo)函數(shù) 為最小值的變量 。設(shè) 為 維向量，對(duì) 存在二階偏導(dǎo)數(shù)。 現(xiàn)假設(shè)已經(jīng)迭代到第 步，得到此時(shí)刻的 ，考慮 有一個(gè)微小的變化，即 (6.3.1) 為 附近的點(diǎn)，其兩點(diǎn)的距離為： (6.3.2),6.3 多變量尋優(yōu)技術(shù),因?yàn)?的微小變化，必然引起目標(biāo)函數(shù) 也有一個(gè)變化： (6.3.3) 所謂 下降最快，及最大變化的問題，經(jīng)過上述變換，就轉(zhuǎn)化為以下具有約束的極值問題。 在下列約束條件下： (6.3.4) 通過適當(dāng)選擇 ，使下式極大化 (6.3.5),6.3 多變量尋優(yōu)技術(shù),具有約束的極值問題可以采樣拉格朗日乘子，化為無約束極值問題。設(shè) 為拉格朗日乘子，則 (6.3.6) 式(6.3.5)對(duì) 求偏微分，并令其等于零，有 解出 為 (6.3.7) 將方程(6.3.7)代入(6.3.2)，計(jì)算出 因子為,6.3 多變量尋優(yōu)技術(shù),令： (6.3.9) 則 (6.3.10) 將(6.3.10)代入(6.3.7)得到 (6.3.11) 即，我們可以得到第 步時(shí)的 為 (6.3.12),6.3 多變量尋優(yōu)技術(shù),下面，確定(6.3.12)的正負(fù)號(hào)。將(6.3.8)式代入(6.3.7)式，得到 (6.3.13) 再將上式代入(6.3.5)式得到 即： (6.3.14) 因?yàn)?是距離，故為正，因此取“”號(hào)時(shí)，目標(biāo)函數(shù)增加，而取“”號(hào)時(shí)，對(duì)應(yīng)的目標(biāo)函數(shù)減小。換句話說，沿著目標(biāo)函數(shù)的負(fù)梯度方向走，目標(biāo)函數(shù)是減小的。,6.3 多變量尋優(yōu)技術(shù),又因?yàn)?，?6.3.6)對(duì) 的二階偏微分等于 ，為了保證式(6.3.5)中的 沿著負(fù)數(shù)方向有最大值，即式(6.3.5)有極小值，因此只有 等于正數(shù)。我們可在式(6.3.10)中取負(fù)號(hào)，來保證(6.3.6)對(duì) 的二階偏微分大于零，也就保證式(6.3.5)有極小值。 其中 為迭代步長(zhǎng)， 不能選擇太小，否則目標(biāo)函數(shù) 下降太慢，但如果 很大，目標(biāo)函數(shù) 可能會(huì)出現(xiàn)“上下起伏”現(xiàn)象，因此選擇最優(yōu)步長(zhǎng) 應(yīng)使 在方向的目標(biāo)函數(shù)數(shù)值最小，即,6.3 多變量尋優(yōu)技術(shù),(6.3.15) 顯然，這是一個(gè)單變量尋優(yōu)問題，即尋找最佳步長(zhǎng) ?？梢岳蒙弦还?jié)所介紹的方法。 最速下降法的一般計(jì)算關(guān)系式為：若出發(fā)點(diǎn)為,則 (6.3.16),6.3 多變量尋優(yōu)技術(shù),式中 梯度向量； 梯度向量模； 梯度方向上的單位向量。 控制迭代的收斂要求可以為 = 或 (6.3.17) 式中 梯度誤差，它是很小的正數(shù)； 目標(biāo)函數(shù)誤差，它也是很小的正數(shù)。,6.3 多變量尋優(yōu)技術(shù),最速下降法的程序框圖如圖6.3.1所示。 圖6.3.1 最速下降法的程序框圖,6.3 多變量尋優(yōu)技術(shù),用C語言編寫的最速下降法的程序清單如下。其中R是梯度模 ；P是梯度方向的單位向量 ；h是步長(zhǎng) ；f是目標(biāo)函數(shù) 。 #include “math.h” #include “stdio.h” float x10, y10, p10, f, h; int n; vod fun( ) int i; for(i=1, in; i+) xi=yi-h*pi;,6.3 多變量尋優(yōu)技術(shù),f=x1*x1+x2*x2-x1*x2-10*x1-4*x2; f=f+60; return; main( ) float g10, d10, q, r, e, h1, h2, h3, h4, t, t0, c1, c2, f1, f2, f3, f4, f5, v; int i, k, u; printf(“input n, en”); scanf(“%d, %f”, ,6.3 多變量尋優(yōu)技術(shù),x1=0; x2=0; p4: g1=2*x1-x2-10; g2=2*x2-x1-4; q=0; for(i=1; in;i+) q=gi*gi+q; r=sqrt(q); for(i=1; in;i+) yi=xi;pi=gi/r; if(re)go to p3; else,6.3 多變量尋優(yōu)技術(shù),t0=1; v=0.1; h1=0; h=h1 fun( ); f1=f; p2: u=0;t=t0; h2=h1+t; h=h2; fun( ); f2=f; if(f1f2) t=t+t; u=u+1; elset=-t; h3=h1; f3=f1; h1=h2;f1=f2;h2=h3;f2=f3; p1: h3=h2+t; h=h3; fun( );f3=f;,6.3 多變量尋優(yōu)技術(shù),if(f2f3) t=t+t; u=u+1; h1=h2;f1=f2;h2=h3;f2=f3;goto p1; elseif(u0) h4=0.5*(h2+h3); h=h4; fun( ); f4=f; if(f4f2) h3=h4; f3=f4; elseh1=h2; f1=f2; h2=h4; f2=f4; c1=(f3-f1)/(h3-h1); c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);,6.3 多變量尋優(yōu)技術(shù),if(fabs(c2)e) h1=h2;f1=f2;t0=v*t0; goto p2; elseh4=0.5*(h1+h3-(c1/c2); h=h4; fun( ); f4=f; if(f21) f5=1; else f5=f2; if(fabs(f4-f2)/f5)e) for(i=1; in; i+) xi=yi-h4*pi; goto p4; ,6.3 多變量尋優(yōu)技術(shù),else if(f4f2) h1=h2;f1=f2; else h1=h4;f1=f4; t0=v*t0; goto p2; p3: h=0; fun( ); printf(“OBJ.FUNC F=%fn”, f); for(i=1; in; i+),6.3 多變量尋優(yōu)技術(shù),printf(“X(%d”, I); printf(“)=%fn”, xi); 最速下降法的搜索方向是所謂的最速下降方向，但是也只能逐次地接近最優(yōu)點(diǎn) ，對(duì)本例來說，開始搜索時(shí)，每次的步長(zhǎng)大，目標(biāo)函數(shù)下降也較快，但愈接近極值點(diǎn)，步長(zhǎng) 愈來愈小，目標(biāo)函數(shù)的改進(jìn)也小，其搜索路徑如圖6.3.2所示。,6.3 多變量尋優(yōu)技術(shù),圖6.3.2 最速下降法收斂曲線,6.3 多變量尋優(yōu)技術(shù),最速下降法從表面看是個(gè)最好的方法，但實(shí)際上并非如此。大量的計(jì)算實(shí)踐說明，最速下降法收斂的速度并不快。這主要是因?yàn)樽钏傧陆捣ǖ姆较騼H僅是指某點(diǎn)附近而言，是一個(gè)局部的性質(zhì)，一旦離開了該點(diǎn)原先的方向就不再保證是最速下降方向了。因此對(duì)整個(gè)過程來說，它并不總是具有最速下降的性質(zhì)。盡管如此，最速下降法仍然不失為一種最常用的基本尋優(yōu)方法。這不僅因?yàn)樽钏傧陆捣看蔚?jì)算比較簡(jiǎn)單，記憶容量小，適合計(jì)算機(jī)運(yùn)算，而且對(duì)初值要求也比較低，在遠(yuǎn)離極值點(diǎn)時(shí)收斂快，所以它也經(jīng)常與其他尋優(yōu)方向共同配合，加快尋優(yōu)速度。,6.3 多變量尋優(yōu)技術(shù),6.3.2 共軛梯度法 軛梯度法是解優(yōu)化問題的有效方法之一，特別是用于二次泛函指標(biāo)系統(tǒng)。共軛梯度法程序清單容易實(shí)現(xiàn)，具有梯度法優(yōu)點(diǎn)，而在收斂速度方面比梯度法快。下面分三部分較詳細(xì)地介紹這種方法，并給出一個(gè)實(shí)用程序。 一、共軛梯度法 設(shè) 為定義在 維歐氏空間內(nèi)區(qū)域 中的 元函數(shù)。向量 的分量 是函數(shù)的自變量。設(shè) 為 域內(nèi)的一個(gè)點(diǎn)，則函數(shù) 可在這個(gè)點(diǎn)的附近以泰勒級(jí)數(shù)展開，且只取其二階導(dǎo)數(shù)項(xiàng)，即：,6.3 多變量尋優(yōu)技術(shù),(6.3.18) 其中: ， 分別為： (6.3.19),6.3 多變量尋優(yōu)技術(shù),是 在點(diǎn) 處的二階偏導(dǎo)數(shù)矩陣，又稱赫森矩陣。 極值點(diǎn)存在的必要條件。 元函數(shù)在 域內(nèi)極值點(diǎn) 存在的必要條件為 (6.3.20) 即每個(gè)一階偏導(dǎo)數(shù)值都必須為零，或梯度為 維零向量。但這只是必要條件，而不是充分條件，滿足上式的點(diǎn)稱為駐點(diǎn)。 極值點(diǎn)存在的充分條件。設(shè) 為 的駐點(diǎn)，將(6.3.20)式代入(6.3.18)式得,6.3 多變量尋優(yōu)技術(shù),(6.3.21) 欲使 為極小點(diǎn)，只要在 附近，其差 所以必須有 (6.3.22) 這就是說，在點(diǎn) 處的赫森矩陣 為正定的，即 為極小點(diǎn)的充分條件。因此利用處的赫森矩陣 的性質(zhì)即可判斷是駐點(diǎn)還是極值點(diǎn)。 二、共軛梯度法的基本思想,6.3 多變量尋優(yōu)技術(shù),為了改進(jìn)在極值點(diǎn)附近尋優(yōu)的收斂速度，就要尋求更好的尋優(yōu)方法。共軛梯度法是一種有效算法。 首先舉例說明共軛方向的意義。如果兩個(gè)2維向量 與 相互正交，見圖6.3.3(a)，則其內(nèi)積 0，也可以寫成 0， 為單位矩陣。于是可以稱 與 以單位矩陣互為共軛，可記為 。 圖6.3.3 共軛方向,6.3 多變量尋優(yōu)技術(shù),設(shè)有二階對(duì)稱矩陣 ，如 成立，即 與 相互正交，如圖6.3.3(b)所示，則稱 與 以 互為共軛，可記為 (6.3.23) 對(duì)于任意形式的目標(biāo)函數(shù) ，如將其在 附近展開稱泰勒級(jí)數(shù)，且只取到二次導(dǎo)數(shù)項(xiàng)，則得 (6.3.24) 式中: 為 在 處的二階偏導(dǎo)數(shù)矩陣，即赫森矩陣。,6.3 多變量尋優(yōu)技術(shù),因?yàn)樵跇O值點(diǎn) 處 ,故 (6.3.25) 此式表示函數(shù)為二次函數(shù)。由此可以看出：任意形式得函數(shù) 在極值點(diǎn)附近的特性都近似于一個(gè)二次函數(shù)。對(duì)于二次函數(shù) ，如圖6.3.4所示，在初始點(diǎn) 做 的切線向量。設(shè)最優(yōu)點(diǎn)為 ，則連接 與 的向量 與切線 互為共軛。這一點(diǎn)可證明如下。,6.3 多變量尋優(yōu)技術(shù),在最優(yōu)點(diǎn),Q(x*)=0, 在 點(diǎn)的梯度 切線向量 與梯度向量 互為正交，即 而,6.3 多變量尋優(yōu)技術(shù),即 顯然， 與 ，可寫成下式： 即 與 以 互為共軛。 上述性質(zhì)表明，如果對(duì)二次函數(shù),從某點(diǎn)出發(fā)，沿共軛方向搜索，可以很快得到函數(shù)的極值點(diǎn).,6.3 多變量尋優(yōu)技術(shù),三、共軛梯度法的計(jì)算方法 設(shè) 元函數(shù) 在極值點(diǎn)附近可用一個(gè)二次函數(shù)逼近： (6.3.26) 式中： 為 維對(duì)稱矩陣。 = (6.3.27) (6.3.28),6.3 多變量尋優(yōu)技術(shù),對(duì)于兩個(gè)變量問題，可以用等高線來表示，見圖6.3.5。設(shè)從某點(diǎn) 出發(fā)以 的方向搜索，使 達(dá)到極小的點(diǎn) ，則 為該處等高線的切點(diǎn)。切點(diǎn)的梯度方向?yàn)榈雀呔€的法線方向，因此,圖6.3.4 二次函數(shù)中的共軛方向 圖6.3.5 兩個(gè)變量的等高線圖,6.3 多變量尋優(yōu)技術(shù),若從另一點(diǎn) 出發(fā)，也以 方向搜索，又得到一個(gè)極小點(diǎn) ,同理也應(yīng)有 (6.3.29) (6.3.28)式與(6.3.29)式之差為 (6.3.30) 若令 ,則 (6.3.31) 這就說明 與 以 互為共軛。而 正是 與 兩切點(diǎn)連線方向，此方向上的極小點(diǎn)即Q(x)的極小點(diǎn)。,6.3 多變量尋優(yōu)技術(shù),例 6.3.1目標(biāo)函數(shù) 式中：C=10 4T；A= ，從 出發(fā)搜索，求極小點(diǎn)。 解：如果第一次的搜索方向?yàn)?，則它與共軛方向的關(guān)系為 一個(gè)向量的方向可以用單位方向向量E來表示，若 的單位方向向量 即 與軸 平行，因 ,則 (6.3.32),6.3 多變量尋優(yōu)技術(shù),為了求最優(yōu)步長(zhǎng) ，將(6.3.31)式代入目標(biāo)函數(shù)，得 (6.3.33) 將(6.3.33)式對(duì)求導(dǎo)并令其等于零，得 (6.3.34) 故： 因此，第一次搜索的結(jié)果為,6.3 多變量尋優(yōu)技術(shù),第二次搜索的方向應(yīng)為 的共軛方向，即 (6.3.35) 得 又有單位向量 (6.3.36) 解聯(lián)立方程(6.3.35)式及(6.3.36)式，得,6.3 多變量尋優(yōu)技術(shù),因此： (6.3.37) 為求最優(yōu)步長(zhǎng) ，將式(6.3.37)式代入目標(biāo)函數(shù)得 (6.3.38) 將(6.3.38)式對(duì) 求導(dǎo)，并令其等于零，得 (6.3.39),6.3 多變量尋優(yōu)技術(shù),得： 因此： 由此可見，因是一個(gè)二元的二次函數(shù)，只要搜索兩個(gè)方向 ， 就可以達(dá)到極小點(diǎn)，即 8， 6。對(duì)于一個(gè) 元的二次函數(shù)，可以用不超過 次的搜索方向，就可以達(dá)到極小點(diǎn)。 從上例可知，計(jì)算共軛方向時(shí)要用矩陣 ，如果已知 ，則計(jì)算共軛方向是容易的。例如，當(dāng)函數(shù)為二次函數(shù)時(shí)， 為二次項(xiàng)的常系數(shù)矩陣。但當(dāng)函數(shù)為非二次時(shí)， 為二階偏導(dǎo)數(shù)矩陣(赫森矩陣)，求起來相當(dāng)麻煩，尤其當(dāng)維數(shù)很高時(shí)更加麻煩。因此，能否避免矩 陣 的直接計(jì)算，而用間接的方法確定共軛方向呢？下面介紹一種間接求共軛方向的方法。,6.3 多變量尋優(yōu)技術(shù),設(shè)目標(biāo)函數(shù)為元的二次函數(shù) (6.3.40) 設(shè) 為n維向量； 為任意給定的起點(diǎn)。 為 次迭代中要尋求得對(duì)的共軛方向。依次為沿這些方向求得的近似極小點(diǎn)。因此有 (6.3.41) (6.3.42) 為最優(yōu)步長(zhǎng)，它滿足 (6.3.43),6.3 多變量尋優(yōu)技術(shù),當(dāng)然，對(duì) 也有 (6.3.44) 將(6.3.44)式與(6.3.41)式相減，并將(6.3.42)式代入，得 (6.3.45) 根據(jù)共軛的定義，應(yīng)有 (6.3.46) 將(6.3.45)式代入(6.3.46)式，得 (6.3.47) 從(6.3.47)式看出，不計(jì)算矩陣A可以求出共軛的方向。,6.3 多變量尋優(yōu)技術(shù),現(xiàn)從點(diǎn) 開始進(jìn)行搜索，在確定第一個(gè)搜索方向 時(shí)，因?yàn)槌颂荻?可以直接計(jì)算外，沒有其他有用的信息，因此可取 (6.3.48) 將沿 方向作為一位搜索，求最優(yōu)步長(zhǎng) ,使 (6.3.49) 由此得一新的點(diǎn) ,并算出 。因?yàn)?是點(diǎn) 的法線方向， 而 是 點(diǎn)的切線方向，所以 與 正交，從而也和 正交，即,6.3 多變量尋優(yōu)技術(shù),為在 和 構(gòu)成的正交系中尋求共軛方向 ,可令 (6.3.51) 共軛方向 為該次的反梯度方向與上次搜索方向得線性組合，這里的問題是選擇一個(gè) ，使 與 共軛。 根據(jù)(6.3.47)式，有 (6.3.52) 將(6.3.50)式與(6.3.51)式代入(6.3.52)式中，化簡(jiǎn)得,6.3 多變量尋優(yōu)技術(shù),所以有： = (6.3.53) 把(6.3.53)式代入(6.3.51)式， 得 (6.3.54) 由此可見，通過 與 即可求出共軛方向 .沿此 方向在進(jìn)行一維搜索求最優(yōu)步長(zhǎng) ，得到 ，如此進(jìn)行下去，一般來說有以下的迭代方向： (6.3.55) (6.3.56) 所得到的 即為共軛方向。,6.3 多變量尋優(yōu)技術(shù),按照(6.3.55)式及(6.3.56)式確定搜索方向的算法成為共軛梯度法。其程序框圖如圖6.3.6所示。,圖 6.3.6 共軛梯度法的程序框圖,6.3 多變量尋優(yōu)技術(shù),例6.3.2目標(biāo)函數(shù) ，設(shè)起點(diǎn)為 ，試用共軛梯度法求最小值。 解：第一次迭代計(jì)算：,6.3 多變量尋優(yōu)技術(shù),求 得 本例題中的 可以用解析法求得 經(jīng)兩次迭代即達(dá)到極值點(diǎn)。與一階梯度法相比其收斂速度較快。,6.3 多變量尋優(yōu)技術(shù),用C語言編寫的共軛梯度法計(jì)算程序清單如下： #include “math.h” #include “stdio.h” float x10,y10,p10,f,h; int n; void fun() int i; for(I=1;In,I+) xI=yI+h*pI; f=x1*x1+x2*x2-x1*x2-10*x1-4*x2; f=f+60; return; ,6.3 多變量尋優(yōu)技術(shù),main() float g10,q1,q0,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v; int I,k,u; printf(“INPUT N,En”); scanf(“%d,%d”,6.3 多變量尋優(yōu)技術(shù),for(i=1;If2) t=t+t;u=u+1; else t=-t;h3=h1;f3=f1;h1=h2;f1=f2;h2=h3;f2=f3;,6.3 多變量尋優(yōu)技術(shù),p1: h3=h2+t;=h3; fun( );f3=f; if(f2f3) t=t+t;u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;goto p1; else if(u0) h4=0.5*(h2+h3);h=h4; fun( );f4=f; if(f4f2) h3=h4;f3=f4; elseh1=h2;f1=f2;h2=h4;f2=f4; c1=(f3-f1)/(h3-h1); c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);,6.3 多變量尋優(yōu)技術(shù),if(f2f2)h1=h2;f1=f2; else h1=h4;f1=f4; t0=v*t0;goto p2; ,6.3 多變量尋優(yōu)技術(shù),goto p4; p3: h=0;fun( ); printf(“OBJ.FUNC F=%fn”,f); for(I=1;In;I+) printf(“X%d”,I); printf(“=%fn”,xI); ,6.3 多變量尋優(yōu)技術(shù),6.3.3 單純形法 函數(shù) 的導(dǎo)數(shù)是函數(shù) 特性的重要反映，但在許多實(shí)際問題中，常常得不到計(jì)算 導(dǎo)數(shù)的解析式，而只能采用近似的方法，常用方法是有限差分法。用有限差分法計(jì)算 的導(dǎo)數(shù)不僅誤差大，而且要多次計(jì)算目標(biāo)函數(shù)，計(jì)算工作量很大。為了克服求 導(dǎo)數(shù)所帶來的問題，提出了松弛法、單純形法、隨機(jī)搜索法等方法。這一節(jié)介紹工程中常用的單純形法。從直觀上看，如果不計(jì)算導(dǎo)數(shù)，則可以先算出 在若干個(gè)點(diǎn)處的函數(shù)值，然后將它們進(jìn)行比較，從它們之間的大小關(guān)系就可以看出函數(shù)變化的大致趨勢(shì)，這樣也能為尋求函數(shù)的下降方向提供參考。,6.3 多變量尋優(yōu)技術(shù),例如，圖6.3.7所示的情況，變量有兩個(gè) ， ，圖中畫出了 的等高線簇。若先計(jì)算1，2，3三點(diǎn)(他們構(gòu)成一個(gè)三角形)的函數(shù)值，然后對(duì)它們的大小進(jìn)行比較，其中 最大，故將1點(diǎn)拋棄，在1點(diǎn)的對(duì)面取一點(diǎn)4，則構(gòu)成一個(gè)新的三角形再比較各點(diǎn) 的大小，其中 最大，故將2點(diǎn)拋棄，在2點(diǎn)的對(duì)面取一點(diǎn)5，這樣3，4，5又構(gòu)成一個(gè)新的三角。如此一直循環(huán)下去最后可找到最小點(diǎn)。單純形尋優(yōu)方法的思想是很簡(jiǎn)單明了的，但是為了使其比較使用，同時(shí)能加快它收斂速度，還要解決一下幾個(gè)主要問題。,6.3 多變量尋優(yōu)技術(shù),一、單純形應(yīng)由幾個(gè)點(diǎn)構(gòu)成 對(duì)于一般的n元函數(shù) ( 為 維向量)，可取 維空間中 個(gè)點(diǎn)， ，構(gòu)成初始單純形。這 個(gè)點(diǎn)，應(yīng)使n個(gè)向量， ， ， 為線性獨(dú)立。這就是說，在平面上( )取不同一直線的三點(diǎn)構(gòu)成單純形(三角形)，在三維空間( )內(nèi)取不同的四個(gè)點(diǎn)(4面體)。如果點(diǎn)取得少，或n個(gè)向量有一部分線性相關(guān)，那么就會(huì)使搜索極小點(diǎn)的范圍局限在一個(gè)低維空間內(nèi)，如果極小點(diǎn)不在這個(gè)空間內(nèi)，就搜索不到了。,6.3 多變量尋優(yōu)技術(shù),二、單純形的形狀 為了簡(jiǎn)單起見，單純形取n個(gè)向量為“等長(zhǎng)”。 具體來講，若已選定 ，則 這n個(gè)點(diǎn)為 (6.3.57) 其中， 為第 個(gè)單位坐標(biāo)向量，即 (6.3.58) 只有第 個(gè)元素為1，其他均為0。,6.3 多變量尋優(yōu)技術(shù),三、新點(diǎn)的選取 根據(jù)經(jīng)驗(yàn)及考慮到計(jì)算方便 ，一般新的點(diǎn)取在被拋棄的點(diǎn)的“對(duì)面”，稱為反射點(diǎn)。以圖6.3.8所示為例，假定為要拋棄的點(diǎn)，則新點(diǎn)的坐標(biāo)應(yīng)為，坐標(biāo)可以這樣來求：,圖6.3.7 單純形法尋優(yōu)過程 圖6.3.8 反射點(diǎn)的確定,6.3 多變量尋優(yōu)技術(shù),先求出 及 兩個(gè)點(diǎn)的中心 ，則 (6.3.59) 然后再求其反射點(diǎn) ，即 (6.3.60) 推廣到多變量(n維)的情況，則有 , 共 個(gè)點(diǎn)，假定其中 點(diǎn)是被拋棄的，那么， 反射點(diǎn) 為 (6.3.61) 其中:,6.3 多變量尋優(yōu)技術(shù),四、關(guān)于新點(diǎn)的擴(kuò)張壓縮及單純形的收斂問題 對(duì)組成單純形的(n1)個(gè)點(diǎn)，可以定義： 為最壞點(diǎn)(即目標(biāo)函數(shù) 最大的點(diǎn)) 為最好點(diǎn)(即 最小的點(diǎn))； 為次壞點(diǎn)(即 比 小，但比其他各點(diǎn)的目標(biāo)函數(shù)都大)。 如果新的點(diǎn) 的函數(shù)值 小于 ，這說明點(diǎn)可能前進(jìn)得不夠，此時(shí)可以沿反射方向再多前進(jìn)一些(稱為擴(kuò)張)，即 (6.3.62),6.3 多變量尋優(yōu)技術(shù),反之，若按(6.3.61)式找到 ，而 大于 ，這說明 點(diǎn)前進(jìn)得太遠(yuǎn)了，需要壓縮，即要在 與 的延長(zhǎng)線上(即沿原來的反射方向)后退一些，得 (6.3.63) 為壓縮因子，它是01之間的一個(gè)常數(shù)，為了避免 與 重合(即 )，要求 ( 與 重合會(huì)使單純形的空間維數(shù)降低，這不利于搜索)。 如果壓縮后 仍然大于 ，這說明原先的單純形取得太大了，可以將他們所有的邊都縮小，構(gòu)成新的單純形，這叫單純形的收縮。 具體辦法是： (6.3.64),6.3 多變量尋優(yōu)技術(shù),五、什么時(shí)候停止搜索 若 則說明搜索成功，此時(shí)可以認(rèn)為 即為極小點(diǎn)，而 為極小值。如果經(jīng)過K次搜索，仍然不能滿足上式，說明搜索失敗。 根據(jù)上面的介紹，可畫出單純形法的程序框圖，如圖6.3.9所示。這個(gè)程序基本上包括以下7個(gè)部分： (1)計(jì)算原始的單純形； (2)計(jì)算原始的單純形各點(diǎn)的目標(biāo)函數(shù)值； (3)找到最好點(diǎn) ，最壞點(diǎn) ，以及次壞點(diǎn) ； (4)尋優(yōu)次數(shù) 加1，并判斷計(jì)算是否收斂，若收斂，則打印出結(jié)果；,6.3 多變量尋優(yōu)技術(shù),(5)搜索次數(shù)是否超過規(guī)定，若已超過，則說明搜索失敗，打印出結(jié)果，并停止搜索，若未超過，則計(jì)算反射點(diǎn)； (6)判斷是否要壓縮，若要，則進(jìn)行壓縮計(jì)算，若壓縮失敗，則進(jìn)行收縮計(jì)算，然后轉(zhuǎn)(3)或(4)； (7)判斷是否要擴(kuò)張，若要，則進(jìn)行擴(kuò)張計(jì)算，并評(píng)價(jià)擴(kuò)張效果，然后轉(zhuǎn)(4)； 關(guān)于單純形法的詳細(xì)程序可參看本書配套的程序，該程序除考慮了上述諸點(diǎn)之外，還考慮到參數(shù)變量上下界限制，這樣在使用時(shí)就更為方便了。,6.3 多變量尋優(yōu)技術(shù),圖6.3.9 單純形法程序框圖,6.4 隨機(jī)尋優(yōu)法,在第三節(jié)中已分別介紹了兩種多變量尋優(yōu)的方法。梯度法雖然每一步尋優(yōu)方向十分明確沿著梯度所給的信息來確定尋優(yōu)方向，但是這種方法每一步都要計(jì)算目標(biāo)函數(shù)的梯度，這常常占用相當(dāng)長(zhǎng)的計(jì)算時(shí)間。而單純形法則不同梯度這個(gè)信息，它是利用對(duì)參數(shù)點(diǎn)的目標(biāo)函數(shù)值的比較來確定尋優(yōu)方向。這種方法對(duì)于變量較多，目標(biāo)函數(shù)的形態(tài)比較復(fù)雜的情況(比如有好幾個(gè)極值點(diǎn))收斂都不十分快。隨著統(tǒng)計(jì)仿真方法的發(fā)展，近年來隨機(jī)尋優(yōu)法也得到了發(fā)展，當(dāng)變量數(shù)目較多，目標(biāo)函數(shù)的形態(tài)又比較復(fù)雜時(shí)，用此法一般較好。,6.4 隨機(jī)尋優(yōu)法,尤其是當(dāng)采用混合仿真系統(tǒng)來進(jìn)行控制系統(tǒng)參數(shù)尋優(yōu)時(shí)，可以用模擬機(jī)部分來計(jì)算系統(tǒng)的運(yùn)動(dòng)方程，即計(jì)算目標(biāo)函數(shù)；而用數(shù)字機(jī)部分來做尋優(yōu)搜索，此時(shí)采用隨機(jī)尋優(yōu)法更為有效。 隨機(jī)尋優(yōu)法的種類很多，這里向讀者介紹的是三種用得較多的隨機(jī)尋優(yōu)法。它們是：隨機(jī)貫尋優(yōu)，隨機(jī)搜索尋優(yōu)以及隨機(jī)模式搜索尋優(yōu)。,6.4 隨