特征对比:
传统算法无法在有限的时间内精确求解
智能算法寻求在求解时间和求解速度上的平衡
最优算法:
一个问题的最优算法求得该问题每个实例的最优解;
启发式算法(Heuristic):
一个基于直观或经验构造的算法,在可接受的花费(计算时间、占用空间等)下给出待解决优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计。这类算法中的每一个算法都以人类、生物的行为方式或物质的运动形态为背景,经过数学抽象建立算法模型,通过计算机的计算来求解组合最优化问题,因此启发式算法也称为智能优化算法。
启发式算法特点:
- 是一种技术
- 不能保证所得解的最优性
启发式算法的缺点:
- 不能保证最优;
- 不稳定;
- 依赖于实际问题、设计者经验;
传统优化技术:
追求理论上的准确与完美
待解决的问题:连续性问题,以微积分为基础,规模较小
主要传统优化方法:
线性与非线性规划、动态规划、多目标规划、整数规划、排队论、库存论、对策论、决策论等。
评价方法:算法收敛性、收敛速度
现代优化技术:
待解决的问题:离散性、不确定性、大规模
现代的优化方法:启发式算法(heuristic algorithm)、追求满意(近似解)、实用性强(解决实际工程问题)
现代的评价方法:算法复杂性
现代优化算法:
禁忌搜索算法、模拟退火算法、遗传算法、人工神经网络、蚁群算法、粒子群算法、混合算法
算法性能分析:
评价算法优劣的指标
- 算法的复杂性(计算效率)
- 解的偏离程度(计算效果)
- 算法的稳健性(不同实例、不同时间、不同起点的差异)
评价算法优劣的手段
- 最坏情况分析(纯理论)
- 概率分析(理论分析)
- 计算模拟分析(统计特性)
版权归原作者 Zachery. 所有, 如有侵权,请联系我们删除。