2023年復(fù)合形法大作業(yè)

優(yōu)化理論與最優(yōu)控制大作業(yè)

（2023--2023年度第1學(xué)期）

題目:___________復(fù)合形法大作業(yè)____________

院系：控制與計算機工程學(xué)院

小組成員：

研控計1320班：范冠男

習(xí)春苗

程丕建

王凱

郭萍

研控計?1322班：趙亮

成績:_____________________________________

日期：2023年12月8日

一、作業(yè)題目

運用復(fù)合形法求解Schaffer'sfunction

(sin2Jx?)-0.5----------

max/(X)=0.5--一絲~:…(-4<x,.<4i=1,

(l+0.001.(x；+x；))2|-----!

2)

注：本組各函數(shù)中的n值均取為2

二、復(fù)合形法的基本原理及本文思緒

1、復(fù)合形法原理:復(fù)合形法的基本思緒是在n維空間的可行域中選取

K個設(shè)計點(通常取n+l[lK團2n)作為初始復(fù)合形(多面體)的頂點。然后比

較復(fù)合形各頂點目的函數(shù)的大小，其中目的函數(shù)值最大的點作為壞點,以壞點

之外其余各點的中心為映射中心，尋找壞點的映射點,一般說來此映射點的

目的函數(shù)值總是小于壞點的，也就是說映射點優(yōu)于壞點。這時，以映射點替

換壞點與原復(fù)合形除壞點之外其余各點構(gòu)成K個頂點的新的復(fù)合形。如此

反復(fù)迭代計算，在可行域中不斷以目的函數(shù)值低的新點代替目的函數(shù)值最大

的壞點從而構(gòu)成新復(fù)合形，使復(fù)合形不斷向最優(yōu)點移動和收縮，直至收縮到

復(fù)合形的各頂點與其形心非常接近、滿足迭代精度規(guī)定期為止。最后輸出復(fù)

合形各頂點中的目的函數(shù)值最小的頂點作為近似最優(yōu)點。

2、本文思緒:本文在理解復(fù)合形法的基礎(chǔ)上，提出將定義域區(qū)域進

行等分，提成mXm個小塊。然后對每小塊區(qū)域選取一個初始點進行尋優(yōu)，

最后比較這些初值點找到的最優(yōu)值，并把最佳的一個最優(yōu)值作為最終的輸出

最優(yōu)值。

三、基本程序流程圖

使復(fù)合形向最好點可收縮

收縮后的單純形頂點代替%

圖一、程序流程圖

四、求解尋優(yōu)過程

1、函數(shù)三維圖形:

圖二、目的函數(shù)三維圖

2、理論結(jié)果：

由函數(shù)的三維圖形不難看出，該函數(shù)的理論最大值為1。即當X=0,Y=0,

時，Z=f(x)取最大值為1。故理論解為X=E0,0]T,f(X)=lo

3、尋優(yōu)過程：

本文在運用復(fù)合形法求解過程中，在平面區(qū)域內(nèi)將區(qū)域等提成為64小塊，

并在每個小塊中選取一個初始值作為復(fù)合形法的初始值進行尋優(yōu)計算，并將最終

的最優(yōu)值作為尋優(yōu)結(jié)果。在區(qū)域內(nèi)初始點散點圖如下，從中可以看到在每個網(wǎng)狀

線格子中都有一個初值。

初始點在區(qū)域散點圖

4

圖三、64個初始點在定義域散點圖

同時,本文選取部分初始值尋優(yōu)結(jié)果列入下表：

初始點序號X0(l)X0(2)迭代次數(shù)過程最優(yōu)值

1-3.-3.270.

2-2.03612987-3.240.

3-1.-3.210.

4-0.-3.370.

50.-3.460.

........................................

221.-1.230.

232.-1.230.

243.-1.500.

25-3.-0.210.

26-2.03612987-0.400.

........................................

60-0.3.390.

610.3.260.

621.3.220.99028409

632.3.490.

643.3.470.

表一、64個初始點尋優(yōu)登記表

為了清楚地展示復(fù)合形的尋優(yōu)過程，本文繪制了復(fù)合形法在迭代過程的尋優(yōu)

軌跡，也即最大值的尋找過程。下圖為復(fù)合形法中找到最優(yōu)值時的尋優(yōu)軌跡圖。

尋優(yōu)軌跡

