近年演算法的發展

⑴ 卡爾曼濾波演算法的發展歷史如何

全球定位系統（GPS）是新一代的精密衛星導航定位系統。由於其全球性、全天候以及連續實時三維定位等特點，在軍事和民用領域得到了廣泛的發展。近年來，隨著科學技術的發展，GPS導航和定位技術已向高精度、高動態的方向發展。但是由於GPS定位包含許多誤差源，尤其是測量隨機誤差和衛星的幾何位置誤差，使定位精度受到影響。利用傳統的方法很難消除。而GPS動態濾波是消除GPS定位隨機誤差的重要方法，即利用特定的濾波方法消除各種隨機誤差，從而提高GPS導航定位精度。 經典的最優濾波包括：Wiener濾波和Kalman濾波。由於Wiener濾波採用頻域法，作用受到限制；而Kalman濾波採用時域狀態空間法，適合於多變數系統和時變系統及非平穩隨機過程，且由於其遞推特點容易在計算機上實現，因此得到了廣泛的應用。為此，本文對Kalman濾波方法進行了深入的研究，並取得了一些成果。 本文首先概述了GPS的組成、應用及最新動態。在此基礎上介紹了GPS的導航定位原理，給出了衛星可見性演算法、選星演算法及定位演算法。然後介紹了卡爾曼濾波的基本原理，在此基礎上對動態用戶的飛行軌跡進行了模擬，對「singer」模型下的8狀態和11狀態卡爾曼濾波演算法進行了模擬分析，同時對「當前」統計模型下11狀態卡爾曼濾波演算法進行了模擬分析，並對濾波前後的定位精度進行了比較。在此基礎上，就如何提高濾波器的動態性能作者提出了改進演算法，即自適應卡爾曼濾波演算法、帶漸消因子的優化演算法及改進的優化演算法，並分別進行了模擬分析。最後作者將卡爾曼濾波演算法分別應用於GPS/DR和GPS/INS組合導航定位系統中，並分別對這兩種系統進行了建模和模擬分析，取得了較理想的結果。 本文的研究工作，對改進傳統的濾波方法有一定的參考和應用價值，並對卡爾曼濾波方法在提高GPS動態導航定位精度方面的應用起到積極的促進作用。

⑵ 粒子群演算法國內發展

粒子群演算法介紹（摘自http://blog.sina.com.cn/newtech）
優化問題是工業設計中經常遇到的問題,許多問題最後都可以歸結為優化問題. 為了解決各種各樣的優化問題,人們提出了許多優化演算法,比較著名的有爬山法、遺傳演算法等.優化問題有兩個主要問題:一是要求尋找全局最小點,二是要求有較高的收斂速度. 爬山法精度較高,但是易於陷入局部極小. 遺傳演算法屬於進化演算法( Evolutionary Algorithms) 的一種,它通過模仿自然界的選擇與遺傳的機理來尋找最優解. 遺傳演算法有三個基本運算元:選擇、交叉和變異. 但是遺傳演算法的編程實現比較復雜,首先需要對問題進行編碼,找到最優解之後還需要對問題進行解碼,另外三個運算元的實現也有許多參數,如交叉率和變異率,並且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗.1995 年Eberhart 博士和kennedy 博士提出了一種新的演算法;粒子群優化(Partical Swarm Optimization -PSO) 演算法 . 這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視,並且在解決實際問題中展示了其優越性.

粒子群優化(Partical Swarm Optimization - PSO) 演算法是近年來發展起來的一種新的進化演算法( Evolu2tionary Algorithm - EA) .PSO 演算法屬於進化演算法的一種,和遺傳演算法相似,它也是從隨機解出發,通過迭代尋找最優解,它也是通過適應度來評價解的品質. 但是它比遺傳演算法規則更為簡單,它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作. 它通過追隨當前搜索到的最優值來尋找全局最優 .

粒子群演算法

1. 引言

粒子群優化演算法(PSO)是一種進化計算技術(evolutionary computation)，有Eberhart博士和kennedy博士發明。源於對鳥群捕食的行為研究

PSO同遺傳演算法類似，是一種基於疊代的優化工具。系統初始化為一組隨機解，通過疊代搜尋最優值。但是並沒有遺傳演算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優的粒子進行搜索。詳細的步驟以後的章節介紹

