查看: 9986|回复: 7

[其他资源] 局部搜索算法

[复制链接]

字体大小: 正常放大

Seawind2012

102 主题	5 听众	913 积分

升级 78.25%

TA的每日心情

	开心 2013-4-28 12:11

签到天数: 160 天

[LV.7]常住居民III

群组: 数学软件学习

电梯直达

1^#

发表于 2012-6-21 10:57 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

全局搜索和局部搜索.
目前使用较普遍的、有影响的
全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS算法;
局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类.
接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法.
此外,接触问题的并行计算也是不可忽视的研究内容

局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。

局部搜索算法是从爬山法改进而来的。

爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。

局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。

现实问题中，f在D上往往有多个局部的极值点。一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。考虑归一化问题，使得邻域内所有点被选中的概率和为1。

一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图

爬山算法

1, n := s;

2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);

3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)}

4, IF h(n)<h(nextn) THEN EXIT(Fail);

5, n:=nextn;

6, GO LOOP;

该算法在单峰的条件下，必能达到山顶。

局部搜索算法

（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);

   //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等

（3）Begin

（4）选择P的一个子集P‘，xn为P’的最优解

      // P’可根据问题特点，选择适当大小的子集。可按概率选择

（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)

   // 重新计算P，f(x)为指标函数

（6）否则P=P-P‘，转(2)

（7）End

（8）输出计算结果

（9）结束

局部搜索算法2——可变步长

（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

   //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等

（3）Begin

（4）选择P的一个子集P‘，xn为P’的最优解

（5）如果f(xn)<f(xb)，则xb=xn

（6）按某种策略改变步长，计算P=N(xb)，转（2）继续

（7）否则P=P-P‘，转（2）

（8）End

（9）输出计算结果

（10）结束

局部搜索算法3——多次起始点

（1）k=0

（2）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

（3）如果不满足结束条件，则：

（4）Begin

（5）选择P的一个子集P‘，xn为P’的最优解

（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）

（7）否则P=P-P‘，转（3）

（8）End

（9）k=k+1

（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）

（11）输出结果

（12）结束

zan

算法, 搜索, 影响