最优化原理及应用

“最优化原理及应用”

［用C语言，或者Matlab,或者Fortran等编写一个完整的SimulatedAnnealing算法和

Genetic算法的优化程序。

解：此题采用Matlab语言编写一个完整的SA算法优化程序。在该程序中选用的代价函数

为：/(x)=sin(U-1.5)2)+U-6)2-3,初始的C0=1000,每一个阶段的Lk选为20,接受

概率设为0.6,迭代的终止条件为e<0.00001(e二旧-青初始值的选取范围为［-10,10］,

每次迭代的扰动C=C0/ko

的趋势如下列图所示:

经过SA算法得出的结果为：x1=5.6682f(x)=-3.88540

程序如下：

%退火算法

clearall

clc

C()=l()()();

x0=20*rand(1,1)-10;%取初始值

k=0;

Lk=20;

F=sin((x0-1.5)A2)+(xO-6)A2-3;%代价函数

dclta_x=6;%扰动

e=l;

epsilon=0.6;%接受概率

i=l；

while(e>0.00001)

k=k+l;

C=C0/k;

for(i=l:Lk)

vv=2*rand(l,l)-l;

xl=xO+w*deIta_x;%产生一个xi

Fl=xlA4-xlA3-15*xlA2+l;

dclla_f=Fl-F;

e=abs(delta_f);

if(Fl<F)

xO=xI;

F=F1;

X(i)=xl;

i=i+l;

else

prob=exp(-delta_f/C);

if(prob>epsilon)

xO=xI;

F=F1;

X(i)=i+1;

end

end

end

end

xO

F

下面为采用遗传算法的优化程序。该程序中的代价函数与上面的SA算法所用的一致。设

定变量的二进制码链长度为10,基因库中的二进制码链个数为10。自变量的取值区间为

[0J0],设定遗传算法的迭代次数为500。在每次迭代保存基因的选择中分别采用了均值法

和轮盘赌的方法，在保存、交换和异化的过程中每次都将最好的基因保存在基因库的最后

一行，即精英操作。

经过GA算法得出的结果为：xl=5.6696f(x)=-3.8851.

从图中我们可以看出SA和GA算法均找到了该代价函数的最小值点。在运行的过程中GA

的速度要明显快于SA。

程序如下：

%遗传算法

%F=sin((x-1.5)A2)+(x-6)A2-3;最优化问题的代价函数

%Q=1000-(sin((x-1.5)A2)+(x-6)A2-3);遗传算法中定义的fitness

clc

clearall

num=10;

length=10;

total=2A(lcngth)-1;

min=-5;%取值区间的长度

max=5;

G=100;

genome=round(rand(num,length));%定义自变量的随机二进制编码，长度为length

for(k=l:G)

X=zcros(l,num);%二进制转化为十进制

for(i=l:num)

for(j=length:-l:1)

X(i)=X(i)+genome(ij)*2A(length-j);

end

X(i)=X(i)/total*(max-min)+min;

end

for(i=l:num)%计算各变量的fitness

Q(i)=1000-(sin((X(i)-1.5)A2)+(X(i)-6)A2-3);

end

[order,location]=sort(Q);

bestgene=location(num);%最好的基因位置

BEST(k,:)=genome(bestgene,:);%最好的基因

%%保存

%q=sum(Q);

%vector=(Q/q)*num;

%vector=floor(vector);%将品质因数大于均值的gene选出来，保存到下次

%j=l；

%for(i=l:num)

%if(vector(i)==l)

%geneupdate(j,:)=genome(i,:);

%j=j+l；

%end

%end

%geneupdate(num,:)=BEST(k,:);

%保存％使用轮盘赌的筛选方法

q=sum(Q);

selectvariable=ceil(q)*rand(1,1);

j=h

while(1)

a=0;

i=l；

a=a+Q(i);

while(1)

if(a<selectvariable)

i=i+l;

a=a+Q(i);

else

geneupdate(j,:)=genome(i,:);

月+1；

break;

end

end

if(j==num)

break;

end

end

geneupdate(num,:)=BEST(k,:);

%交换

kk=l;

probc=0.5;

for(i=l:2:num-l)

variablel=rand(l,l);

variable2=floor((length-1)*rand(l,1)+1);%找出截断点

if(variablel<probc)

for(j=variable2:lengih)

a(kk)=gcncupdatc(i,j);

b(kk)=geneupdate(i+1,j);

kk=kk+l;

end

kk=l;

for(j=variable2:length)

geneupdate(i,j)=b(kk);

gcncupdatc(i+l,j)=a(kk);

kk=kk+l;

end

end

end

geneupdate(num,:)=BEST(k,:);

genome=geneupdate;

%异化

probt=().1;

for(i=l:num)

for(n=l:length)

variable3=rand(l,l);

if(variablc3<probt)

if(genome(i,n)==l)

genome(i,n)=0;

else

genome(i,n)=l;

end

end

end

end

geneupdate(num,:)=BEST(k,:);

genome=geneupdate;

end

x=0;

for(j=length:-l:l)

x=x+genome(num,j)*2A(length-j);

end

x=x/total*(max-min)+min;

x

F=sin((x-1.5)A2)+(x-6)A2-3;

F

2.利用模拟退火和遗传算法求函数/1)=2/一]_]的最小值点，xe[-l,l],x的精度控制在

