机械优化设计第三章.

第三章一维搜索方法一维搜索：对于单个变量（一维问题）的直接探索（搜索或寻查）。多维问题的数值迭代法1(0,1,2,)kkkkxxdk1()()()minkkkkkfxfxd每步为一维搜索*'()01）解析法：2）数值解法的基本思想：确定α*所在的搜索区间，然后根据区间消去原理不断缩小区间，从而获得α*的数值近似解。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理单峰区间：函数在该区间只有一个极值点。12xxx12()()()fxfxfx“高——低——高”第三章一维搜索方法第二节搜索区间的确定与区间消去法原理确定搜索区间的外推法（进退法/成功失败法）：12xxx12()()()fxfxfx“高—低—高”第三章一维搜索方法第二节搜索区间的确定与区间消去法原理确定搜索区间的外推法的基本步骤：10210112212320332332123132300122312231.()()()[,]2hhyfyfyyhyfyyyyyyyyyhhyyyy选定初始点，初始步长，计算点，然后比较函数值和的大小。2.若，则试探方向正确，计算点和，比较和的大小。如果，则形成，找到所需的区间，即；如果，则需要继续向前搜索，这时候令，，，同时令，，开01231313[,][min(,),max(,)]hyyyab始新一轮的试探（这时候的是原来的二倍，步长加长了），直到找到时，新的搜索区间是。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理确定搜索区间的外推法的基本步骤：1200121233313112122323122320333.,,,,()yyhhyyyyyyyyyhff若，则试探方法错误，需要反向，即令，并且将和交换，同时交换和，在程序中，如果用替换，则另一个函数值就没有了，所以加入和做中间变量，即：；；。然后得到新的和后，用新的向前推出（这里的已经反向了）。这时就得到了新的三个点，以及三个试探点的函数231231313[,][min(,),max(,)]yyyyyab值，则继续前面的比较与，直至找到时，新的搜索区间是。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理确定搜索区间的外推法的程序流程图：第三章一维搜索方法第二节搜索区间的确定与区间消去法原理例：210()710[,]01fxxxabh试用进退法确定函数的一维优化的初始搜索。其中，设初始点，初始搜索步长。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理一维搜索的基本原理：通过外推法，我们可以确定一个包含一元函数极值点的搜索区间，为了进一步找到极小点，我们需要不断的缩小搜索区间，消去不可能包含极小点的区间，使区间在缩小的过程中逐步向极小点靠拢，最后缩小到极小点附近一个极小的领域内。这个时候，如果我们规定一个足够小的正数ε，称为收敛精度。则当区间长度达到足够小，即取该区间的中点作为极值点，这才能完成整个一维搜索。kkba*1()2kkxab第三章一维搜索方法第二节搜索区间的确定与区间消去法原理区间消去原理：不断缩小区间所用的原理。包括：1）直接法：直接比较试选点的函数值；2）间接法：利用函数导数值的变化信息。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理111111[,]()()abababfafb假定在搜索区间内任取两点和，且，并计算和，可能出现三种情况：直接法11111111111.()()[,]2.()()[,]3.()()[,]fafbabfafbabfafbab，由于函数的单峰性，极小点一定在内；，极小点一定在内；，极小点一定在内。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理111111[,]()()abababfafb假定在搜索区间内任取两点和，且，并计算和，可能出现三种情况：直接法1111111.()()[,]2.()()[,]fafbabfafbab若，则取为缩短后的搜索区间；若，则取为缩短后的搜索区间。第三章一维搜索方法第二节搜索区间的确定与区间消去法原理[,],'()abxfx假定在搜索区间内取一点并计算它的导数值，可能出现三种情况：间接法*1.'()0[,]2.'()0[,]3.'()0fxxbfxaxfxxx，则新区间是；，则新区间是；，则在此点就是极小点。xfxabxx0xfxabxx0fxxabx0第三章一维搜索方法第二节搜索区间的确定与区间消去法原理区间缩短率：缩短后的新区间长度（01）缩短前的原区间长度第三章一维搜索方法第二节搜索区间的确定与区间消去法原理一维搜索方法的分类：•试探法：它是按照某种给定的规律来确定区间内插入点的位置的。插入点位置的确定是为了使区间缩短的更快，而不管函数值的分布规律。它包括：黄金分割法（0.618法）、裴波纳契（Fibonacci）法等。•插值法（函数逼近法）：这种方法是根据某点处的某些信息（如函数值、一阶导数、二阶导数等）来构造一个差值函数来逼近原来的函数，用插值函数的极小点作为区间的插入点。它包括：二次差值法、三次插值法等。第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：基本原理：通过比较单峰区间内两个内分点的函数值，不断舍弃单峰区间的左端或者右端的一部分，使区间按照固定区间缩短率（λ=0.618）逐步缩短，直到极小点所在的区间缩短到给定的误差范围内，而得到近似最优解。第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：黄金分割法的内分点的选取原则：每次区间缩短都取相等的区间缩短率（λ），同时插入点距离两个端点有对称性。0.61812()0.618()()0.618()bbabbaabaaba第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：计算步骤：121211221?[,]2[,]()0.618()()0.618()()()ababbbabbaabaabayfyf）给定初始单峰区间和收敛精度，将赋值为0.618；）在区间内，取两个内分点和，并计算其函数值：和，第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：计算步骤：12221221211111211211213[,][,],,()()[,][,],,yybyybbayfyybbay）比较函数值大小，根据区间消去法原理缩短区间：若，则极小点必在区间内，即为新区间,则为新区间内的第一个试验点，即令，而另一个试验点可按下式算出，它的函数值为；若，则极小点必在区间内，即为新区间，则为新区间内的第一个试验点，即令2222(),()yabayf，而另外一个试验点可以按下式给出。第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：计算步骤：212***4315()()2yybabyxabyfx）进行迭代终止条件检验，检查区间是否缩短到足够小和函数值是否收敛到足够近，即和，如果不满足条件，则转到第）步；满足条件则继续执行下一步。）输出最优解和最优函数值。第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：程序框图：第三章一维搜索方法第三节一维搜索的试探法黄金分割法（0.618法）：例：2*()2,35f如图所示，对函数当给定搜索区间时，试用黄金分割法求极小点。第三章一维搜索方法第三节一维搜索的试探法斐波那契法：和黄金分割法相似，都是在搜索区间内对称的取点，通过比较两点函数值逐步缩小初始单峰区间来搜索出满意的极小点x*。与黄金分割法不同的是：黄金分割法每次迭代式按照同一区间缩短率λ=0.618来缩短区间，而斐波那契法每次迭代的区间缩短率是不同的，它是按斐波那契数列{Fn}产生的分数序列为缩短率来缩短区间的。，第三章一维搜索方法第三节一维搜索的试探法斐波那契法：，011FF12(2,3,)nnnFFFn斐波那契数：凡是满足递推关系而产生的正数序列{Fn}，就称为斐波那契数。n01234567891011121314…Fn1123581321345589144233377610…第三章一维搜索方法第三节一维搜索的试探法斐波那契法：，n01234567891011121314…Fn1123581321345589144233377610…区间缩短率用相邻两数的前一数与后一数之比产生，如计算五个点的函数值（即迭代四次，每次区间缩短率分别为123412514342134233253852132nnnnnnnnFFFFFFFFFFFFFFFF11234518FF第三章一维搜索方法第三节一维搜索的试探法斐波那契法：，n01234567891011121314…Fn1123581321345589144233377610…推广到计算n个点的函数值，经过n-1次迭代所获得的区间总缩短率为11211nnnFFF第三章一维搜索方法第三节一维搜索的试探法斐波那契法的特点：，11(1)1/n21/0.61830.618nnnnFFF）斐波那契法开始计算第一个内点（即第一次缩短率）就要用到，也就是首先要确定计算函数的次数（即计算的总点数），否则无法确定缩短率）与黄金分割法相比，收敛效果好，即计算相同试点数，斐波那契法总区间缩短率。黄金分割法的区间总缩短率。）斐波那契法每次的区间缩短率是变化的，当计算函数值的点数较多时，其区间缩短率将逼近。第三章一维搜索方法第三节一维搜索的试探法斐波那契法的迭代步骤：，11111101121a,b2nn11||()()Fn1,(2,3,)nnnnnnnnnnnnbababababaFbaFFFFFFn）由外推法（进退法）选定初始单峰区间。）确定所需计算的试点总数（即计算函数的次数）。当给定区间缩短率的绝对精度时，经过次迭代，最后获得的新区间长度（）必须满足。而，故。由即可从斐波那契数列表或按推算出相应的。112111223a,b(),(),(),()nnnnFFxabaxbbaffxffxFF）确定试点并计算相应的函数值，在区间内的两个试点：第三章一维搜索方法第三节一维搜索的试探法斐波那契法的迭代步骤：，212221211211211112122122***114[,],,,()[,],,,()15(),()2nnffaxbxxxffxabxffxffxbaxxxffxabxffxbaxabffx）比较函数值的大小后进行区间缩短。若，即为新区间，并作如下置换：即令若时，得新区间，并作如下置换：）检查迭代终止条件：，若满足，则输出最优解，若不满足，则转入（4），继续进行迭代。第三章一维搜索方法第四节一维搜索的插值方法插值法（函数逼近法）：我们就可以根据几个试验点的函数值，利用插值方法建立函数的某种近似表达式，进而求得函数的极小值，并用它作为原函数极小点的近似值。这种方法称为插值法，或函数逼近法。•牛顿法（切线法）：利用一点的函数值，一阶导数值和二阶导数值来构造此二次函数。•抛物线法（二次插值法）：利用三点的函数值形成一个抛物线来构造二次函数。，第三章一维搜索方法第四节一维搜索的插值方法牛顿法（切线法）：用切线代替弧逐渐逼近函数极值的一种方法。，1'()(0,1,2,)''()kkkkfkf牛顿法的迭代公式:第三章一维搜索方法第四节一维搜索的插值方法牛顿法的计算步骤：，01*11k01'()''()'()2''()3||4411kkk