4局域随机搜索(副本).ppt

1、局域搜索与随机搜索,概要,爬山法 随机搜索 模拟退火法 局域射线搜索 遗传算法,局域搜索,假设对每个状态X，定义一个邻域（或移动集）Neighbors(X)，其是从X出发在一步内能到达的状态集。 X0初始态 重复直到满意当前状态为止。 评估Neighbors(Xi)中的一些近邻 选择其中一个近邻，Xi+1 移到Xi+1,最简单实例,S=1,100 Neighbors(X)=X-1,X+1,最简单实例,虽然对全域极值有兴趣，但可能只有满足于局域极值。 事实上，每次迭代只能得到局域极值。 挑战性：通过一系列的局域移动来试图达到全域极值。,S=1,100,全域极值Eval(X*)所有X的Eval(X

2、),局域极值Eval(X*)在Neighbors(X)中所有X的Eval(X),Neighbors(X)=X-1,X+1,搜索问题的提出：,已知： 一个状态（或构形）集：S=X1,XM, 一个评估每个状态的函数：Eval(X). 求解： 寻找全域极值：寻找X*使得Eval(X*)比所有其它Eval(Xi)都更大，Xi是所有可能的值。,实例,调度：已知m个机器，n个任务。 X=给机器的任务安排 Eval=这n个任务完成时间的极小化 其它：车辆路由、设计、处理排序，,任务,机器,时间,实例：旅行推销商问题（TSP）,寻找一个经过每个结点一次，且长度最小的旅行路线。,Eval(X1)Eval(X2)

3、,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,实例：N个皇后,寻找一个构形，使得没有一个皇后能攻击其她任何一个皇后。,EVAL(X)=5,EVAL(X)=2,EVAL(X)=0,实例：N个皇后,构形X=在N列中N个皇后的位置。 Eval(X)=能两两

4、相互攻击的皇后对数目。 寻找X*来实现极小：Eval(X)=0。 搜索空间尺寸：NN量级。 注意：N10时，搜索空间是巨大的。,EVAL(X)=5,EVAL(X)=2,EVAL(X)=0,最基本的算法：爬山法（局域贪婪搜索）,算法描述： 顾名思义，爬山法就是向Eval(X)值增大的方向持续移动。 算法分析： 爬上法终将在一个“峰顶”终止，此时相邻状态中没有比它更高的值。算法不维护搜索树，当前节点的数据结构只记录当前状态和它的目标函数值。爬山法不会前瞻与当前状态不直接相邻的那些状态值。所以爬山法到达一个局部最大值或者“平原”的时候，就会无路可走，可见，爬山法不是最优的。,爬山法（局域贪婪搜索）,

