文档介绍：现代优化技术
第5讲:传统启发式算法之构筑法
主要内容
启发式算法含义
启发式算法的宿命论
启发式算法求解问题的一般程序
启发式算法策略
几种典型的构筑法
(1)背包问题的构筑法
(2)旅行商问题的构筑法
(3)配送问题的构筑法
启发式算法(heuristics)
含义:启发性算法是一种优化技术,可以在可接受计算时间下给出待求解问题每一个实例的近似最优解,但无法保证所得解的精确度。
目标:求得“满意解”,而非最优解
1)精确解无法找到;
2)过高精度的解无实际意义;
3)求最优解代价太高。
启发式方法的概念图
全局最优解
可行解集合
目标函数
局部最优解
启发式算法的宿命论 例:Traveling Salesman Problem (TSP)
启发式算法的宿命论:计算复杂性 例:Traveling Salesman Problem (TSP)
30个客户的TSP問題( 30! ~ 1030 )
高性能計算機求解最优解需要3日
(n-1)×(n-2)×…×3×2×1=(n-1)!
1 PIPS (Peta Instruction Per Second)=1015
30!/1015 (秒) ≧π×1015 (秒)
≒ 105 (世紀)
(穷举法)
启发式算法的宿命论:问题复杂性
GR120 solved by Groetschel (1977)
启发式算法的宿命论:问题复杂性
The optimal tour of ATT532 (532 AT&T switch locations in the USA) found by Padberg and Rinaldi (1987)