局部搜索算法

Seawind2012

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

局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。
/ ^' G3 E$ t4 Z1 \
* ^5 U* [' p) a局部搜索算法是从爬山法改进而来的。
5 h5 N+ T3 {1 N* n$ l+ {# v
爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。

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

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

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

爬山算法
4 r/ k2 ~2 t4 I  |+ s
1, n := s;

2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);
* h, Q9 b0 d2 q5 t- P0 R
3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)}
% a- o; ?  p1 x, I; h( |$ i" Y: P
# ~* V4 L, U* S8 J/ }4, IF h(n)<h(nextn) THEN EXIT(Fail);
! u! J6 S. M: g  `4 n9 e. V# Y
+ Q  ~0 q0 \: g) Y+ i% t* P5, n:=nextn;

# d2 `% c8 C, s* I' p  I; D6, GO LOOP;

该算法在单峰的条件下，必能达到山顶。
0 s- ^1 z. v) n. [
) M3 t" {/ u& u. F, i局部搜索算法

（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);
: Y. m. S3 p- g7 o) O& a
2 `) J. C; g( _5 \, W     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。

" [, B* i, G5 ~# D4 y& N* g" F（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等

（3）Begin

9 u/ @. H: G6 U1 D（4）选择P的一个子集P‘，xn为P’的最优解

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

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

2 b& Q7 l' `, n2 M       // 重新计算P，f(x)为指标函数

（6）否则P=P-P‘，转(2)
* Y0 f+ [9 P5 U( e1 T* w
  m/ \3 V& r; q（7）End

（8）输出计算结果

（9）结束

2 C3 G) l$ b3 v7 k% v! V
局部搜索算法2——可变步长
( u. A/ j' P+ ^- g' @


（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);
/ P/ [5 ~% ~, e
4 K" M. Z3 V9 t, N& `     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。
: U) ^3 }4 r0 q- s6 ~- p% j1 E) B
7 q$ `9 r1 ^9 [# K9 ]# m! `- P（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
" e7 e" x. Z0 V3 p4 e: g1 t2 @% ]. g
' w: ~3 e' @/ n（3）Begin
$ A# y5 H5 s4 Q3 M2 _0 ^
9 M6 e" z- u, {* g0 ~（4）选择P的一个子集P‘，xn为P’的最优解
7 X- u6 q; T& [6 Q, V
（5）如果f(xn)<f(xb)，则xb=xn
# \& _2 q; r+ \6 Q. m/ ~
2 X( z- O/ h( y# R+ E- u5 {: S/ j（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续

（7）否则P=P-P‘，转（2）
- t1 V3 E3 [0 r8 V, ]' K- p# B; r3 N; s  j
（8）End

（9）输出计算结果
& a2 z/ h/ E8 }7 a+ p' z# E7 Y
（10）结束
* x- P- u* I& U
( [; v1 h% d. y& e
' z8 {$ a) A/ G- @局部搜索算法3——多次起始点



' D( z2 a3 h# h/ V1 l（1）k=0
9 S1 D1 p/ ?: Q: y8 t* ]. k
（2）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

（3）如果不满足结束条件，则：
. c8 w) V# l; w: q6 p% I9 K
, e- d: @  X, U1 `' ~1 L4 _0 J（4）Begin

. l' A, B* Z1 \（5）选择P的一个子集P‘，xn为P’的最优解

( t9 u/ y- ?7 v% b# e" I4 r（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）

+ w* r" R, z$ f4 P( y（7）否则P=P-P‘，转（3）
, L3 Q2 R# ~4 b4 Y
" I( a7 H& o, z1 E5 J! P; L（8）End

（9）k=k+1

+ M% P5 c3 w/ J( ]0 F/ i% ]3 ]9 O' k（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）

（11）输出结果
- Y2 i, O/ r- u, |' M2 ~
（12）结束

darker50

   做成一个文档的形式发布会比较好点!

Seawind2012

darker50 发表于 2012-6-21 11:19
/ Z$ O  [2 U0 F4 Q+ N做成一个文档的形式发布会比较好点!

; H% Y& E8 j( I% T- A& IThank you for your attention and review!

925274979

谢谢楼主。。。赞

happi

谢谢分享，顶了

liu168ad

感觉不错                                             

Jaafar

很好啊！！