0.001范围内。

解：在此题中所用的代价函数为:f(x)=2x2-x-\,初始的C0=10()(),每一阶段的Lk取为

20,接受概率设为()6迭代的终止条件为e<().()O()()()l(e=|61-尸|)。初始值x()的选取范围

为[-0.5,0.5],每次迭代的扰动双=2,C=C0/ko

八幻的趋势如下列图所示：

经过SA算法得出的结果为：x1=0.2505f(x)=-L1250o

由原函数我们可以容易地得出：f(x)的最小值为0.25。经过SA得到的最优解与真实值的差

值为0.0005,满足题目所给的精度要求。

程序如下：

%退火算法

clearall

clc

C0=1000;

x0=(2*rand(1,1)-1)*0.5;

k=0;

Lk=20;

F=2*xOA2-xO-l;

delta_x=2;

e=1;

epsilon=0.6;

while(O0.000001)

k=k+l;

C=C0/k;

for(i=1:Lk)

w=2*rand(l,l)-i;

x1=xO+w*delta_x;

Fl=2*xlA2-xl-l;

delta_f=Fl-F;

e=abs(delta_f);

if(Fl<F)

xO=xl;

F=F1;

else

prob=cxp(-dclta_17C);

if(prob>epsilon)

x()=x1;

F=F1;

end

end

end

end

xO

F

X=-l:0.1:l;

y=2*X.A2-X-l;

plot(X,y);

gridon;

