局部搜索算法

Seawind2012

全局搜索和局部搜索.
目前使用较普遍的、有影响的
( c5 i/ U  g" J/ k- v+ X全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS算法;
局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类.
5 U# A; @8 F+ v, I- A' C接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法.
此外,接触问题的并行计算也是不可忽视的研究内容
& s# v* K! _/ e1 r
局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。
1 p* S6 y  L: z' [1 t* m" F# j
局部搜索算法是从爬山法改进而来的。

' _: }! M5 T0 A  m/ A爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。

- K+ V$ k. ~1 @局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
2 q3 ?) O5 F0 \2 L: D
1 i9 }# C2 J( c& ?6 c现实问题中，f在D上往往有多个局部的极值点。一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。考虑归一化问题，使得邻域内所有点被选中的概率和为1。
" z. o; d* L! s+ z; O
$ z! w6 }5 j# y一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图
( |" S+ N/ X) Z# w) L7 b) W
$ }8 }! `! j, s* X7 Y6 T+ M( f! X爬山算法

1, n := s;

7 U0 n1 i) P% U6 z  y' O2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);
2 a( d2 [$ t2 X! i! ~: t. @
. b3 t3 d9 t0 d  k. `  l3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)}

3 w: r+ A( T& q! Q0 d6 Z3 O4, IF h(n)<h(nextn) THEN EXIT(Fail);
% U7 G# f0 s& y0 r% ]5 d
- V( H+ T, j5 |2 h5, n:=nextn;
. n6 P* Y. f0 g5 \1 `, B
6, GO LOOP;
/ ~1 o* a& \/ k7 Q; Z( Z
7 _0 q0 O! k  I: k/ _该算法在单峰的条件下，必能达到山顶。

2 Q" i9 Q% T; c" D0 X: l1 u/ P局部搜索算法
, [  n( o& I2 \( F8 _7 i+ B
* F; Z+ i8 n% Q% @/ ]5 T' t（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);
) @. T4 Y8 ?( f2 h' r; A  u
" ?5 G  X9 x7 @8 O* I     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
3 T+ c- \0 |+ t' D* \
（3）Begin
( H& \+ g# n2 k1 l$ k
  [! c5 p4 r0 ]+ D（4）选择P的一个子集P‘，xn为P’的最优解
! j& S" v# ~0 W6 Y1 o* S$ P5 b
' x5 `' T0 p( d/ o; f: t        // P’可根据问题特点，选择适当大小的子集。可按概率选择

（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)
5 R, |4 K; [2 e8 Z
2 B2 W# ~! t. F6 M       // 重新计算P，f(x)为指标函数

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

（7）End

( t9 Q( S* G, {/ @, @（8）输出计算结果
' i+ P4 t  d6 P+ m8 Z9 \0 e
（9）结束

6 t  i  S8 J* @- k# E
局部搜索算法2——可变步长

4 g3 P& p1 y1 u. s
; \* I1 k8 ?5 I) H& M" P
) ^1 V1 E' y' G3 ~6 U1 }( C; h（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。
+ _, X# }" {) s0 W1 b0 v: d3 D
（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
3 \& X$ z8 s/ ^) U. E) a' f
（3）Begin
  z/ a0 w/ z; _* E+ D! m
' w% N3 @) y* Y. S/ A（4）选择P的一个子集P‘，xn为P’的最优解
; o6 |4 h# ?: ~; V/ Q# [0 B
（5）如果f(xn)<f(xb)，则xb=xn
7 U, v  I7 r* n2 p! ^; W. H) G
（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续

' i7 ^7 }9 `' S" V1 H（7）否则P=P-P‘，转（2）

( J, q% a6 U! D. v' k; M" S（8）End
5 M6 D& D$ v+ [9 v; U2 G
（9）输出计算结果

（10）结束
. d* ]' b: v" }

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

3 r* C6 l  \1 c8 P2 X" k" H

0 e' y- K$ o! Z; X/ \0 D5 i（1）k=0

（2）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);
1 b& a$ }7 Y$ z3 |+ i/ x! m9 W2 v+ K
（3）如果不满足结束条件，则：
. ]9 n2 n: g9 V+ ]; x( N% X# Z! u
（4）Begin

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

% T5 f2 ~$ I& P8 r" ]1 C（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）
' t- A8 n5 l! q' v
（7）否则P=P-P‘，转（3）
4 d; [( V5 H: J1 m
! z9 A, D* C' g: _# `（8）End
% @; l* [; u& f1 u$ m4 k+ B1 @
（9）k=k+1

! K. ]  X2 ~" g+ E（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）
1 m3 p+ ]. u9 \, d, l0 r
（11）输出结果

! Z0 q- ]0 S* _1 l) s* l（12）结束

darker50

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

Seawind2012

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

Thank you for your attention and review!

925274979

谢谢楼主。。。赞

happi

谢谢分享，顶了

liu168ad

感觉不错                                             

Jaafar

很好啊！！