同遺傳演算法比較，PSO的優勢在於簡單容易實現並且沒有許多參數需要調整。目前已廣泛應用於函數優化，神經網路訓練，模糊系統控制以及其他遺傳演算法的應用領域

2. 背景: 人工生命

"人工生命"是來研究具有某些生命基本特徵的人工系統. 人工生命包括兩方面的內容

1. 研究如何利用計算技術研究生物現象
2. 研究如何利用生物技術研究計算問題

我們現在關注的是第二部分的內容. 現在已經有很多源於生物現象的計算技巧. 例如, 人工神經網路是簡化的大腦模型. 遺傳演算法是模擬基因進化過程的.

現在我們討論另一種生物系統- 社會系統. 更確切的是, 在由簡單個體組成的群落與環境以及個體之間的互動行為. 也可稱做"群智能"(swarm intelligence). 這些模擬系統利用局部信息從而可能產生不可預測的群體行為

例如floys 和 boids, 他們都用來模擬魚群和鳥群的運動規律, 主要用於計算機視覺和計算機輔助設計.

在計算智能(computational intelligence)領域有兩種基於群智能的演算法. 蟻群演算法(ant colony optimization)和粒子群演算法(particle swarm optimization). 前者是對螞蟻群落食物採集過程的模擬. 已經成功運用在很多離散優化問題上.

粒子群優化演算法(PSO) 也是起源對簡單社會系統的模擬. 最初設想是模擬鳥群覓食的過程. 但後來發現PSO是一種很好的優化工具.

3. 演算法介紹

如前所述，PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的例子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索

PSO 初始化為一群隨機粒子(隨機解)。然後通過疊代找到最優解。在每一次疊代中，粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優解。這個解叫做個體極值pBest. 另一個極值是整個種群目前找到的最優解。這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分最為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。

在找到這兩個最優值時, 粒子根據如下的公式來更新自己的速度和新的位置

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] 是粒子的速度, persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於（0， 1）之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2.

程序的偽代碼如下

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用戶設定的Vmax，那麼這一維的速度就被限定為Vmax

4. 遺傳演算法和 PSO 的比較

大多數演化計算技術都是用同樣的過程
1. 種群隨機初始化
2. 對種群內的每一個個體計算適應值(fitness value).適應值與最優解的距離直接有關
3. 種群根據適應值進行復制
4. 如果終止條件滿足的話，就停止，否則轉步驟2

從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機初始化種群，而且都使用適應值來評價系統，而且都根據適應值來進行一定的隨機搜索。兩個系統都不是保證一定找到最優解

但是，PSO 沒有遺傳操作如交叉(crossover)和變異(mutation). 而是根據自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶。

與遺傳演算法比較, PSO 的信息共享機制是很不同的. 在遺傳演算法中，染色體(chromosomes) 互相共享信息，所以整個種群的移動是比較均勻的向最優區域移動. 在PSO中, 只有gBest (or lBest) 給出信息給其他的粒子，這是單向的信息流動. 整個搜索更新過程是跟隨當前最優解的過程. 與遺傳演算法比較, 在大多數的情況下，所有的粒子可能更快的收斂於最優解

5. 人工神經網路 和 PSO

人工神經網路(ANN)是模擬大腦分析過程的簡單數學模型，反向轉播演算法是最流行的神經網路訓練演算法。進來也有很多研究開始利用演化計算(evolutionary computation)技術來研究人工神經網路的各個方面。

演化計算可以用來研究神經網路的三個方面：網路連接權重，網路結構(網路拓撲結構，傳遞函數)，網路學習演算法。

不過大多數這方面的工作都集中在網路連接權重，和網路拓撲結構上。在GA中，網路權重和/或拓撲結構一般編碼為染色體(Chromosome)，適應函數(fitness function)的選擇一般根據研究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應值

演化計算的優勢在於可以處理一些傳統方法不能處理的例子例如不可導的節點傳遞函數或者沒有梯度信息存在。但是缺點在於：在某些問題上性能並不是特別好。2. 網路權重的編碼而且遺傳運算元的選擇有時比較麻煩

