黃金分割搜索算法

黃金分割搜索算法一.介紹黃金分割律是公元前六世紀(jì)古希臘數(shù)學(xué)家畢達(dá)哥拉斯所發(fā)現(xiàn)，后來(lái)古希臘美學(xué)家柏拉圖將此稱為黃金分割。這其實(shí)是一個(gè)數(shù)字的比例關(guān)系，即把一條線分為兩部分，此時(shí)長(zhǎng)段與短段之比恰恰等于整條線與長(zhǎng)段之比，其數(shù)值比為1.618:1或1:0.618，也就是說(shuō)長(zhǎng)段的平方等于全長(zhǎng)與短段的乘積。0.618，以嚴(yán)格的比例性、藝術(shù)性、和諧性，蘊(yùn)藏著豐富的美學(xué)價(jià)值。有趣的是，這個(gè)數(shù)字在自然界和人們生活中到處可見(jiàn)：人們的肚臍是人體總長(zhǎng)的黃金分割點(diǎn)，人的膝蓋是肚臍到腳跟的黃金分割點(diǎn)。大多數(shù)門窗的寬長(zhǎng)之比也是0.618...；有些植莖上，兩張相鄰葉柄的夾角是137°28'，這恰好是把圓周分成1:0.618......的兩條半徑的夾角。據(jù)研究發(fā)現(xiàn)，這種角度對(duì)植物通風(fēng)和采光效果最佳。建筑師們對(duì)數(shù)學(xué)0.618.特別偏愛(ài)，無(wú)論是古埃及的金字塔，還是巴黎圣母院，或者是近世紀(jì)的法國(guó)埃菲爾鐵塔，都有與0.618.有關(guān)的數(shù)據(jù)。人們還發(fā)現(xiàn)，一些名畫(huà)、雕塑、攝影作品的主題，大多在畫(huà)面的0.618.處。藝術(shù)家們認(rèn)為弦樂(lè)器的琴馬放在琴弦的0.618...處，能使琴聲更加柔和甜美。黃金矩形鸚鵡螺的內(nèi)部結(jié)構(gòu)蛇提農(nóng)袖廟聯(lián)合國(guó)總吝憂樓在學(xué)術(shù)界的應(yīng)用黃金矩形鸚鵡螺的內(nèi)部結(jié)構(gòu)蛇提農(nóng)袖廟聯(lián)合國(guó)總吝憂樓數(shù)字0.618...更為數(shù)學(xué)家所關(guān)注，它的出現(xiàn)，不僅解決了許多數(shù)學(xué)難題(如：十等分、五等分圓周；求18度、36度角的正弦、余弦值等)，而且還使優(yōu)選法成為可能。優(yōu)選法是一種求最優(yōu)化問(wèn)題的方法。如在煉鋼時(shí)需要加入某種化學(xué)元素來(lái)增加鋼材的強(qiáng)度，假設(shè)已知在每噸鋼中需加某化學(xué)元素的量在1000—2000克之間，為了求得最恰當(dāng)?shù)募尤肓?，需要?000克與2000克這個(gè)區(qū)間中進(jìn)行試驗(yàn)。通常是取區(qū)間的中點(diǎn)(即1500克)作試驗(yàn)。然后將試驗(yàn)結(jié)果分別與1000克和2000克時(shí)的實(shí)驗(yàn)結(jié)果作比較，從中選取強(qiáng)度較高的兩點(diǎn)作為新的區(qū)間，再取新區(qū)間的中點(diǎn)做試驗(yàn)，再比較端點(diǎn)，依次下去，直到取得最理想的結(jié)果。這種實(shí)驗(yàn)法稱為對(duì)分法。但這種方法并不是最快的實(shí)驗(yàn)方法，如果將實(shí)驗(yàn)點(diǎn)取在區(qū)間的0.618處，那么實(shí)驗(yàn)的次數(shù)將大大減少。這種取區(qū)間的0.618處作為試驗(yàn)點(diǎn)的方法就是一維的優(yōu)選法，也稱0.618法。實(shí)踐證明，對(duì)于一個(gè)因素的問(wèn)題，用“0.618法”做16次試驗(yàn)就可以完成“對(duì)分法”做2500次試驗(yàn)所達(dá)到的效果。因此大畫(huà)家達(dá)?芬奇把0.618.稱為黃金數(shù)。優(yōu)選法是一種具有廣泛應(yīng)用價(jià)值的數(shù)學(xué)方法，著名數(shù)學(xué)家華羅庚曾為普及它作出重要貢獻(xiàn)。優(yōu)選法中有一種0.618法應(yīng)用了黃金分割法。例如，在一種試驗(yàn)中，溫度的變化范圍是0°C~10°C，我們要尋找在哪個(gè)溫度時(shí)實(shí)驗(yàn)效果最佳。為此，可以先找出溫度變化范圍的黃金分割點(diǎn)，考察10x0.618=6.18(C)時(shí)的試驗(yàn)效果，再考察10x(1-0.618)=3.82(C)時(shí)的試驗(yàn)效果，比較兩者，選優(yōu)去劣。然后在縮小的變化范圍內(nèi)繼續(xù)這樣尋找，直至選出最佳溫度。黃金分割與植物有些植莖上，兩張相鄰葉柄的夾角是137°28'，這恰好是把圓周分成1:0.618的兩條半徑的夾角。據(jù)研究發(fā)現(xiàn)，這種角度對(duì)植物通風(fēng)和采光效果最佳。植物葉子，千姿百態(tài)，生機(jī)盎然，給大自然帶來(lái)了美麗的綠色世界。盡管葉子形態(tài)隨種而異，但它在莖上的排列順序(稱為葉序)，卻是極有規(guī)律的。有些植物的花瓣及主干上枝條的生長(zhǎng)，也是符合這個(gè)規(guī)律的。你從植物莖的頂端向下看，經(jīng)細(xì)心觀察，發(fā)現(xiàn)上下層中相鄰的兩片葉子之間約成137.5°角。如果每層葉子只畫(huà)一片來(lái)代表，第一層和第二層的相鄰兩葉之間的角度差約是137.5°，以后二到三層，三到四層，四到五層......兩葉之間都成這個(gè)角度。植物學(xué)家經(jīng)過(guò)計(jì)算表明：這個(gè)角度對(duì)葉子的采光、通風(fēng)都是最佳的。葉子的排布，多么精巧！葉子間的137.5°角中，藏有什么“密碼”呢？我們知道，一周是360°，360°-137.5°=222.5°，而137.5:222.5-0.618。瞧，這就是“密碼”！葉子的精巧而神奇的排布中，竟然隱藏著0.618的比例。優(yōu)選法數(shù)字0.618.更為數(shù)學(xué)家所關(guān)注，它的出現(xiàn)不僅解決了許多數(shù)學(xué)難題(如：十等分、五等分圓周；求18度、36度角的正弦、余弦值等)，而且還使優(yōu)選法成為可能。優(yōu)選法是一種求最優(yōu)化問(wèn)題的方法。如在煉鋼時(shí)需要加入某種化學(xué)元素來(lái)增加鋼材的強(qiáng)度，假設(shè)已知在每噸鋼中需加某化學(xué)元素的量在1000—2000克之間，為了求得最恰當(dāng)?shù)募尤肓?，需要?000克與2000克這個(gè)區(qū)間中進(jìn)行試驗(yàn)。通常是取區(qū)間的中點(diǎn)(即1500克)作試驗(yàn)。然后將試驗(yàn)結(jié)果分別與1000克和2000克時(shí)的實(shí)驗(yàn)結(jié)果作比較，從中選取強(qiáng)度較高的兩點(diǎn)作為新的區(qū)間，再取新區(qū)間的中點(diǎn)做試驗(yàn)，再比較端點(diǎn)，依次下去，直到取得最理想的結(jié)果。這種實(shí)驗(yàn)法稱為對(duì)分法。但這種方法并不是最快的實(shí)驗(yàn)方法，如果將實(shí)驗(yàn)點(diǎn)取在區(qū)間的0.618處，那么實(shí)驗(yàn)的次數(shù)將大大減少。這種取區(qū)間的0.618處作為試驗(yàn)點(diǎn)的方法就是一維的優(yōu)選法，也稱0.618法。實(shí)踐證明，對(duì)于一個(gè)因素的問(wèn)題，用“0.618法”做16次試驗(yàn)就可以完成“對(duì)分法”做2500次試驗(yàn)所達(dá)到的效果。其他方面的應(yīng)用人的體溫37度，室溫25度是人們感受最舒適的溫度，而25-37=0.676很接近0.618。電腦顯示器長(zhǎng)與寬比值約為1.6。(1/0.618=1.618)理想體重計(jì)算很接近身高x(1—0.618)。普通人一天上班8小時(shí)，8x0.618=4.944，上班第5個(gè)小時(shí)是最需要休息的時(shí)候，同時(shí)也是開(kāi)始期待下班的時(shí)候。小學(xué)生一節(jié)課40分鐘，而注意力只有40x(1—0.618)=15.28分鐘，因此教師必須不斷注意學(xué)生的學(xué)習(xí)。二.實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)上機(jī)實(shí)現(xiàn)黃金分割搜索算法，了解并掌握黃金分割搜索算法的內(nèi)涵。通過(guò)動(dòng)態(tài)演示搜索全過(guò)程深刻理解該算法。三.實(shí)驗(yàn)內(nèi)容與要求用黃金分割搜索算法求cos(x),x￡[-n/2,n/2]的最大值，設(shè)計(jì)出具體的程序，使之能夠動(dòng)態(tài)演示搜索過(guò)程。參考算法Input{a,b,e}X]=a+0.382*(b-a);x2=a+0.618*(b-a)『亦1)￡二亦2)while(b-a>e)if(f>f1)(a=x;x=x;f=f;x2=a+0.382*(b-a);f=f(x);}i1，12'12v71v1，Jelse(b=x;x=x;f=x;x=a+0.382*(b-a);f=f(x);}22121111xmax=(a+b)/2output{xmax}五.源代碼importjava.awt*;importjava.awt.event.*;importjavax.swing.*;publicclassGOLD{publicstaticdoublePi=3.1415926;publicstaticvoidmain(Stringargs[]){Aa=newA("");a.init();}}classAextendsJFrame{A(Strings){super(s);}publicvoidinit(){getContentPane().add(newMyPanel());setSize(600,400);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true);}}classMyPanelextendsJPanelimplementsRunnable{privatedoublex1,y1,x2,y2,a,b,x,n,l;privateintm;privateintcount;publicMyPanel(){setSize(600,400);newThread(this).start();}publicvoidrun(){inti=0;a=100.00;b=400.00;x1=a+0.328*(b-a);x2=a+0.618*(b-a);y1=250-(Math.cos((x1-250)*(GOLD.Pi/300)))*(300/GOLD.Pi);y2=250-(Math.cos((x2-250)*(GOLD.Pi/300)))*(300/GOLD.Pi);while(count<=5)if(y1>y2){a=x1;x1=x2;y1=y2;x2=a+0?618*(b-a);y2=250-(Math.cos((x2-250)*(GOLD.Pi/300)))*(300/GOLD.Pi);}else{b=x2;x2=x1;y2=y1;x1=a+0.328*(b-a);y1=250-(Math.cos((x1-250)*(GOLD.Pi/300)))*(300/GOLD.Pi);}try{Thread.sleep(1000);}catch(Exceptione){}m=(int)((a+b)/2);System?ou匕println("m="+m);n=(250-(Math.cos((((a+b)/2)-250)*(GOLD.Pi/300)))*(300/GOLD.Pi));System?out?println("n="+n);repaint();count++;}}publicvoidpaintComponent(Graphicsg){g?setColor(Color?black);g?drawLine(10,250,490,250);g?drawLine(250,100,250,340);g,drawString("0",242,262);g,drawString("x",490,262);g,drawString("y”,254,105);g?drawLine(250,100,248,104);g?drawLine(250,100,252,104);g.drawLine(490,250,486,248);g?drawLine(490,250,486,252);g.drawString("1",242,150);g,drawString("-PI/2'',98262);g.drawString("PI/2",382,262);for(intx=10;x<=490;x++){doubledouble_y=250-(Math.cos((x-250)*(GOLD.Pi/300)))*(3