超启发式算法综述

何雨

摘要：在编程的过程中，我们经常会遇到一些复杂的问题。在面对有复杂的问题的情况时，我们就不能按部就班、像平常那样去编程;而是应该有针对性的、采取适合该复杂的问题的解决方法，算法由此而来。算法是要解决合适的问题，不能遇到问题，就随便找一个算法来解决。我们在学习编程的过程中，会研究一些最基本的算法，比如二分查找算法（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.