第七章 單純形優(yōu)化法

第七章單純形優(yōu)化法§7-1概述單純形法是一種優(yōu)化設(shè)計(jì)方法和正交試驗(yàn)相比的特點(diǎn)：計(jì)算簡(jiǎn)便不受因素?cái)?shù)的限制因素?cái)?shù)的增加不會(huì)導(dǎo)致試驗(yàn)次數(shù)大量增加它屬于非線性動(dòng)態(tài)調(diào)優(yōu)過程發(fā)展簡(jiǎn)史1962年，Spendley提出基本單純形法1965年，Nelder等提出改進(jìn)單純形法之后，Routh提出加權(quán)形心法與控制加權(quán)形心法§7-2基本單純形一、雙因素基本單純形法 如果我們有一個(gè)試驗(yàn)設(shè)計(jì)，只選有兩個(gè)影響因素，即因素?cái)?shù)為2。分別取值a1和a2作為試驗(yàn)的初點(diǎn)。記為A(a1,a2)。對(duì)其余兩個(gè)點(diǎn)分別設(shè)為B和C，再設(shè)三角形的邊長(zhǎng)為a(步長(zhǎng))。那么B、C點(diǎn)就可以計(jì)算出來假設(shè)AB、AC、BC間距均為，等邊三角形可以算出B點(diǎn)為：B=(a1+p,a2+q)根據(jù)對(duì)稱性可知：C=(a1+q,a2+p)可以根據(jù)等邊三角形性質(zhì)解得：a2+pa2+qa2a1+pa1+qa1因素2因素1ABCDEo由A、B、C三點(diǎn)構(gòu)成得單純形稱為初始單純形首先在A、B、C三點(diǎn)下分別試驗(yàn)，得出三個(gè)響應(yīng)值，比較其大小，找出最壞響應(yīng)值的點(diǎn)稱為壞點(diǎn)此處設(shè)A為壞點(diǎn)，去掉A點(diǎn)并取A的對(duì)稱點(diǎn)D點(diǎn)作為新試驗(yàn)點(diǎn)，比較B、C、D三點(diǎn)響應(yīng)值的好壞此處設(shè)C為壞點(diǎn)，去點(diǎn)C點(diǎn)，取其反點(diǎn)E，此時(shí)C、D、E三點(diǎn)又構(gòu)成新的單純形…………重復(fù)以上結(jié)果，最終達(dá)到優(yōu)化試驗(yàn)的目的二、新試驗(yàn)點(diǎn)的計(jì)算方法 以初始單純形A、B、C為例，設(shè)A為壞點(diǎn)，A應(yīng)該去掉，求其反射點(diǎn)D，此時(shí) A(a1,a2)、B=(a1+p,a2+q)、C=(a1+q,a2+p) D=B+C-A=(a1+p+q,a2+p+q) E=B+D-C=(a1+2p,a2+2q)即：[新試驗(yàn)點(diǎn)]＝[留下各點(diǎn)之和]－[去掉點(diǎn)](9-8)三、多因素基本單純形設(shè)有n個(gè)因素n＋1個(gè)定點(diǎn)構(gòu)成的n維空間單純形，設(shè)有一點(diǎn)A=(a1,a2,

a3,…

an)，步長(zhǎng)為a則其余各點(diǎn)為：

B=(a1+p,a2+q,a3+q,……an+q)C=(a1+q,a2+p,a3+q,……an+q)(n)=(a1+q,a2+q,…an-1+p,

an+q)(n+1)=(a1+q,a2+q,a3+q,……an+p)其中新點(diǎn)計(jì)算[新坐標(biāo)點(diǎn)]＝2×[n留下點(diǎn)的坐標(biāo)和]/n

