優選法

優選法（optimization method）以數學原理為指導，合理安排試驗，以儘可能少的試驗次數儘快找到生產和科學實驗中最優方案的科學方法。即最最佳化方法。實際工作中的優選問題 ，即最最佳化問題，大體上有兩類：一類是求函式的極值；另一類是求泛函的極值。如果目標函式有明顯的表達式，一般可用微分法、變分法、極大值原理或動態規劃等分析方法求解（間接選優）；如果目標函式的表達式過於複雜或根本沒有明顯的表達式，則可用數值方法或試驗最最佳化等直接方法求解（直接選優）。

基本介紹

• 中文名：優選法
• 外文名：optimization method
• 指導：數學原理
• 又稱：最最佳化方法
• 分類：數學
• 功能：找到最優方案

優選法介紹

優選法在數學上就是尋找函式極值的較快較精確的計算方法。1953年美國數學家J.基弗提出單因素優選法棗分數法和0.618法（又稱黃金分割法） ，後來又提出拋物線法。至於雙因素和多因素優選法，則涉及問題較複雜，方法和思路也較多，常用的有降維法、瞎子爬山法、陡度法、混合法、隨機試驗法和試驗設計法等。優選法的套用範圍相當廣泛，中國數學家華羅庚在生產企業中推廣套用取得了成效。企業在新產品、新工藝研究，儀表、設備調試等方面採用優選法，能以較少的實驗次數迅速找到較優方案，在不增加設備、物資、人力和原材料的條件下，縮短工期、提高產量和質量，降低成本等。

優選法,是指研究如何用較少的試驗次數，迅速找到最優方案的一種科學方法。例如：在現代體育實踐的科學實驗中，怎樣選取最合適的配方、配比；尋找最好的操作和工藝條件；找出產品的最合理的設計參數，使產品的質量最好，產量最多，或在一定條件下使成本最低，消耗原料最少，生產周期最短等。把這種最合適、最好、最合理的方案，一般總稱為最優；把選取最合適的配方、配比，尋找最好的操作和工藝條件，給出產品最合理的設計參數，叫做優選。也就是根據問題的性質在一定條件下選取最優方案。最簡單的最最佳化問題是極值問題，這樣問題用微分學的知識即可解決。

實際工作中的優選問題 ，即最最佳化問題，大體上有兩類：一類是求函式的極值；另一類是求泛函的極值。如果目標函式有明顯的表達式，一般可用微分法、變分法、極大值原理或動態規劃等分析方法求解（間接選優）；如果目標函式的表達式過於複雜或根本沒有明顯的表達式，則可用數值方法或試驗最最佳化等直接方法求解（直接選優）。

優選法是儘可能少做試驗，儘快地找到生產和科研的最優方案的方法,優選法的套用在我國從70年代初開始，首先由我們數學家華羅庚等推廣並大量套用,優選法也叫最最佳化方法。

優選法優點

怎樣用較少的試驗次數，打出最合適的訓練量，這就是優選法所要研究的問題。套用這種方法安排試驗，在不增加設備、投資、人力和器材的條件下，可以縮短時間、提高質量，達到增強體質．迅速提高運動成績的目的。

基本步驟

1）選定最佳化判據（試驗指標），確定影響因素，優選數據是用來判斷優選程度的依據。

優選法

2）最佳化判據與影響因素直接的關係稱為目標函式。

3）最佳化計算。最佳化(選）試驗方法一般分為兩類：

分析法：同步試驗法

黑箱法：循序試驗法

優選法分類

優選法分為單因素方法和多因素方法兩類。單因素方法有平分法、0.618法(黃金分割法)、分數法、分批試驗法等；多因素方法很多．但在理論上都不完備．主要有降維法、爬山法、單純形調優勝。隨機試驗法、試驗設計法等。優選法已在體育領域得到廣泛套用。

優選法

1.單因素優選法

如果在試驗時，只考慮一個對目標影響最大的因素，其它因素儘量保持不變，則稱為單因素問題。一般步驟：

（1）首先應估計包含最優點的試驗範圍,如果用a表示下限，b表示上限，試驗範圍為[a，b];

（2）然後將試驗結果和因素取值的關係寫成數學表達式,不能寫出表達式時，就要確定評定結果好壞的方法。

2.多因素優選法

多因素問題：首先對各個因素進行分析，找出主要因素，略去次要因素，劃“多”為“少”，以利於解決問題。

計算方法

單因素優選法解決的問題是針對函式 在區間 上有單峰極大值（或者極小值），如何通過更加有效的選點方法縮小極值點的範圍。

在（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法（黃金分割法）

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序列的套用

由於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));    else        a(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));     end    n=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;else    y = 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))      j=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-2    R(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));    else        a(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));    end    plot(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);else    a(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;else    y = x^2+5*x;end         function F=Fibonacci(n)i=1;Fibonacci(2)=2;Fibonacci(1)=1;if n==0    F=1;else    for i=3:1:n        Fibonacci(i)=Fibonacci(i-1)+Fibonacci(i-2);    end    i=n;endF=Fibonacci(i);