最近已經有一些利用PSO來代替反向傳播演算法來訓練神經網路的論文。研究表明PSO 是一種很有潛力的神經網路演算法。PSO速度比較快而且可以得到比較好的結果。而且還沒有遺傳演算法碰到的問題

這里用一個簡單的例子說明PSO訓練神經網路的過程。這個例子使用分類問題的基準函數(Benchmark function)IRIS數據集。(Iris 是一種鳶尾屬植物) 在數據記錄中，每組數據包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數據. 這樣總共有150組數據或模式。

我們用3層的神經網路來做分類。現在有四個輸入和三個輸出。所以神經網路的輸入層有4個節點，輸出層有3個節點我們也可以動態調節隱含層節點的數目，不過這里我們假定隱含層有6個節點。我們也可以訓練神經網路中其他的參數。不過這里我們只是來確定網路權重。粒子就表示神經網路的一組權重，應該是4*6+6*3=42個參數。權重的范圍設定為[-100，100] (這只是一個例子，在實際情況中可能需要試驗調整).在完成編碼以後，我們需要確定適應函數。對於分類問題，我們把所有的數據送入神經網路，網路的權重有粒子的參數決定。然後記錄所有的錯誤分類的數目作為那個粒子的適應值。現在我們就利用PSO來訓練神經網路來獲得盡可能低的錯誤分類數目。PSO本身並沒有很多的參數需要調整。所以在實驗中只需要調整隱含層的節點數目和權重的范圍以取得較好的分類效果。

6. PSO的參數設置