－[去掉點(diǎn)坐標(biāo)](9-11)四、n，p，q取值對(duì)應(yīng)表由(9-8)我們可以算出n取不同值的p、q的取值n2345678pqn9101112131415pq0.9660.9430.9260.9110.9010.8920.8830.2590.2360.2190.2040.1940.1850.1760.8780.8720.8650.8610.8550.8540.8480.1710.1650.1580.1540.1480.1470.141n、q、p取值對(duì)應(yīng)表五、小結(jié)用前面的例子，對(duì)兩因素問題A、B、C構(gòu)成初始單純形，在此三點(diǎn)上進(jìn)行試驗(yàn)規(guī)則1：去掉最壞點(diǎn)，用其對(duì)稱反射點(diǎn)作新試點(diǎn)例A、B、C中，A為最壞點(diǎn)，去掉A點(diǎn)并取A的對(duì)稱點(diǎn)D點(diǎn)作為新試驗(yàn)點(diǎn)。D＝[留下各點(diǎn)之和]－[去掉點(diǎn)]＝B＋C－A在B、C、D三角形中繼續(xù)使用規(guī)則1，如果C為壞點(diǎn)，去點(diǎn)C點(diǎn)，取其反點(diǎn)E，此時(shí)C、D、E三點(diǎn)又構(gòu)成新的單純形。如果最壞點(diǎn)為D那么對(duì)稱點(diǎn)就會(huì)返回到與A重合，此時(shí)改用規(guī)則2規(guī)則2：去掉次壞點(diǎn)，用其對(duì)稱反射點(diǎn)作新試點(diǎn)對(duì)稱計(jì)算公式與前面相同經(jīng)過反復(fù)使用后，如果有一個(gè)點(diǎn)老是保留下來，必須使用規(guī)則3規(guī)則3：重復(fù)、停止和縮短步長(zhǎng)一般一個(gè)點(diǎn)勁3次單純形后仍未被淘汰，它可能是一個(gè)很好點(diǎn)，也可能是偶然性或試驗(yàn)誤差導(dǎo)致的假象。此時(shí)需要重復(fù)試驗(yàn)：結(jié)果不好，淘汰；結(jié)果已很滿意則停止試驗(yàn)反之則以它為起點(diǎn)縮短步長(zhǎng)，繼續(xù)試驗(yàn)六、特殊方法 前面介紹的單純形是正規(guī)的，任意兩點(diǎn)間的距離一樣，實(shí)際上，這個(gè)要求可以不要。尤其是由于各個(gè)因素所取的量綱不一樣（例如一個(gè)因素是溫度（℃），另一個(gè)因素是時(shí)間（秒）。即使量綱一樣所取的單位也可以不一樣。（一）直角單純形法 我們考慮雙因素模型，開始不從正三角形出發(fā)，而是從一個(gè)直角三角形出發(fā)，其頂點(diǎn)取值如下：=(a1,a2)=(a1+p1,a2)=(a1,a2+p2) 用圖表示如下a2+p2a2a1+2p1a1+p1a1因素2因素1

同樣比較三個(gè)頂點(diǎn)響應(yīng)值的結(jié)果，若最壞，則新點(diǎn)就用對(duì)稱公式

=+-=(a1+p1,a2+p2) 在得到點(diǎn)后，再用、、三點(diǎn)試驗(yàn)，比較其結(jié)果，若最壞，則取其對(duì)稱點(diǎn)做新試驗(yàn)點(diǎn)=+-=(a1+2p1,a2) 、、構(gòu)成一個(gè)新單純形，比較其結(jié)果，若最壞，則用規(guī)則2去掉次壞點(diǎn)，若次壞點(diǎn)為，則新點(diǎn)

=+-=(a1+2p1,a2-p2) 如此等等，有時(shí)還會(huì)使用規(guī)則3，直至結(jié)果滿意為止。一般在任意n個(gè)因素時(shí) =(a1,a2,

a3,…

an)

=(a1+p1,a2,a3,……an)

