黃金分割搜索算法.doc

1、。黃金分割搜索算法一.介紹黃金分割律是公元前六世紀(jì)古希臘數(shù)學(xué)家畢達(dá)哥拉斯所發(fā)現(xiàn)，后來(lái)古希臘美學(xué)家柏拉圖將此稱(chēng)為黃金分割。這其實(shí)是一個(gè)數(shù)字的比例關(guān)系，即把一條線(xiàn)分為兩部分，此時(shí)長(zhǎng)段與短段之比恰恰等于整條線(xiàn)與長(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ù)門(mén)窗的寬長(zhǎng)之比也是0.618；有些植莖上，兩張相鄰葉柄的夾角是13728 ，這恰好是把圓周分成1:0.

2、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處，能使琴聲更加柔和甜美。1。在學(xué)術(shù)界的應(yīng)用數(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)增加鋼材的

3、強(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)法稱(chēng)為對(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)選法，也稱(chēng)0.618法。實(shí)踐證明，對(duì)于一個(gè)因素的問(wèn)題，用

4、“0.618 法 ”做 16 次試驗(yàn)就可以完成“對(duì)分法 ”做 2500 次試驗(yàn)所達(dá)到的效果。因此大畫(huà)家達(dá)芬奇把 0.618 稱(chēng)為黃金數(shù)。優(yōu)選法是一種具有廣泛應(yīng)用價(jià)值的數(shù)學(xué)方法，著名數(shù)學(xué)家華羅庚曾為普及它作出重要貢獻(xiàn)。優(yōu)選法中有一種0.618法應(yīng)用了黃金分割法。例如，在一種試驗(yàn)中，溫度的變化范圍是 0 10 ，我們要尋找在哪個(gè)溫度時(shí)實(shí)驗(yàn)效果最佳。為此，可以先找出溫度變化范圍的黃金分割點(diǎn)，考察 100.618=6.18()時(shí)的試驗(yàn)效果，再考察10(1-0.618)=3.82( ) 時(shí)的試驗(yàn)效果，比較兩者，選優(yōu)去劣。然后在縮小的變化范圍內(nèi)繼續(xù)這樣尋找，直至選出最佳溫度。黃金分割與植物有些植莖上，兩張

5、相鄰葉柄的夾角是137 28 ，這恰好是把圓周分成1:0.618的兩條半徑的夾角。據(jù)研究發(fā)現(xiàn)，這種角度對(duì)植物通風(fēng)和采光效果最佳。植物葉子，千姿百態(tài)，生機(jī)盎然，給大自然帶來(lái)了美麗的綠色世界。盡管葉子形態(tài)隨種而異，但它在莖上的排列順序( 稱(chēng)為葉序) ，卻是極有規(guī)律的。有些植物的花瓣及主干上枝條的生長(zhǎng)，也是符合這個(gè)規(guī)律的。你從植物莖的頂端向下看，經(jīng)細(xì)心觀(guān)察，發(fā)現(xiàn)上下層中相鄰的兩片葉子之間約成137.5 角。 如果每層葉子只畫(huà)一片來(lái)代表，第一層和第二層的。2。相鄰兩葉之間的角度差約是137.5 ，以后二到三層，三到四層，四到五層兩葉之間都成這個(gè)角度。植物學(xué)家經(jīng)過(guò)計(jì)算表明：這個(gè)角度對(duì)葉子的采光、通風(fēng)都是

6、最佳的。葉子的排布，多么精巧！葉子間的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ù)募尤肓?/p>

7、，需要在1000 克與 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)法稱(chēng)為對(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)選法，也稱(chēng)0.618法。實(shí)踐證明，對(duì)于一個(gè)因素的問(wèn)題，用“0.618法 ”做 16 次試驗(yàn)就可以完成“對(duì)分法 ”做 2500 次試驗(yàn)所達(dá)到的效果。其他方

8、面的應(yīng)用1、人的體溫37 度，室溫25 度是人們感受最舒適的溫度，而2537=0.676很接近 0.618 。2電腦顯示器長(zhǎng)與寬比值約為1.6 。 (1/0.618=1.618)3理想體重計(jì)算很接近身高(1 0.618)。4普通人一天上班8 小時(shí)， 80.618=4.944，上班第5 個(gè)小時(shí)是最需要休息的時(shí)候，同時(shí)也是開(kāi)始期待下班的時(shí)候。5小學(xué)生一節(jié)課40 分鐘，而注意力只有40(1 0.618)=15.28分鐘，因此教師必須不斷注意學(xué)生的學(xué)習(xí)。3。二實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)上機(jī)實(shí)現(xiàn)黃金分割搜索算法，了解并掌握黃金分割搜索算法的內(nèi)涵。通過(guò)動(dòng)態(tài)演示搜索全過(guò)程深刻理解該算法。三 .實(shí)驗(yàn)內(nèi)容與要求用黃金分割搜索

9、算法求cos(x),x- /2, /2 的最大值，設(shè)計(jì)出具體的程序，使之能夠動(dòng)態(tài)演示搜索過(guò)程。四參考算法1. Inputa,b,e2. x 1=a+0.382*(b-a);x 2=a+0.618*(b-a)3. f 1=f(x 1),f 2=f(x 2)4. while(b-ae)5. if(ff1)5.1 a=x1;x1=x ;f1=f ;x2=a+0.382*(b-a);f=f(x1);221else5.2 b=x;x2=x ;f2=x ;x=a+0.382*(b-a);f1=f(x1);21116. x =(a+b)/2max7. output xmax 五源代碼import java.

10、awt.*;import java.awt.event.*;。4。import javax.swing.*;public class GOLDpublic static double Pi=3.1415926;public static void main(String args)A a=new A( ? );a.init();class A extends JFrameA (String s)super(s);public void init()getContentPane().add(new MyPanel();setSize(600,400);setDefaultCloseOperati

11、on(JFrame.EXIT_ON_CLOSE);setVisible(true);class MyPanel extends JPanel implements Runnableprivate double x1,y1,x2,y2,a,b,x,n,l;private int m;private int count;public MyPanel()setSize(600, 400);new Thread(this).start();public void run()int i=0;a=100.00;b=400.00;x1=a+0.328*(b-a);x2=a+0.618*(b-a);y1=25

12、0-(Math.cos(x1-250)*(GOLD.Pi/300)*(300/GOLD.Pi);。5。y2=250-(Math.cos(x2-250)*(GOLD.Pi/300)*(300/GOLD.Pi);while(county2)a=x1;x1=x2;y1=y2;x2=a+0.618*(b-a);y2=250-(Math.cos(x2-250)*(GOLD.Pi/300)*(300/GOLD.Pi);elseb=x2;x2=x1;y2=y1;x1=a+0.328*(b-a);y1=250-(Math.cos(x1-250)*(GOLD.Pi/300)*(300/GOLD.Pi);tryT

13、hread.sleep(1000);catch (Exception e)m=(int)(a+b)/2);System.out.println(m=+m);n=(250-(Math.cos(a+b)/2)-250)*(GOLD.Pi/300)*(300/GOLD.Pi);System.out.println(n=+n);repaint();count+;public void paintComponent(Graphics g)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);。6。g.drawLine(490,250,486,248);g.drawLine(490,250,486,252);g.drawStr