启发式算法研究小结0.探究启发式算法的缘由在选《管理优化决策》这门课的时候，我抱着很强的好奇心和巨大的求知欲，试图尝试在这门课上学到我感兴趣的知识点以及确定我今后极有可能的研究领域和大方向。

很幸运的是，我找到了。

为什么这么说呢？就在我选择博士专业内选修课和专业外选修课的同时我发现了管理优化决策这门课和计算机学院那边开的选修课——《启发式优化》（由吕志鹏教授讲授），有很多是相通的，发现管理界尤其是在管理科学与工程方向和计算机技术应用领域所探究的问题出奇的一致，已经很难分清，哪个是管理方面的问题，哪个是计算机技术应用的范围了。

正如各位都知道的是，由于选修课最终确定前一个月是可以去试听的，然而我并没有因为两者看上去内容有些相似就匆忙退选。

通过对这两门课的内容进行比较，它给了我很大的触动，也带给我巨大的好奇，到底是管理方面的研究越来越偏向运用计算机等其他学科的知识和工具，还是计算机应用研究的方面越来越偏向实际的管理优化问题了呢？亦或者两个学科的边界正在走向模糊？我想学科交叉和融合的这一说法对于我来说可能并不是很新鲜，但这的确是我亲身经历的一种美妙体验和发现。

它带给我新奇的同时也无疑给了我值得我深思几点的启示：首先，众所周知，管理学科作为一门交叉的新兴学科，它的方法和工具都是依托和借助其他领域和学科而来的，它本身并没有或者几乎没有一个完完整整的只属于管理学科的方法和工具，几乎是其它学科的知识演变而来的，这就是我们所知道的学科交叉和学科融合；然而管理领域和传统计算机研究等领域的视角并不完全一样，其中对于计算机领域的研究者们而言，他们不但在乎启发式算法是否能够解决问题、效率是否大幅提高（而管理领域的专家们更在乎这点，能用第一，好用第二，或者说管理专家们更在乎第一点——问题能够得到的解决，至于第二点就不是那么迫切。

而对计算机领域的向专家们而言，可以说两者都非常重要、要求非常苛刻），更在乎它所表现出来的优越特性（就时间、空间复杂度以及算法求解过程中保持一定的集中性和分散性而言的）。

然而当管理领域的学者们求解类似问题，一般来说都是和我们生活中的管理者经常遇到且直接和的决策相关的问题，因为由于管理者的决策质量好坏会往往直接导致企业和团体的效率和绩效和高低，进而导致企业和组织的竞争力强弱，所以一般企业或者个人都是基于一定的价值诉求来解决管理问题，进而提高工作效率。

由于管理者们非常了解生活中并不存在完完全全的理性人和完全信息，因此他们很难也极少去尝试寻找最优解，找到满意解就可以了，这一点和启发式算法的设计思想不谋而合（由于时间、硬件资源有限，特别是遇到组合爆炸问题时短时间难于穷举和难与求解出最优解，而且短时间还必须给出解。

尽管二者有所差异，但都有一些共同之处，都是资源受限）。

综上所述，对于同一个所以在求解管理方面较为复杂的问题时，我们短时间很难给出精确地解析解时，这时考虑运用启发式算法也不失为一种飞常有效的方法，而且生活我们经常在用，也不断地被证明了启发式算法优良的特性（简单、迅速且解的质量较高）。

其次，随着社会经济的高速发展，我们面对的管理问题逐渐变得越来越复杂，而且超出了人们的求解和计算的能力范围，比如：当我们求解经典的TSP问题时，我们会发现尽管我们可以用很简单的数学加以描述和刻画，但是对其进行求解尤其是计算得到问题的最优解时，可以说难于上青天，然而这类问题在我们的生活中普遍存在，而且甚至严重地影响到了企业和个人的效益和效率以及人们生活的便利性。

在这个过程中还必须给出一定的满意解，此时，我们不求助与启发式算法，那还有什么办法呢？这也是启发式算法得以存在并高速发展的根本原因，这也是众多管理学者相继运用启发式算法的技术和工具去探究一些飞常复杂的管理问题根本原因，这也是我想在前人深厚的启发式算法研究的基础上继续尝试探究启发式算法在管理问题的根本目的。

最后，其实启发式算法的设计思想往往来源于一些朴素的哲学思想和观点，比如：启发式算法的设计过程中非常注重集中性和疏散性，从而实现某种平衡的状态，这与古代中国哲人先贤们的思想如出一辙，随机和确定同步进行，既有随机又有确定，随机存在确定之中，确定亦存在随机之中。

在保证全局最优的方向上引入随机的思想，防止过于最优，从而陷入局部最优无法自拔。

这对于每个人的人生也是同样的道理，我们在人生的道路上，充满各种选择，此时，我们是时时抓住眼前的最优，解未必是最优的；还是心里早已有一个最优的安排后（人生目标），允许牺牲/放弃短暂的眼前收益呢？这一点发人深思，这也是我最感兴趣的地方。

