局部搜索算法

Seawind2012

全局搜索和局部搜索.
! d: @  H* M# q/ i( l- C3 Q目前使用较普遍的、有影响的
全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS算法;
局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类.
6 j) @/ s2 L. ~$ q7 {, U接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法.
; f$ w5 J) H  ^5 ?2 ~此外,接触问题的并行计算也是不可忽视的研究内容

  E2 S1 t" ~* e- I: l- E( u局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。

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

爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。
9 d$ v  j# m0 c8 S8 q
局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
7 L( ~  e1 _, ^* N
1 }1 a- l6 Q3 U! n+ J1 z8 C$ s现实问题中，f在D上往往有多个局部的极值点。一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。考虑归一化问题，使得邻域内所有点被选中的概率和为1。
' }' D* v0 q$ D5 P
& ]! A* A$ p- o, l3 k" |) J一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图

2 @* r$ c& ?% @6 d" t爬山算法
: C$ O- f& @& c% j9 m# {3 x& t1 F; q* U
* o7 z6 C& i- }8 q3 W1, n := s;
* ?  |% s9 i  s0 F/ }4 l
+ n" w& e6 L  s& I% e1 @4 k8 Y0 k2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);

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

* m' Q1 D3 n7 P# u) v5 K4, IF h(n)<h(nextn) THEN EXIT(Fail);
1 z+ y) H' C- ^3 S* ^" c0 S1 @2 s
5, n:=nextn;

: S6 n5 L: C: L6, GO LOOP;

9 `* D" [* c0 z% U8 L8 a/ c9 s该算法在单峰的条件下，必能达到山顶。
+ f- A. k5 R2 s) H
# I+ o) \0 S, @. b局部搜索算法
% `, G/ C2 I/ x! o5 V$ d7 v4 @5 B
（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);

$ b$ A$ L- b) l# {1 k" {5 F# ?- t     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。

1 `4 @1 S0 x6 ?1 J# L（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
) `5 j; V, V! X% m' b$ q8 Z8 I+ E, ]
4 g& Q( `5 c* R' Q' Z2 p* O（3）Begin

（4）选择P的一个子集P‘，xn为P’的最优解
& L; [, X5 P4 e, n
  B) p$ s9 F# N! Y4 z( h1 q' N        // P’可根据问题特点，选择适当大小的子集。可按概率选择
+ o  u7 e9 f: ]+ b, @4 T, z
" s( Y, k8 E1 t) v5 [（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)

' d/ B7 L2 `7 c5 Z! F       // 重新计算P，f(x)为指标函数

（6）否则P=P-P‘，转(2)
! W- `9 P2 A* _4 s, m
8 J. M2 G* v2 s: V（7）End

, l& z1 W3 z; V1 h2 o（8）输出计算结果
9 w6 @: z+ u! G/ x
+ U$ H" v) U7 X（9）结束
' R% r7 J1 O$ J9 }% H* k! T9 N
! f% p1 a( e4 U6 p  v2 _8 ~7 u/ z+ ~
$ Y8 ?+ Y8 W3 q" h局部搜索算法2——可变步长
$ e0 }7 Q' W9 {, b& t- ^3 d" L

8 m" J) J$ N6 k% d' a8 U
; y$ ~/ Q  p" d4 g2 K+ K( J* J1 p（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。
" t6 z8 b% d+ M% Q
+ H8 M) L  m5 G3 P' Y3 R（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
5 D$ Z5 S, U, b7 }
5 C3 Y  S. K; \& h( N（3）Begin
* ~& B: c6 O  E" d, K2 d
# K5 w) L. K0 F8 O5 q  k/ {（4）选择P的一个子集P‘，xn为P’的最优解

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

（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续
7 b5 i7 @( e" B. ~% S$ R3 d
- p4 v7 g' J7 ~! O6 x. A（7）否则P=P-P‘，转（2）
' M$ u- G& N0 k3 E4 L$ n
（8）End

（9）输出计算结果
/ `6 m; z0 ~, q2 u! q. k
（10）结束


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



（1）k=0
# w6 A! i" ?# `+ c+ `, O& r! ^, ?* z8 p
& v: W1 t8 B" O$ |! A7 A  `（2）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

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

（4）Begin

（5）选择P的一个子集P‘，xn为P’的最优解
6 ^6 V. `7 [# x/ G7 {1 I9 q1 B) P
' c8 D& ?) A5 u  ~1 U1 q6 ~（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）
% q' [" R. D6 g4 A
9 K+ Z1 c: o& O2 n' M, j（7）否则P=P-P‘，转（3）

（8）End

! {1 F2 @2 _2 ~  m（9）k=k+1

# |+ Z+ n0 c9 p6 W9 q（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）

5 g1 w7 M; ?$ z9 S4 d! _（11）输出结果
% d. Z4 O! x) e  P+ a
% l6 A; }% q5 J' k1 n' \' C（12）结束

Jaafar

很好啊！！

liu168ad

感觉不错                                             

happi

谢谢分享，顶了

925274979

谢谢楼主。。。赞

Seawind2012

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

, a7 u2 n# j) q' Z% LThank you for your attention and review!

darker50

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