4局域随机搜索

局域搜索与随机搜索概要•爬山法•随机搜索•模拟退火法•局域射线搜索•遗传算法搜索问题•已知：–一个状态（或构形）集：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DBDECDEACE……ABCDEEvalX1真真伪真伪5X2真真真真真4实例：可满足性问题（SAT）ABCACDBDECDEACE……ABCDEEvalX1真真伪真伪5X2真真真真真4•构形X=有N个布尔变量值的矢量。•Eval(X)=在已知X值的条件下，可满足的句子数。•寻找X*来使Eval(X)极大。•搜索空间尺寸=2N。•注意：变量和句子上千时，搜索空间是巨大的。实例：N个皇后•寻找一个构形，使得没有一个皇后能攻击其她任何一个皇后。EVAL(X)=5EVAL(X)=2EVAL(X)=0实例：N个皇后•构形X=在N列中N个皇后的位置。•Eval(X)=能两两相互攻击的皇后偶对的数目。•寻找X*来实现极小：Eval(X)=0。•搜索空间尺寸：NN量级。•注意：N10时，搜索空间是巨大的。EVAL(X)=5EVAL(X)=2EVAL(X)=0局域搜索•假设对每个构形X，定义一个邻域（或移动集）Neighbors(X)，它是从X出发在一步内能到达的构形集。1.X0初始态2.重复直到满意当前构形为止：•评估Neighbors(Xi)中的一些近邻•选择其中一个近邻，Xi+1•移到Xi+1局域搜索•议题：–一般情况下，不能直接、清楚、唯一地定义邻域，然而搜索算法的性能依赖于邻域的定义。–选择策略：怎样决定接受哪个近邻？–满意条件，即停止条件？最简单的实例S={1,…,100}Neighbors(X)={X-1,X+1}最简单的实例•虽然对全域极值有兴趣，但可能只得到一个局域极值。•事实上，每次迭代只能得到局域极值。•挑战性：通过一系列的局域移动来试图达到全域极值。S={1,…,100}全域极值Eval(X*)所有X的Eval(X)局域极值Eval(X*)在Neighbors(X)中所有X的Eval(X)Neighbors(X)={X-1,X+1}最基本的算法：爬山法(HillClimbing)（局域贪婪搜索(GLS)）•X初始构形•迭代：1.EEval(X)2.NNeighbors(X)3.对在N中的每个XiEiEval(Xi)4.if所有的Ei都比E低ReturnXelsei*=argmaxi(Ei)XXi*EEi*更有趣的实例•怎样来定义Neighbors(X)?SATABCACDBDECDEACE……TSPN个皇后议题多个局域极值Eval(.)恒定值的平台区山脊：仅用爬山移动是不可能从Xstart到达X*的。议题•空间开销恒定。•所能期望的，就是找到最接近初始构形的局域极值。还能做到比这更好吗？•山脊与平台将困扰所有的局域算法。•邻域的设计是与算法的设计一样的关键。•对邻域尺寸要权衡：–较大的邻域=找到一个好极值的机会较大，但可能需要评估巨大的移动数。–较小的邻域=较小的评估量，但可能会被困在局域极值处。贪婪爬山vs.随机爬山随机搜索：随机爬山法•X初始构形•迭代：1.EEval(X)2.X’在Neighbors(X)中随机选择一个构形3.E’Eval(X’)4.ifE’EXX’EE’•议题：–迭代停止条件？–不再选择在整个邻域中的最佳移动，但又是什么的其它移动呢？TSP移动选择2条边颠倒对应结点的次序2边改变，产生O(N2)的邻域3边改变，产生O(N3)的邻域选择3条边爬山法：TSP示例•k边优化=采用k边变化邻域的爬山法•结果：–3边优化比2边优化好。–在给定计算时间增量下，4边优化没有明显更好。–采用随机重算以提高成功的几率。–更好的度量：离开极小代价估值的百分数。与极小代价间的误差%(N=100)与极小代价间的误差%(N=1000)执行时间(N=100)执行时间(N=1000)2边优化4.54.91112边优化(1000中最好的)1.93.63边优化2.53.11.213.73边优化(1000中最好的)1.02.1爬山法：N个皇后•基本爬山法不是很有效。•由于许多构形有相同的代价，所有出现平台问题。•多次随机重算是提高性能的标准方法。N=8成功%平均移动数直接爬山法144横向(sideways)移动9421(成功)/64(失败)E=5E=2E=0爬山法：SATABCACDBDECDEACE……WALKSAT算法：•状态X=N个布尔变量的赋值。•随机初始化变量（x1,…,xN）为真或伪。•迭代直到所有句子被满足或是到达迭代极限：1.选择一个不满足的句子2.以p的概率，随机选择一个变量xi3.以1-p的概率，选择这样的变量xi，改变xi后只不满足极少数句子，即使Eval(X)极大。4.改变所选择变量的值。注：2为随机行走，3为贪婪爬山。爬山法：SAT•WALKSAT算法是最为有效的SAT算法之一。•结合两个要素：随机行走和贪婪爬山。•不完全搜索：不能发现该句子无法满足。模拟退火法（SA）1.EEval(X)2.X’一个在Neighbors(X)中随机选择的构形。3.E’Eval(X’)4.ifE’EXX’EE’else以某概率p接受到达X’的该移动：XX’EE’注：不再总是爬山移动了。怎样选择p？怎样给p赋值？•X初始构形•迭代：1.EEval(X)2.X’一个在Neighbors(X)中随机选择的构形。3.E’Eval(X’)4.ifE’EXX’EE’else以某概率p接受到达X’的该移动：XX’EE’•如果p为常数：则不知道该给p赋怎样的值，因为其值应依赖于Eval函数的形状。•随着迭代的发展，p应降低。由此可在趋向全域极值时，接受较少的下山移动。•随着E-E’增加，p应降低。如果坡度陡，则应降低下山移动的概率。怎样给p赋值？E-E’大：较可能的是，迭代正朝着一个敏锐的极大值移动。因此，此时不宜采取大的下山移动。E-E’小：可能是迭代正朝着一个平缓的极大值移动。这类极值可能是一个局域极值，因此，希望移下山，去探索其它地方。选择p：模拟退火法•ifE’E，接受该移动•else接受该移动，并置概率为：p=e-(E-E’)/T•从高温开始，随着迭代开展而逐渐降低T，即冷却调度选择p：模拟退火法•ifE’E，接受该移动•else接受该移动，并置概率为：p=e-(E-E’)/T•从高温开始，随着迭代开展而逐渐降低T,即冷却调度增加Ep增加T模拟退火法1.迭代K次：1)EEval(X)2)X’一个在Neighbors(X)中随机选择的构形。3)E’Eval(X’)4)ifE’EXX’；EE’else接受该移动，并置概率为p=e-(E-E’)/T：XX’；EE’2.TT模拟退火法•X初始构形•T初始高温•迭代：1.迭代K次：1)EEval(X)2)X’一个在Neighbors(X)中随机选择的构形。3)E’Eval(X’)4)ifE’EXX’；EE’else接受该移动，并置概率为p=e-(E-E’)/T：XX’；EE’2.TT模拟退火法•注意事项：–迭代K次时，保持温度恒定。–T=0，p=0，随机爬山法；T=，p=1，随机行走。–采用一个指数冷却调度来逐步降低温度：T(n)=nT，且1，即=n。–采用前次迭代定义的概率值来接受下山移动。示例T=15.8975T=12.877起点：爬山移动。150次迭代：随机下山移动以避开局域极值。示例T=11.5893T=3.2731180次迭代：随机下山移动已使迭代离开了局域极值。800次迭代：随着T降低，只允许较少的下山移动，由此就留在最高点。基本示例在高温下，允许大范围地不使用爬山搜索。E温度迭代次数模拟退火法起源•如果一块固体的温度为T，则在两能量状态间转移的概率为：e-Energy/kT。•如果固体温度缓慢下降，则它将到达一个平衡态，固体处于一个特殊状态的概率为：Probability(State)e-Energy(State)/kT。•波尔兹曼分布：相对于T的低能量状态是更可能的状态。•类比：–固态与构形X–能量与评估函数Eval(.)TSP示例1N=13个结点K=100NE=25注：有一个明显的解答。起始构形E(X)=55TSP示例在高温下，允许大范围地不使用下山搜索。E温度迭代次数迭代次数起始构形收敛后的最终构形中间态可能比起始态还差TSP示例2N=13个结点K=100N起始构形TSP示例2在高温下，允许大范围地不使用下山搜索。E温度迭代次数迭代次数起始构形收敛后的最终构形什么是收敛？•理论上：Pr为在温度T下，K次迭代后，模拟退火所到达的状态X是一个全域极值的概率。•实际上：–执行足够多的迭代，即K足够大。–温度降低要足够慢，即要足够接近于1。–但是，如果不小心，可能不得不执行大量计算。1*,Prlimlim0SKTXKT模拟退火法•X初始构形•T初始高温•迭代：1.迭代K次：1)EEval(X)2)X’一个在Neighbors(X)中随机选择的构形。3)E’Eval(X’)4)ifE’EXX’；EE’else接受该移动，并置概率为p=e-(E-E’)/T：XX’；EE’2.TT需要处理的参数有：初始构形、初始温度、K、Neighbors(X)、随机选择一个构型、等。SA讨论•邻域设计是关键性的。•怎样选择K？通常，K是与邻域尺寸有关的。•怎样选择？是避免大量无用计算的关键。特别是在接近收敛时，这确是一个问题。经验告我们，大部分时间是花在极值附近的。SA讨论•怎样选择初始温度？通常与E的期望值的分布有关。例如，Tstart=max{E：一个近邻偶对的大样本}•如果选择了一个差的起始X，怎么办？多次随机重算。•怎样避免重复估算？用一点存储空间来记录已试过的移动（禁忌(Tabu)搜索）。•如可能，采用快的近似估算。SA讨论•通常优于爬山法。在很多应用中很成功。•要处理许多参数。如不小心，所需要的计算量可能非常大。•根据具体应用，可采用半无限的变化来改善性能。局域射线搜索（LBS）•不是追踪一个状态，而是k个状态–开始，随机产生k个状态–在每一步•产生这k个状态的后续态–如果有一个是终态，则停止–否则从完整序列中选择k个最佳的后续态•随