启发式优化算法介绍.ppt

启发式优化算法介绍
报告人: 张成芬
1
报告内容
一
启发式优化算法研究背景
二
启发式优化算法简介
4
三
应用实例
2




3
1. 概念
启发式算法(heuristic algorithm)定义1 一种基于直观或经验构造的算法,在可接受的耗费(指计算时间、占用空间等)下给出待解决优化问题每一实例的一个可行解,该可行解与最优解的偏离程度未必可事先估计。
启发式算法定义2 启发式算法是一种技术,该技术使得能在可接受的计算费用内去寻找尽可能好的解,但不一定能保证所得解的可行性和最优性,甚至在多数情况下,无法描述所得解与最优解的近似程度。
4
2. 应用领域
6
2. 应用领域
科学领域
物理、化学、生态学
医学、计算机科学等
1993年,Jones等
用多目标遗传算法
进行分子结构分析
7
3. 研究意义
汉诺塔问题:和尚搬盘子
天神梵天的三条规则:
每次只能移动一个盘子;
盘子只能在三根柱子上来回移动,不能放在他处;
在移动过程中,三根柱子上的盘子必须始终保持大盘在下,小盘在上。
8
3. 研究意义
当n=64时,移动次数=?花费时间=?
h(n)=2h(n-1)+1
=2(2h(n-2)+1)+1=22h(n-2)+2+1
=23h(n-3)+22+2+1
……
=2nh(0)+2n-1+…+22+2+1
=2n-1+…+22+2+1=2n-1
需要移动盘子的次数为:
264-1=18446744073709551615
9
3. 研究意义
假定每秒移动一次,一年有31536000秒,则僧侣们一刻不停地来回搬动,也需要花费大约5849亿年的时间。
假定计算机以每秒1000万个盘子的速度进行搬迁,则需要花费大约58490年的时间。
理论上可以计算的问题,实际上并不一定能行,这属于算法复杂性方面的研究内容。