最优化思想—黄金分割和优选法课件.ppt

斐波那契数列及其应用 斐波那契《计算之书》兔子问题（1202年） 如果每1对成兔每月生1对幼兔，幼兔经过2个月后成为成兔，即开始繁殖， 问年初的1对幼兔经过1年后能繁殖成多少对兔子？ 假定这一过程兔子不发生任何死亡。 由兔子问题抽象得递推关系 本月底幼兔总对数=上上个月底兔子总对数 所以：本月底兔子总对数 =上月底兔子总对数+上上个月底兔子总对数。 “走楼梯”问题 某人要走一架n个台阶的楼梯，某人每步向上走1个台阶或2个台阶。 un表示该人从地面向上走到第n个台阶时所有不同的走法种数，求un。 0.618优选法（黄金分割法） 问题：做2千克大米的干饭，放多少水最好吃？ （1000g-2000g) “饭好吃f(x)”是“放水量x”的函数； 但不知其具体表达式，或即使知道但太复杂； 函数f(x)有何特点？ 单峰（谷）函数 不能用数学方法寻找单峰函数的最优点，怎么办？. 通过作试验的方法来寻找最佳点。 优选法是以最少的试验次数迅速找到最佳点的试验方法。 这是最优化一种新的思维方法！ 归纳：0.618优选法（黄金分割法） 问题：做2千克大米的干饭，应该放多少水？（1000g-2000g) 寻找单峰（谷）函数（不知其具体表达式或太复杂）的最优点. 通过作试验的方法寻找最佳点 优选法是以最少的试验次数迅速找到最佳点的试验方法。 操作过程： 第一个试验点x1=a+(b-a)0.618，第二个试验点x2=a+b-x1； 对比x1,x2处结果，裁去“坏点”外边的部分；以此类推； 在确定第n个试点xn时，如果存优范围内相应的好点是xm， 那么有xn=小+大-xm. 称“加两头，减中间”来确定下1个试点。 经过n次试验后留下的区间长为原区间长的0.618n-1（精度）。 0.618法试点为什么这样选择？ 第一、第二次试点选择的原则： 1、公平原则； ——使两个试点关于区间[a,b]的中点对称 2、继承原则 ——每次舍去的区间占舍去前的区间的比例数相同。 据上述原则求出第1、第2次试点的位置 线段[a,b]的黄金分割点 0.618法（黄金分割法） 分数法 例：在配置某种清洗液时，需要加入某种材料。经验表明，加入量大于130ml肯定不好。用150ml的锥形量杯计量加入量，该量杯的量程分为15格，每格代表10ml。 用试验法找出这种材料的最优加入量。 能用0.618法吗？ 如果用0.618法，算出的试点不是10ml的整数倍，此法不能用。 采用分数法，借助Fibonacci数列来处理。 分数法的操作 把实验区间[0,130]分成13等分，分点依次设为1,2,3,…,12。 选分数8/13作为黄金分割数的近似值。 第一个试点为8，第二个为5， 若8好，则去掉[0,5]，剩下[5，13]； 8已试过，在10处做第3个试验，若还是8好，去掉[10,13]，剩下[5，10]； 在7处做第四个试验，若7比8好，去掉[8，10]，剩下[5，8]； 在6做第五个试验，如6比7好，则6为最佳点。 五次试验后，精度为1/13。 分数法 现实中，由于受时间、人力等影响，往往使试验次数受到限制，此时采用分数法可以达到较好的效果。 分数法与0.618法的本质是相同的。 有两种情况： 1.可能的试点总数正好是某一个(Fn+1-1)； 2.可能的试点总数大于某一(Fn-1)，而小于(Fn+1-1)。 分数法的最优性 结论1：在目标函数为单峰的情形，通过n次试验，最多能从(Fn+1-1)个试点中保证找出最佳点。并且这个最佳点就是n次试验中的最优试验点。 结论2：目标函数为单峰的情形，只有按照分数法安排试验，才能通过n次试验，保证从(Fn+1-1)个试点中找出最佳点。 综上所述，对于试点个数为某常数k时，用分数法找出其最佳点的试验次数最少。 分数法的最优性可以用数学方法证明。 * 温州大学数学与信息科学学院 黄忠裕 zyhuang0577@163.com 2012年12月16日 浙江省中小学教师专业发展培训项目 高中数学知识拓展指导 选修3-1：数学史选讲 选修3-2：信息安全与密码 选修3-3：球面上的几何 选修3-4：对称与群 选修3-5：欧拉公式与闭曲面分类 选修3-6：三等分角与数域扩充 选修4-1：几何证明选讲 选修4-6：初等数论初步 选修4-2：矩阵与变换 选修4-7：优选法与试验设计初步 选修4-3：数列与差分 选修4-8：统筹法与图论初步 选修4-4：坐标系与参数方程 选修4-9：风险与决策 选修4-5：不等式选讲 选修4-10：开关电路与布尔代数 浙江普通高中知识拓展类选修课程实施方案