局部搜索算法

Seawind2012

全局搜索和局部搜索.
; f4 n" m. S5 q( g& n4 b$ Y目前使用较普遍的、有影响的
全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS算法;
- i2 L. y4 Y+ T0 n& w局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类.
接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法.
* Z1 q4 K3 o5 f此外,接触问题的并行计算也是不可忽视的研究内容

6 r" J; e% `1 K! s4 G5 e5 u局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。
( J3 i4 F" |, q9 {
7 Y, B4 b4 L0 M% J! ~, c局部搜索算法是从爬山法改进而来的。
9 K% `6 G, c/ N$ G8 m; c* r. Q1 y
爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。
$ P! a4 i0 `0 p
局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
! S% _! n3 O, \, a+ M! ^+ D- f# ^
现实问题中，f在D上往往有多个局部的极值点。一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。考虑归一化问题，使得邻域内所有点被选中的概率和为1。
* u9 r9 ]7 _( i# T* f- e, o
' f6 L( ^  {6 Z: C4 m5 |一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图
; c; X9 X5 S& ]* W" A7 K
0 ]: _  [6 }, @# \爬山算法
4 {; K3 b5 o3 a% V: [
1, n := s;
0 v# a, R% {9 y# }2 v
  T6 ~5 o+ m8 H! |2 Y9 V! @2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS);

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

4, IF h(n)<h(nextn) THEN EXIT(Fail);

5, n:=nextn;
1 u+ B9 ~' G  x! R" ?
6, GO LOOP;

该算法在单峰的条件下，必能达到山顶。
) {3 g  J2 t) ?& ~% b6 M
局部搜索算法

6 z- ]. M/ _0 t8 u（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);
& N4 S  R5 V0 r+ X
     //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等
% k; N1 ]" S( q
, \+ }; [, p3 g, z3 j" [0 s（3）Begin

; _7 [2 x' o7 k. T$ r（4）选择P的一个子集P‘，xn为P’的最优解

: u* e9 |% p! K$ f3 h0 j  R        // P’可根据问题特点，选择适当大小的子集。可按概率选择
& f  D4 ^1 a4 G* X7 z
（5）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转(2)

( j; ~- ]( g3 e" o0 Y5 F$ ~       // 重新计算P，f(x)为指标函数

（6）否则P=P-P‘，转(2)
4 n& m' f1 B' I3 r9 p' z
, F# T" z0 j# S0 p. F; ?7 l/ r9 C* I5 V（7）End

（8）输出计算结果
' j% A* r) @& R( O8 ~
3 s" V# D; m" F% C: ^1 Y（9）结束
: U$ \4 H! h7 i" i4 Q! }
- U3 d+ p6 Z  j) R: c3 N+ j( o
' L* M0 k/ A1 X- d" s4 g/ N& |. Z局部搜索算法2——可变步长
  @" O0 \$ T, X3 |! Q1 ]
  u9 y2 K# z6 N/ {1 P' j

) Q# O- u6 {+ J（1）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);

* X/ T% [/ ~4 Y2 [0 ^  t     //D是问题的定义域，xb用于记录到目标位置的最优解，P为xb的邻域。

（2）如果不满足结束条件，则： //结束条件为循环次数或P为空等

1 d7 ^, b( J$ x" ^: d（3）Begin

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

5 P4 W& k" B. p6 H2 z（5）如果f(xn)<f(xb)，则xb=xn
( h$ f* X1 e# i6 B9 N
（6）按某种策略改变步长，计算P=N(xb)，转（2） 继续
9 N" a, L9 W6 ?
（7）否则P=P-P‘，转（2）
5 w+ q2 P5 E/ g! [% L, a& w
/ a7 b: ~5 f; V4 |3 Z（8）End

（9）输出计算结果

（10）结束

0 [0 A, c0 ^* r; p
局部搜索算法3——多次起始点
3 u5 ^, l) q* h5 p& z
+ p3 t! Z+ c+ z9 u$ \. H& |1 H8 Z
, j2 `* b# m4 ~+ Z8 f1 _& K& D
+ R# |- S3 W9 j  B（1）k=0

（2）随机选择一个初始的可能解x0属于D，xb=x0,P=N(xb);
2 S+ j5 @9 f) [  L  t  c  @, Z
; G9 {/ @0 Q2 o5 [# ^! ?) e（3）如果不满足结束条件，则：

$ F8 ?4 A( u; }2 `) r! |+ e（4）Begin
4 T. W  }9 B% H1 r! }1 l0 h0 _
+ F7 U2 i+ ^2 E) V（5）选择P的一个子集P‘，xn为P’的最优解
6 }& {/ \+ m8 I; U
（6）如果f(xn)<f(xb)，则xb=xn，P=N(xb)，转（3）

（7）否则P=P-P‘，转（3）
8 l7 V: e8 j3 i) Z6 p# l
" W0 V3 t0 Z: m8 I* p（8）End

* G7 V- p- s6 |6 \$ n( y（9）k=k+1
  |& K4 H- B- y7 \6 s* X
（10）如果k达到了指定的次数，则从k个结果中选择一个最好的结果，否则转（2）
% p/ o9 b, x9 B
, d9 k! k( I+ i9 n3 A4 j) v- D（11）输出结果
# j) V: e" H% ^# V  O7 ?9 k
8 I( V7 x( Z; D' b（12）结束

darker50

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

Seawind2012

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

Thank you for your attention and review!

925274979

谢谢楼主。。。赞

happi

谢谢分享，顶了

liu168ad

感觉不错                                             

Jaafar

很好啊！！