【平臺】啟發式算法簡談(一)

2021-02-15 中國量化投資學會

引言：
解決實際的問題，要建模型，在求解。求解要選擇算法，只有我們對各種算法的優缺點都很熟悉後才能根據實際問題選出有效的算法。但是對各種算法都了如指掌是不現實的，但多知道一些，會使你的選擇集更大，找出最好算法的概率越大。現在研一，要開題了些點文獻綜述，願與大家分享。

大自然是神奇的，它造就了很多巧妙的手段和運行機制。受大自然的啟發，人們從大自然的運行規律中找到了許多解決實際問題的方法。對於那些受大自然的運行規律或者面向具體問題的經驗、規則啟發出來的方法，人們常常稱之為啟發式算法（Heuristic Algorithm）。現在的啟發式算法也不是全部來自然的規律，也有來自人類積累的工作經驗。

啟發式算法的發展：
啟發式算法的計算量都比較大，所以啟發式算法伴隨著計算機技術的發展，取得了巨大的成就。
40年代：由於實際需要，提出了啟發式算法（快速有效）。
50年代：逐步繁榮，其中 貪婪算法和局部搜索 等到人們的關注。
60年代: 反思，發現以前提出的啟發式算法速度很快，但是解得質量不能保證，而且對大規模的問題仍然無能為力（收斂速度慢）。
70年代：計算複雜性理論的提出，NP問題。許多實際問題不可能在合理的時間範圍內找到全局最優解。發現貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區域內找解，等到的解沒有全局最優性。
由此必須引入新的搜索機制和策略………..Holland的遺傳算法出現了（Genetic Algorithm）再次引發了人們研究啟發式算法的興趣。
80年代以後： 模擬退火算法（Simulated Annealing Algorithm），人工神經網絡（ArtificialNeural Network），禁忌搜索（Tabu Search）相繼出現。
最近比較熱或剛熱過去的：演化算法（Evolutionary Algorithm）, 蟻群算法（Ant Algorithms）， 擬人擬物算法，量子算法等。
各個算法的思想這就不再詳細給出（以後會給出一些，關注我的blog） ，為什麼要引出啟發式算法，因為NP問題，一般的經典算法是無法求解，或求解時間過長，我們無法接受。這裡要說明的是：啟發式算法得到的解只是近似最優解（近似到什麼程度，只有根據具體問題才能給出）. 二十一世紀的最大的數學難題NP？=P，如果NP=P啟發式算法就不在有存在的意義。

啟發式算法的不足和如何解決方法：水平有限 僅僅提出6點）
啟發式算法目前缺乏統一、完整的理論體系。很難解決！ 啟發式算法的提出就是根據經驗提出，沒有什麼堅實的理論基礎。
由於NP理論，啟發式算法就解得全局最優性無法保證。等NP？=P有結果了再說吧，不知道這個世紀能不能行。
各種啟發式算法都有個自優點如何，完美結合。
如果你沒有實際經驗，你就別去幹這個，相結合就要做大量嘗試，或許會有意外的收穫。
啟發式算法中的參數對算法的效果起著至關重要的作用，如何有效設置參數。
還是那句話，這是經驗活但還要悟性，只有try again………..
啟發算法缺乏有效的迭代停止條件。
還是經驗，迭代次數100不行，就200，還不行就1000…………
還不行估計就是算法有問題，或者你把它用錯地方了………..
啟發式算法收斂速度的研究等。
你會發現，沒有完美的東西，要快你就要付出代價，就是越快你得到的解也就遠差。

歡迎加入量化投資大家庭！

微信公眾號：chinaqi201203

主編：丁鵬

編輯：劉楓、果果、石詠、Alice

中國量化投資學會微博:http://weibo.com/577997668

中國量化投資學會QQ群：24165237

和訊專欄-中國量化投資學會專題http://stock.hexun.com/2013/zglhtzxh/

投稿郵箱：lf63698238@qq.com

歡迎廣大量化愛好者投稿，扶助新人！支持原創！