5、X初始构形(状态） loop do： E Eval(X) N Neighbors(X) 对在N中的每个Xi Ei Eval(Xi) /评估每个后续的值 Ei*=argmaxi(Ei) /选择具有最大值的后续 if (Ei* E) return X else XXi* EEi*,爬山法的局限,多个局域极值,Eval(.)恒定值的平台区,山脊=仅用爬山移动是不可能从Xstart到达X*的。,随机搜索：随机爬山法,随机爬山法就是指在上山的过程中随机的选择下一步，选择的概率随上山的陡峭程度而变化。 X初始状态 迭代： EEval(X) X在Neighbors(X)中随机选择一个状态 EEval(X)

6、if EE XX EE 问题： 迭代停止条件？选择下一步的概率为0，即周围的值都比E小（EE） 不再选择在整个邻域中的最佳移动。,模拟退火法（SA）,算法描述： SA算法是爬山法和随机行走算法的结合，以同时求的有效性和完备性。SA算法没有选择最佳的移动，而是选择随机的移动。如果移动使情况改善，那么该移动。否则，算法以某个小于1的概率接受该移动。这个概率按照移动的“恶劣状态”评价值变坏的梯度E(E-E)成指数级下降。这个概率同时也随着“温度”的降低而下降：当一开始温度高的时候，“坏的”移动更可能被允许发生，T越低就越不可能发生。如果让T下降的足够慢，这个算法找到全局最优解的概率将逼近1。,模拟退

7、火法（SA）,EEval(X) X一个在Neighbors(X)中随机选择的状态。 EEval(X) if EE /即E0 XX EE else 以某概率p接受此到达X的移动： XX EE 注：不再总是爬山移动了。怎样选择p？,怎样给p赋值？,X初始构形 loop do： EEval(X) X一个在Neighbors(X)中随机选择的构形。 EEval(X) if EE XX EE else 以某概率p接受此到达X的移动： XX EE,如果p为常数：则不知道该给p赋怎样的值。其值应依赖于Eval函数的形状。 随着迭代的发展，p应降低。由此可在趋向全域极值时，接受较少的下山移动。 随着E-E 增

8、加，p应降低。如果坡度陡，则应降低下山移动的概率。,怎样给p赋值？,E-E 大：较可能的是，迭代正朝着一个敏锐的极大值移动。因此，此时不宜采取大的下山移动。,E-E 小：可能是迭代正朝着一个平缓的极大值移动。这类极值可能是一个局域极值，因此，希望移下山，去探索其它地方。,选择p：模拟退火法,if EE，接受该移动 else 接受该移动，并置概率为： p=e(E-E)/T 从高温开始，随着迭代开展而逐渐降低T,即冷却调度,增加E,p,增加T,模拟退火法,X初始构形 T初始高温 loop do： 循环K次： EEval(X) X一个在Neighbors(X)中随机选择的构形 EEval(X) if

9、 EE XX；EE else 以概率p=e(E-E)/T接受该移动 XX；EE TT 需要处理的参数有： 初始构形、K、初始温度、随机选择、Neighbors(X)、等。,模拟退火法,注意事项： 循环K次时，保持温度恒定。 T=0，以p=1的概率选择最大值后继（贪婪爬山法）；T=，以p=0的概率选择最大值后继（随机行走）。 采用一个指数冷却函数来逐步降低温度：T(n)= T，其中=n，且1。 采用p=e(E-E)/T概率值来接受下山移动。,局域射线搜索,算法描述： 局部射线搜索记录k个状态，而不是一个。它由K个随机生成的状态开始。在每步产生这k个状态的所有后继状态，如果有一个是终态，则停止。否

10、则从后继列表中选择k个最佳的后继，然后重复这个过程。 改进： 随机重启搜索 局域射线搜索与平行k个随机重启搜索 随机射线搜索 随机射线搜索不是从候选后继集合中选择最好的k个后继状态，而是按一定的概率随机地选择k个后继状态。其中选择给定后继状态的概率是状态值的递增函数。,遗传算法（GA）,以进化来看待优化。 把状态看做群体中的个体。 把Eval看做适应性度量。（适应度函数） 让最不适应个体无繁殖死去。 对比上一代来说，每代总体上应有更好的适应，即较高的Eval值。 如果等得足够长，则群体应进化成每个体都具有高适应性，即Eval最大。 遗传算法的操作主要有：选择、繁殖、变异。,适应度函数,为了对个

11、体的适应能力进行度量，而引入了一个适应度函数。通过适应度函数来决定染色体的优劣程度。对于优化问题，适应度函数就是目标函数，TSP的目标是路径总长度为最短，自然地，路径总长度就可以作为TSP问题的适应度函数。 适应度函数要有效地反映每一个个体与群体的最优个体之间的差距。若一个个体与群体的最优个体差距较小，则对应的适应度函数之差就较小，否则就较大。,基本GA概述,产生初始群体X=X1, Xp 迭代： 选择K对随机双亲(X,X) 对每对双亲(X,X)： 采用交叉操作来生产后代(Y1,Y2) 对每个后代Yi： 用Yi来替换在群体中随机选取的组元 以概率来对Yi实施一个随机变异。 给出群体中的最佳个体。

12、 注: 迭代的停止条件不是很明了。 选择K可能的策略：选择最佳的rP个个体(r1)来繁殖，并去掉所有剩余个体，即选择最适应的个体。 一种生产后代的方式：只产生一个后代。,遗传算法的实现,构形用位串来表示：X= 类比： 串是代表个体的染色体。 串由基因组成。 基因构形被传给后代。 对高实用性有贡献的基因构形趋向于在群体中继续生存。 从一个有P个构形的随机群体开始，并实施下面两个操作： 繁殖：选择2个双亲，并生产2个后代。 变异：在一个随机选择的构形中，选择一个随机入口处，并改变它。,遗传算法：选择,通过对Eval的阀值或固定的群体百分数来去掉最不适应的个体。 优先选择最适应（较大Eval）的双亲

13、。 示例：根据概率分布来随机选择个体： 示例（比赛）：选择群体的一个小随机亚组，并选择其中最适应的个体作为一个。 实施最适者生存。 可对应于爬山法的贪婪部分。,遗传算法：繁殖（交叉）,一个后代从双亲那里接受部分基因。 通过交叉操作来实现。,后代：,选择随机交叉点： (此处选择的交叉 点为5),双亲：,遗传算法：变异,在一个构形中随机改变某一组元 实现对遗传特征的随机偏离。 可对应于随机行走：引进随机移动来避免小局域极值。,选择一个随机个体,选择一个随机入口,改变此入口,变异就是随机地改变位串上某个位置上的组元。二进制表示位串 只有0和1两种可能。,此处随机为6,GA与爬山法,产生初始群体X=X1, Xp 迭代： 选择K对随机双亲(X,X) 对每对双亲(X,X)： 采用交叉操作来生产后代(Y1,Y2) 对每个后代Yi： 用Yi来替换在群