=(a1,a2+p2,a3,……an) ………… (n)=(a1,a2,…an-1+pn-1,

an) (n+1)=(a1,a2,a3,……an+pn)（二）、雙水平單純形法§7-3改進(jìn)單純形法為了解決優(yōu)化結(jié)果精度和優(yōu)化速度的矛盾，可以采用可變步長(zhǎng)推移單純形，此即改進(jìn)單純形法，既能加快優(yōu)化速度，又能獲得較好的優(yōu)化精度。改進(jìn)單純形法是1965年J．A．Nelder等提出來的，它是在基本單純形法的基礎(chǔ)上引入了反射、擴(kuò)大、收縮與整體收縮規(guī)則，變固定步長(zhǎng)為可變步長(zhǎng)，較好地解決了優(yōu)化速度與優(yōu)化精度之間的矛盾，是各種單純形優(yōu)化法中應(yīng)用最廣泛的一種單純形優(yōu)化方法。兩因素單純形的推移過程因素1因素2BACDEONA改進(jìn)單純形ND單純形的整體收縮因素1因素2ABCC’A’在單純形的推移過程中，新實(shí)驗(yàn)點(diǎn)在空間的位置坐標(biāo)按以下方法計(jì)算：討論：a＝1，此時(shí)(9-19)式變差基本單純形中新點(diǎn)的計(jì)算公式，此時(shí)新試驗(yàn)點(diǎn)為去掉點(diǎn)的等距離反射點(diǎn)，這時(shí)改進(jìn)單純形又變成了基本單純形a>1，按基本單純形法（a＝1）計(jì)算出新點(diǎn)后，對(duì)新試驗(yàn)點(diǎn)做試驗(yàn)得出新試驗(yàn)點(diǎn)的響應(yīng)值。如果新點(diǎn)的響應(yīng)值好，說明我們搜索方向正確，可以進(jìn)一步沿AD搜索。因此取a>1，稱為擴(kuò)大。如果擴(kuò)大點(diǎn)E不如反射點(diǎn)D好，則“擴(kuò)大”失敗，仍采用D，由反射點(diǎn)何留下點(diǎn)構(gòu)成的單純形BCD繼續(xù)優(yōu)化-1<a<0，按（a＝1）計(jì)算出來的反射點(diǎn)D的響應(yīng)值最壞，此時(shí)采用-1<a<0（稱為內(nèi)收縮）計(jì)算新試驗(yàn)點(diǎn)，此時(shí)形成新的單純形BNAC0<a<1，按基本單純形法（a＝1）計(jì)算除反射點(diǎn)D響應(yīng)值最壞。但比去掉點(diǎn)A響應(yīng)值好。此時(shí)采用0<a<1，稱為收縮，新試點(diǎn)仍按(9-19)式計(jì)算，此時(shí)形成新的單純形BCND如果去掉點(diǎn)與其反射點(diǎn)連線AD方向上所有點(diǎn)的響應(yīng)值都比去掉點(diǎn)A壞，則不能沿此方向搜索。這時(shí)應(yīng)以單純形中最好點(diǎn)為初點(diǎn)，到其它各點(diǎn)的一半為新點(diǎn)，構(gòu)成新的單純形BA’C’進(jìn)行優(yōu)化。此時(shí)步長(zhǎng)減半，稱為“整體收縮”§7-4加權(quán)形心法基本單純形和改進(jìn)單純形都是采用去掉點(diǎn)的反射方向?yàn)樾略囼?yàn)點(diǎn)的搜索方向，這就意味著，去掉點(diǎn)的反射方向作為近似的優(yōu)化方向，就是梯度變化最大的方向?qū)嶋H上，這個(gè)方向是一個(gè)近似的梯度最大方向，這樣的搜索結(jié)果可能導(dǎo)致搜索次數(shù)的增加和搜索結(jié)果精度的降低為了解決這個(gè)問題，提出了加權(quán)形心法，加權(quán)形心法利用加權(quán)形心代替單純的反射形心，使新點(diǎn)的搜索方向更接近實(shí)際的最優(yōu)方向因素1因素2BCOEE'O形心點(diǎn)O和加權(quán)形心點(diǎn)O如圖，使W、B、C三個(gè)頂點(diǎn)組成的一個(gè)二因素的優(yōu)化過程的一個(gè)單純形，并知W點(diǎn)的響應(yīng)最壞，B的響應(yīng)最好。如果搜索優(yōu)化過程中函數(shù)不出現(xiàn)異常，那么搜索最優(yōu)點(diǎn)的方向明顯應(yīng)當(dāng)更靠近WB的方向，而不是靠近WC的方向。因此可以通過加權(quán)的辦法來使搜索的方向由原來的WE（反射方向）變?yōu)閃E'方向（加權(quán)方向），此時(shí)用加權(quán)形心點(diǎn)O代替反射形心點(diǎn)O§7-5單純形優(yōu)化的參數(shù)選擇在試驗(yàn)中，我們只研究?jī)?yōu)化條件，可用基本單純形法時(shí)，首先必須確定研究的因素由于單純形法不受因素的限制，考察的因素可以相對(duì)的多些因素確定后，據(jù)分析儀器和試驗(yàn)要求，規(guī)定因素變化的上下限，據(jù)上下限的范圍確定步長(zhǎng)的大小。步長(zhǎng)較大，優(yōu)化速度加快，精度較差；步長(zhǎng)太小試驗(yàn)次數(shù)增多，優(yōu)化速度變慢一、試驗(yàn)指標(biāo)試驗(yàn)指標(biāo)是用于衡量和考核試驗(yàn)響應(yīng)的各種數(shù)值在分析測(cè)試中可將儀器響應(yīng)值作為試驗(yàn)指標(biāo)，但有時(shí)須轉(zhuǎn)換稱其它的數(shù)量，試驗(yàn)指標(biāo)是數(shù)量化的，以便直接比較結(jié)果的大小二、初始單純形的構(gòu)成本章第一節(jié)介紹的方法是根據(jù)初始點(diǎn)和步長(zhǎng)來計(jì)算初始單純形的各個(gè)頂點(diǎn)，各因素的步長(zhǎng)是相同的實(shí)際過程中，各因素步長(zhǎng)和單位并不相同，利用這種方法會(huì)變得很麻煩，在實(shí)際應(yīng)用中問題較多我們介紹下述兩個(gè)構(gòu)成初始單純形的方法（一）long系數(shù)表法D.E.Long提出一種用系數(shù)表構(gòu)成初始單純形各頂點(diǎn)的方法，可以解決試驗(yàn)設(shè)計(jì)中初始單純形的構(gòu)成問題使用時(shí)把表中的對(duì)應(yīng)值乘上該因素的步長(zhǎng)后，再加到初始點(diǎn)坐標(biāo)上1234567891010ABCDEFGHIJ01.000.500.500.500.500.500.500.500.500.50000.8660.2890.2890.2890.2890.2890.2890.2890.2890000.8170.2040.1580.2040.2040.2040.2040.20400000.7910.1580.1580.1580.1580.1580.158000000.7750.1290.1290.1290.1290.1290000000.7640.1090.1090.1090.10900000000.7560.0940.0940.094000000000.7500.0830.0830000000000.7450.07500000000000.742因素頂點(diǎn)Long系數(shù)表例：有一個(gè)二因素的設(shè)計(jì)過程，其初始點(diǎn)為(10.0,2.0)；步長(zhǎng)為1.0和0.5，據(jù)Long系數(shù)表來計(jì)算其余兩個(gè)頂點(diǎn)的坐標(biāo)頂點(diǎn)1：（10.0,2.0）頂點(diǎn)2：（10.0+1.00×1.0，1.0+0×0.5）

=（11.0,2.0）頂點(diǎn)3：（10.0+0.5×1.0，2.0+0.866×0.5）

=（10.5，2.433）（二）均勻設(shè)計(jì)表法利用Long系數(shù)表法所構(gòu)成的初始單純形各頂點(diǎn)在空間的分布是不均勻的，因此進(jìn)行的是不均勻優(yōu)化均勻設(shè)計(jì)表改變了這個(gè)缺點(diǎn)，使各頂點(diǎn)在空間均勻分布，這樣進(jìn)行的優(yōu)化就是整體的均勻優(yōu)化據(jù)所選因素的因素?cái)?shù)，確定一個(gè)比較合適的均勻表，使用時(shí)把表中的對(duì)應(yīng)數(shù)值乘以響應(yīng)因素的步長(zhǎng)，加到初始點(diǎn)坐標(biāo)上即可例：我們有一個(gè)四因素的優(yōu)化過程，因此可以選用四因素的均勻設(shè)計(jì)表。設(shè)初點(diǎn)為(1.0,1.0,1,0,1.0);步長(zhǎng)為0.5,1.0,1.5,2.0。要求計(jì)算初始單純形的各頂點(diǎn)四因素均勻設(shè)表U5(54)頂點(diǎn)1