而且这种思想还可以延伸到我们研究的管理研究领域，也改变了过去很多观点和看法，比如：我曾经坚信运用数学模型、数据以及相关的数学量化的方法和工具可以实现管理问题的最优解，经过此次了解，我逐渐改变了我的观点（尽管原来学习博弈论课程探究完全和完美信息对决策的影响时就已经有这种改变的趋势，但这种趋势并不明显，因为它并不直观和具体），很多问题都有一定的复杂度，有时甚至超出了人们求解能力的范围，因此把握问题求解可能性和解的质量二者的平衡就尤为重要了。

总之，处处需要平衡！1.什么是启发式算法启发式（Heuristics）是指“探索性的”，不过通常被翻译为“启发式”，然而我觉得发把Heuristics翻译为探索性的更加简单直观而易于理解。

初学者对启发式这个专业词语有点摸不着头脑或者第一直觉打不起兴趣，因而耽误了自己的学习兴趣的发掘和最佳的学习机会。

启发式算法（heuristic algorithm)是相对于最优化算法提出的。

一个问题的最优算法求得该问题每个实例的最优解。

启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

现阶段，启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、神经网络等。

计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。

而启发式算法则试图一次提供一或全部目标。

例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

精确和启发式算法有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据组合，也许永远不会在现实世界出现。

因此现实世界中启发式算法常用来解决问题。

启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

常见的启发式算法如下表所示：可能本人介绍的不是很形象，因此摘抄了网上经典的一段描述几种常见搜索算法的例子来作为总结：为了找出地球上最高的山，一群有志气的兔子们开始想办法。

（1）兔子朝着比现在高的地方跳去。

他们找到了不远处的最高山峰。

但是这座山不一定是珠穆朗玛峰。

这就是爬山法，它不能保证局部最优值就是全局最优值。

（2）兔子喝醉了。

他随机地跳了很长时间。

这期间，它可能走向高处，也可能踏入平地。

但是，他渐渐清醒了并朝他踏过的最高方向跳去。

这就是模拟退火。

（3）兔子们知道一个兔的力量是渺小的。

他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。

他们制定了下一步去哪里寻找的策略。

这就是禁忌搜索。

（4）兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。

他们不知道自己的使命是什么。

但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。

这就是遗传算法。

2.启发式算法的发展历史谈到启发式算法，它已经有很长的发展历史，自从有了启发式算法，人们能够解决很多之前很难求解的问题在很短的时间内，尤其是伴随着计算机性能的飞速发展，启发式的威力更加凸显无疑。

我们大致将启发式算法的发展阶段按照年代进行划分如下：40年代：由于实际需要，人们已经提出了一些解决实际问题快速有效的启发式算法。

50年代：启发式算法的研究逐步繁荣起来。

随后，人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合，提出了许多启发式的搜索算法。

其中贪婪算法和局部搜索等到人们的关注。

60年代:随着人们对数学模型和优化算法的研究越来越重视，发现以前提出的启发式算法速度很快，但是解得质量不能保证。

虽然对优化算法的研究取得了很大的进展，但是较大规模的问题仍然无能为力（计算量还是太大）。

70年代：计算复杂性理论的提出。

NP完全理论告诉我们，许多实际问题不可能在合理的时间范围内找到全局最优解。

发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解不能保证全局最优性。

由此必须引入新的搜索机制和策略，才能有效地解决这些困难问题，这就导致了超启发式算法（meta-heuristic algorithms）的产生。

Holland模拟地球上生物进化规律提出了遗传算法（Genetic Algorithm），它的与众不同的搜索机制引起了人们再次引发了人们研究启发式算法的兴趣，从而掀起了研究启发式算法的热潮。

80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。

最近，演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等油相继兴起，掀起了研究启发式算法的高潮。

由于这些算法简单和有效，而且具有某种智能，因而成为科学计算和人类之间的桥梁。

3.启发式算法特性和不足尽管启发式算法能力非常强大，几乎可以说每种启发式算法都能独当一面并取得很好的效果。

但是仍然存在一些客观的局限如下：1.启发式算法目前缺乏统一而完整的理论体系。

由于每种启发式算法作用发挥好了都很强大，均能解决很多问题，因而导致现阶段启发式算法山头林立，其中研究的学者并没有多少全部涉足研究的，因而导致启发式算法缺乏像其他成熟理论体系那样的完整和体系化。

2.由于NP理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断以及如何跳出局部最优。

3.各种启发式算法都有个自优点如何，如何将各种启发式的有点互相借鉴和完美整合。

4.启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。

5.启发算法缺乏有效的迭代停止条件。

6.启发式算法收敛速度的研究等。

4.几种经典的启发式算法首先，我们介绍一下爬山法，算法思想：爬山算法即是模拟爬山的过程，随机选择一个位置爬山，每次朝着更高的方向移动，直到到达山顶，即每次都在临近的空间中选择最优解作为当前解，直到局部最优解。

这样算法会陷入局部最优解，能否得到全局最优解取决于初始点的位置。