大牛，Neumaier 把全局优化方法分成了四类 （Deterministic global optimization），

1：不完备算法：仅利用启发式方法（Heuristics）搜索全局最优解，但是对于这一搜索过程是否会卡在局部最小值附近没有任何理论性的保证。

2：渐进完备算法：如果有无限长的计算时间，这类方法一定能找到全局最优解或者其找到全局最优解的概率为1。但是这类方法无法得知当前找到的解是否是全局最优解。

3：完备算法：如果有无限长的计算时间，这类方法一定能找到全局最优解，并且在有限的时间内能找到，在给定误差范围之内的全局次优解。

4：严格算法：可以找到满足给定误差范围的全局最优解。不过当问题近似退化时（near-degenerate），这些解可能不满足给定的误差容许度。

所以实际上，你如果想要在有限时间内保证一定能得到在给定误差范围内全局最优解，你需要3,4类的方法。纯启发式的方法不可能做到这一点，任何混沌机制都不能保证。

启发式算法中，局部最优值的陷入无法避免。启发式，本质上是一种贪心策略，这也在客观上决定了不符合贪心规则的更好（或者最优）解会错过。

而启发式优化算法在针对不同的问题时，表现出来的性能可能是不一样的。而且，由于这类优化算法是随机搜索算法。

因此很有必要在整个优化迭代过程中增加一定的监督机制，比如说PSO中个体最优和整体最优，以及如何设置下一步的搜索方向，是简单的全局最优个体减去当前个体的向量偏差还是其他？这些都会对问题是否会很快收敛到局部最优有很大的影响。

对于目前的一些问题，可能会出现较多的局部最优解，而启发式优化算法一般情况下只会找到一个局部最优或者全局最优.

此时，我们可以考虑设计算法，使得其能够保证在优化过程中记录不同搜索空间的局部最优，在这些局部最优点中重新去迭代优化，这样个人感觉迭代优化会更快一些，这就是与禁忌搜索算法结合起来。

好的启发式算法，一般都是集中性和疏散性达到了某个平衡点。找到局部最优解的过程就是集中性的一种体现，集中性越强，找到局部最优解的速度越快，但缺点是，由于一般NP难问题的解空间过于庞大，集中性太强的算法没有考虑到全局最优性。

另外，疏散性越强，算法搜索的区域越大，越可能覆盖到全局最优解所在地方。所以，找到二者之间的平衡点是非常重要的，禁忌搜索，模拟退火，进化算法，种群算法等都是既考虑集中性又考虑疏散性的算法。

一般来说，针对某个具体问题，用某种启发式算法，找到集中性和疏散性的平衡点比较困难，也会涉及到很多参数，显得不具有普遍性和智能化，这也是启发式算法现在存在的问题。

如果能不依靠参数测试，根据某个问题能让算法自动确定策略或者参数来平衡集中性和疏散性，那应该就是希望看到的了，但可惜的是，这样的算法很少。

总的来说，避免陷入局部最优就是两个字：随机。

具体实现手段上，可以根据所采用的启发式框架来灵活地加入随机性。

比如遗传里面，可以在交叉变异时，可以在控制人口策略中，也可以在选择父本母本样本时；禁忌里面，可以在禁忌表的长度上体现，也可以在解禁策略中使用，等等。这些都要结合具体问题特定的算例集，需要反复尝试摸索才行。

参数的敏感性是一个问题，建议不要超过3个参数，参数越不敏感越好。不同算例集用不同种子运行多次（100次左右才有统计意义），统计平均性能即可。需注意全局的随机重启通常来说不是一个好办法，因为等于主动放弃之前搜索结果，万不得已不要用，或者就是不用。

三个原则应该把握：越随机越好；越不随机越好；二者平衡最好。

越随机越好

没有随机性，一定会陷入局部最优。为了获得更大的找到最优解的期望，算法中一定要有足够的随机性。具体体现为鲁棒性较好，搜索时多样性较好。算法的每一步选择都可以考虑加入随机性，但要控制好概率。比如，某个贪心策略下，是以概率1做某一动作，可以考虑将其改为以概率0.999做之前的操作，以剩余概率做其他操作。具体参数设置需调试。

越不随机越好

随机性往往是对问题内在规律的一种妥协。即没有找到其内在规律，又不知道如何是好，为了获得更好的多样性，逼不得已加入随机。

因此，对给定问题的深入研究才是根本：分辨出哪些时候，某个动作就是客观上能严格保证最优的——这点至关重要，直接决定了算法性能。最好的算法一定是和问题结构紧密相连的，范范地套用某个启发式的框架不会有出色的性能。当然，如果不是追求性能至上，而是考虑到开发效率实现成本这些额外因素，则另当别论。

二者平衡最好

通常情况下，做好第一点，可以略微改善算法性能；做好第二点，有希望给算法带来质的提高。而二者调和后的平衡则会带来质的飞跃。

贪心是“自强不息”的精进，不放过任何改进算法的机会；多样性的随机是“厚德载物”的一分包容，给那些目前看似不那么好的解一些机会。调和好二者，不偏颇任何一方才能使算法有出色的性能。要把握这种平衡，非一朝一夕之功，只能在反复试验反思中去细细品味。

最后，当然算法要结合具体问题而言，没有一个算法是可以解决所有问题。

如果觉得对你有帮助的话，麻烦点个赞吧。

。