局部搜索算法

Seawind2012

全局搜索和局部搜索.
1 g) z. N' R* H' o目前使用较普遍的、有影响的
全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS算法;
! l# t$ b0 Z$ f0 o9 `" p& m$ K9 q  I局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类.
  N: ]  R" n1 G6 `: n/ _; U% Q8 M接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法.
此外,接触问题的并行计算也是不可忽视的研究内容
& F4 U2 K' C9 M% s- v3 l' X
局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。

- q( J& D" s* {( u" Z; T. w局部搜索算法是从爬山法改进而来的。
) D8 g8 X* A5 t
5 X! U! f3 Y1 u- z$ M8 R爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。

; `3 f8 E7 ~) g5 q- F, m1 @" G局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。

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

  e( R6 `5 y9 ^$ ]  k( h8 z一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图
$ I% {* ?& d: `2 {; {
: n1 P6 b- t' ]* x. [! r' O爬山算法
& q* Z) Y6 d& e" _& c/ y  k8 \
1, n := s;
* p3 v- L$ n3 z2 Q: W
# w% v! }5 ~0 H! o% ]2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);

( ]  u, [4 E  ^8 T0 d1 x; z- {# u3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)}
2 T% w+ X1 B: q" B6 }0 j
4, IF h(n)<h(nextn) THEN EXIT(Fail);
2 |7 S8 y4 w5 p8 t6 S; S6 Y; J! }
5, n:=nextn;

& L3 v! t. j- L# D2 ^) g6, GO LOOP;

该算法在单峰的条件下，必能达到山顶。
# M" v8 h+ [5 v8 G. p% r7 N; g
4 q" I9 Q/ ~% c局部搜索算法
# e1 q" c/ G+ z
（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);
: J+ ]/ h$ {3 B  ^3 M
# p$ t! K! w2 W4 l# w; o     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。
/ H3 d2 c5 j+ _  W2 [& z! Q
（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
$ M0 q1 B8 x2 ~/ t( b" v% G8 P
( Z. S1 T2 G+ S/ X  x（3）Begin
# y/ E( D9 E' m$ n
2 z. B8 j, |4 a5 q% v. N（4）选择P的一个子集P‘，xn为P’的最优解
* H/ w, O0 Z2 N. z. D
        // P’可根据问题特点，选择适当大小的子集。可按概率选择
/ q/ {: n) ]" h& U9 i; t" O) x7 C2 {
（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)
- B, r7 H0 J1 o# t+ X
       // 重新计算P，f(x)为指标函数

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

7 c) A7 R# P6 O0 `8 L! P9 j! S- U% C（7）End
9 w4 r! S) \( J( Z7 N
3 f: A3 H; D: ?" F: C4 z, L4 w" H（8）输出计算结果

) m- P; q) z* ^" l+ s（9）结束
6 T% {& t, O9 }2 n- R. p

5 K1 y6 l% Q3 @5 N: s局部搜索算法2——可变步长
" C" F. W! j/ _- m; \4 a4 W


（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);
8 m$ e, c' V  C  d, M
     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
+ E! H+ b) U7 r
（3）Begin

（4）选择P的一个子集P‘，xn为P’的最优解
1 ]+ M5 J- m9 b& i# ]" U$ ]
（5）如果f(xn)<f(xb)，则xb=xn
: F+ p) z  E$ k8 ~2 b; t
7 H; q. C4 ?4 |" R; c（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续

) Q9 w4 r# C) ]* ?4 m  D$ q( o7 _（7）否则P=P-P‘，转（2）

（8）End
! g. A8 j( {0 v/ j
（9）输出计算结果

（10）结束

3 R6 G, e, T) L, g+ }( Q
2 Y5 u) v# |2 `- N( |5 t. _9 l局部搜索算法3——多次起始点
2 `4 m8 W5 b. l  T


1 [; L  b+ [$ M/ e  s4 @（1）k=0

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

9 J  L* j. }, }& @( g! ]（3）如果不满足结束条件，则：
+ P) c0 p6 l/ ~6 I# s/ {- P0 N
  O) j' v7 H3 A) g（4）Begin
$ @, }& t8 j# G. n1 y
* }1 {8 T( Z  k9 ^（5）选择P的一个子集P‘，xn为P’的最优解

9 b+ d2 G$ j9 S/ {（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）
1 N* m( y2 o3 a2 I6 H
（7）否则P=P-P‘，转（3）
6 S* J8 q$ s# k% E3 n: l
2 ~- F0 w4 N- L4 `（8）End
8 A& o% A' o5 _/ y
+ C: {& q: x: ?7 o" {（9）k=k+1

4 S9 E2 s1 I7 Z1 v5 _: J（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）
" B  V- z5 ~: }& ]+ D# i1 E! `* M
3 J4 K9 y# u- X/ v# |+ y（11）输出结果

（12）结束

darker50

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

Seawind2012

darker50 发表于 2012-6-21 11:19
. K! u* A6 f: |& w: H" ^做成一个文档的形式发布会比较好点!

7 v- f7 Y) M! ^5 O% g" F9 QThank you for your attention and review!

925274979

谢谢楼主。。。赞

happi

谢谢分享，顶了

liu168ad

感觉不错                                             

Jaafar

很好啊！！