set(gcf,'color1,'w');

下面利用GA算法来计算f(x)的最小值，为了到达题目中给定的精度要求，这里设定二进

制码链的长度为11，基因库中二进制码链的个数为10，自变量的取值区间定为：[-1,1]O

遗传算法的迭代次数为l()0o在每次迭代保存基因的选择中分别采用了均值法和轮盘赌的

方法，在保存、交换和异化的过程中每次都将最好的基因保存在基因库的最后一行，即精

英操作。

经过GA算法得出的结果为：x1=0.2496f(x)=-1.125Oo

满足题目中所给的精度要求。

程序如下：

%遗传算法

%F=2*xA2-x-l;最优化问题的代价函数

%Q=1000-(2*xA2-x-l);遗传算法中定义的fitness

cic

clearall

num=10;

lengthen；

total=2A(lcngth)-l;

min=-l;%取值区间的长度

max=1;

G=100;

genome=round(rand(num,length));%定义自变量的随机二进制编码，长度为length

for(k=l:G)

X=zeros(l,num);%二进制转化为十进制

for(i=l:num)

for(j=length:-l:l)

X(i)=X(i)+genome(i,j)*2A(length-j);

end

X(i)=X(i)/total*(max-min)+min;

end

for(i=l:num)%计算各变量的fitness

Q(i)=l000-(2*X(i)A2-X(i)-I);

end

forder,locationl=sort(Q);

bestgene=Iocation(num);%最好的基因位置

BEST(k,:)=genoiiie(beslgene,:);%最好的基因

%%保存

%q=sum(Q)；

%vector=(Q/q)*num;

%vector=floor(vector);%将品质因数大于均值的gene选出来，保存到下次

%J=1；

%for(i=l:num)

%if(vector(i)==l)

%geneupdate(j,:)=genome(i,:);

%j=j+h

%end

%end

%geneupdate(num,:)=BEST(k,:);

%保存％使用轮盘赌的筛选方法

q=sum(Q);

selectvariable=ceil(q)*rand(1,1);

j二l；

while(1)

a=0;

i=l；

a=a+Q(i);

while(1)

if(a<selectvariable)

i=i+1;

a=a+Q(i);

else

geneupdate(j,:)=genome(i,:);

j=j+l；

break;

end

end

if(j==iium)

break;

end

end

geneupdate(num,:)=BEST(k,:);

%交换

kk=l;

probc=0.5;

for(i=l:2:nuin-l)

variablel=rand(1,1);

variable2=floor((length-1)*rand(1J)+1);

if(variablel<probc)

for(j=variable2:length)

a(kk)=gcncupdatc(i,j);

b(kk)=geneupdate(i+l,j);

kk=kk+l;

end

kk=l;

for(j=variable2:length)

gencupdate(ij)=b(kk);

gcncupdatc(i+l,j)=a(kk);

kk=kk+l;

end

end

end

geneupdate(num,:)=BEST(k,:);

genome二geneupdate;

%异化

probt=().1;

for(i=l:num)

for(n=l:length)

variablu3=rand(1,1);

%n=floor(7*rand(1,1)+1);

if(variable3<probt)

if(genome(i,n)==l)

genome(i,n)=0;

else

gcnomc(i,n)=l;

end

end

end

end

geneupdate(num,:)=BEST(k,:);

genome二gencupdale;

end

x=();

for(j=length:-l:l)

x=x+genome(num,j)*2A(length-j);

end

x=x/tolal*(max-min)+min;

F=2*xA2-x-l;

F

3.利用模拟退火和遗传算法求函数/«)，)=2，+)，2的最小值点，工了£[一1,1],x的精度控制在

0.001范围内。

解:首先采用SA算法,取C0=1000,每阶段的Lk=100,接受概率取为0.5,设定迭代次

数K=100,为了加快收敛，令C0=C0/log(k)。x,y的扰动都定为0.1。从给定的代价函数

我们容易看出其最小值点是(0,0)o经过SA运算可以得到优化后的结果为：

xl=2.2i14e-004,yl=3.1916e-004o

x,y的收敛趋势如下列图所示：

结果到达了题目中的精度要求。

程序如下：

%SA退火算法计算F=2*xA2+yA2的最小值

clearall

cic

CO=IOOO;

x0=0.5*(2*rand(1,1)-1);

y0=0.5*(2*rand(1,1)-1)；

k=l;

Lk=l()OO;

F=2*xOA2+yOA2;

F

delta_x=O.1;

delta_y=O.1;

cpsilon=0.8;

K=l()();

1=1；

for(j=l:K)

k=k+l;

C0=C0/log(k);

for(i=l:Lk)

x1=x0+(2*rand(1,1)-1)*delta_x;

y1=y()+(2*rand(1,1)-1)*delta_y;

Fl=2*xlA2+ylA2;

delta_f=Fi-F;

if(Fl<F)

xO=xI;

yO=y1;

F=F1;

templ(l)=xl;

temp2(I)=yl;

1=1+1;

else

prob=exp(-delta_f/CO);

if(prob>epsilon)

xO=x1;

yO=yl;

F=F1;

tcmpl(l)=xl;

temp2(I)=yl;

1=1+1;

end

end

end

end

