人工智慧-啟發式算法(Heuristic Algorithm)簡談

2021-02-25 合晶睿智

最近人工智慧火了，緊跟著啟發式算法又火了，當年在學校的時候，作為數學系的學生，研究的就是啟發式算法，如果人工智慧或許數據挖掘能早些熱起來的話，自己也不至於後來幹了金融…… 閒話少說，講當年自己寫的一篇啟發式算法簡談分享給大家!


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

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

一、啟發式算法的發展：


啟發式算法的計算量都比較大，所以啟發式算法伴隨著計算機技術的發展，取得了巨大的成就。

40年代：由於實際需要，提出了啟發式算法（快速有效）。

50年代：逐步繁榮，其中貪婪算法和局部搜索 等到人們的關注。

60年代: 反思，發現以前提出的啟發式算法速度很快，但是解得質量不能保證，而且對大規 模的問題仍然無能為力（收斂速度慢）。

70年代：計算複雜性理論的提出，NP問題。許多實際問題不可能在合理的時間範圍內找到全局最優解。發現貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區域內找解，等到的解沒有全局最優性。由此必須引入新的搜索機制和策略………..Holland的遺傳算法出現了（Genetic Algorithm）再次引發了人們研究啟發式算法的興趣。

80年代以後：模擬退火算法（Simulated Annealing Algorithm），人工神經網絡（Artificial Neural Network），禁忌搜索（Tabu Search）相繼出現。
最近比較熱或剛熱過去的：演化算法（Evolutionary Algorithm）, 蟻群算法（Ant Algorithms）， 擬人擬物算法，量子算法等。


各個算法的思想這就不再詳細給出，為什麼要引出啟發式算法，因為NP問題，一般的經典算法是無法求解，或求解時間過長，我們無法接受。這裡要說明的是：啟發式算法得到的解只是近似最優解（近似到什麼程度，只有根據具體問題才能給出）. 二十一世紀的最大的數學難題NP？=P，如果NP=P啟發式算法就不在有存在的意義。

二、啟發式算法的不足和如何解決方法：

啟發式算法目前缺乏統一、完整的理論體系。很難解決！ 啟發式算法的提出就是根據經驗提出，沒有什麼堅實的理論基礎。由於NP理論，啟發式算法就解得全局最優性無法保證。等NP？=P有結果了再說吧，不知道這個世紀能不能行。

各種啟發式算法都有個自優點如何，完美結合。如果你沒有實際經驗，你就別去幹這個，相結合就要做大量嘗試，或許會有意外的收穫。啟發式算法中的參數對算法的效果起著至關重要的作用，如何有效設置參數。還是那句話，這是經驗活但還要悟性，只有try again………..

啟發算法缺乏有效的迭代停止條件。還是經驗，迭代次數100不行，就200，還不行就1000…………還不行估計就是算法有問題，或者你把它用錯地方了………..

啟發式算法收斂速度的研究等。你會發現，沒有完美的東西，要快你就要付出代價，就是越快你得到的解也就遠差。   

三、各類啟發式算法概述

優勝劣汰是大自然的普遍規律，它主要通過選擇和變異來實現。選擇是優化的基本思想，變異（多樣化）是隨機搜索或非確定搜索的基本思想。「優勝劣汰」是算法搜索的核心，根據「優勝劣汰」策略的不同，可以獲得不同的超啟發式算法。超啟發式算法的主要思想來自於人類經過長期對物理、生物、社會的自然現象仔細的觀察和實踐，以及對這些自然現象的深刻理解，逐步向大自然學習，模仿其中的自然現象的運行機制而得到的。

遺傳算法：是根據生物演化，模擬演化過程中基因染色體的選擇、交叉和變異得到的算法。在進化過程中，較好的個體有較大的生存機率。

模擬退火：是模擬統計物理中固體物質的結晶過程。在退火的過程中，如果搜索到好的解接受；否則，以一定的概率接受不好的解（即實現多樣化或變異的思想），達到跳出局部最優解得目的。

神經網絡：模擬大腦神經處理的過程，通過各個神經元的競爭和協作，實現選擇和變異的過程。

禁忌搜索：模擬人的經驗，通過禁忌表記憶最近搜索過程中的歷史信息，禁忌某些解，以避免走回頭路，達到跳出局部最優解的目的。