相關焦點

  • 啟發式算法 --數學化的經驗
    這篇來聊一下，理論上是依賴經驗人人都能做的： 網絡規劃中的啟發式算法。但人人能做不代表結果能做好，啟發式算法有高效的地方，也能把人帶溝裡。先看定義，啟發式算法(heuristic algorithm)：一個基於直觀或經驗構造的算法，在可接受的花費(指計算時間和空間)下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計。
  • 再談啟發式搜索算法
    何謂啟發式搜索啟發式搜索算法有點像廣度優先搜索，不同的是，它會優先順著有啟發性和具有特定信息的節點搜索下去，這些節點可能是到達目標的最好路徑。作為例子，下面介紹一個包括最優搜索版本的一般圖搜索算法（為了更詳細地了解啟發式搜索，可以參考引用的文章和Pearl寫的書[pearl 1984]）。二、一個通用的圖搜索算法為了更準確地解釋啟發式搜索過程，這裡提出一個通用的圖搜索算法，它允許各種用戶—偏愛啟發式的或盲目的，進行定製。
  • blast啟發式算法概述
    啟發式算法是一種來自於經驗的算法，區別於有精確數學推理的算法。
  • 網絡規劃中的啟發式算法 --數學化的經驗
    上一篇聊了《網絡規劃中的重心法--人人能懂的算法》，所謂人人能懂得前提是你沒完全忘記初中數學。所幸的是會點開這類標題讀的小夥伴，果然都能想起來勾股定理，算是人人能懂了。這篇來聊一下，理論上是依賴經驗人人都能做的： 網絡規劃中的啟發式算法。但人人能做不代表結果能做好，啟發式算法有高效的地方，也能把人帶溝裡。
  • 自動駕駛路徑規劃技術-A*啟發式搜索算法
    1968年發明的A*算法就是把啟發式方法（heuristic approaches）如BFS，和常規方法如Dijsktra算法結合在一起的算法。有點不同的是，類似BFS的啟發式方法經常給出一個近似解而不是保證最佳解。然而，儘管A*基於無法保證最佳解的啟發式方法，A*卻能保證找到一條最短路徑。1.3 A*算法我將集中討論A*算法。
  • 自我代碼提升之啟發式算法(番外篇)
    作者：數據取經團——JQstyle   Python愛好者社區專欄作者     數據取經團（公眾號：zlx19930503）     專注R、Python數據分析挖掘、可視化、機器學習本文代碼及數據獲取方式：關注Python愛好者社區，在公眾號中回復旅行商本期給大家帶來一些啟發式算法的介紹和代碼實現
  • 啟發式算法之遞歸與去遞歸
    啟發式算法之遞歸與去遞歸一個問題的複雜性
  • 什麼是啟發式?什麼是產生式?
    啟發式算法可以這樣定義：一個基於直觀或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計。計算機科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的算法。而啟發式算法則試圖一次提供一或全部目標。
  • 論文精選|利用有效的啟發式和迭代貪婪算法實現分布式環境中阻塞流程車間的生產調度
    （1）問題描述DBFSP描述：有F個相同的工廠，每個工廠都有一套m臺機器串聯處理。一組n個作業必須在任何一個F工廠中處理，每個作業的m個操作對應於m臺機器，作業j的處理時間恆定的。將作業分配到工廠進行處理，並對每個工廠中作業的處理順序進行排序且所有工廠中最大完工時間(完工時間)的最小化。
  • A*算法簡介
    啟發式算法(heuristic algorithm)，是相對於最優算法的一種算法類型。在許多算法 中，我們最終得到了一個問題的最優解；但在有些算法中，我們通過我們構造的方法， 最終得到了一個在我們的邏輯內認為可行的解，但這個解並不一定是最優解，甚至其相 對於最優解的偏離程度都是我們難以評估的。這種算法被我們稱作啟發式算法。（詳見百度百科「啟發式算法」）    2.
  • 如何進行可用性啟發式評估
    作為用戶體驗專家，你可以自由選擇調研的方法，甚至可以使用超越傳統工具的方法，但是今天，我想回歸簡單，談一談啟發式評估方法。什麼是啟發式評估？「啟發式評估是指安排一組評估人員檢查界面，並判斷其是否與公認的可用性原則相符（「啟發法」）。」
  • 模擬退火算法
    現代優化算法是80年代初興起的啟發式算法。
  • 十五個經典算法研究與總結(1)-A*搜索算法
    A*搜尋算法，俗稱A星算法，作為啟發式搜索算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
  • 模擬退火算法詳解
    搜索算法包括盲目搜索和啟發式搜索，按照預定的控制策略實行搜索，在搜索控制中獲取的中間信息不用來改進控制搜索，稱為盲目搜索，反之，稱為啟發式搜索。關於「啟發式」有兩種看法：（1）任何有助於找到問題的解，但不能保證找到解的方法均是啟發式方法；（2）有助於加速求解過程和找到較優解的方法是啟發式方法。盲目搜索有深度優先、廣度優先、代價優先、向前、向後、雙向。。。
  • A*算法
    A*算法是一個目標導向的算法。
  • 啟發式方法第一講(上)
    啟發式方法第一講（上）本講內容提要：Optimization problems  Continuous and discrete variables;
  • 【算法】混合整數規劃/離散優化的精確算法--分支定界法及優化求解器
    Prune情況一：下界大於上界Prune情況二：該Node的LRP問題無解（Infeasible）。5啟發式/近似算法（Heuristic/Approximation Algorithms）作為研究世界上最難問題的學者，想出了解決整數規劃問題的各種其他途徑，例如近似算法（Approximation Algorithms），啟發式算法（Heuristic Algorithms），遺傳算法（Generic
  • 關於尋路算法的一些思考(3):A*算法的實現
    然而在遊戲中，經常會得到不可信的啟發式函數。請點擊這裡 查看Python和C++實現.連通性如果遊戲中起點和終點在圖上根本就不連通，此時A*算法會耗時很久，因為從起點開始，它需要查探所有的節點，直到它意識到根本沒有可行的路徑。因此，我們可以先確定連通分支，僅當起點和終點在同一個連通分支時，才使用A*算法。
  • 路徑規划算法學習
    算法原理：參考路徑規划算法學習Day1https://blog.csdn.net/CltCj/article/details/110529598此方法會結合網絡佔用法-柵格法來進行實現提示：本文會用matlab實現Dijkstra算法，並且會分享一些函數用法的連結，也是本人學習得來，供大家參考，批評指正。
  • 如何利用公司內部資源進行啟發式評估?(下)
    上文我們簡單了解了什麼是啟發式評估以及尼爾森的十大原則。知道了評估人和評估原則，那麼啟發式評估什麼時候適合用呢？