大连海事大学《现代优化技术》第7讲：传统启发式算法之改进形态PPT课件.ppt

现代优化技术
第7讲:传统启发式算法之改进形
传统启发式算法之改进形
构筑法的改进形
(贪婪算法的改进形)
改善法的改进形
(局部探索法的改进形)
传统启发式算法之改进形
构筑法(贪婪算法)的局限性
构筑法(贪婪算法)在任何给定的时点都采取当时的最佳移动,但最终的整体结果却不一定是最佳的。其问题在于现时点局部是最好的,却不一定是后面所需要的。如果在探索的途中有一个评估函数,能提供现在及未来的一些信息,就可以改善、避免短期的贪婪行为。
改进的贪婪法
传统启发式算法之改进形
最佳优先(best-first)探索:A*算法
深度优先策略(deep-first): 以一种任意的模式往尽可能深的空间探索。
广度优先策略(wide-first): 探索完某一层次中所有节点后才进入下一层次。
例:TSP的探索树
两种传统的探索策略:
传统启发式算法之改进形
两种传统的探索策略:例
B
R
L
R
B
B
L
R
L
B
R
L
B
L
R
M
B
R
M
R
B
B
M
R
M
B
R
M
B
B
R
L
B
L
M
L
B
B
M
L
M
B
L
M
B
M
L
R
R
L
M
L
R
R
M
L
M
R
L
M
R
M
L
B
Z
3047
3047
3407
3485
3485
3596
3297
3497
3407
3825
4034
3256
3297
3784
4034
3674
3825
3584
3297
3674
3784
3497
3256
3596
传统启发式算法之改进形
最佳优先(best-first)探索:
最佳优先探索使用启发性规则,在探索过程中给每个已经构造的部分解q提供一个性能值来辅助下一个节点的选择、引导进一步的探索。这一性能值包括:
1)已作决策的性能值----c(q)
2)有待决策的潜在性能值----h(q)
一个部分解q的性能评价函数为:
eval (q)=c(q)+h(q)
传统启发式算法之改进形
改善法(局部探索法)的改进形
改善法的探索路径
改善法的局限性
改善法的改进形
传统启发式算法之改进形
局部最优解
近邻与局部最优解(概念図)
近邻 N(x)
可行解x