從上面的例子我們可以看到應用PSO解決優化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數
PSO的一個優勢就是採用實數編碼, 不需要像遺傳演算法一樣是二進制編碼(或者採用針對實數的遺傳操作.例如對於問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應度函數就是f(x). 接著我們就可以利用前面的過程去尋優.這個尋優過程是一個疊代過程, 中止條件一般為設置為達到最大循環數或者最小錯誤

PSO中並沒有許多需要調節的參數,下面列出了這些參數以及經驗設置

粒子數: 一般取 20 – 40. 其實對於大部分的問題10個粒子已經足夠可以取得好的結果, 不過對於比較難的問題或者特定類別的問題, 粒子數可以取到100 或 200

粒子的長度: 這是由優化問題決定, 就是問題解的長度

粒子的范圍: 由優化問題決定,每一維可是設定不同的范圍

Vmax: 最大速度,決定粒子在一個循環中最大的移動距離,通常設定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬於 [-10, 10], 那麼 Vmax 的大小就是 20

學習因子: c1 和 c2 通常等於 2. 不過在文獻中也有其他的取值. 但是一般 c1 等於 c2 並且范圍在0和4之間

中止條件: 最大循環數以及最小錯誤要求. 例如, 在上面的神經網路訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環設定為2000, 這個中止條件由具體的問題確定.

全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優化演算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優. 後者收斂速度慢一點不過很難陷入局部最優. 在實際應用中, 可以先用全局PSO找到大致的結果,再有局部PSO進行搜索.

另外的一個參數是慣性權重, 由Shi 和Eberhart提出, 有興趣的可以參考他們1998年的論文(題目: A modified particle swarm optimizer)

⑶ 量子遺傳演算法的國內外研究現狀

當前科學技術正進入多學科互相交叉、互相滲透、互相影響的時代，生命科學與工程科學的交叉、滲透和相互促進是其中一個典型例子，也是近代科學技術發展的一個顯著特點。遺傳演算法的蓬勃發展正體現了科學發展的這一特點和趨勢。
製造機器智能一直是人類的夢想，人們為此付出了巨大的努力。人工智慧技術的出現，就是人們得到的成果。但是，近年來，隨著人工智慧應用領域的不斷拓廣，傳統的基於符號處理機制的人工智慧方法在知識表示、處理模式信息及解決組合爆炸等方面所碰到的問題已變得越來越突出，這些困難甚至使某些學者對強人工智慧提出了強烈批判，對人工智慧的可能性提出了質疑。
眾所周知，在人工智慧領域中，有不少問題需要在復雜而龐大的搜索空間中尋找最優解或准優解。像貨朗擔問題和規劃問題等組合優化問題就是典型的例子。在求解此類問題時，若不能利用問題的固有知識來縮小搜索空間則會產生搜索的組合爆炸。因此，研究能在搜索過程中自動獲得和積累有關搜索空間的知識，並能自適應地控制搜索過程，從而得到最優解或准有解的通用搜索演算法一直是令人矚目的課題。遺傳演算法就是在這種背景下產生並經實踐證明特別有效的演算法。
遺傳演算法(Genetic Algorithm, GA)是近年來迅速發展起來的一種全新的隨機搜索與優化演算法,其基本思想是基於Darw in的進化論和Mendel的遺傳學說。該演算法由密執安大學教授Holland及其學生於1975年創建。此後，遺傳演算法的研究引起了國內外學者的關注。自1985年以來.國際上已召開了多次遺傳演算法的學術會議和研討會.國際遺傳演算法學會組織召開的ICGA( International Conference on Genetic Algorithms)會議和FOGA( Workshop on Foundation of Genetic Algorithms)會議。為研究和應用遺傳演算法提供了國際交流的機會。
作為一種通用的問題求解方法，遺傳演算法採用簡單的編碼技術來表示各種復雜的結構並通過對一組編碼表示進行簡單的遺傳操作和優勝劣汰的自然選擇來指導學習和確定搜索的方向。
近年來，遺傳演算法已被成功地應用於下業、經濟答理、交通運輸、工業設計等不同領域.解決了許多問題。例如，可靠性優化、流水車間調度、作業車間調度、機器調度、設備布局設計、圖像處理以及數據挖掘等。本文將從遺傳演算法的理論和技術兩方而概述目前的研究現狀。描述遺傳演算法的主要特點、基木原理以及各種改進演算法，介紹遺傳演算法的程序設計。
遺傳程序設計是借鑒生物界的自然選擇和遺傳機制，在遺傳演算法的基礎上發展起來的搜索演算法，它己成為進化計算的一個新分支。在標準的遺傳演算法中，由定長字元串(問題的可行解)組成的群體藉助於復制、交叉、變異等遺傳操作不斷進化找到問題的最優解或次優解。遺傳程序設計運用遺傳演算法的思想，常採用樹的結構來表示計算機程序，從而解決問題。對於許多問題，包括人工智慧和機器學習上的問題都可看作是需要發現一個計算機程序，即對特定輸入產生特定輸出的程序，形式化為程序歸納，那麼遺傳程序設計提供了實現程序歸納的方法。
把遺傳演算法和計算機程序結合起來的思想出現在遺傳演算法中，Holland把產生式語言和遺傳演算法結合起來實現分類系統，還有一些遺傳演算法應用領域的研究者將類似於遺傳演算法的遺傳操作施加於樹結構的程序上。
近年來，遺傳程序設計運用遺傳演算法的思想自動生成計算機程序解決了許多問題，如預測、分類、符號回歸和圖像處理等，作為一種新技術它己經與遺傳演算法並駕齊驅。 1996年，舉行了第1次遺傳程序設計國際會議，該領域己引起越來越多的相關學者們的興趣。
1967年，Holland的學生J.D.Bagley在博士論文中首次提出「遺傳演算法（Genetic Algorithms）」一詞。此後，Holland指導學生完成了多篇有關遺傳演算法研究的論文。1971年，R.B.Hollstien在他的博士論文中首次把遺傳演算法用於函數優化。1975年是遺傳演算法研究歷史上十分重要的一年。這一年Holland出版了他的著名專著《自然系統和人工系統的自適應》（Adaptation in Natural and Artificial Systems），這是第一本系統論述遺傳演算法的專著，因此有人把1975年作為遺傳演算法的誕生年。Holland在該書中系統地闡述了遺傳演算法的基本理論和方法，並提出了對遺傳演算法的理論研究和發展極其重要的模式理論（schema theory）。該理論首次確認了結構重組遺傳操作對於獲得隱並行性的重要性。同年，K.A.De Jong完成了他的博士論文《一類遺傳自適應系統的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。該論文所做的研究工作，可看作是遺傳演算法發展進程中的一個里程碑，這是因為，他把Holland的模式理論與他的計算實驗結合起來。盡管De Jong和Hollstien 一樣主要側重於函數優化的應用研究，但他將選擇、交叉和變異操作進一步完善和系統化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術。可以認為，De Jong的研究工作為遺傳演算法及其應用打下了堅實的基礎，他所得出的許多結論，迄今仍具有普遍的指導意義。
進入八十年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。1985年，在美國召開了第一屆遺傳演算法國際會議（International Conference on Genetic Algorithms ，ICGA），並且成立國際遺傳演算法學會（International Society of Genetic Algorithms ，ISGA），以後每兩年舉行一次。
1989年，Holland的學生D.E.Goldberg出版了專著《搜索、優化和機器學習中的遺傳演算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。該書總結了遺傳演算法研究的主要成果，對遺傳演算法及其應用作了全面而系統的論述。同年，美國斯坦福大學的Koza基於自然選擇原則創造性地提出了用層次化的計算機程序來表達問題的遺傳程序設計( genetic programming, GP)方法，成功地解決了許多問題。
在歐洲，從1990年開始每隔一年舉辦一次Parallel Problem Solving from Nature 學術會議，其中遺傳演算法是會議主要內容之一。此外，以遺傳演算法的理論基礎為中心的學術會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。這些國際會議論文，集中反映了遺傳演算法近些年來的最新發展和動向。
1991年，L.Davis編輯出版了《遺傳演算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳演算法在工程技術和社會生活中的大量應用實例。
1992年，Koza發表了他的專著《遺傳程序設計:基於自然選擇法則的計算機程序設計》」。1994年，他又出版了《遺傳程序設計，第二冊:可重用程序的自動發現》深化了遺傳程序設計的研究，使程序設計自動化展現了新局面。有關遺傳演算法的學術論文也不斷在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》\《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等雜志上發表。1993年，MIT出版社創刊了新雜志《Evolutionary Computation》。1997年，IEEE又創刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》雜志即將發刊，由模糊集合創始人L.A.Zadeh教授為名譽主編。目前，關於遺傳演算法研究的熱潮仍在持續，越來越多的從事不同領域的研究人員已經或正在置身於有關遺傳演算法的研究或應用之中。

⑷ music演算法的理論發展及應用

MUSIC（Multiple Signal Classification多信號分類）演算法是1979年由美國人R.O.Schmidt提出的，它標志著空間譜估計測向進入了繁榮發展的階段。它將「向量空間」的概念引入了空間譜估計領域，經過三十年的發展，可以說其理論已經比較成熟。
自80年代以來，人們對基於特徵分解的超解析度空間譜估計演算法進行了廣泛深入的研究，並提出了一系列高效的處理方法，其中最經典的是多信號分類（MUSIC）演算法，這種演算法要經過一維搜索才能求出信源的來向，而相對最大似然（ML）和加權子空間擬合（WSF）等多維搜索演算法的運算量已經減少了很多。以MUSIC為代表的演算法存在一個缺點，即對相干信號處理的不理想。在針對相干信號源的一系列處理方案中，比較經典的是空間平滑技術，如空間平滑（SS）和修正的空間平滑（MSS）演算法。然而，空間平滑技術是以損失陣列有效孔徑為代價的，而且只適用於等距均勻線陣（ULA）。
事實上空間譜估計演算法都是在已知信號源數目下計算的，而在實際應用中這是不可能的，只能根據觀測數據對源數目進行估計。R.O.Schmidt在他的經典之作中提出了依據陣列協方差矩陣特徵值的分布來估計信號源的方法。這種方法在理論上是完美的，至少對獨立源和部分相關源是正確的，但實際上由於數據長度有限，很大程度上只能依靠主觀判斷來確定源數。

⑸ 演算法的歷史

「演算法」即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了演算法這個概念。「演算法」原為algorism，意思是阿拉伯數字的運演算法則，在18世紀演變為algorithm。歐幾里得演算法被人們認為是史上第一個演算法。 第一次編寫程序是Ada Byron於1842年為巴貝奇分析機編寫求解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。 因為well-defined procere缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用。

⑹ 偽·從零開始學演算法 - 1.2 演算法的歷史

我在寫1.1節的時候本來是要寫這個的，但是突然就忘了……就作為一節來寫吧。

順便說一下，1946年的今天，世界上第一台通用電腦——電子數值積分計算機在美國賓夕法尼亞大學正式啟用，就是那個ENIAC。

別只想著情人節，要不是幾十年來科技的進步，你們才沒機會在朋友圈、空間什麼的大秀恩愛。

中文的「演算法」一詞至少在唐代就出現了，在此之前也有「術」「算術」等詞，最早出現在《周髀算經》《九章算術》。而且，「演算法」一詞的含義從古到今幾乎沒有發生變化。

英文的「演算法」（algorithm）一詞來源於9世紀波斯數學家花拉子米（al-Khwārizmī，780?~850?）——就是那個解決一次方程及一元二次方程的方法的人。花拉子米的拉丁文譯名是「Algoritmi」。英文對「演算法」原譯為「algorism」，意思是花拉子米的運演算法則，在18世紀演變為「algorithm」。這個詞出現於12世紀，指的是用阿拉伯數字進行算術運算的過程。

對於算籌、算盤的操作的方法，我不知道是否屬於演算法。

約公元前300年記載於《幾何原本》中的輾轉相除法（歐幾里得演算法）被人們認為是史上第一個演算法，可以求兩數的最大公約數。直到今天，它還有很大的用途。

《九章算術》給出了四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃拉托斯特尼篩法，線性方程組求解的演算法。

三國時代的劉徽給出求圓周率的演算法：劉徽割圓術，比阿基米德割圓術得出的結果更加精確。祖沖之使用該方法將圓周率的准確值計算到了3.1415926和3.1415927之間，保持了世界最准確圓周率達900年之久。

唐代以來，歷代更有許多專門論述「演算法」的專著。宋代的秦九韶提出的秦九韶演算法，直到今天仍是多項式求值比較先進的演算法。

在9世紀的阿拉伯世界，花拉子米寫成《代數學》，其對解決一次方程及一元二次方程的方法催生了代數——大家熟知的求多元（尤其是二元）一次方程和一元二次方程的解法就來源於此。700多年後，三次方程、四次方程的求根公式才被得出。

牛頓於1671年提出的牛頓法，相比於二分法可以更快速地求函數的根或者是函數的極值。

17世紀起，早期的機械計算機出現了。從加法到傅里葉變換，它們的功能越來越強大。

工業革命帶來了紡織業的變革，出現了可以自動織出帶花紋的布的織布機，它們使用打孔卡輸入指令。這種設計也被英國數學家查爾斯·巴貝奇設計的分析機使用。

拜倫的女兒愛達·勒芙蕾絲（Ada Byron；Ada, Countess of Lovelace）於1842年為這個想像中的機器編寫求解伯努利微分方程的程序，因此愛達·勒芙蕾絲被大多數人認為是 世界上第一位程序員 。但是，這個機器因為種種原因，直到巴貝奇去世也沒有被真正地製造出來。

後來的數學家對演算法的貢獻大多在於數理邏輯的構建上，在此我因為知識缺乏，看不懂資料，不便講述。感興趣的話可以看一下參考資料。

20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要的作用。

在此之後，演算法更偏向於計算機科學領域，各種解決不同問題的演算法也層出不窮，涉及排序、統計、線性規劃、搜索、壓縮等方面。

到了現在，隨著人工智慧和機器學習的發展，涉及到神經網路的演算法變得越發重要。

The Best of the 20th Century: Editors Name Top 10 Algorithms

http://www.uta.e/faculty/rcli/TopTen/topten.pdf

⑺ 演算法應用的利弊！（致各平台）

近年來，演算法應用在給經濟、 社會 發展注入新動能的同時，演算法歧視、「大數據殺熟」、誘導沉迷等演算法不合理應用也給我們的生活帶來煩惱。針對這些問題，國家網信辦等四部門聯合制定的《互聯網信息服務演算法推薦管理規定》1月4日正式發布，向各種演算法亂象伸出「利劍」。

什麼叫「大數據殺熟"！在網路上購物的人，特別是「剁手黨"，都應該深有體會！

誘導沉迷，真的只能呵呵呵！就一個

「農葯"大家都懂，但南山卻假裝不懂！

還有一個叫做扭腰女……

演算法歧視！知道什麼叫做流量就應該懂

或者說最近的

一婭等於多少

一庭等於多少

不公平帶來的……

《規定》明確，應用演算法推薦技術是指利用生成合成類、個性化推送類、排序精選類、檢索過濾類、調度決策類等演算法技術向用戶提供信息。這意味著各類提供演算法推薦服務的互聯網公司幾乎都在監管范圍內，如各類短視頻平台、電商平台、社交平台及餐飲外賣平台等。

演算法推薦……

類似於一些非常難纏的銷售…

我們必須把互聯網發展納入有法可依、有法必依、執法必嚴、違法必究的軌道，用依法管網的建設意識，培育出趨利避害、生機勃勃、欣欣向榮的網路生態。

企業追求利潤無可厚非！

但網路不是無法之地

追求利潤的同時也要遵守法律

公平競爭，合法獲取

否則讓你們嘗嘗覆舟的感覺！

⑻ 操作系統，數據結構和演算法的發展方向

從軟體角度來看，可以參考以前伺服器級的技術來處理個人電腦環境，更大的空間、更多的處理單元，你其實可以理解為現在的個人電腦是一個十年前的縮小版伺服器集群；

多核任務調度、針對有限存儲空間而設計的演算法（很多演算法為了節省空間開銷，都是以時間性能為代價的）等，都可以在硬體提升的基礎上，讓軟體也得到進一步提升，不過這些也是很有限的，而且也有不少人在做或者已經做了...；

在空間與計算速度大幅提升的前提下，單純的考慮性能就很不夠了，很多問題比如計算機智能化、信息安全等等，其實很早的時候就已經提出了，只是當時的性能甚至無法滿足實驗的要求，不過現在，這些都有可能了，所以當下這些領域都是很熱門的，或者一些還沒有人關注，而你發現的某些領域，都是除了性能之外，很值得研究的。

⑼ 演算法研究現狀

Farmer以及Deutsch和Journel雖然在1992年就提出了多點地質統計學方法,但其主要是通過在模擬退火中加入多點統計目標函數,然後對模擬圖像進行反復迭代達到與輸入統計參數匹配。該演算法受到數據樣板大小、模擬類型值多少的影響,此外迭代收斂也是一個不可避免的問題。受計算機性能以及演算法的雙重影響,模擬速度極其緩慢。因此對該方法的應用報道很少。1993年,Guardiano et al.提出了一種非迭代演算法。它並不通過變差函數及克里金建立條件概率分布,而是直接利用數據樣板掃描訓練圖像,並根據數據樣板掃描獲得的不同數據事件出現頻率,代替數據事件的多點統計概率。即對於每一個未取樣點,通過局部條件數據構成的數據事件,掃描訓練圖像推斷局部數據事件聯合未知點的條件概率(cpdf)。該方法屬於序貫模擬的范疇,但由於每次條件概率的推斷都需要重復掃描訓練圖像,對計算機性能要求相當高,因而該方法也一直停留在實驗室階段。

多點地質統計學得到快速發展,是源於搜索樹概念的提出,即一種存儲數據事件概率的數據結構。Strebelle(2000)對Guardiano et al.的演算法進行了改進,提出將掃描訓練圖像獲得的多點概率保存在「搜索樹」里,隨後的模擬採用序貫模擬的思路。在每模擬一個未知節點時,條件概率直接從「搜索樹」里讀取,大大縮短了運算機時,使得多點統計學儲層建模真正意義上的推廣成為可能。Strebelle將此演算法命名為Snesim(Singlenormal equation simulation)。Snesim演算法推出後,立刻受到建模界的關注,成為近幾年儲層建模熱點。通過實際研究區建模,有些學者指出Snesim尚存在一些缺陷,表現在以下幾個方面:

1)訓練圖像的平穩性問題。如何將實際儲層中的大量非平穩信息表現為訓練圖像並能應用多點統計方法進行建模;

