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

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

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

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

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

小組成員：

研控計(jì)1320班：范冠男

習(xí)春苗

程丕建

王凱

郭萍

研控計(jì)?1322班：趙亮

成績(jī):_____________________________________

日期：2023年12月8日

一、作業(yè)題目

運(yùn)用復(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個(gè)設(shè)計(jì)點(diǎn)(通常取n+l[lK團(tuán)2n)作為初始復(fù)合形(多面體)的頂點(diǎn)。然后比

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

之外其余各點(diǎn)的中心為映射中心，尋找壞點(diǎn)的映射點(diǎn),一般說(shuō)來(lái)此映射點(diǎn)的

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

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

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

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

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

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

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

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

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

最優(yōu)值。

三、基本程序流程圖

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

收縮后的單純形頂點(diǎn)代替%

圖一、程序流程圖

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

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

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

2、理論結(jié)果：

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

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

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

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

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

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

線(xiàn)格子中都有一個(gè)初值。

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

4

圖三、64個(gè)初始點(diǎn)在定義域散點(diǎn)圖

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

初始點(diǎn)序號(hào)X0(l)X0(2)迭代次數(shù)過(guò)程最優(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個(gè)初始點(diǎn)尋優(yōu)登記表

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

軌跡，也即最大值的尋找過(guò)程。下圖為復(fù)合形法中找到最優(yōu)值時(shí)的尋優(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.形心點(diǎn)的軌跡_

0.1?/I-

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

05101520253035404550

迭代次數(shù)

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

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

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

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

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

1、復(fù)合形法

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

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

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

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

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

2、Matlab工具箱求解

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

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

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

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

初始點(diǎn)序號(hào)X0(1)X0(2)過(guò)程最優(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個(gè)初始點(diǎn)尋優(yōu)登記表

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

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

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

值，進(jìn)一步驗(yàn)證了分區(qū)的有效性。

六、總結(jié)

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

大這一問(wèn)題，提出將定義域區(qū)域進(jìn)行等分，然后對(duì)每小塊區(qū)域選取一個(gè)初始點(diǎn)進(jìn)

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

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

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

證。從仿真結(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=[]；%記錄每個(gè)初值迭代后最優(yōu)值的向量

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

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

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

m=8;%定義域提成8*8個(gè)塊數(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]

%?為運(yùn)算中止精度

%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]；%用來(lái)記錄每次迭代所產(chǎn)生的最壞點(diǎn)Xh

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

FXk=U；

while1

fori=l:k

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

end

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

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

traceFXk=［traceFXk,FX(k)］；

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

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);%除最壞點(diǎn)外其余K—1個(gè)頂點(diǎn)的形心點(diǎn)

gxc=subs(g,var,xc);

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

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í)反射系數(shù)alpha已經(jīng)小于e1

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

fori=1:k

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

end

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

alpha=a1pha⑵％則將反射系數(shù)減小為本來(lái)的一半，重新計(jì)算反射點(diǎn)

end

end

else

alpha=alpha/2；

end

eIse

fori=l:n%若形心點(diǎn)不可行，則分別用形心點(diǎn)xc(i)和最佳點(diǎn)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