plot(tcmpl/r');

gridon;

set(gcf/color','w');

holdon

plot(temp2；g');

gridon;

set(gcf,'color','w1);

xO

yo

F

采用GA算法，为了到达题中所给的精度要求，所以取二进制码链的长度为22。其中前11

位表示x,后11位表示y。基因库里二进制码链的个数为25个。遗传迭代200次。采用轮

盘赌和均值筛选两种方式，进行精英操作。

得出的结果为：xl=4.8852e-004,y1=4.8852e-004。

将每次迭代的精英代码对应的x,y值画出来可以得到卜.列图：

得到的结果到达了题目中所要求的精度要求。

程序如下：

%应用遗传算法计算F=2*x"+yA2的最小值

ulu

clearall

num=25;

lengthx=l1;

length_y=l1;

length=length_x+length_y；

totai_x=2A(Iength_x)-1;

total_y=2A(Iength_y)-1;

min=-l;%取值区间的长度

max=1;

G=200;

k=l;

gcnomc=round(rand(num,length));%自变量定义的随机二进制编码，长度为length

for(i=l:G)%二进制转化为十进制

X=zeros(l,num);

Y=zeros(l,num);

for(i=l:num)

for(j=length_x:-1:1)

X(i)=X(i)+genome(iJ)*2A(length_x-j);

end

X(i)=X(i)/total_x*(max-min)+min;

end

for(i=l:num)

for(j=length:-1:length-length_x+1)

Y(i)=Y(i)+genome(i,j)*2A(length-j);

end

Y(i)=Y(i)/total_y*(max-min)+min;

end

for(i=l:num)%计算各变量的fitness

Q(i)=1000-(2*X(i)A2+Y(i)A2);

end

[order,loualion]=sorl(Q);

bestgene=location(num);%最好的基因位置

BEST(k,:)=genome(bestgene,:);%最好的基因

%保存

q=sum(Q);

vector=Q/q*num;

vector=floor(vector);%将品质因数大于均值的gene选出米，保存到下次

j=l；

for(i=l:num)

if(vector(i)==l)

geneupdate(j,:)=genome(i,:);

月+1；

end

end

geneupdate(num,:)=BEST(k,:);

%交换

kk=1;

probc=0.5;

for(i=l:2:num-l)

variablel=rand(1,1);

variablc2=floor((lcngth-1)*rand(1,1)+1);

if(variablel<probc)

for(j=variable2:length)

a(kk)=geneupdate(i.j);

b(kk)=geneupdate(i+1j);

kk=kk+l;

end

kk=l;

for(j=variable2:length)

geneupdate(i,j)=b(kk);

geneupdate(i+1,j)=a(kk);

kk-kk+1;

end

end

end

geneupdate(num,:)=BEST(k,:);

genome=geneupdate;

%异化

probt=0.2;

for(i=l:num)

for(n=l:length)

variable3=rand(l,l);

n=floor(7*rand(1,i)+1);

if(variable3<probt)

if(genomc(i,n)==1)

genome(i,n)=();

else

genome(i,n)=l;

end

end

end

end

geneupdate(num,:)=BEST(k,:);

genome=geneupdate;

k=k+l;

x=0;

for(j=length_x:-l:l)

x=x+genome(num,j)*2A(length_x-j);

end

x=x/totaLx*(max-min)+min;

x

y=0;

for(j=length:-l:length-length_x+1)

y=y+genome(num,j)*2A(length-j);

end

y=y/total_x*(max-min)+min;

y

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

X=zeros(1,G);

Y=zeros(l,G);

for(i=l:G)

for(j=length_x:-1:1)

X(i)=X(i)+BEST(iJ)*2A(length_x-j);

end

X(i)=X(i)/total_x*(max-min)+min;

end

for(i=l:G)

for(j=length:-l:length-length_x+1)

Y(i)=Y(i)+BEST(ij)*2A(length-j);

end

Y(i)=Y(i)/total_y*(max-min)+min;

end

plot(X；g');

gridon;

set(gcf/color','w');

holdon

plot(Y；f);

gridon;

set(gcf,'color','w1);

4.推销员问题是很有名的最正确化问题。假定一个推销员必须访问某区域里的N个村庄,

他从第一号村庄出发走访其他N-1个村庄。如果村庄i和村庄j之间的距离为小,那么他如

何选择路线才能使他走的距离最近？给出其最正确化解决方法。

解：在该题中假设有10个村庄，代价函数定为走遍所有村庄的距离和，固定一个起始点,

运用SA算法对其进行优化「得到以下的结果：

没有优化之前的路径：一号村庄的坐标为(46,26)。总长度为：554.6568

优化之后的路径：总长度为：237.0437

程序如下：

%利用SA算法实现推销员问题

clearall

clc

C0=50()()0()()()0;

Lk=2000;

N=10;

%position=round(100*rand(2,N));%随机给出10个村庄的位置坐标

position=[46,4,61,92,11,32,13,96,42,71;26,27,77,44,99,93,20,32,92,79;];

%给出1()个村庄的固定位置

F()=();

Fl=0;

k=l;

epsilon=0.5;

posorderO=l:N;

posordcrl=l:N;

for(i=l:N-l)

F()=F()+sqrt((position(1,posorder()(i+1))-position(1,posorder()(i)))A2

+(position(2,posorder()(i+l))-position(2,posorder0(i)))A2);

end

F0%代价函数

%循环开始的地方

while(1)

k=k+l;

C()=C()/log(k);

if(C0<eps)

break;

end

for(i=l:Lk)

posorder1=posorderO;%随机交换除第一个村庄之外的其余村庄的位置

p=ceil((N-1)*rand(1,1)+1);

while(p=l)%防止p=l,即防止交换第一个村庄

p=ceil((N-1)*rand(1,1)+1);

end

q=ceil((N-1)*rand(1,1)+1);

while(q==l)

q=ceil((N-1)*rand(1,1)+1);

end

temp=posorderl(p);

posorder1(p)=posorder1(q);

posorder1(q)=tcmp;

Fl=();

for(i=l:N-l)

Fl=F1+sqrt((position(1,posorder1(i+l))-position(1,posorderl(i)))A2

+(position(2,posorderl(i+1))-position(2,posorderl(i)))A2);

end

if(FKFO)

FO=F1;

posorder()=posorderl;

else

ifexp((F0-FI)/C0)>epsilon

FO=F1;

posorderO=posorder1;

end

end

end

end

for(i-l;N)

positionl(:,i)=position(:,posorder()(i));

end

figure(1)

setCgcf/color'/w1);

ploKposition1(1,:),position1(2,:));

holdon;

plot(position1(1position1(2,:),'*');

优化后的行走路线);

figure(2)

set(gcf/color','w');

plot(position(1,:),position(2,:));

holdon

plot(position(1,:),position(2,:)/**);

title=C没有经过优化的路线)；

5.如下递推公式：

是有名的WidrowLMS算法递推公式。其中Wn是权向量，Xn是输入向量，口是常数，

Cn是误差函数。该公式的推导是一个典型的二次方程式加随机编程处理最正确化问题，

请给出该公式的完整推导°I：参阅B.Widiuw的'Adaplivcsignalprocessing，教材和龚耀寰的“自适应

原理及应用”或其他有关自适应信号处理书籍)

T

解：由各变量的定义，^=dn-WXlt,最小均方误差MSE=E[会h针，

匕=暮=%萼=-2/“，根据递推公式：1％=%-〃▽〃，所以此讨=明+2延/,

oWkdWk

将毓=4-卬2”代入上式，并对两边求数学期望，可以得到：

T

用W”+J=E[Wn]+2^E[dnXn-WXnXn]，又因为E[d.X,1=P,E[XnX„]=R，

仇吗+J=仇此],所以可以求得w*=/rA

6.基阵方向图设计是阵设计的根本问题，对于等间隔线列阵，已经证明切比雪夫加权是最

正确权系数，其最正确化意义在于对于相同次瓣级，主瓣宽度最窄；而对于固定主瓣宽度

次瓣级最低(参见Urick”工程水声原理”)。假设有一6元等间隔线列阵，试利用模拟退火

或遗传算法求其最正确加权系数。并画出有关波束图*由切比雪夫加权法求得的最正确加权系

数为[0.3,069,1,1,0.69,0.3],可利用该系数求出方向图函数G0(。),0为空间角,范围[-90,90],构成代价

函数f=LHG(0)-G0(0川和品质函数F=C-fo

解：应用SA退火算法求一个6元等间隔线列阵的最正确加权系数，假设6元的等间隔线列阵

相邻阵元