模式搜索法

数学与计算科学学院实验报告实验项目名称模式搜索法所属课程名称最优化方法实验类型算法编程实验日期2015年11月20号班级学号20姓名成绩一、实验概述：【实验目的】1(1)掌握模式搜索法；(2)使用计算机语言表达最优化方法。【实验原理】模式搜索算法从初始基点开始，包括两种类型的移动，这就是探测移动和模式移动。探测移动依次沿n个坐标轴进行，用以确定新的基点和有利于函数值下降的方向。模式移动沿相邻两个基点连线方向进行，试图顺着“山谷”使函数值更快的减小。设目标函数为(),nfxxR。坐标方向(0,,0,1,0,,0),1,,Tjejn给定初始步长，加速因子。任意初始点(1)x作为第1个基点。下面以()jx表示第j个基点。在每轮探测移动中，自变量用()jy表示，即()jy是沿je探测的出发点。这样，(1)y是沿1e探测的出发点，(1)ny是沿ne探测得到的点。首先，从(1)(1)yx出发，进行探测移动。先沿1e探测。如果(1)(1)1()()fyefy，则探测成功，令(2)(1)1yye并从(2)y出发，沿2e进行探测。否则，沿1e方向的探测失败，再沿-1e方向探测。如果(1)(1)1()()fyefy，则沿-1e方向探测成功，则令(2)(1)1yye并从(2)y出发，沿2e探测。如果(1)(1)1()()fyefy，则沿-1e方向的探测也失败。令(2)(1)yy再从(2)y出发，沿2e进行探测。方法同上，得到的点记作(3)y，按此方式做下去，直至沿n个坐标轴方向探测完毕，得到点(1)ny。2如果(1)(1)()()nfyfx，则(1)ny作为新的基点。记作(2)(1)nxy这时，可望(2)(1)dxx是有利函数值减小的方向。下一步，沿方向(2)(1)xx进行模式移动，令新的(1)y为(1)(2)(2)(1)()yxxx模式移动以后，以(1)y为起点进行探测移动，这轮探测仍然沿坐标轴方向进行。探测完毕，得到的点仍记为(1)ny。如果(1)(2)()()nfyfx，则表明此次模式移动成功，于是取新的基点(3)(1)nxy再沿方向(3)(2)xx进行模式移动。如果(1)(2)()()nfyfx，则表明模式移动及此次模式移动之后的探测移动均无效。于是退回到基点(2)x，减小步长，再从(2)x出发，依次沿坐标轴各个方向进行探测移动。如此继续下去，直到满足精度要求，即步长小于事先给定的正数为止。【实验环境】计算机VC++二、实验内容：【实验方案】1.列举例题2.手工计算3.将计算步骤等实现程序化34.实验结果分析【实验过程】例题min24212(2)(2)xxx,取初点(1)(3,0)Tx初始步长1411计算步骤：4（1）给定初始点(1)nxR，n个坐标方向12,,,neee，初始步长，加速因子1，缩减率(0,1)，允许误差0，置(1)(1)yx，k=1，j=1.（2）如果()()()()jjjfyefy，则令(1)()jjjyye，进行步骤（4），否则，进行步骤（3）。（3）如果()()()()jjjfyefy，则令(1)()jjjyye进行步骤（4），否则，令(1)()jjyy进行步骤（4）。（4）如果jn，则令:1jj，转步骤（2）；否则，进行步骤(5).（5）如果(1)()()()nkfyfx，则进行步骤（6）；否则，进行步骤（7）。（6）置(1)(1)knxy，令(1)(1)(1)()()kkkyxxx置:1,1kkj，转步骤（2）。（7）如果，则停止迭代，得到点kx；否则，置5(1)()(1)():,,kkkyxxx置:1,1kkj，转步骤（2）。【实验结论】最优解(1,2)Tx最小值0【实验小结】（收获体会）通过本次实验，初步了解了最优化方法在机器语言上的实现，更深刻的了解了模式搜索法，理解和掌握了他们的优缺点。同时也认识了自己的缺点，编程能力弱，需要极大的提高。在以后的实验中会努力学习，争取把这门课学好。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：6附录1：源程序functiony=myfun(z,noise）;y=zeros(1,size(z,1));noise=1;fori=1:size(z,1)x=(z,:);ifx(1)^2+x(2)^2=25y(i)=x(1)^2+x(2)^2-25+noise*randn;elseifx(1)^2+(x(2)-9)^2=16y(i)=x(1)^2+(x(2)-9)^2-16+noise*randn;elsey(i)=0+noise*randn;endendend%2、确定初始点%3、编写主程序X0=;LB=;UB=;range=;Objfcn=@myfun;Clf;showSmoothFcn(Objfcn,range);holdon;Title('objectivefunction')fig=gcf;PSoptions=psoptimset('Display','iter','OutputFcn',@psOut);=patternsearch(Objfcn,X0,,,,,LB,UB,Psoptions)Figure(fig);holdon;plot3(x(1),x(2),z,'dr','MarkerSize',12,'MarkerFaceColor','r');holdoff;functiony=myfun(z,noise)y=zeros(1,size(z,1));noise=1;fori=1:size(z,1)x=z(i,:);ifx(1)^2+x(2)^2=25y(i)=x(1)^2+x(2)^2-25+noise*randn;elseifx(1)^2+(x(2)-9)^2=16y(i)=x(1)^2+(x(2)-9)^2-16+noise*randn;elsey(i)=0+noise*randn;7endendclcX0=;LB=;UB=;range=;Objfcn=@myfun;Clf;showSmoothFcn(Objfcn,range);holdon;Title('objectivefunction')fig=gcf;PSoptions=psoptimset('Display','iter','OutputFcn',@psOut);=patternsearch(Objfcn,X0,,,,,LB,UB,PSoptions);figure(fig);holdon;plot3(x(1),x(2),z,'dr','MarkerSize',12,'MarkerFaceColor','r');holdoff;8附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致.2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求.3．实验原理：简要说明本实验项目所涉及的理论知识.4．实验环境：实验用的软、硬件环境.5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容.概括整个实验过程.对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作.对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明.对于创新性实验，还应注明其创新点、特色.6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析.7．实验结论（结果）：根据实验过程中得到的结果，做出结论.8．实验小结：本次实验心得体会、思考和建议.9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价.