螞蟻算法：模擬螞蟻的行為，擬人擬物，向螞蟻的協作方式學習。

這幾種超啟發式算法都有一個共同的特點：從隨機的可行初始解出發，才用迭代改進的策略，去逼近問題的最優解。他們的基本要素：

（1）隨機初始可行解；

（２）給定一個評價函數（常常與目標函數值有關）；

（３）鄰域，產生新的可行解；

（４）選擇和接受解得準則；

（５）終止準則。

其中（４）集中反映了超啟發式算法的克服局部最優的能力。

　　

Over，才發現過去的我比現在的我要勤奮……

I will be back!


相關焦點

  • DDO(6): Metaheuristic
    Metaheuristic（元啟發式方法 ）"In computer
  • minimax算法 - CSDN
    minimax算法In this lesson, we』ll explore a popular algorithm called minimax.通過選擇經過深思熟慮的啟發式得分，我們可以教我們的AI代理如何在玩「隔離」遊戲時最好地選擇其下一步行動。 Now there’s probably an unlimited number of heuristic scores we could come up with.
  • 數據挖掘十大算法 ——The k-means algorithm(二)
    不僅僅是選中的十大算法，其實參加評選的18 種算法，實際上隨便拿出一種來都可以稱得上是經典算法，它們在數據挖掘領域都產生了極為深遠的影響。算法綜述：k-means algorithm算法是一個聚類算法，把n的對象根據他們的屬性分為k個分割，k < n。
  • 人工智慧之機器學習算法體系匯總
    Github開源機器學習系列文章及算法源碼1. 人工智慧之機器學習體系匯總【直接上乾貨】此處梳理出面向人工智慧的機器學習方法體系，主要體現機器學習方法和邏輯關係，理清機器學習脈絡，後續文章會針對機器學習系列講解算法原理和實戰。
  • 新一代人工智慧算法-人工教學並超越自身訓練的算法
    來源：多倫多大學一種由多倫多大學工程學院開發的新的機器學習訓練算法使神經網絡能夠直接從人類定義的規則中學習，為人工智慧領域開闢了新的可能，它可以延伸到醫療診斷和自動駕駛汽車領域。「嘿，Siri,我的頭髮看起來怎麼樣？」
  • ​隨機算法(randomized algorithm)概述——概念、方法、類型、複雜度、設計方法和計算舉例(14k字)
    algorithm)是一個概率圖靈機，也就是在算法中引入隨機因素，即通過隨機數選擇算法的下一步操作。本文概述隨機算法(randomized algorithm)的概念、方法、類型、複雜度、設計方法和計算舉例。關鍵詞：隨機算法(randomized algorithm)、隨機、計算。
  • 啟發式教學法的內涵
    啟發式教育 (heuristic education)，或啟發式教學法(heuristic teaching method)，大家可能都已經不是那麼陌生了，尤其是在西方教育的範疇，在教學方法上，是特別強調這一點的，注重啟發（inspiration
  • 如何實現一個高效的啟發式算法?
    說起來，小編似乎就是做啟發式算法起家的。當時記得老師是這麼跟我說的，啟發式算法這東西很簡單，你不需要基礎，有高中基礎就夠了（其實他想說的是初中……）。後來小編一直在學這個東西，做了三四年了，用啟發式算法做過的大大小小的project已經不記得有多少了，所以還算得上有一點點經驗。因此今天就來寫寫，怎樣實現一個比較高效的啟發式算法吧~二、何為高效？
  • 遺傳算法(Genetic Algorithm)概述
    （Genetic Algorithm）又叫基因進化算法，或進化算法。屬於啟發式搜索算法一種，這個算法比較有趣，並且弄明白後很簡單，寫個100-200行代碼就可以實現。在某些場合下簡單有效。本文就花一些篇幅，儘量白話方式講解一下。  首先說一下問題。在我們學校數據結構這門功課的時候，時常會有一些比較經典的問題（而且比較複雜問題）作為學習素材，如八皇后，背包問題，染色問題等等。上面列出的幾個問題都可以通過遺傳算法去解決。
  • 啟發式算法在最優化問題求解中的應用與實踐
    本文介紹了最優化問題的常見應用場景和求解方式，並重點對啟發式算法在求解NP問題的次優解過程進行了分析。在解決這類問題時，常規的確定性時間複雜度的算法不再適用，而啟發式算法這類非確定性時間複雜度的算法，卻能夠較好的尋找到該類問題的一個可以接受的次優解。通常，啟發式算法搜索得到的問題的解不是最優解，而是隨著算法的改進和迭代無限接近最優解的次優解。因為目前，我們找不到一個更好的算法，能夠證明其執行效率良好、穩定，並且能得到問題最優解的算法，所以啟發式算法是目前我們解決這類問題的一種較好手段。
  • 白話講解遺傳算法 (Genetic Algorithm)
    （Genetic Algorithm）又叫基因進化算法，或進化算法。屬於啟發式搜索算法一種，這個算法比較有趣，並且弄明白後很簡單，寫個100-200行代碼就可以實現。在某些場合下簡單有效。本文就花一些篇幅，儘量白話方式講解一下。 首先說一下問題。在我們學校數據結構這門功課的時候，時常會有一些比較經典的問題（而且比較複雜問題）作為學習素材，如八皇后，背包問題，染色問題等等。上面列出的幾個問題都可以通過遺傳算法去解決。
  • Dr.Yu談啟發式教學法的內涵
    啟發式教育 (heuristic education)，或啟發式教學法(heuristic teaching method)，大家可能都已經不是那麼陌生了，尤其是在西方教育的範疇，在教學方法上，是特別強調這一點的，注重啟發（inspiration） 與理解（understanding），而不鼓勵填鴨式教學、生產線式教學…然而，如何來具體實現啟發式教育呢
  • Myers 差分算法 (Myers Difference Algorithm) —— DiffUtils 之核心算法(一)
    Myers's difference algorithm這個算法，我們可以簡單的翻譯成Myers 差分算法，來計算兩個列表最小的更新操作數。在這個類的頭部注釋的最後，也給出了相關性能的數據： 1這個性能非常可觀呀，如果結合我們的業務實際，這種計算性能，再考慮把計算操作放置到非 UI 線程中操作，那麼我們得到的就是一個非常平滑的操作體驗了。
  • golang 調用 python 實戰路徑規劃之 A* 算法
    其函數表示如下：function heuristic(node) = dx = abs(node.x - goal.x) dy = abs(node.y - goal.y) return D * sqrt(dx * dx + dy * dy)算法實現雖然前面介紹了很多內容，但實際上A*算法並不複雜，實現起來也比較簡單。
  • 一文縱覽人工智慧的23個分支技術(上)
    搜索算法一般可以分成兩類:無信息(uninformed)搜索和有信息(in-formed)搜索。其中有信息啟發式搜索是相當流行的，因為它能根據一些指示快速找到解答。這一類別中包含一種最受歡迎的搜索算法:A*搜索。A*搜索可被定義為是一種(貪婪)最佳優先搜索((greedy) best-first search)。
  • 人工智慧時代的算法裁判及其規制
    摘    要：現在的世界已經進入人工智慧時代, 我們也已經進入了算法社會。在人工智慧的發展中, 算法發揮著極其重要的作用。隨著大數據的積聚、理論算法的革新、計算能力的提升, 人工智慧在很多學科領域得到了廣泛應用, 並取得了豐碩成果, 無論在理論還是實踐上都已自成一個系統。[2]1可以毫不誇張地說, 現在的世界已經進入了人工智慧時代。與此同時, 我們已經進入了算法社會, 人工智慧、網際網路、物聯網這些只不過都是算法社會的序曲, [3]我們正在進入「算法統治的時代」, [4]我們生活在算法的時代。
  • 人工智慧必備50種算法
    譯者：彎月，責編：郭芮本文是一些機器人算法（特別是自動導航算法）的Python代碼合集。其主要特點有以下三點：選擇了在實踐中廣泛應用的算法；依賴最少；容易閱讀，容易理解每個算法的基本思想。希望閱讀本文後能對你有所幫助。前排友情提示，文章較長，建議收藏後再看，項目地址在文末，記得點個「好看」哦。
  • 每個算法人員都應該知道的4個超參數調試方法
    超參數超參數是在建立模型時用於控制算法行為的參數。這些參數不能從常規訓練過程中獲得。在對模型進行訓練之前，需要對它們進行賦值。傳統手工搜索在傳統的調參過程中，我們通過訓練算法手動檢查隨機超參數集，並選擇符合我們目標的最佳參數集。