演演算法是誰

1. 圓周率的計算方法是如何發展的

在不同的歷史時期，受制於生產力發展水平和科技發展水平，π 的計算方法、計算效率、准確度各不相同。圓周率（π）的計算方法的探索主要有實驗時期、幾何法時期、分析法時期、計算機時代。

1、實驗時期——對圓周率的估算：

一塊古巴比倫石匾（約產於公元前1900年至1600年）清楚地記載了圓周率 = 25/8 = 3.125。同一時期的古埃及文物，萊因德數學紙草書（Rhind Mathematical Papyrus）也表明圓周率等於分數16/9的平方，約等於3.1605。埃及人似乎在更早的時候就知道圓周率了。

英國作家 John Taylor (1781–1864) 在其名著《金字塔》（《The Great Pyramid: Why was it built, and who built it?》）中指出，造於公元前2500年左右的胡夫金字塔和圓周率有關。例如，金字塔的周長和高度之比等於圓周率的兩倍，正好等於圓的周長和半徑之比。公元前800至600年成文的古印度宗教巨著《百道梵書》（Satapatha Brahmana）顯示了圓周率等於分數339/108，約等於3.139。

2. 誰能解釋基因演演算法

基因演演算法 1975年 John Holland 學者所提出
成為非常著名的演演算法
Genetic Algorithm (GA)
基因演演算法 又稱: 遺傳演演算法
基因演演算法的概念
將問題編碼成 染色體的型式
基因: 0 or 1
染色體: x = 0 1 0 0 1 1 0
設計 適應函數 (fitness function)
f(x) :適應函數，給一 x 可得一 適應值 f(x)
適應值愈高, 表愈適應環境
基因演演算法三個基本動作
選擇(Selection)與復制 (Reproction)：
X = 0 1 0 0 1 1 0
選擇 適應值高 之染色體
復製成多個染色體
基因演演算法三個基本動作
交換 (crossover)：
父：0 1 0 0 1 1 0 0 1 1 1 0 1 0
母：1 0 1 1 0 0 1 1 0 0 0 1 0 1
交換 基因演演算法三個基本動作
突變 (mutation)：
0 1 0 0 1 1 0
1 選擇 產生初始族群
計算適應値 復制 交換
突變 產生下一子代
是否滿足 停止條件
產生最適個體
否是 基因演演算法 基本架構圖
取材自:輔仁大學資管系林文修老師
選擇與 基因操作階段
評估階段 初始階段 生成下一世代
問題否是 生成母體
評估適應函數
符合停止條件？
選擇 復制 交換 突變
開始 結束 編碼 適應函數
領域知識 表現型 基因型
解碼 基因演演算法 之流程圖
取材自:輔仁大學資管系林文修老師
演演算法步驟 Step1：隨機產生N個染色體
Step2：利用適應函數算出每個染色體的適應值
Step3 : 選擇與復制: 選擇 適應值高 之染色體 復製成多個染色體
Step4：利用交換及突變的動作產生新的染色體
Step5：測試新染色體的適應值是否達到門檻值
是：則 停止
否：則 Go to Step3
範例1 假設 x 在 (0,31) 之間，y = x ，求 x = ，y 可得最大值
將問題編碼成 基因的型式
x : 0 0 0 0 0～1 1 1 1 1
設計 適應函數 (fitness function)
f (x) = y = x
範例1 <Step 1, 2, 3>
取4組染色體 x f (x) f (x) /m 復制個數
0 1 1 1 0 (14) 196 0.71 1
1 1 0 0 0 (24) 576 2.07 2
1 0 0 0 1 (17) 289 1.04 1
0 0 1 1 1 ( 7) 49 0.18 0
m = = 278
196+576+289+49
4 範例1 <Step 4.1> 交換
x f (x)
0 1 1 1 0 0 1 0 0 0 (8) 8 = 64
1 1 0 0 0 1 1 1 1 0 (30) 30 = 900
1 1 0 0 0 1 1 0 0 1 (25) 25 = 625
1 0 0 0 1 1 0 0 0 0 (16) 16 = 256
交換 交換 範例1 <Step 4.1> 交換
交換點 下一子代 x f (x)
0 1 1 1 0 2 0 1 0 0 0 8 64
1 1 0 0 0 2 1 1 1 1 0 30 900
1 1 0 0 0 4 1 1 0 0 1 25 625
1 0 0 0 1 4 1 0 0 0 0 16 256
範例1 <Step4.2>突變 (機率0.1)
4個染色體× 5個基因 = 20個基因
20 × 0.1 = 2 有2個基因要突變
1 st：0 1 0 0 0 0 1 1 0 0 (12)
第一個染色體之第3基因突變
3 rd：1 1 0 0 1 1 0 0 0 1 (17)
第三個染色體之第2基因突變
範例1 <Step5>
停止條件有三種可能方法：
設定繁衍代數 (ex：1000代)
收斂 (ex：最佳適應值已50代未改進)
適應值達到門檻
否則，Go to Step3
編碼（coding）-1
運用基因演化演算法的目的是求問題的解，在初始階段的編碼步驟是把與問題相關變數的值（或稱為問題解）以特定編碼的方式將其組合成一條染色體 （chromosome，或稱為字串string），每一條染色體即代表一可能的問題解答，
最簡單而且被廣泛使用的是標准二進位編碼法（Standard binary encoding）。這種編碼法是將染色體內的每個基因用二進位碼{0，1}來表示，而編碼後的染色體即是一串由01組合字串（string）。

3. 模擬退火演算法是一種什麼演算法

模擬退火演算法（Simulate Anneal Arithmetic，SAA）是一種通用概率演演算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發明。而V.Čern&amp;yacute;在1985年也獨立發明此演演算法。模擬退火演算法是解決TSP問題的有效方法之一。

產生新解的方式很多，以二進制編碼為例，假如一個解為01001101，可以隨機選取一位進行取反。假如選中了第3位，則第3位按位取反，新解為01101101。這個過程有點類似於遺傳演算法中的基因突變。上述演算法描述中每個溫度值只產生了一次新解，實際問題中可以產生多次。

演算法的關鍵在於Metropolis准則。如果新解的函數值較小，自然要把新解作為當前解；如果新解函數值較大，則它仍有一定概率被選作當前解。這個概率與df有關，df越大，說明新解越差，它被選作當前解的概率也越小；此外，這個概率還和當前溫度有關，當前溫度越高，概率越大（類似於分子熱運動越劇烈）。