局部搜索算法

Seawind2012

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

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

! W3 V/ _) m3 w* Z6 B0 _  {局部搜索算法是从爬山法改进而来的。

3 S; g; c$ c1 G! g0 f) m! e爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。

8 N' f. q$ M; I0 b; K局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。

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

5 h' C( o4 m& Q, O/ o. L一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图
* F: B- J( O: M  d1 q' H
/ l2 r: C- h7 ^2 S  T4 [爬山算法
4 ~4 q* q9 m+ i2 ^
- R2 J$ @7 p9 b& P; C( h1, n := s;

* A' p% y* m$ m$ x7 N$ G2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);

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

$ `  P1 X+ x* d$ L) Q8 g; b4, IF h(n)<h(nextn) THEN EXIT(Fail);

/ z) c' z* L' r! b' m4 S$ g) B5, n:=nextn;

6, GO LOOP;

该算法在单峰的条件下，必能达到山顶。
, _8 @2 Q/ u& V9 o# \' n
5 m& t* U( e9 H7 p" {局部搜索算法
5 q' Y( H4 O+ d" w8 Q
（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);

& T% R+ x: h2 S9 s% }- A5 j     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。
4 B# y0 @/ q$ A/ k# B, J
$ x  f% x, _6 f2 _! V（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
$ y6 I1 ]! x' f7 S. d
（3）Begin
3 h, @4 w1 Z0 r+ v5 R, z
. y, Z$ w* v4 [. p（4）选择P的一个子集P‘，xn为P’的最优解

9 H$ P2 T5 _3 ]( M        // P’可根据问题特点，选择适当大小的子集。可按概率选择

0 H' N( `5 Q4 e+ |  r) p（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)
* I1 X& ~) w( `# Q( m5 i
' m+ T8 R' ?  \# D* z0 ~/ G       // 重新计算P，f(x)为指标函数
" Q) B* k" |9 U; h8 t2 A
（6）否则P=P-P‘，转(2)
5 I# R5 u/ p9 p2 L: a
（7）End

（8）输出计算结果
5 \+ v+ b# Q: t) B1 q
（9）结束

$ L7 o/ M; K0 a  N. B
" ~* y" H, x; c& a. B) a/ [1 V( r局部搜索算法2——可变步长


' K+ t' W$ a8 O0 X; z9 j* a  T
7 }4 H9 V8 n6 J- v# n" N（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

2 I5 ?. `5 M9 f     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。

% T1 z- m% P) p) h4 J（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等

（3）Begin

/ q) v, |# }' z% K（4）选择P的一个子集P‘，xn为P’的最优解

（5）如果f(xn)<f(xb)，则xb=xn
+ {8 j. q6 O, d9 e; K0 J: N
9 {  v1 \9 f2 @  Y! e: R' {) x（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续
  Y9 v* [7 c" a" u; }
) }8 F# q2 E7 \" X: e（7）否则P=P-P‘，转（2）

（8）End

（9）输出计算结果
7 G5 m3 [- `7 Y0 u- l! a
（10）结束
3 }' F1 k) d) r' z/ }

  q, M4 O9 k# C5 T# g* \局部搜索算法3——多次起始点
7 }. k) Z5 w) b) a
3 u( Z5 I3 ~7 _# t
5 ?# l0 |  L0 [0 K$ @( V3 {
2 X2 K9 s2 I+ ^9 S; e( r, ~8 z$ Y（1）k=0

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

' E/ }: U( c- g. D( ?7 D+ t$ w+ W1 |（3）如果不满足结束条件，则：
' S$ l8 b+ a) f* `3 e# n0 q
' S8 }% x% }! Z3 j. M（4）Begin
; ]8 ~! x: v  C1 V3 Z! C& x
' R$ f. f6 R6 N/ q. ^（5）选择P的一个子集P‘，xn为P’的最优解
, i# a) |/ G3 h# t% J5 U* K
+ d# i8 u7 ]1 i) ?. R# J" z0 A1 _（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）
; o/ l! n# o3 n
. f( O$ w3 n7 ]. e/ d) A. g3 V（7）否则P=P-P‘，转（3）

1 M- S. A. y, g6 D$ m（8）End

/ Y" H; \/ R# V2 e( ~- Q8 O" s（9）k=k+1
3 h/ k0 f$ J; `4 H
（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）

  H3 E# ?) Z: q（11）输出结果
+ u' C2 m5 u8 J  H) ?4 R
（12）结束

darker50

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

Seawind2012

darker50 发表于 2012-6-21 11:19
做成一个文档的形式发布会比较好点!

Thank you for your attention and review!

925274979

谢谢楼主。。。赞

happi

谢谢分享，顶了

liu168ad

感觉不错                                             

Jaafar

很好啊！！