超啟發式算法綜述

何雨

摘要：在編程的過程中，我們經常會遇到一些復雜的問題。在面對有復雜的問題的情況時，我們就不能按部就班、像平常那樣去編程;而是應該有針對性的、采取適合該復雜的問題的解決方法，算法由此而來。算法是要解決合適的問題，不能遇到問題，就隨便找一個算法來解決。我們在學習編程的過程中，會研究一些最基本的算法，比如二分查找算法（Binary search algorithm）等。我們在有了這些最基本的算法知識的基礎上，就可以研究一些更復雜、更智能的算法，就像蟻群算法（Ant colony algorithm）這種啟發式算法（Heuristic algorithm）。而隨著問題的進一步的復雜化，人們的要求越來越高，目前啟發式算法，在解決很多復雜程度高的問題時，已經不是最佳的解決辦法了，這個時候我們就要用到超啟發式算法（Hyperheuristic algorithm）來解決這樣的問題。超啟發式算法對于求解各類NP-難解問題，具有非常高的效率[1]。

關鍵詞：二分查找算法;蟻群算法;啟發式算法;超啟發式算法;NP-難解問題

中圖分類號：TP18 文獻標識碼：A 文章編號：1007-9416（2020）09-0094-02

0 引言

我們可以把算法看成是一道道的指令組合而成的，而這一道道指令，從數學的角度去分析，就好比我們在進行加法運算的時候，需要用到加法法則，還要有兩個加數A和B，最終計算得到結果是：;而從計算機的角度去分析指令的話，就好比一個流水CPU中，有取指階段。取指，顧名思義，就是把指令取出來。指令取出來才可以用，指令不取出來是不能用的。但是取出的指令不能夠馬上去執行，而是要經過譯碼階段后，才能夠去執行指令。我們給算法一個輸入項，經過了有限個步驟后，我們最終會得到輸出項。

算法除了上段中提到的輸入項、輸出項以及有窮性之外，還有兩個特性，兩者是：確切性：算法的每一個步驟不能有二義性，不能讓編程人員覺得這一步算法是模棱兩可的，必須有唯一的通路;可行性：算法可以執行完成，不會不限制地循環下去[2]。可行性也叫有效性。

計算機中的算法，我們可以把它看成是偽代碼，而我們編程的過程，就是將偽代碼轉化為真實的代碼的過程。偽代碼是不能夠在計算機里面的編程軟件上執行編譯的，可是我們將它轉換成真實的代碼后，我們就可以對代碼進行編譯、調試等步驟。

如果我們想通過一個算法得到一個目標，可以先通過數學關系構造出函數，確定目標所在的一個大概的范圍，以提高算法的收斂速度[3]。

1 啟發式算法概述

啟發式算法是智能化程度較高的算法，有了像各類排序算法這樣最基本的算法的基礎后，我們要完善已有的算法，使算法變得越來越智能化，這樣我們才能跟上問題復雜化的腳步。我們在求解一個問題的解的過程中，有的時候，求出來一個解，并非難事;難的是我們如何去求解這個問題的最優解，或者說是在滿足某些特定條件下的特解。這里有一個范圍，這個范圍是一個具體的概念，無論是從時間的角度，還是空間的角度，在這個具體的范圍內，去給出待解決組合優化問題每一個實例的一個可行解[4]。

雖然啟發式算法不止一種，但是它們的本質都是一樣的，就是要求解出全局的最優解[5]。在現代科研中，對啟發式算法的研究越來越深入，實踐也越來越多，我們需要去不斷創新出新的想法和技術去研究它[6]。啟發式算法的輸入因題目而異，不同的輸入，就會有不同的步驟;輸出一定是全局的最優解，而不是局部的最優解。我們在使用啟發式算法的時候，要注意，我們不斷去迭代而尋求的解是全局的最優解，我們很容易被局部的最優解而迷惑住。

2 超啟發式算法概述

我們已經知道了啟發式算法的一些基本的概念。接下來[7]，重點介紹一下超啟發式算法。超啟發式算法是由一系列的啟發式算法組合而成的，超啟發式算法相當于高層，啟發式算法是與超啟發式算法相對比而言的，超啟發式算法提供了策略，這些用來操縱或管理啟發式算法，來獲得新的啟發式算法[8]。每一種超啟發式算法有其自己的機制，現有超啟發式算法可以大致分為4類：基于隨機選擇、基于貪心策略、基于元啟發式算法、基于學習的超啟發式算法[9]。

超啟發式算法是智能化程度更高的算法。我們都希望使用的算法能夠更加智能，這樣會給我們在編程過程中，解決更復雜的問題帶來便利。

超啟發式算法分為兩個層面：在問題域層面上應用領域專家需根據本人的背景知識，提供問題的定義、評估函數等信息和一系列低層啟發式算法（Low-Level Heuristics）;而在高層策略層面上，智能計算專家則通過設計高效的操縱管理機制，利用問題域所提供的問題特征信息和低層啟發式算法算法庫，構造新的啟發式算法。

3 超啟發式算法應用

我們已經知道了超啟發式算法的一些基本的概念。接下來，重點介紹一下超啟發式算法的應用[10]。超啟發式算法的存在，就是為了幫助我們更好地解決編程的過程中所遇到的問題，尤其是各類NP-難解問題。超啟發式算法也是算法中的一種，所以超啟發式算法的應用范圍是不能脫離算法的應用范圍的。

超啟發式算法是對一堆操作進行操作，而不直接作用于具體問題;啟發式算法直接作用于問題領域。就是因為這一區別，導致超啟發是算法可以脫離具體問題情境。因為對于一堆具體操作，已經沒有了什么順序約束，數量約束等。超啟發式算法非常有用。

4 結論

本篇論文介紹了超啟發式算法的基本概念及其應用。在這之前，介紹了算法和啟發式算法的基本概念。每一種算法都能幫助我們找到待解決問題的解甚至是最優解，每一種算法都有其自身的特點，有其自身的應用場景。我們在編程的過程中，就是要根據問題的背景，選擇適合的算法，這樣的話，編程才能事半功倍。

參考文獻

[1] 蓋文妹，鄧云峰，蔣仲安，等.雙權重應急交通網絡最優路徑數學模型及算法研究[J].中南大學學報（自然科學版），2015，46（6）：2366-2375.

[2] 林恒建.算法效率探討[J].福建電腦，2013，29（10）：161-162.

[3] 張俊，朱慶偉，嚴俊杰，溫波.改進強化學習算法的UAV室內三維航跡規劃[J/OL].計算機工程與應用：1-9[2020-09-01].http：//kns.cnki.net/kcms/detail/11.2127.TP.20200828.1612.012.html.

[4] 樊瑩瑩.高速鐵路列車運行調整及時空穩態分析研究[D].北京：北京交通大學，2018.

[5] 孫上明，謝如鶴，李展旺，等.生鮮果蔬冷鏈物流前端集貨運輸優化[J].物流工程與管理，2017，39（9）：55-60+63.

[6] 叢明煜，王麗萍.現代啟發式算法理論研究[J].高技術通訊，2003（5）：105-110.

[7] 王睿.植物花授粉算法及應用研究[D].南寧：廣西民族大學，2016.

[8] 張艷梅，姜淑娟，陳若玉，等.基于粒子群優化算法的類集成測試序列確定方法[J].計算機學報，2018，41（4）：931-945.

[9] 張春波.車聯網條件下高速公路車道變窄路段緩堵控制方法[D].南京：東南大學，2018.

[10] 林博.改進遺傳算法在物流配送中的應用研究[D].鞍山：遼寧科技大學，2016.