復合形法完整版本

束優(yōu)化算法——復合形法

一、基本原理

復合形法的基本思路是在n維空間的可行域中選取K個設(shè)計點（通常?。┳鳛槌跏紡秃闲危ǘ嗝骟w）的頂點。然后比較復合形各頂點目標函數(shù)的大小，其中目標函數(shù)值最大的點作為壞點，以壞點之外其余各點的中心為映射中心，尋找壞點的映射點，一般說來此映射點的目標函數(shù)值總是小于壞點的，也就是說映射點優(yōu)于壞點。這時，以映射點替換壞點與原復合形除壞點之外其余各點構(gòu)成K個頂點的新的復合形。如此反復迭代計算，在可行域中不斷以目標函數(shù)值低的新點代替目標函數(shù)值最大的壞點從而構(gòu)成新復合形，使復合形不斷向最優(yōu)點移動和收縮，直至收縮到復合形的各頂點與其形心非常接近、滿足迭代精度要求時為止。最后輸出復合形各頂點中的目標函數(shù)值最小的頂點作為近似最優(yōu)點。

現(xiàn)以圖5所示二維不等式約束優(yōu)化問題來作進一步說明。其數(shù)學模型為D：

其中，，可稱為隱式約束條件，而邊界約束，可稱為顯式約束條件。

在可行域內(nèi)先選定四個點、、、(這里取)作為初始復合形的頂點，計算這四個點的目標函數(shù)值，并作比較，得出壞點和好點：(7)(8)

由圖5,可以看出點為好點，點為壞點，即。以、、三點的中心為映射中心，尋找壞點的映射點：（9）式中，a為映射系數(shù)，一般，通常取a=1.3。然后計算映射點處目標函數(shù)與壞點目標函數(shù)值相比是否下降，并同時檢查是否在可行域內(nèi)。如果下降性、可行性這兩方面都得到滿足，則以點替換點，由與、、共四個點構(gòu)成一個新復合形（如圖5中虛線所示)。這個新復合形肯定優(yōu)于原復合形；如果上述兩個條件不能同時滿足.則可將映射系數(shù)縮半，即，仍按式(9)迭代，重新取得新的映射點，使其同時滿足下降性、可行性條件。有時甚至要經(jīng)過多次縮減映射系數(shù)才能使回縮的映射點最后滿足這兩個條件。這時以回縮成功的映射點和、、構(gòu)成新復合形。構(gòu)成新復合形就完成了一輪迭代。以后再按上述方法進行迭代搜索，不斷地使復合形向著目標函數(shù)減小的方向移動和收縮，直到逼近最優(yōu)解。

通過以上說明，復合形尋優(yōu)可以歸為兩大步驟：第一步是在可行域內(nèi)構(gòu)成初始復合形，第二步是通過復合形的收縮和移動不斷調(diào)優(yōu)，逐步逼近最優(yōu)點。二、初始復合形的產(chǎn)生

初始復合形的全部K個頂點都必須在可行域內(nèi)。對于維數(shù)較低、不很復雜的優(yōu)化問題，可以人為地預先按實際情況決定K個可行設(shè)計點作為初始復合形的頂點；對于維數(shù)較高的優(yōu)化問題則多采用隨機方法產(chǎn)生初始復合形?，F(xiàn)將隨機方法產(chǎn)生初始復合形的過程闡述如下：

(一)確定一個可行點作為初始復合形的第一個頂點

在區(qū)間給定一點或調(diào)用(0,1)區(qū)間內(nèi)服從均勻分布的隨機數(shù)列在區(qū)間產(chǎn)生第一個隨機點的分量：（10）

檢驗是否可行。若非可行點，則調(diào)用隨機數(shù)，重新產(chǎn)生隨機點，直到為可行點。

(二)產(chǎn)生其他(K一1)個隨機點繼續(xù)調(diào)用隨機數(shù)，在區(qū)間產(chǎn)生其他(K一1)個隨機點：，，，其分量為(11)

(三)將非可行點調(diào)入可行域構(gòu)成初始復合形

用上述方法產(chǎn)生的K個點，除第一點已在可行域內(nèi)，其他(K一1)個隨機點未必都在可行域內(nèi)。因此應設(shè)法將不在可行域的所有隨機點逐一調(diào)入可行域。這就需要依次檢查，是否在可行域內(nèi)。檢查過程中如依次都在可行域內(nèi)，它們均作為初始復合形的頂點；至第點不在可行域內(nèi)，則應首先將點調(diào)入可行域。其步驟為：

1.求出已在可行域的q個點的點集的中心(12)

2.將點向點的方向推進，移到與的中點，即按下式產(chǎn)生新的點(13)

如果推移后的點已進入可行域，如圖6(a)所示，即點，則此點可作為初始復合形的第q+1個頂點;如果仍不滿足可行性條件，如圖6(b)所示，則仍按上式再次推移產(chǎn)生新的點，即點，使之更向推移。如此重復迭代推移，直到新點成為可行點為止。

3.繼續(xù)依次檢查，一旦遇到可行點，即作為初始復合形的頂點;一遇到不可行點則按上述方法處理，使之調(diào)入可行域。直到全部成為可行點，從而構(gòu)成了可行域內(nèi)的初始復合形。三、迭代過程及算法框圖

對于n個設(shè)計變量、僅有不等式約束的非線性最優(yōu)化問題，采用復合形法的具體迭代步驟如下：

(1)給定設(shè)計變量數(shù)目n，變量界限范圍，復合形頂點數(shù)目K，精度要求。

(2)產(chǎn)生初始復合形

如前所述得初始復合形K個頂點。

(3)計算復合形各頂點的目標函數(shù)值，在各頂點中找出最壞點和最好點轉(zhuǎn)入第(8)步。

(4)計算除壞點外其余各頂點的中心（14）

(5)檢查點的可行性。若不在可行域D內(nèi)，則D域可能是一個非凸集，如圖7所示。這時可在以點為起點、點為端點的超立方體中(二維則為長方形)利用隨機數(shù)產(chǎn)生新復合形的各個頂點，即以，然后轉(zhuǎn)回第(2)步;若在可行域，則進行下一步。

(6)尋求映射點式中映射系數(shù)a通常取1.3。亦須檢查點是否在可行域內(nèi)。若在可行域內(nèi)，則進行第(7)步;否則將映射系數(shù)a減半，即，再按上式計算新的映射點使其向可行域方向靠攏;若新的映射點仍在可行域外，則將a再次減半繼續(xù)重復迭代直到映射點進入可行域為止。而后進行下一步。

（7)比較映射點與最壞點的目標函數(shù)值，構(gòu)成新復合形。計算映射點的目標函數(shù)值并與最壞點的目標函數(shù)值相比較。若，則用替換點，即，構(gòu)成一個新復合形，返回第(3)步；否則將步長減半，即，返回第(6)步，重新計算新的回縮的映射點，循環(huán)迭代，直至，則以新的替換構(gòu)成新復合形，返回第(3)步。如果經(jīng)過若干次的減半映射系數(shù)a，直到a值小于一個預先給定的很小正數(shù)(通常取)，仍不能使映射點優(yōu)于最壞點，這說明該映射方向不利。為了改變映射方向，找出復合形各頂點中的次壞點，即(15)并以次壞點替換最壞點，即，返回第(4)步。

(8)檢驗是否滿足迭代終止條件反復執(zhí)行上述過程，復合形隨之收縮。在每一個新復合形構(gòu)成之時，均應檢驗終止條件以判別是否結(jié)束達代。當復合形縮得很小時，各頂點的