精确算法与启发式近似算法

转自： blog.csdn.net/xujinpeng99/article/details/8947816

        组合优化问题是通过用数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，其变量是离散分布的。对于结构化的组合优化问题，其解空间的规模能够得到控制，对于这样的问题，使用精确算法就可以求得最优解。而当问题的规模逐渐增大时，求解这些问题最优解需要的计算量与存储空间的增长速度非常快，会带来所谓的“组合爆炸”，使得在现有的计算能力下，通过各种枚举方法、精确算法寻找并获得最优解几乎变得不可能。这时候，启发式算法应运而生。下面详细介绍这些算法。

    一、精确算法（Exact Algorithm）

    精确算法是指能够求出问题最优解的算法。对于难解的组合优化问题，当问题的规模较小时，精确算法能够在可接受的时间内找到最优解；当问题的规模较大时，精确算法一方面可以提供问题的可行解，另一方面可以为启发式方法提供初始解，以便能搜索到更好的解。

    精确算法主要包括分支定界法、割平面法、动态规划法等。

    二、启发式算法（Heuristic Algorithm）

    启发式算法是指通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观判断或试探的方法，以求得问题的次优解或以一定的概率求其最优解。通用性、稳定性以及较快的收敛性是衡量启发式算法性能的主要标准。

    启发式算法可分为传统启发式算法和元启发式算法。

    传统启发式算法包括构造型方法、局部搜索算法、松弛方法、解空间缩减算法等。

    三、元启发式算法（Meta-heuristic Algorithm）

    元启发式算法是启发式算法的改进，是随机算法与局部搜索算法相结合的产物。元启发式是一个迭代生成过程，通过对不同概念的智能组合，该过程以启发式算法实现对搜索空间的探索和开发。在这个过程中，学习策略被用来获取和掌握信息，以有效地发现近似最优解。

    元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法、人工神经网络算法等。

    四、近似算法（Approximate Algorithm）

    近似算法没有严格的定义，一般来说能求出可行解的算法都能归为近似算法。

    常见的近似算法有贪婪算法、局部搜索算法、松弛算法、动态规划法等。

    五、群智能算法

    即群体智能源于对以蚂蚁、蜜蜂等为代表的社会性昆虫的群体行为的研究。最早被用在细胞机器人系统的描述中。它的控制是分布式的，不存在中心控制。群体具有自组织性。

    六、增长方式

    目前能常见到的增长方式有：

线性增长：2n；

多项式增长：2n^3+3n^2+5n+1；

指数增长：2^n；

阶乘增长：n!；

幂函数增长：n^3；

特殊：

-n^(-1)，当n→0时，无限增长趋向于∞；

超级幂：E(n,a)=n^n^n^n……（a个n）；

    备注：本文部分内容来自《基于单点搜索的元启发式算法》