複製鏈接
請複製以下鏈接發送給好友

優選法

(科學方法)

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

優選法優選法介紹

優選法在數學上就是尋找函數極值的較快較精確的計算方法。1953年美國數學家J.基弗提出單因素優選法棗分數法和0.618法(又稱黃金分割法) ,後來又提出拋物線法。至於雙因素和多因素優選法,則涉及問題較複雜,方法和思路也較多,常用的有降維法、瞎子爬山法陡度法、混合法隨機試驗法和試驗設計法等。優選法的應用範圍相當廣泛,中國數學家華羅庚在生產企業中推廣應用取得了成效。企業在新產品、新工藝研究,儀表、設備調試等方面採用優選法,能以較少的實驗次數迅速找到較優方案,在不增加設備、物資、人力和原材料的條件下,縮短工期、提高產量和質量,降低成本等。
優選法,是指研究如何用較少的試驗次數,迅速找到最優方案的一種科學方法。例如:在現代體育實踐的科學實驗中,怎樣選取最合適的配方、配比;尋找最好的操作和工藝條件;找出產品的最合理的設計參數,使產品的質量最好,產量最多,或在一定條件下使成本最低,消耗原料最少,生產週期最短等。把這種最合適、最好、最合理的方案,一般總稱為最優;把選取最合適的配方、配比,尋找最好的操作和工藝條件,給出產品最合理的設計參數,叫做優選。也就是根據問題的性質在一定條件下選取最優方案。最簡單的最優化問題是極值問題,這樣問題用微分學的知識即可解決。
實際工作中的優選問題 ,即最優化問題,大體上有兩類:一類是求函數的極值;另一類是求泛函的極值。如果目標函數有明顯的表達式,一般可用微分法、變分法、極大值原理動態規劃等分析方法求解(間接選優);如果目標函數的表達式過於複雜或根本沒有明顯的表達式,則可用數值方法或試驗最優化等直接方法求解(直接選優)。
優選法是儘可能少做試驗,儘快地找到生產和科研的最優方案的方法,優選法的應用在我國從70年代初開始,首先由我們數學家華羅庚等推廣並大量應用,優選法也叫最優化方法。

優選法優選法優點

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

優選法基本步驟

優選法 優選法
1)選定優化判據(試驗指標),確定影響因素,優選數據是用來判斷優選程度的依據。
2)優化判據與影響因素直接的關係稱為目標函數
3)優化計算。優化(選)試驗方法一般分為兩類:
分析法:同步試驗法
黑箱法:循序試驗法

優選法優選法分類

優選法 優選法
優選法分為單因素方法和多因素方法兩類。單因素方法 [1]  有平分法、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);
end
xStar = (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;
end
r(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);
end
R(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);
end
Z(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;
end
F=Fibonacci(i);
    

參考資料
  • 1.    盧開澄.《組合數學》(第4版):清華大學,2006-12:P48-P51