1，二丁''''=丁'':

//\

0.9-;1/-

///

0.8-1；I-

0.7-!|；-

0.6-II，1-

㈣

金口5、丁1.

圖

0.4-?I-

03

、J尋優(yōu)軌跡(f(xh))-

02.形心點的軌跡_

0.1?/I-

0卜rr「「「I」」「rr;

05101520253035404550

迭代次數(shù)

圖四、全局最優(yōu)點的尋優(yōu)軌跡圖

4、尋優(yōu)結(jié)果：

由該方法找到的最優(yōu)解為X=[0.02955566；-0.00589362],此時最大值f(X)=

0.99909101o由此可知,該結(jié)果與理論值很接近的，證明了算法的有效性。

五、尋優(yōu)分析與探討

1、復(fù)合形法

通過上面的求解過程，我們得出并不是任意給定的初始點都能找到全局最

優(yōu)點,也即函數(shù)的最大值。本文通過在定義域內(nèi)選取大量的初始點來進行優(yōu)化求

解，并且在將區(qū)域提成64塊時找到了最優(yōu)點。但是事實上在這64個初始點中，

能找到最優(yōu)點的概率還是很低的。當然，通過仿真實驗我們還發(fā)現(xiàn)隨著在定義域

內(nèi)選取的初始點越多，也即分的區(qū)域塊數(shù)越多，找到最優(yōu)點的概率越大。

2、Matlab工具箱求解

為了驗證分區(qū)選取初始點的有效性，本文還通過Matlab中自帶的優(yōu)化

工具箱，即求解非線性規(guī)劃的fmincon命令來求取該函數(shù)的最大值。事實上，

對于給定函數(shù)解析式的非線性函數(shù)，該方法比復(fù)合形法要更有效。下表為結(jié)合初

始點分區(qū)選擇和非線性規(guī)劃方法求解該函數(shù)最值的過程。

初始點序號X0(1)X0(2)過程最優(yōu)值

1-3.-3.0.

2-0.75535277-3.0.

31.-3.0.99028409

43.-3.0.

5-3.-0.755352770.

6-0.75535277-0.755352770.

71.-0.755352770.

83.-0.755352770.

9-3.1.0.99028409

10-0.755352771.0.

111.1.0.

123.1.0.99028409

13-3.3.0.

14-0.755352773.0.

151.3.0.99028409

163.3.0.

表二、16個初始點尋優(yōu)登記表

由此表可知，本文僅將定義域提成16塊即找到3次全局最優(yōu)點（即表中綠色

部分初始點）。同時，本文也做過仿真實驗，當分的區(qū)域塊數(shù)越大，找到全局最優(yōu)的

機率越大。而對于尋優(yōu)而言，我們只需找到一次全局最優(yōu)點即得到該函數(shù)的最大

值，進一步驗證了分區(qū)的有效性。

六、總結(jié)

本文在理解復(fù)合形法的基礎(chǔ)上，針對復(fù)合形法尋優(yōu)過程對初值的依賴性很

大這一問題，提出將定義域區(qū)域進行等分，然后對每小塊區(qū)域選取一個初始點進

行尋優(yōu)，然后比較這些初值點找到的最優(yōu)值,把最佳的一個最為最終的最優(yōu)值。實

驗證明該方法很有效。同時，我們也結(jié)識到復(fù)合形法也存在一定的問題，運算比較

慢。本文通過Matlab求解非線性規(guī)劃的方法進一步對定義域分區(qū)的思想進行驗

證。從仿真結(jié)果中結(jié)果中可以看出，這種方法比復(fù)合形法更有效。

七、附錄

1、目的函數(shù)的三維圖形繪制程序

x=—4:0.1:4;

y=-4:0.1:4;

[XY]=meshgrid(x,y);

A

Z=O.5-(sin((sqrt(X.2+Y,"2))).-2-0.5)./(1+0.001*(X.人2+Y,八2)).八2;

mesh(X,Y,Z)

xlabel('X');

x1abe1('Y1);

xlabe1CZ');

2、復(fù)合形法求解程序如下:

symsxlx2

f=-(0.5-(sin((sqrt(x1.人2+x2.八2))).-2—0.5)./(1+0.001*(x1.A2+x2.A2)).A

2);%目的函數(shù)

a=[—4;—4]；

b=[4;4];

alpha=1;

var=[xl;x2];

e=l.0e-8;

el=1.Oe-6；

sita=0.5;

M=[]；%記錄每個初值迭代后最優(yōu)值的向量

W=口;％記錄各個初始值取最優(yōu)值時的解向量

t=口；％記錄各個初始值取最優(yōu)值時的解向量

D=[];%記錄各個初始值取最優(yōu)值時的迭代次數(shù)

m=8;%定義域提成8*8個塊數(shù)

al=-4;

b1=4；

z=zeros(l,m);

X0=zeros(2,m*m);

fbri=1:m

z(i)=al+(b1-al)/m*(i—1)+rand(b1-al)/m；

end

fori=1：m

fbrj=l:m

XO(l,i+m*(j-l))=z(i);

end

end

fbri=l:m

W=[Wones(l,m)*z(i)];

end

XO(2,:)=W;

fori=l:m*m

[x,d,minf]=chi1dfun(f,XO(:,i),a,b,alpha,sita,var,e,el);

M=LM,minfj;

t=[t,x];

D=[D,d];

end

[maxfindex]=min(M)

x=t(:,index)

dl=D(index)

function[x,d,minf]=childfun(f,xO,a,b,alpha,sita,var,e,e1)

%f為目的函數(shù)

%%g為約束條件

%a為xi的下限a=[al；a2;…;an]

%b為xi的上限b=[bl;b2;…；bn]

%alpha為反射系數(shù)o

%var為自變量向量var=[xl;x2;…;xn]

%?為運算中止精度

%el為反射系數(shù)收縮下限

%sita為緊縮系數(shù)

aa=a;

bb=b;

n=2;

k=3;

while!

fx=zeros([l,k]);

X=zeros([n,k])；

g=[var-aavar+bb1;%約束函數(shù)g(X)

%產(chǎn)生初值

X(:,1)=xO;

fori=2:k

r=abs(rand([2,ID);

X(:,i)=aa+r.*(bb—aa);

end

%%尋優(yōu)

traceFXk=[0]；%用來記錄每次迭代所產(chǎn)生的最壞點Xh

tracefxc0=[0];%用來記錄每次迭代所產(chǎn)生的形心點Xc0

FXk=U；

while1

fori=l:k

fx(i)=subs(f,var,X(:,i));%計算復(fù)合形所有頂點的函數(shù)值

end

[FX,IX]=sort(fx);%對復(fù)合形所有頂點的函數(shù)值從小到大排序

Xsorted=X(:,IX);%得到排序后的函數(shù)值所相應(yīng)的x值

traceFXk=［traceFXk,FX(k)］；

xcO=sum(Xsorted,2)/k;%復(fù)合形所有頂點的形心點

fxc0=subs(f,var,xcO);

tracefxc0=EtracefxcO,fxc0］；

Sum=0;

fori=l:k

Sum=Sum+(FX(i)-fxcO)"2；

end

E=sqrt(Sum/k);%終止迭代條件

ifE<=e

x=Xsorted(:,l);%令x=xL

break;

eIse

xc=sum(Xsorted(:,l：(k-1)),2)/(k-1);%除最壞點外其余K—1個頂點的形心點

gxc=subs(g,var,xc);

ifmin(gxc)>=0%若形心點滿足約束

xr=xc+a1pha*(xc—Xsorted(:,k))；

fxr=subs(f,var,xr);

gxr=subs(g,var,xr);

ifmin(gxr)>=0

iffxr<FX(k)%若曲「)<￡(xh),則令xh=xi?，產(chǎn)生新的復(fù)合形

Xsorted(:,k)=xr;

e1se

ifalpha<=el%若戈乂r)>f(xh),但此時反射系數(shù)alpha已經(jīng)小于e1

xO=Xsorted(:,1);%則需將復(fù)合形中的所有頂點向最佳點收縮以產(chǎn)生新的復(fù)合形

fori=1:k

Xsorted(：,i)=x0+sita*(Xsorted(:,i)-x0);

end

e1se%若f(xr)>f(xh),但此時反射系數(shù)alpha仍大于e1

alpha=a1pha⑵％則將反射系數(shù)減小為本來的一半，重新計算反射點

end

end

else

alpha=alpha/2；

end

eIse

fori=l:n%若形心點不可行，則分別用形心點xc(i)和最佳點xL(i)代替變量x

i的上下限

ifxc(i)<Xsorted(i,l)

aa(i)=xc(i);

bb(i)=Xsorted(i,1);

else

aa(i)=Xsorted(i,1);

bb(i)=xc(i);

end

end

break；

end

end

X=Xsorted；%得到新的復(fù)合形

end

ifaa==a&bb==b

break；

else

continue;

end

end

format1ong

minf=subs(f,var,x)

minfl=minf*ones(1,length