2)集成軟數據(如地震)及評估訓練圖像或軟數據的權重問題,尤其是它們在某種程度上不一致時;

3)儲層形態合理再現問題。在現有演算法中,當數據事件稀少時,往往通過去除最遠條件節點方法來獲得可靠的數據事件,而這種處理方法往往會導致儲層構型再現失敗;此外,訓練圖像過小將導致目標不連續,影響建模真實性;而訓練圖像過大則導致運行機時大,Snesim的實施存在困難;

4)多重網格搜索問題。兩點統計學的多重網格搜索方法,不能改變粗網格模擬值,而條件數據重新分配具有相當大的誤差,導致實際地質結構特徵再現效果較差;

5)由於多點地質統計學仍然是基於像元的演算法,所以只能在一定程度上重現目標的形狀,對於更復雜的如尖角或者U型目標的應用則效果較差。

對於Snesim存在的問題,不同學者通過研究提出了各自的解決方案或建議。如非平穩性問題,Caers(2002)就採取類似於變差函數套合方式,通過伸縮和旋轉變換,將非平穩的地質模式變化為平穩的地質模式,隨後採用Snesim進行建模。再如數據樣板再現,Liu(2003)就通過賦予不同節點不同權重,在數據事件稀少時,舍棄權重最小數據點以獲得可靠的數據事件,而不是Snesim中去除最遠條件節點的方式;Stien(2007)則允許刪除條件數據點的值,而不是把它從條件數據集中移去。當所有節點被模擬後,再對那些被刪掉值的點重新模擬。Suzuki(2007)提出了一種新的方法,即實時後處理方法(PRTT),其主要思想是在某一點上如果條件化失敗,不是去掉一些條件數據縮小數據模板,而是返回到上一步,對前面模擬的數據進行修改,以達到數據事件合理化。在儲層屬性及數據事件多時,Arpat(2003)、Zhang(2003)等提出聚類的思想對相似數據事件進行歸類,從而減少運行機時及不合理數據事件的出現概率。

