启发式算法的基础定义与了解

声明：本文为作者学习笔记，学习所得随手而记，部分材料来源于网上学习，若侵权请联系作者。

1.什么是启发式算法

        启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。现阶段，启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、遗传算法、粒子群算法、神经网络等。

       启发式算法一般用于解决NP-hard问题，其中NP是指非确定性多项式。

       例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从南京出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

       推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。

例子

        我们举一个例子来具体说明一下：

       现在要求你开车去A镇的同学B家，那算法是这样写的：你沿着1号公路向东走一直到2号公路，之后左转沿着2号公路前进3公里，在一个五金店旁边的十字路口右转，直走1.5公里后你会发现在左手边有一个红色的大房子，那就是同学B家。

       如果用启发式方法来描述则可能是这样(一种思路)：首先找出上一次同学B寄给你的信，按照信上的地址你先开车到这个镇，到了之后你问一下周围的人，同学B的家在哪里，因为这里每个人都认识同学B，肯定有人会很愿意帮助你的，当然，如果你找不到人，那就找个公共电话亭给同学B打电话，他会出来接你。

        对这个例子的简单理解：一般的最优化算法会提供很明确的思路去找寻最优解，即使不是最优解，那也应该是接近于最优解；但是启发式算法只是给你一个大致的思路，要想找到可行解需要算法去根据条件(问题所限定的条件)以及算法本身的思路特点(这里的思路特点理解为遗传算法、粒子群算法等搜寻可行解时的思路，即不同的思路等同于不同的启发式算法)去找寻可行解，同时这个可行解不能保证就是最优解，有可能还是不怎么靠谱的解。

2.关于启发式算法的一些补充说明

       1.启发式算法(Heuristics Algorithm)是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。

        2.我们在解决问题时经常根据经验规则来探究分析问题，主要内容是在解决问题时,利用过去的经验,选择已经有效的方法，而不是按照系统地、确定性的步骤去寻求答案，启发式解决问题的方法是与算法相对立的。一般来说，算法是对所有可能性进行尝试，最终找到问题的最优解，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。而启发式的方法则是在有限的搜索空间内，极大地减少尝试的次数，能迅速找到问题的答案。但是由于这种方法具有尝试错误的特点，所以失败的可能性也不少。

3.启发式算法分类

        1.传统启发式算法，例如贪心算法、爬山算法等；

        2.元启发式算法，主要指一类通用型的启发式算法，简单的来说，它在传统启发式算法的思想上增加了随机搜索的思想，并且这类算法的优化机理不过分依赖于算法的组织结构信息，可以广泛的应用到函数的组合优化和函数计算中；

        3.超启发式算法，超启发式算法是由一系列的启发式算法组合而成的，超启发式算法是智能化程度更高的算法，每一种超启发式算法有其自己的机制。超启发式算法分为两个层面：在问题域层面上应用领域专家需根据本人的背景知识，提供问题的定义、评估函数等信息和一系列低层启发式算法(Low-Level Heuristics)；而在高层策略层面上，智能计算专家则通过设计高效的操纵管理机制，利用问题域所提供的问题特征信息和低层启发式算法算法库，构造新的启发式算法。由于超启发式算法的的研究尚处于起步阶段，对于已有的各种超启发式算法，国际上尚未形成一致的分类方法。按照高层策略的机制不同，现有超启发式算法可以大致分为4类：基于随机选择、基于贪心算法、基于元启发式算法和基于学习的超启发式算法。

        具体的分类算法如下图所示：

4.启发式算法的优缺点

（1）优点：

        a.算法简单直观，易于修改；

        b.减少大量的工作量，显著节约开支和时间,算法可在短时间内给出一个可行解。

（2）缺点：

        a.不能保证为全局最优解；

        b.算法不稳定，性能取决于实际问题以及算法设计者的经验和技术。

一些常见的启发式算法后续会一一介绍并赋具体代码，敬请关注。