4局域随机搜索.ppt

局域搜索与随机搜索
概要
爬山法
随机搜索
模拟退火法
局域射线搜索
遗传算法
搜索问题
已知:
一个状态(或构形)集:S={X1,…,XM},
一个评估每个状态的函数:Eval(X).
求解:
寻找全域极值:寻找X*使得Eval(X*)比所有其它Eval(Xi)都更大,Xi是所有可能的值。
实例
超大规模集成电路(VLSI)布局图:
X=组件放置+连接路由
Eval=组件间距离+没用的组件%+路由长度
放置
铺设安排
信道路由
封装
实例
调度:已知m个机器,n个任务
X=给机器的任务安排
Eval=这n个任务完成时间的极小化
其它:车辆路由、设计、处理排序、……
任务
机器
时间
挑战性
感兴趣的问题:
构形集太大,不能显式列举。
计算Eval(.)可能很昂贵。
没有用来寻找Eval(.)极大值的有效算法。
对于要解决的问题,Eval(.)值相似的解被认为是等同的。
不关心怎样得到X*,仅关心对X*构形的描述。这是与以前介绍的搜索问题的一个关键不同。
实例:旅行推销商问题(TSP)
寻找一个经过每个结点一次,且长度最小的旅行路线。
Eval(X1)>Eval(X2)
X1={1,2,5,3,6,7,4}
X2={1,2,5,4,7,6,3}
实例:旅行推销商问题(TSP)
构形X=经过结点{1,…,N}的旅行
Eval=由{1,…,N}的一个排列来定义的路径长度
寻找X*来实现Eval(X)的极小。
搜索空间尺寸=(N-1)!/2量级。
注意:N为几十万时,搜索空间是巨大的。
Eval(X1)>Eval(X2)
X1={1,2,5,3,6,7,4}
X2={1,2,5,4,7,6,3}
实例:可满足性问题(SAT)
命题逻辑(布尔代数):
ABC
ACD
BDE
CDE
ACE
……
A
B
C
D
E
Eval
X1
真
真
伪
真
伪
5
X2
真
真
真
真
真
4
实例:可满足性问题(SAT)
ABC
ACD
BDE
CDE
ACE
……
A
B
C
D
E
Eval
X1
真
真
伪
真
伪
5
X2
真
真
真
真
真
4
构形X=有N个布尔变量值的矢量。
Eval(X)=在已知X值的条件下,可满足的句子数。
寻找X*来使Eval(X)极大。
搜索空间尺寸=2N。
注意:变量和句子上千时,搜索空间是巨大的。