儲層建模是對地下沉積儲層地質模式的再現。考慮到儲層建模過程,實質上是對地下儲層特徵沉積模式的重建過程。如果將各種地質模式看成是一幅圖像的構成單元,對儲層預測也就是圖像的重建過程。基於此思想,在2003年Stanford油藏預測中心舉行的會議上,Arpat提出了Simpat(Simulation with pattenrs)多點地質統計學隨機建模方法,即通過識別不同的地質模式,採用相似性判斷方法,在建模時再現這些地質模式。Simpat模擬流程採用的也是序貫模擬的思路。由於是對地質模式處理,而地質模式是通過空間多個點構成的數據事件反映的,因此,在模擬實現時以整個數據事件賦值或者數據事件的子集取代了單個模擬網格節點的賦值。也就是說,在模擬過程中,在對某個未知值的預測過程中,除了模擬節點處賦值外,用來預測節點處值的條件數據的值也會有變化。Arpat通過這種數據事件整體賦值,實現儲層地質模式再現。在數據事件選擇上,Arpat擯棄了傳統的概率推斷、蒙特卡羅抽樣的隨機建模方法,而是借鑒計算機視覺及數字圖像重建領域的知識,利用數據事件的相似性對數據事件進行選擇。Arpat對此方法進行了較詳細的論證,表明此方法能夠較好再現儲層結構特徵。在此基礎上,基於距離相似度的多點地質統計學(distance-based multiple point geostatistics)開始得到研究和發展(Suzuki et al.,2008;Scheidt et al.,2008;Honarkhah et al.,2010)。與傳統基於統計抽樣的模擬不同,基於距離相似度的方法直接計算數據事件的相似性,並用最相似的數據進行整體替換。

基於統計抽樣以及儲層模式分類的考慮,Zhang(2006)提出了Fitlersim(Filter-Based simulation)方法。他認為在訓練圖像中眾多儲層模式可以由幾個濾波函數進行描述,由濾波函數獲得儲層模式的統計得分,在此基礎上,進行儲層模式的聚類,達到降低儲層維數、提高運算效率的目的。此外,在聚類過程中考慮相似的儲層模式出現的頻率,使得儲層預測具有統計學的意義。Yin(2009)則從目標骨架提取出發,約束多點統計模式選擇,提出了基於儲層骨架的多點地質統計學方法。