优选法是谁提出的优选法( 二 )

在（a,b）区间内取两点x1，x2 。显然：
1）当f(x1)f(x2)时，极大点在（a,x2）的范围内，（x2,b）的区间舍去。
2）当f(x1)f(x2)时，极大点在（x1,b）的范围内，（a,x1）的区间舍去。
3）当f(x1)=f(x2)时，极大点在（x1,x2）的范围内，（a,x1)，(x2,b)的区间舍去。
每次舍弃完一定的区间后，在剩余的点中需要重新找点，迭代计算。
即第一次迭代，需要找到x1,x2,并且计算f(x1),f(x2)
第二次迭代，需要找到x3,x4，并且计算f(x3),f(x4)
右图中的阴影部分就是舍去区间的范围，可见每次迭代都可以将区间缩小，缩减的范围的大小与x1，x2的选取方法有关。而且考虑到舍去的区间可能是某个实验点到上下限的范围，则另一个实验点如果能够重用，将非常减少计算量。0.618法就是采用上面的思路来选取x1和x2的：
不失一般性，假定(a,b)区间是(0,1)，即f(x)在(0,1)区间上有单峰极值，选取得两个点x1，x2分别记为x和1-x，即在x和1-x两点进行实验，不妨假定保留下来的是(0,x)区间。
继而在(0,x)区间上两个点x^2和(1-x)x处做实验，如果x^2=1-x，那么上次在1-x处的实验就可以派上用场，节省一次实验，而且舍去的区间是原来区间1-x的一部分。故有x^2+x-1=0，可以解得。
第一次选择0.382(b-a),0.618(b-a)，若保留了（0，0.618），由于0.618*0.618=0.382，因此下一轮只需要在0.618*0.382=0.216处做另一次实验，0.382的实验结果在上一轮中得出，减少了计算量，每次消去的区间还大。由于Fibonacci序列中后项与前项的比值是越来越趋近于黄金分割数0.618的，所以单因素优选法也可以利用Fibonacci序列来完成，此方法与0.618法的最大不同在于它能够预先确定迭代次数，而0.618法需要额外指定一个参数，当区间长度缩小到小于这个参数时才结束迭代。利用Fibonacci序列进行优选的另一个优越之处还在于它能适用于参数只能取整数情况。
还是以区间(a,b)中的单峰函数f(x)为例。
将(a,b)区间分成等分，问题变为在（0，）范围内求极值。第一次选择和，若保留下的区间是(0, )，则下次只需要计算，已经在上次迭代中计算过。
若受限于现实条件，可选取出来参加实验的点数有限（x只能够取到有限的一些散点），比小，比大，则可以通过添加几个无关的点来凑足个点。只要保证在[0, ]区间中是单峰极小点即可，而且可以默认这些新加入的点比其他现实能够取到的实验点都差。
上述讨论中，对于初始时包含个等分点的Fibonacci序列优选法，一轮迭代就可将包含极值的单峰区间缩为包含个等分点的区间，而且当点数够多时，有 / 约等于于0.618 。选定区间[-4,4]中的单峰函数f(x)=x^2+5*x，以0.01为要求的精度查找其最小值。
0.618法（黄金分割法）的Matlab代码如下：function [yStar,xStar,log] = goldSearch(a,b,eps)%% 0.618法(黄金分割法)%函数：yFunc为y关于x的函数，具体形式见最下，此时为：y=x^2+5*x%输入：a,b,eps分别代表了区间[-4,4]及精度0.01；%输出：[yStar,xStar] 分别是函数的最小值及其对应的x值，log纪录了具体步骤；%执行：在命令行中输入[yStar,xStar,log]=goldSearch(-4,4,0.01),%即可开始在区间[-4,4]中查找最小值，优化精度达到0.01时停止；%figure(1);x = a:0.01:b;y = yFunc(x);plot(x,y,'k-');hold on; a(1)=a; b(1)=b;n=1;plot(a(n),yFunc(a(n)),'c*');plot(b(n),yFunc(b(n)),'b*');pause(0.5);t(1)=a(1)+0.382*(b(1)-a(1)); u(1)=a(1)+0.618*(b(1)-a(1));while((b(n)-a(n))eps)B(n)=b(n)-a(n);m(n)=yFunc(t(n));g(n)=yFunc(u(n));if m(n)g(n)a(n+1)=t(n);b(n+1)=b(n);t(n+1)=u(n);u(n+1)=a(n+1)+0.618*(b(n+1)-a(n+1));elsea(n+1)=a(n);b(n+1)=u(n);u(n+1)=t(n);t(n+1)=a(n+1)+0.382*(b(n+1)-a(n+1));endn=n+1;plot(a(n),yFunc(a(n)),'c*');plot(b(n),yFunc(b(n)),'b*');pause(0.5);endxStar = (b(n)+a(n))/2; yStar = yFunc(xStar);plot(a(n),yFunc(a(n)),'ro');hold off;t(n)=0;u(n)=0;m(n)=0;g(n)=0;B(n)=b(n)-a(n);n=n-1;log=[a',b',t',u',m',g',B'];function y = yFunc(x) if (length(x)1)y = x.^2+5.*x;elsey = x^2+5*x;end 对应的Fibonacci法的代码如下：function [yStar,xStar,log]=FibonacciSearch(a,b,xStep,eps)%% Fibonacci法%函数：yFunc为y关于x的函数，具体形式见最下，此时为：y=x^2+5*x%输入：a,b,eps分别代表了区间[-4,4]及精度；xStep为Fibonacci序列划分区间的精度%输出：[yStar,xStar] 分别是函数的最小值及其对应的x值，log纪录了具体步骤；%执行：在命令行中输入[yStar,xStar,log]=FibonacciSearch(-4,4,0.2,0.01),%即可开始在区间[-4,4]中查找最小值，优化精度达到0.01时停止；%figure(1);x = a:0.01:b;y = yFunc(x);plot(x,y,'k-');hold on; n=1;j=1;a(n)=a;b(n)=b;while(Fibonacci(j)*xStep(b-a))% ?¤?è????μ?μ?2é?òμ?μü′ú′?êyj=j+1;endr(1)=a(1)+(1-Fibonacci(j-1)/Fibonacci(j))*(b(1)-a(1));u(1)=a(1)+Fibonacci(j-1)/Fibonacci(j)*(b(1)-a(1));for n=1:1:j-2R(n)=yFunc(r(n));U(n)=yFunc(u(n));Z(n)=b(n)-a(n);if R(n)U(n)a(n+1)=r(n);b(n+1)=b(n);r(n+1)=u(n);u(n+1)=a(n+1)+Fibonacci(j-n-1)/Fibonacci(j-n)*(b(n+1)-a(n+1));elsea(n+1)=a(n);b(n+1)=u(n);u(n+1)=r(n);r(n+1)=a(n+1)+(1-Fibonacci(j-n-1)/Fibonacci(j-n))*(b(n+1)-a(n+1));endplot(a(n),yFunc(a(n)),'c*');plot(b(n),yFunc(b(n)),'b*');pause(0.5);endR(j-1)=yFunc(r(j-1));U(j-1)=yFunc(u(j-1));r(j)=r(j-1);u(j)=r(j-1)+eps;R(j)=yFunc(r(j));U(j)=yFunc(u(j));if R(j)U(j)a(j)=r(j);b(j)=b(j-1);elsea(j)=a(j-1);b(j)=u(j);endZ(j-1)=b(j-1)-a(j-1);Z(j)=b(j)-a(j);x=(a(j)+b(j))/2;xStar = (b(n)+a(n))/2; yStar = yFunc(xStar);plot(a(n),yFunc(a(n)),'ro');hold off;log=[a',b',r',u',R',U',Z']; function y = yFunc(x) if (length(x)1)y = x.^2+5.*x;elsey = x^2+5*x;endfunction F=Fibonacci(n)i=1;Fibonacci(2)=2;Fibonacci(1)=1;if n==0F=1;elsefor i=3:1:nFibonacci(i)=Fibonacci(i-1)+Fibonacci(i-2);endi=n;endF=Fibonacci(i);

优选法是谁提出的 优选法( 二 )

秒懂生活扩展阅读

优选法是谁提出的优选法( 二 )