最优化DFP算法报告
最优化DFP算法姓名：施政学号：1010010125 班级：1 班专业：通信与信息系统
目录
1 算法流程图 (1)
1.1DFP算法的流程图 (1)
1.2 黄金分割法流程图 (1)
1.3 回退法计算初始区间的算法 (2)
2 测试函数 (3)
2.1 二维、二次函数 (3)
2.2 二维、高次函数 (3)
2.3 高维、二次函数 (4)
2.4 高维、高次函数 (4)
3 运行结果及分析 (5)
4 Matlab源程序 (6)
4.1 主函数 (6)
4.2 DFP算法函数 (8)
4.3 黄金分割法函数 (9)
4.4 回退法求解初始区间 (10)
4.5 计算测试函数的值 (11)
4.6 计算测试函数的梯度 (12)
5 参考文献 (12)
1 算法流程图
对于DFP算法主要涉及到3个主要的算法，分别是：利用回退法计算初始区间、利用黄金分割法进行一维搜索、然后利用DFP算法计算最小点对应的自变量的值。
下面分别画出了这三个算法流程图。
1.1DFP算法的流程图
设定控制误差为ε；输入的初始点坐标是0x；0E是与0x同维的单位阵。
图 1
1.2 黄金分割法流程图
给定精确度ε>0;当区间长度小于等于ε时，即停止运行，同时取x=(a+b)/2作为最小点坐标。
在给定初始区间[a,b]内，求最小点时对应的α值，要保证α是大于等于零的，否则函数值就不是朝下降方向递降的了。在本算法中保证初始区间的端点是大于等于零的，就可以满足这一条件了。
算法如下图所示：
图 2
1.3 回退法计算初始区间的算法
针对这个算法,参考文献[1]上面利用的回退法不能保证a ，b 两个端点的值大于零，因为利用黄金分割法求α时，α肯定是大于等于零的，所以可以对书上的算法适当的改进。初始的点是0x ；步长是x Δ；算法如下：
图 3
注意：上面的算法是针对一维的情况，所以在计算0x ；1x ；2x 时，应该注意使
用0000*x a t p =+；0a 代表的是对应DFP 算法上次迭代的自变量的坐标值，0p 代表的是0a 点的梯度，0t 开始的值是0；同样有1010*x a t p =+；2020*x a t p =+；10t t t =+Δ；
21t t t =+Δ。注意t Δ的变化，算法中已显示其变化规律。
2 测试函数
2.1 二维、二次函数
对于二维、二次的测试函数，算法中应用的是First De Jong function(sphere) [3]。
221212(,)f x x x x =+…………………………………………..（式2.1）
下面就是函数对应的3维图形，从图4可以看出其最小点，在(x 1,x 2)=(0,0),该点对应的函数值是0。也是该函数全局极小点。
图 4
2.2 二维、高次函数
对于二维、高次的测试函数，算法中应用的是Goldstein-Price's function [3]。
2222121211212(,)(1(1))(191431463))Gold f x x x x x x x x x x =+++??+?++?
2
2
12112122(30(23)2)(1832483627))x x x x x x x x +???++?+………..（式2.2）
其中，22,1,2i x i ?≤≤=
下面就是该函数对应的三维图形，该函数的全局极小点是(x1,x2)=(0,-1)，f(x 1,x 2)=3。
图 5
2.3 高维、二次函数
对于高维、二次的测试函数，算法中应用的是Axis parallel hyper-ellipsoid function [3]。
2121
(,,,)n
n i i f x x x i x ==?∑"…………………………………………....（式2.3）
其中， 5.12 5.12,1,2,,i x i n ?≤≤="
显然，可以看出，其极小点对应的i x =0，且12(,,,)n f x x x "极小点的值是0。
2.4 高维、高次函数
在这里，算法中利用到了两个测试函数，分别是Rosenbrock's valley (De Jong's function
2)[2]和Sum of different power function [3]。 1.Rosenbrock's valley (De Jong's function 2)
1
2221211
(,,,)100()(1)n n i i i i f x x x x x x ?+==?+?∑"……………………….………....（式2.4）
2.048 2.048,1,2,,i x i n ?≤≤="
对应的极小点坐标是12(,,,)(1,1,,1)n x x x =""，且此时对应的极小点的函数值是0。 2. Sum of different power function
1121
(,,,)||n
i n i i f x x x x +==∑"…..............................................…………….………....（式2.5）
11,1,2,,i x i n ?≤≤="
对应的极小点坐标是12(,,,)(0,0,,0)n x x x =""，且此时对应的极小点的函数值是0。
3 运行结果及分析
以下是DFP算法对四类测试函数(5种)运行的结果，如下表所示：
从上表中可以看出，迭代的快慢要看运行时间，不能只看迭代次数，测试函数二、三就说明了这个问题，显然是高维、二次函数较二维、高次函数收敛性质更好。这个也说明DFP 算法对二次函数的求解非常有效，因为它是从二次函数的性质推出来的。所以对于其他函数来说，需要改进算法，来提高收敛速度。
从上表中还可以看到，对于二维、二次函数，在实际的求解中，实际只需要两步就可以了，但是由于计算机的误差，需要三步才能完成。所以、说计算机中的误差是不容忽视的，有时可能会导致收敛的速度不是很理想。
从上图可以看到，最终结果与理想的结果非常靠近。要提高收敛的效果，可以通过改变控制误差来实现。
4Matlab源程序
下面是程序的框架，也就是程序的调用关系：
4.1 主函数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:main.m %% %%该函数是DFP算法的主函数，%% %%功能：调用5次DFP算法分别对5个函数进行最优化的计算%% %%输出: 迭代的次数、运行的时间、对应的最优化坐标、以及函数值%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear
clc
disp('*********************************************************************************')
disp('*********************************************************************************')
disp(' 最优化DFP算法' ) disp('*********************************************************************************')
disp('*********************************************************************************')
disp('利用DFP算法对以下4种函数求其最小值，其中后两种是相同的类型，只是第五种阶次高于第四种：')
disp(' ')
disp('----------------------------------------------------------------------------------')
disp(' ')
disp('1.测试函数1(二维、二次)：Second De Jong function(Rosenbrock''s saddle)')
disp(' f(x,y)=x^2+y^2')
disp(' ')
disp('----------------------------------------------------------------------------------')
disp(' ')
disp('2.测试函数2(二维、高次):Goldstein-Price''s function')
disp(' f(x,y)=(1+(x+y+1)^2*(19-4*x+3*x^2-14*y+6*x*y+3*y^2))*')
disp(' (30+(2*x-3*y)^2*(18-32*x+12*x^2+48*y-36*x*y+27*y^2))')
disp(' ')
disp('----------------------------------------------------------------------------------')
disp(' ') disp('3.测试函数3(高维、二次):Axis parallel hyper-ellipsoid function')
disp(' f(x1,x2,...xn)=x1^2+2*x2^2+...+n*xn^2')
disp(' ') disp('----------------------------------------------------------------------------------')
disp(' ') disp('4.测试函数4(高维、高次):Rosenbrock''s valley (De Jong''s function 2)')
disp(' f(x1,x2,...xn)=(100*(x2-x1^2)^2+(1-x1)^2)+...+100*(xi+1-xi^2)^2+(1-xi)^2+...')
disp(' 100*(xn-xn-1^2)^2+(1-xn-1)^2')
disp(' ') disp('----------------------------------------------------------------------------------')
disp(' ') disp('5.测试函数5(高维、高次):Sum of different power functions')
disp(' f(x1,x2,...xn)=|x1|^2+|x2|^2+...+|xn|^2')
disp(' ') disp('*******************************运行代码*******************************************') disp(' ') for i=1:5
disp(['利用测试函数',num2str(i),'检验DFP算法，运行结果如下：'])
switch i
case 1
disp(' f(x,y)=x^2+y^2')
DFP_algorithm([20;30],i);
disp(' ') disp('---------------------------------------------------------------------')
disp(' ') case 2
disp(' f(x,y)=(1+(x+y+1)^2*(19-4*x+3*x^2-14*y+6*x*y+3*y^2))*')
disp(' (30+(2*x-3*y)^2*(18-32*x+12*x^2+48*y-36*x*y+27*y^2))')
DFP_algorithm([0.4;0.3],i);
disp(' ') disp('---------------------------------------------------------------------')
disp(' ') case 3
disp(' f(x1,x2,...xn)=x1^2+2*x2^2+...+n*xn^2')
DFP_algorithm(ones(10,1),i);
disp(' ') disp('---------------------------------------------------------------------')
disp(' ') case 4
disp(' f(x1,x2,...xn)=(100*(x2-x1^2)^2+(1-x1)^2)+...+100*(xi+1-xi^2)^2+(1-xi)^2+...')
disp(' 100*(xn-xn-1^2)^2+(1-xn-1)^2')
DFP_algorithm(zeros(10,1),i);
disp(' ')
disp('---------------------------------------------------------------------')
disp(' ') otherwise
disp(' f(x1,x2,...xn)=|x1|^2+|x2|^2+...+|xn|^2')
DFP_algorithm(ones(10,1),i);
disp(' ')
disp('---------------------------------------------------------------------')
disp(' ') end
end
disp('*******************************运行结束*******************************************') 4.2 DFP算法函数
function optimal_x=DFP_algorithm(x0,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:DFP_algorithm.m %% %%该函数利用DFP算法来计算其目标函数的最小点%% %%输入参数:初始点x0、以及对应的测试函数的序号k %% %%输出参数:最优化的点坐标optimal_x %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% tic
number_iteration=0; %迭代初始值
n=length(x0);
H0=eye(n); %产生H0的初始矩阵
g0=tf_grads(x0,k);
ipsita=0.000001; %精度
x1=x0;
g1=g0;
while(norm(g1)>ipsita)
p0=-H0*g0;
alpha=golden_section_method(x0,p0,k); %利用黄金分割法求解最优的alpha
x1=x0+alpha*p0;
g1=tf_grads(x1,k); %计算梯度
s0=x1-x0;
y0=g1-g0;
H1=H0-H0*y0*y0'*H0/(y0'*H0*y0)+s0*s0'/(y0'*s0); %更新H0
x0=x1;
H0=H1;
g0=g1;
number_iteration=number_iteration+1; %迭代计数
end
toc
disp(['迭代次数：',num2str(number_iteration)])
disp(['运行时间：',num2str(toc),' seconds'])
disp('对应的最小值点的坐标和对应的函数取值：')
optimal_x=x0
minimum_test_function=test_function(x0,k)
pause(3);
4.3 黄金分割法函数
function optimal_alpha=golden_section_method(x0,p0,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:golden_section_method.m %% %%该函数利用黄金分割法来计算极小点%% %%输入参数:x0对应的前一个所求的最优点的坐标；%% %%输入参数:p0对应x0电脑的梯度；%% %%输入参数:k对应的是测试函数的序号；%% %%输出参数: 算法得到最优的alpha %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [a,b]=initial_interval(x0,p0,k); %利用进退法求初始区间[a,b]
ipsita=0.01;
t1=a+0.382*(b-a);
x1=x0+t1*p0;
f_x1=test_function(x1,k);
t2=a+0.618*(b-a);
x2=x0+t2*p0;
f_x2=test_function(x2,k);
continue_run=true; %程序运行的条件，没有结果则为真
while(continue_run)
if abs(b-a)<=ipsita %满足精度条件则停止程序
optimal_alpha=(a+b)/2;
continue_run=false;
else
if f_x1 b=t2; t2=t1; f_x2=f_x1; t1=a+0.382*(b-a); x1=x0+t1*p0; f_x1=test_function(x1,k); elseif f_x1==f_x2 a=t1; b=t2; t1=a+0.382*(b-a); t2=a+0.618*(b-a); x1=x0+t1*p0; f_x1=test_function(x1,k); x2=x0+t2*p0; f_x2=test_function(x2,k); else a=t1; t1=t2; f_x1=f_x2; t2=a+0.618*(b-a); x2=x0+t2*p0; f_x2=test_function(x2,k); end end end 4.4 回退法求解初始区间 function [a,b]=initial_interval(a0,p0,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:initial_interval.m %% %%该函数利用进退法来求f(x)的初始区间%% %%输入参数:x0是初始点；delta_t(>0)是步长；p0是x0点对应的梯度；%% %%输入参数:k对应的是测试函数的序号；%% %%输出参数:a是初始区间的左端点；b是初始区间的右端点,保证a，b都大于零%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% continue_run=true; %程序运行的条件，没有结果则为真 delta_t=0.01; %步长 t0=0; x0=a0+t0*p0; f_x0=test_function(x0,k); %计算测试函数的值 t1=t0+delta_t; x1=a0+t1*p0; f_x1=test_function(x1,k); if f_x0<=f_x1 a=t0; b=t1; else while(continue_run) delta_t=2*delta_t; t2=t1+delta_t; x2=a0+t2*p0; f_x2=test_function(x2,k); if f_x0<=f_x2 a=t0; b=t2; continue_run=false; else t0=t1; f_x0=f_x1; t1=t2; f_x1=f_x2; end end end 4.5 计算测试函数的值 function f=test_function(x,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:test_function.m %% %%该函数是要算法的测试函数%% %%输入参数:x是要计算的函数值；k对应的是测试函数的序号%% %%输出参数:f是要输出的函数值%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% switch k case 1 f=x(1)^2+x(2)^2; %测试函数1(二维、二次) %Second De Jong function(Rosenbrock's saddle) case 2 f=(1+(x(1)+x(2)+1)^2*(19-4*x(1)+3*x(1)^2-14*x(2)+6*x(1)*x(2)+3*x(2)^2))... *(30+(2*x(1)-3*x(2))^2*(18-32*x(1)+12*x(1)^2+48*x(2)-36*x(1)*x(2)+27*x(2)^2)); %测试函数2(二维、高次)： %Goldstein-Price's function case 3 i=1:length(x); f=sum(i'.*x.^2); %测试函数3(高维、二次): %Axis parallel hyper-ellipsoid function case 4 f=sum(100*(x(2:end)-x(1:end-1).^2).^2+(1-x(1:end-1)).^2); %测试函数4(高维、高次) %Rosenbrock's valley (De Jong's function 2) otherwise f=sum(abs(x).^((2:(length(x)+1))')); %测试函数4(高维、高次) %Sum of different power functions end 4.6 计算测试函数的梯度 function g=tf_grads(x,k) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%File:tf_grads.m %% %%该函数用来计算梯度%% %%输入参数:x对应的函数点坐标；k对应的是测试函数的序号；%% %%输出参数:g是x点对应的梯度%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% switch k case 1 g=[2*x(1);2*x(2)]; %测试函数1的梯度(二维、二次) case 2 g=[(2*(x(1)+x(2)+1)*(19-4*x(1)+3*x(1)^2-14*x(2)+6*x(1)*x(2)+3*x(2)^2)+(x(1)+... x(2)+1)^2*(-4+6*x(1)+6*x(2)))*(30+(2*x(1)-3*x(2))^2*(18-32*x(1)+12*x(1)^2+... 48*x(2)-36*x(1)*x(2)+27*x(2)^2))+(1+(x(1)+x(2)+1)^2*(19-4*x(1)+3*x(1)^2-... 14*x(2)+6*x(1)*x(2)+3*x(2)^2))*(4*(2*x(1)-3*x(2))*(18-32*x(1)+12*x(1)^2+... 48*x(2)-36*x(1)*x(2)+27*x(2)^2)+(2*x(1)-3*x(2))^2*(-32+24*x(1)-36*x(2)))... ;(2*(x(1)+x(2)+1)*(19-4*x(1)+3*x(1)^2-14*x(2)+6*x(1)*x(2)+3*x(2)^2)+(x(1)+... x(2)+1)^2*(-14+6*x(1)+6*x(2)))*(30+(2*x(1)-3*x(2))^2*(18-32*x(1)+12*x(1)^2+... 48*x(2)-36*x(1)*x(2)+27*x(2)^2))+(1+(x(1)+x(2)+1)^2*(19-4*x(1)+3*x(1)^2-... 14*x(2)+6*x(1)*x(2)+3*x(2)^2))*(-6*(2*x(1)-3*x(2))*(18-32*x(1)+12*x(1)^2+... 48*x(2)-36*x(1)*x(2)+27*x(2)^2)+(2*x(1)-3*x(2))^2*(48-36*x(1)+54*x(2)))]; %测试函数2的梯度(二维、高次) case 3 i=1:length(x); g=2*i'.*x; %测试函数3的梯度(多维、二次) case 4 g1=[-400*(x(2:end)-x(1:(end-1)).^2).*x(1:(end-1))-2*(1-x(1:(end-1)));0]; g2=[0;200*(x(2:end)-x(1:(end-1)).^2)]; g=g1+g2; %测试函数4的梯度(多维、高次) otherwise g=(2:(length(x)+1))'.*(2*(x>=0)-1).*abs(x).^((1:length(x))'); %测试函数5的梯度(多维、高次) end 5 参考文献 [1] 解可新,韩健,林友联.最优化方法（修订版）[M].天津：天津大学出版社，2008：12-123 [2] Rainer Storn&Kenneth Price.Differential Evolution - A simple and efficient adaptive scheme for global optimization over continuous spaces[J].1995,5 [3] https://www.wendangku.net/doc/0114204552.html,/docu/fcnindex-01.html#P89_3085 最优化方法 课程设计报告班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日 目录 一、摘要 (1) 二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (4) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (11) 三、最速下降法 (11) 3.1 最速下降法的基本思路 (11) 3.2 算法流程图 (13) 3.3 用matlab编写源程序 (13) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (17) 4.1 惩罚函数法的基本思路 (17) 4.2 算法流程图 (18) 4.3 用matlab编写源程序 (18) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (20) 六、参考文献 (20) 一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB 这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数法 最优化方法实验报告Numerical Linear Algebra And Its Applications 学生所在学院：理学院 学生所在班级：计算数学10-1 学生姓名：甘纯 指导教师：单锐 教务处 2013年5月 实验一 实验名称：熟悉matlab基本功能 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。 二、实验内容： 1. 全面了解MATLAB系统 2. 实验常用工具的具体操作和功能 实验二 实验名称：一维搜索方法的MATLAB实现 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： (一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索 算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当()()k k f f λμ≤转步骤（4）。 （3）置 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5） 第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。 最优化DFP算法姓名：施政学号：1010010125 班级：1 班专业：通信与信息系统 目录 1 算法流程图 (1) 1.1DFP算法的流程图 (1) 1.2 黄金分割法流程图 (1) 1.3 回退法计算初始区间的算法 (2) 2 测试函数 (3) 2.1 二维、二次函数 (3) 2.2 二维、高次函数 (3) 2.3 高维、二次函数 (4) 2.4 高维、高次函数 (4) 3 运行结果及分析 (5) 4 Matlab源程序 (6) 4.1 主函数 (6) 4.2 DFP算法函数 (8) 4.3 黄金分割法函数 (9) 4.4 回退法求解初始区间 (10) 4.5 计算测试函数的值 (11) 4.6 计算测试函数的梯度 (12) 5 参考文献 (12) 1 算法流程图 对于DFP算法主要涉及到3个主要的算法，分别是：利用回退法计算初始区间、利用黄金分割法进行一维搜索、然后利用DFP算法计算最小点对应的自变量的值。 下面分别画出了这三个算法流程图。 1.1DFP算法的流程图 设定控制误差为ε；输入的初始点坐标是0x；0E是与0x同维的单位阵。 图 1 1.2 黄金分割法流程图 给定精确度ε>0;当区间长度小于等于ε时，即停止运行，同时取x=(a+b)/2作为最小点坐标。 在给定初始区间[a,b]内，求最小点时对应的α值，要保证α是大于等于零的，否则函数值就不是朝下降方向递降的了。在本算法中保证初始区间的端点是大于等于零的，就可以满足这一条件了。 算法如下图所示： 图 2 1.3 回退法计算初始区间的算法 针对这个算法,参考文献[1]上面利用的回退法不能保证a ，b 两个端点的值大于零，因为利用黄金分割法求α时，α肯定是大于等于零的，所以可以对书上的算法适当的改进。初始的点是0x ；步长是x Δ；算法如下： 图 3 注意：上面的算法是针对一维的情况，所以在计算0x ；1x ；2x 时，应该注意使 学生科学实验效果最优化的基石实验报告设计 自然科学是以实验为基础的学科。实验是人们研究和认识自然的重要方法。因此，在自然科学的教学中，实验也是重要的教学方法之一。通过实验，不仅可以提供学生对科学现象的感性认识，更可以让学生获得初步的实验技能和观察分析问题的能力。 小学科学实验教学的设计是运用系统论的思想和方法，以学习理论、教学理论为基础，计划和安排实验教学的各个环节、要素，以实现教学效果最优化为目的的活动。通过多年来的实验教学实践与思考，我们可以让学生像科学家那样，亲历科学探究的过程，这有利于充分发挥学生的主体作用，让学生积极主动参与到观察、实验等学习活动中去，亲自感知实验所产生的各种现象和变化，提高自行获取知识的能力，而其中比较重要的一个环节就是学生实验报告的设计与记录。在学生实验的过程中，一份好的实验报告设计，就像是一盏明灯，能给学生指引实验的目标、方向，能提供给学生形成结论的分析数据，进而培养学生科学实验的基本素养，使学生的科学实验效果达到最优化。 一、观察实验报告的填写，有利于学生在实验中观察，进一步培养学生实验的责任心和有序观察能力。 教科版四下《油菜花开了》解剖花的实验中，我设计了如下实验报告，在教学中取得了很好的效果。 《解剖花》实验人 花的名称 实验方法：用镊子把花的各部分，从外向里一层层撕下，整齐排列并贴在相应的名称左边，数一数，填在相应的空格上。 个萼片 个花瓣 个雄蕊 个雌蕊 在班级（1）上课时我没有设计实验报告，就按照书本上的要求，先介绍解剖花的方法、花的结构，然后让学生按照书本要求独立解剖油菜花。在实验过程中，学生非常认真，且相当活跃，但检查结果时，学生雌雄蕊不分，萼片、花瓣不分，桌上、地上掉落的都是花瓣，实验效果之不佳显而易见。 后来，我根据班级（1）出现的情况，设计了如上实验报告，实验的效果就相当出色。在这个实验报告中，我并没有限制学生解剖何种花，但学生可以根据实验要求很清楚地完成解剖的任务。充分体现了以教师为主导、学生为主体的课堂教学思想；而且在实验的过程中，桌上有了这份实验报告，便时刻提醒着学生做实验究竟是何目的，做实验时必须仔细观察什么，做实验的观察步骤是什么。在解剖花的过程中，动作快的同学还可在老师的同意下，多取一两张实验报告单，多解剖几种花，因此既避免了学生在一旁闲着无所事事而打闹的局面，又进一步提高了这些学生的科学素质。至于个别有困难的学生，教师可在巡视的过程中 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(min 30 +-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 加步探索法算法的计算步骤： (1)选取初始点 ]) 0[)(0[max 00t t t ，或，∈?∞+∈，计算 )(00t ??=．给出初始步长0 >h ， 加步系数1α>，令0=k 。 (2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ??，若k k ??<+1，转(3)，否则转(4)。 (3) 加大探索步长．令 k k h h α=+1，同时，令,k t t =,1+=k k t t 1k k =+，转(2)。 (4) 反向探索．若0=k ，转换探索方向，令,k k h h -=1+=k t t ，转（2）。否则，停止迭代，令 11min{}max{}k k a t t b t t ++==，，，。 加步探索法算法的计算框图 程序清单 加步探索法算法程序见附录1 实验结果 运行结果为： 2．用对分法求解 )2()(min +=t t t ?， 已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算． 对分法迭代的计算步骤： (1)确定初始搜索区间],[b a ，要求'()0'()0a b ??<>，。 (2) 计算],[b a 的中点)(2 1 b a c +=． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)． (5) 打印* t ，结束 对分法的计算框图 一维搜索方法的MATLAB 实现 姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的： 通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： 黄金分割法 它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断 的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当 ()()k k f f λμ≤转步骤（4）。 （3） 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5） （4） 转步骤（5） （5）令1k k =+，转步骤（2）。 算法的MATLAB 实现 function xmin=golden(f,a,b,e) k=0; x1=a+0.382*(b-a); x2=a+0.618*(b-a); while b-a>e f1=subs(f,x1); f2=subs(f,x2); if f1>f2 a=x1; x1=x2; f1=f2; x2=a+0.618*(b-a); else b=x2; x2=x1; f2=f1; x1=a+0.382*(b-a); end k=k+1; end xmin=(a+b)/2; fmin=subs(f,xmin) . . 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(min 30 +-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 加步探索法算法的计算步骤： (1)选取初始点])0[)(0[max 00t t t ，或，∈?∞+∈，计算)(00 t ??=．给出初始步长0 >h ， 加步系数1α>，令0=k 。 (2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ??，若k k ??<+1，转(3)，否则转(4)。 (3) 加大探索步长．令k k h h α=+1，同时，令,k t t =,1+=k k t t 1k k =+，转(2)。 (4) 反向探索．若0=k ，转换探索方向，令,k k h h -=1+=k t t ，转（2）。否则，停止迭代， 令 11min{}max{}k k a t t b t t ++==，，，。 加步探索法算法的计算框图 . . 程序清单 加步探索法算法程序见附录1 实验结果 运行结果为： 2．用对分法求解 )2()(min +=t t t ?， 已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算． 对分法迭代的计算步骤： (1)确定初始搜索区间],[b a ，要求'()0'()0a b ??<>，。 (2) 计算],[b a 的中点)(2 1 b a c += ． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)． function [a,b,n,x]=fibonacci(fname,a,b,d,L) % fname函数句柄，d辨别常数，L最终区间长度a(1)=a; b(1)=b; F=zeros(1,10); %选择fibonacci数列k值为10，可任意更改 F(1)=1; F(2)=2; for k=2:10 %k取到10，生成fibonacci数列 F(k+1)=F(k)+F(k-1); F(k); end Fn=(b(1)-a(1))/L; Fk=[F Fn]; N=sort(Fk); n=find(Fn==N); %查找计算函数值的次数n t(1)=a(1)+F(n-2)*(b(1)-a(1))/F(n); %计算试探点t(1),u(1) u(1)=a(1)+F(n-1)*(b(1)-a(1))/F(n); for k=1:n-2 ft=feval(fname,t(k)); fu=feval(fname,u(k)); if ft>fu a(k+1)=t(k); b(k+1)=b(k); t(k+1)=u(k); u(k+1)=a(k+1)+F(n-k-1)*(b(k+1)-a(k+1))/F(n-k); while k==n-2 t(n)=t(n-1); u(n)=t(n-1)+d; ft=feval(fname,t(n)); fu=feval(fname,u(n)); if ft>fu a(n)=t(n); b(n)=b(n-1); else a(n)=a(n-1); b(n)=t(n); end end else a(k+1)=a(k); b(k+1)=u(k); u(k+1)=t(k); if k~=n-2 t(k+1)=a(k+1)+F(n-k-2)*(b(k+1)-a(k+1))/F(n-k); ft=feval(fname,t(k)); 最优化方法 课程设计报告 班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日 目录 一、摘要 (1) 二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (3) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (10) 三、最速下降法 (10) 3.1 最速下降法的基本思路 (10) 3.2 算法流程图 (12) 3.3 用matlab编写源程序 (12) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (16) 4.1 惩罚函数法的基本思路 (16) 4.2 算法流程图 (17) 4.3 用matlab编写源程序 (17) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (19) 六、参考文献 (19) 一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数 法 遗传算法实验报告 专业：自动化姓名：张俊峰学号：13351067 摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。 关键词：串集最优化评估迭代变异 一：实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。。 （2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止： a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一 个解。 二：实验要求 已知函数y=f（x 1,x 2 ,x 3 ,x 4 ）=1/(x 1 2+x 2 2+x 3 2+x 4 2+1),其中-5≤x 1 ,x 2 ,x 3 ,x 4 ≤5, 用遗传算法求y的最大值。三：实验环境 操作系统：Microsoft Windows 7 软件：Microsoft Visual studio 2010 四：实验原理与步骤 1、遗传算法的思想 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。 2、算法实现步骤 ①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合； ②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据； ③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。 ④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。 ⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异； ⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。 五：实验结果 实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 的搜索区间，要求选取 ． 加步探索法算法的计算步骤： (1)选取初始点 ，计算．给出初始步长， 加步系数，令。 (2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ??，若k k ??<+1，转(3)，否则转(4)。 (3) 加大探索步长．令，同时，令，转(2)。 (4) 反向探索．若，转换探索方向，令，转（2）。否则，停止迭代，令。 12)(min 30+-=≥t t t t ?2,1,000===αh t ])0[)(0[max 00t t t ，或，∈?∞+∈)(00t ??=00>h 1α>0=k k k h h α=+1,k t t =,1+=k k t t 1k k =+0=k ,k k h h -=1+=k t t 11min{}max{}k k a t t b t t ++==，，， 加步探索法算法的计算框图 程序清单 加步探索法算法程序见附录1 实验结果 运行结果为： 2．用对分法求解 ， )2()(min +=t t t ? 已知初始单谷区间，要求按精度，分别计算． 对分法迭代的计算步骤： (1)确定初始搜索区间],[b a ，要求。 (2) 计算],[b a 的中点)(2 1b a c +=． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =*，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1*b a t += ，转(5)；否则转(2)． (5) 打印*t ，结束 对分法的计算框图 程序清单 对分法程序见附录2 ]5,3[],[-=b a 3.0=ε001.0=ε'()0'()0a b ??<> ， 最优化方法(Matlab)实验报告 ——Fibonacci 法 一、实验目的： 用MATLAB 程序实现一维搜索中用Fibonacc 法求解一元单峰函数的极小值问题。二、实验原理： （一）、构造Fibonacci 数列：设数列{}k F ，满足条件： 1、011F F == 2、11 k k k F F F +-=+则称数列{}k F 为Fibonacci 数列。（二）、迭代过程： 首先由下面的迭代公式确定出迭代点： 1 1 1 (),1,...,1(),1,...,1n k k k k k n k n k k k k k n k F a b a k n F F u a b a k n F λ---+--+=+ -=-=+ -=-易验证，用上述迭代公式进行迭代时，第k 次迭代的区间长度缩短比率恰好为 1 n k n k F F --+。故可设迭代次数为n ，因此有11121211221111223231 ()()......()()n n n n n n n n n F F F F F F b a b a b a b a b a F F F F F F F ------= -=?-==?-=-若设精度为L ，则有第n 次迭代得区间长度111 ()n n n b a L b a L F -≤-≤，即 就是 111 ()n b a L F -≤，由此便可确定出迭代次数n 。 假设第k 次迭代时已确定出区间[,]k k a b 以及试探点,[,]k k k k u a b λ∈并且k k u λ<。计算试探点处的函数值，有以下两种可能：（1）若()()k k f f u λ>，则令 111111111,,()() () k k k k k k k k n k k k k k n k a b b f f F a b a F λλμλμμ++++--++++-=====+-计算1()k f μ+的值。（2）()()k k f f u λ≤，则令 111121111,,()() () k k k k k k k k n k k k k k n k a a b f f F a b a F μμλμλλ++++--++++-=====+-计算1()k f λ+的值。 又因为第一次迭代确定出了两个迭代点，以后每迭代一次，新增加一个迭代点，这样在迭代n-1后便计算完了n 个迭代点。因此第n 次迭代中，选用第n-1次的迭代点以及辨别常数δ构造n λ和n μ： 1 1n n n n λλμλδ --==+再用同样的方法进行判断：（1）、若()n f λ>()n f μ则令 1 n n n n a b b λ-==（2）、若()n f λ<=()n f μ则令 1n n n n a a b μ-==这样便可确定出最优解的存在区间[,]n n a b 。 第九章最优化方法的Matlab实现 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容：1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述 利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、 非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1 优化工具箱中的函数 优化工具箱中的函数包括下面几类： 1．最小化函数 表9-1 最小化函数表 2．方程求解函数 表9-2 方程求解函数表 3．最小二乘（曲线拟合）函数 表9-3 最小二乘函数表 4．实用函数 表9-4 实用函数表 5．大型方法的演示函数 表9-5 大型方法的演示函数表 计算方法实验报告 实验名称： 实验1 从函数表出发进行插值 1 引言 某个实际问题中，函数f (x)在区间[a,b]上存在且连续，但难以找到其表达式，只能通过实验和观测得到有限点上的函数表。有些情况虽然可以写出表达式，但结构复杂，使用不方便。所以希望构造简单函数P (x)作为f (x)的近似值。插值法是解决此类问题的一种方法。 设函数y=在插值区间[a,b]上连续，且在n+1个不同的插值节点a≤x 0,x 1,…,x n ≤b 上分别取值y 0,y 1,…,y n 。目的是要在一个性质优良、便于计算的插值函数类Φ中，求一简单函数P (x)，满足插值条件P (x i )=y i (i=0,1,…,n)，而在其他点x≠x i 上，作为f (x)近似值。求插值函数P (x)的方法称为插值法[1]。 2 实验目的和要求 运用Matlab 编写m 文件，定义三种插值函数，要求一次性输入整张函数表，并利用计算机选择在插值计算中所需的节点。分别通过分段线性插值、分段二次插值和全区间上拉格朗日插值计算f ，f ，f 的近似值。 3 算法原理与流程图 （1）原理 1.线性插值 当给定了n+1个点x 0 北方民族大学课程设计报告 系（部、中心）信息与计算科学学院 专业信息与计算科学班级 09信计（3）班小组成员 课程名称最优化方法 设计题目名称运用DFP算法解决无约束最优化问题提交时间2012年6月26日 成绩 指导教师 变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系.变尺度法避免了Newton法在每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵而导致随问题的维数增加计算量迅速增加.DFP算法是变尺度法中一个非常好的算法.DFP算法首先是1959年由Davidon提出的后经Fletcher和Powell改进，故名之为DFP算法，它也是求解无约束优化问题最有效的算法之一. DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快. 本文主要分析DFP算法原理及运用Matalb软件编程解决实际数学问题.最后运算结果符合计算精度且只用了一次迭代，由此可见收敛速度快. 关键词：Newton法变尺度法Hesse矩阵Matlab软件 一、课程设计目的 (1) 二、课程设计要求 (1) 三、课程设计原理 (1) （1）变尺度法基本原理 (1) （2）DFP算法 (3) 四、实验内容 (4) 五、数学建模及求解 (4) 1.DFP算法迭代步骤 (4) 2.DFP算法的流程图 (5) 六、程序实现 (5) 七、数值实验的结果与分析 (8) 八、实验总结与体会 (9) 1.DFP公式恒有确切解 (9) 2.DFP算法的稳定性 (9) 参考文献 (10) 智能优化算法实验报告 用遗传算法求解函数优化问题 SC07010062 晏晓辉 目录 1.实验目的 (3) 1.1了解并掌握遗传算法的原理，流程和编码策略； (3) 1.2利用遗传算法goat工具箱测进行30维的多变量函数寻优； (3) 1.3自编遗传算法程序对2维变量函数进行寻优并测试主要参数对结果的影响。 (3) 2.实验条件 (3) 2.1硬件环境： (3) 2.2软件环境： (3) 3.实验原理 (3) 3.1遗传算法简介： (3) 3.2遗传算法流程： (4) (1) 编码 (4) (2) 生成初始种群 (4) (3) 适应度评估 (4) (4) 选择 (4) (5) 交叉 (4) (6) 变异 (4) 4.实验步骤和结果分析 (5) 4.1实验一：利用遗传算法goat工具箱测进行30维的多变量函数寻优。 (5) 4.1.1 goat工具箱说明 (5) 4.1.2优化函数的选择 (6) 4.1.3 实验结果分析 (6) 4.2实验二：自编遗传算法程序对2维变量函数进行寻优并测试主要参数对结果的影响。 (7) 4.2.1编码策略 (7) 4.2.2结果分析 (8) 5.附件 (9) 5.1 利用gaot工具箱对10() f x 寻优执行9次结果轨迹收敛图。 (9) 5.2 自编遗传算法代码： (14) 1.实验目的 1.1了解并掌握遗传算法的原理，流程和编码策略； 1.2利用遗传算法goat工具箱进行30维的多变量函数寻优； 1.3自编遗传算法程序对2维变量函数进行寻优并测试主要参数对结果的影响。 2.实验条件 2.1硬件环境： AMD Sempron(tm) Processor 3600+ 1.99GHz ,1.5G内存 2.2软件环境： Microsoft Windows XP , MATLAB7.0 , goat工具箱 3.实验原理 3.1遗传算法简介： 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化 最优化方法实验报告 实验一：用进退法求函数 的一个形如 的初始区间。 程序如下： function [minx,maxx] = minJT(f,x0,h0,eps) format long; if nargin == 3 eps = 1.0e-6; end x1 = x0; k = 0; ()22+-=x x x f []b ,0 h = h0; while 1 x4 = x1 + h; k = k+1; f4 = subs(f, findsym(f),x4); f1 = subs(f, findsym(f),x1); if f4 < f1 x2 = x1; x1 = x4; f2 = f1; f1 = f4; h = 2*h; else if k==1 h = -h; x2 = x4; f2 = f4; else x3 = x2; x2 = x1; x1 = x4; break; end end end minx = min(x1,x3); maxx = x1+x3 - minx; format short; 窗口中输入： syms x; f= x*x-x+2; [minx,maxx] = minJT(f,0,0.01,eps) minx = 0.3100 maxx = 1.2700 实验二：用黄金分割法求函数在区间[]3,1-上的极小 ()2 2+ - =x x x f 点。 程序为： function [x,minf] = minHJ(f,a,b,eps) format long; if nargin == 3 eps = 1.0e-6; end l = a + 0.382*(b-a); u = a + 0.618*(b-a); k=1; tol = b-a; while tol>eps && k<100000 fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl > fu a = l; l = u; u = a + 0.618*(b - a); else b = u; u = l; l = a + 0.382*(b-a); end k = k+1; tol = abs(b - a); end if k == 100000 disp('找不到最小值！'); x = NaN; minf = NaN; return; end x = (a+b)/2; minf = subs(f, findsym(f),x); format short; 在窗口中输入： >> syms x; >> f=x^2+x-2; >> [x,fx]=minHJ(f,-1,3) x = 关于遗传算法的实验报告 一、实验目的： 理解和掌握遗传算法的应用及意义，能用一门自己擅长的语言实现遗传算法的基本功能，在此基础上进一步理解和巩固对遗传算法的重要，以便在今后的学习和工作中能有效的运用和借鉴！需要指出的是遗传算法并不是能保证所得到的就是最佳的答案但通过一定的方法可以将误差控制在一定的范围内！ 二、实验原理和题目： 1.遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。 （2）对该字符串种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止：a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一个解。 2.通过编码、设置种群、设置适应度函数、遗传操作、解码产生需要的解。 f(x)=x*sin(x)+1，x∈[0,2π],求解f(x)的最大值和最小值。 三、实验条件 硬件：微型计算机。 语言：本实验选用的为C++语言。 四、实验内容： 建造针对f(x)的遗传算法程序，然后进行运行求解。 五、实验步骤： 1. 确定基本功能：本实验是实现f（x）的最大值和最小值的求解。 2. 对f(x)进行编码：用一个二进制矢量表示一个染色体，由染色体来代表变量x的实数值，这里精度取小数点后6位数，变量x的域长为2π，整个区间被分为2π*1000000个等长的区间。由于2π*1000000在23位二进制数的表示范围呢，所以，编码长度为23位。 3. 设计适应度函数：由于要求f（x）的最值，所以适应度函数可根据f（x）做适当的改变。最大值：f(x)=x*sin(x)+5；最小值：f(x)=1/（x*sin(x)+5 ）; 4. 针对f(x)的设计并且实现遗传算法程序：遗传操作主要包括复制、交叉和变异。复制是直接将父代遗传给子代，即根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉从能进入下一代的个体中选出两个，将两者的部分码值进行交换。变异是根据变异概率选出一个个体，随机对其某位编码进行改变。复制由void Selection_operation(bool flag);实现；交叉由void Crossover_operation();实现；变异由void Mution-operation();实现。 5. 设计初始种群：默认设置为50个随机产生的23位字节的染色体。 6. 调试交叉和变异概率：在常用的交叉和变异概率范围内，结果随交叉和变异的概率的改变而改变，之间差异相对来说不太明显 7. 实验参数：实验中主要的参数有遗传代数、群体规模、交叉概率、变异概率。 实验结果： 求最大值：最优化实验报告
最优化方法实验报告(1)
最优化理论与算法(第八章)
最优化DFP算法报告
学生科学实验效果最优化的基石实验报告设计
最优化方法课程实验报告
最优化方法(黄金分割与进退法)实验报告
最优化方法课程实验报告
最优化理论与算法 fibonacci法
最优化实验报告
遗传算法实验报告
最优化方法课程实验资料报告材料
最优化算法实验报告(附Matlab程序)
最优化方法的Matlab实现(公式完整版)
计算方法实验报告习题1
最优化方法 课程设计报告 运用DFP算法解决无约束最优化问题
智能优化算法实验报告
最优化方法实验报告2
关于遗传算法的实验报告