Title 多点局所探索に基づく大域的最適化アルゴリズム (1) Author(s) 金光, 秀雄 ; 今野, 英明 ; 高橋, 伸幸 Citation 北海道教育大学紀要, 自然科学編, 58(2): 1-10 Issue Date 2008/02 URL

Size: px

Start display at page:

Download "Title 多点局所探索に基づく大域的最適化アルゴリズム (1) Author(s) 金光, 秀雄 ; 今野, 英明 ; 高橋, 伸幸 Citation 北海道教育大学紀要, 自然科学編, 58(2): 1-10 Issue Date 2008/02 URL"

しょうこたもん
5 years ago
Views:

1 Title 多点局所探索に基づく大域的最適化アルゴリズム (1) Author(s) 金光, 秀雄 ; 今野, 英明 ; 高橋, 伸幸 Citation 北海道教育大学紀要, 自然科学編, 58(2): 1-10 Issue Date 2008/02 URL Rights Hokkaido University of Education

2 ABSTRACT We will report on the development of a multi-start local search algorithm. At first, we developed a local search algorithm and tested this algorithm. Next, we investigated and developed a simple multi-start local search algorithm. Finally, we developed and demonstrated multi level single linkage algorithm as an effective multi-start local search algorithms. 1 [8] [4, 7, 20] [14] [5] SA (Simulated Anealing) [13] GA (Genetic Algorithm) [1,2,15] SA GA multi-level single linkage; MLSL)

3 2 2.1 (P G ) Minimize f(x) f(x 1,x 2,,x n ) (P G ) Subject to L i x i U i, (i =0, 1,...,n) f(x) objective function S S S = { x (x 1,x 2,,x n ) L i x i U i } S feasible region x δ>0 B(x,δ) x (B(x,δ) S) \{x }, f(x ) <f(x) (1) x f(x) x 1, x 2,...,x M X I M X = { x 1, x 2,...,x M } (2) I M = { 1, 2,...,M} (3) x i D(x i ) relative size η(x i )=µ(d(x i )) /µ(s), (i =1, 2,...,M) (µ( ) ) Lopt x (0) i x i X S D(x i ) D(x i )={ x x i Lopt(f, S, x (0) i ), x (0) i S } (4) x (0) i Lopt X x i D(x i ) η(x i ) D(x i ) D(x j )=, i j I M D(x 1) D(x 2) D(x M )=S (5) η(x 1)+η(x 2)+ + η(x M )=1 x x { f =min{ f(x 1),f(x 2),...,f(x M ) } x =argmin{ f(x 1),f(x 2),...,f(x M ) } (6) Eval v v Eval; 2. p a 1,a 2,...,a p q b 1,b 2,...,b q A name (b 1,b 2,...,b q ) A name (a 1,a 2,...,a p ) ( ) 3. if then T 1 ;..., T r ; else F 1 ;..., F s ; fi ; then T 1 ;..., T r ; else F 1 ;..., F s ; else F 1 ;..., F s ; 1 fi ; for to do L 1 ;... L t ; od ; 1 do...od ; L 1 ;... L t ; 1 od ; 4. A A j A j A A

4 3 3.1 [9, 21] (P L ) (P L ) Local Minimize f(x) (7) x f x f(x )=0 (8) descent method f x 0 R n x f 1 (f, x ) Lopt d (f,x (0) ) Ld1) x (0) k k 0 Ld2) d (k) Ld3) x (k) Ld4) x (k+1) k k +1 Ld2) Ld2) d (k) BFGS Ld2) d (k) x (k) f(x (k) ) f(x (k) ) R n B (k) R n n d (k) 3.4 for y 0, y T B (k) y > 0. (9) 3.3 Ld3) line search x (k) d (k) f(p (k) + αd (k) ) α α (k) (exact line search) (inexact line search) Armijo x (k) d (k) 0 <ξ<1/2, 0 <τ<1 Armijo α (k) 2 Armijo α (k) LSrch A (x (k), d (k),ξ,τ) LS1) α 0 1 i 0 LS2) ξ Armijo f(x (k) + α i d (k) ) f(x (k) )+ξα i f(x (k) ) T d (k) α (k) α i LS3) LS3) α i+1 τα i i i +1 LS2) 3.4 BFGS f x (0) η (ξ, τ) x f 3 (f, x ) Lopt q (f, x (0),η,ξ,τ) Lq1) H (0) R n n k k 0

5 Lq2) f(x (k) )=0 d (k) d (k) = H (k) f(x (k) ) Lq3) α (k) x (k+1) x (k) + α (k) d (k) α (k) LSrch A (x (k), d (k),ξ,τ) Lq4) H (k) (y (k) ) T s (k) η y (k) s (k) H (k+1) H (k) BFGS H (k+1) ( ) H (k+1) H (k) + 1+ (y(k) ) T H (k) y (k) (s (k) ) T y (k) s (k) (s (k) ) T (s (k) ) T y (k) H(k) y (k) (s (k) ) T + s (k) (H (k) y (k) ) T (s (k) ) T y (k) s (k) = x (k+1) x (k), y (k) = f(x (k+1) ) f(x (k) ). k k +1 Lq2). H (0) H (k) (9) B (k) 3.5 C 1) defc.h: 2) defp.h: 3) util.h: 4) bfgs.c: BFGS 5) gfdif.c: f(x) 6) lsearch.c: 7) prnt.c: 4) 7) [9] FORTRAN C f(x (k) ) f(x (k) ) i f(x(k) ) x i f(x (k) ) f(x(k) + δe i ) f(x (k) ) x i δ (10) e i i 1 0 δ = η =10 4, ξ =10 3, τ =0.5 Rosenbrock f(x) =f(x 1,x 2 ) = 100(x 2 x 2 1) 2 +(1 x 1 ) 2 x 0 =( 1.2, 1) f 0 =24.2 x =(1, 1) f = k (x 1,x 2 ) f(x 1,x 2 ) N fe x 2 k x 1 x 2 f(x 1,x 2 ) N fe "rosenbrk.xy" using 1:2 "../prog/lopt/ort.d" using 2: x 1 1: Rosenbrock

6 4 4.1 Lopt multistart local search method; MSLS N f x 4 1 ( f, x ) MSLS1(f, S, N) M1) N M2) M3) M4) f x M2) f S P η(x ) f x MSLS2 5 2 ( f, x ) MSLS2(f, S, P, η(x )) ML1) N P η(x ) 4.2 f + ML2) N for i =1 to N do ML3) S Rand x (0) i x (0) i Rand(S); ML4) x (0) i Lopt x i fi (fi, x i ) Lopt(f, S, x(0) i ) ML5) Lopt fi, x i f x if fi < f then f fi ; x x i ; fi ; od ; ML6) f x return ( f, x ). N L O(NL) 4.2 P 5 ML2) P N 1 P in P out { P in = η(x ) (11) P out =1 η(x ) N Pout N P N out =(1 η(x )) N (12) N 1 Pin N 1 P out N (12) P N in =1 (1 η(x )) N (13) P N 1 (1 η(x )) N = P N = log(1 P ) log[1 η(x )] (14) [6] N P log(1 P ) N = log[1 η(x (15) )] ML1) N (15)

7 η(x ) P N 2 η(x )= % N 20 η(x )= % N η(x ) 2 η(x ) P η(x ) P η(x ) P η(x ) P MSLS2 C 1) msls2.c: MSLS2 2) randnv.c: ML3 Rand(S) S x i 3) mtrand.c: Mersenne Twister [0, 1) 1 msls2.c randnv.c randnv.c mtrand.c BFGS bfgs.c 3) Mersenne Twister [12] diehard test load test ultimate load test 2 Six Hump Camel Back f(x 1,x 2 )=4x x x 1 x x6 1 4x x x 1 2.3, 1.5 x , 2 x 1, x 2 f f = x 1 =( , ), x 2 =( , ) f(x,y) x x x x 1 2 Six Hump Camel Back f(x,y) P =0.99 η = N =13 f = x =( , ) N fe =

8 MSLS2 3 x "6humpc.xy" using 1:2 "../prog/msls/or.d" using 2:3 "../prog/msls/ors.d" using 2:3 3: Six Hump Camel Back MSLS2 k x 1 x 2 f(x 1,x 2 ) N fe x Six Hump Camel Back MSLS2 3 x (0) x (1) Lopt q Lq2) d (0) = H (0) f(x (0) )(H (0) : ) d (0) Lq3) x (1) x (0) + α (0) d (0) ( α (0) =1) x (1) x (0) d (k) 0 <φ<1 d (k) min{ d (k),φ min 1 i n {U i L i }} φ φ =0.1 1 φ MSLS2 [16] 6( 3( )) ( f, x ) MSLS c (S, f, N ) MC1) N MC2) MC3) MC4) f x Multi Level Single Linckage; MLSL Timmer [19] 1 [10]

9 Rinnooy Kan Timmer [17] [14] k r k r k r k = 1 ( (σ µ(s) Γ 1+ n ) ) 1/n log N (16) π 2 N, σ, µ(s) S, Γ( ) N, [5]: X (γn 1) / (γn X 2) X 0.5., X (γn 1) γn X 2 X +0.5 (17) γ (0<γ<1) γn (16), N (0) = N N (k+1) (k =0, 1,...) N N (k+1) 1 γ (2 X 2 +3 X +2), N N + N (k+1) MLSL S f N γ (0 <γ< 1) σ X F 7 4 MLSL (F, X ) MLSL(S, f, N (0),γ,σ); ML1) X ; F ; k 1; N N (0). ML2) N (k) x i (i =1, 2,...,N (k) ) Rand(S) ML3) γn (k) N r γn (k) ML4) r k (16) f(x j )<f(x i ) x j x i <r k x j x i (i = 1, 2,...,N r ) x X ML5) (17) N (k+1) 1 γ (2 X 2 +3 X +2), N N + N (k+1), k k +1, ML2),, σ 4, 1 [17] 5.2 MLSL mlsl.c C ML2 Rand(S) x i 4.3 randnv.c mtrand.c 3.5 BFGS bfgs.c (1) (3) 2 N (1) =40 γ =0.25 σ =4 (1) Six Hump Camel Back N = 69 5 f = x = ( , ) N fe = 229 MSLS2 N fe = 492 MSLS2 (2) Goldstein and Price

10 f(x) ={(1 + (x 1 + x 2 +1) 2 (19 14x 1 +3x x 2 +6x 1 x 2 +3x 2 2)}{30 + (2x 1 3x 2 ) 2 (18 32x 1 +12x 1 x 1 +48x 2 36x 1 x 2 +27x 2 2)} 2 x 1 2, 2 x x = (0, 1) f = 3 N =56 5 f = x = ( , ) N fe = 334 (3) Branin s RCOS ( f(x) = x π 2 x ) 2 π x ( ) cos(x 1 )+10 8π 5 x 1 10, 0 x 2 15, 3 3 f =5/(4π) N = f = x =( , ) N fe = [14, 20] [5] [14] MLSL [11, 18] [17, 19] Bentley [3] Törn [20] 7

11 [1], Vol.49, No.11, , (2001). [2] :, Vol. J 78- D-II, No.1, , (1995). [3] Bentley, J.L., Weide, A.C. and Yao, A.C.: Optimal expected-time algorithms for closest point problems, ACM Transactions on Mathematical Software, Vol.6, , (1980). [4] Boender, C.G.E., Rinnooy Kan, A.H.G. and Timmer, G.T.: A Stochastic Method for Global Optimization, Mathematical Programming, Vol.22, , (1982). [5] Boender, C.G.E., Rinnooy Kan, A.H.G. and Timmer, G.T.: Beyesian stopping rules for multistart global optimization methods, Mathematical Programming, Vol.37, 59 80, (1987). [6] Brooks, S.H.: A Discussion of Random Methods for Seeking Maxima, Operations Research, Vol.6, , (1958). [7] Dzemyda, G., Šaltenis, V. and Žilinskas, A.: Stochastic and Global Optimization, Kluwer Acad. Publ., Dordrecht, pp.233, (2002). [8] Floudas, C.A.: Deterministic Global Optimization Theory, Methods and Applications, Kluwer A.P., pp.739, (2000). [9] : FORTRAN 77,, pp.480, (1991). [10],, :,, Vol.J79-A, No.11, , (1996). [11] Locatelli, M. and Schoen, F. : Random Linkage: a family of acceptance/rejection algorithms for global optimisation, Mathematical Programming, Vol.85, , (1999). [12] Matsumoto, M. and Nishimura, T. : Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, Vol.8, No.1, 3 30, (1998). [13],,, :, Vol.42, No.4, , (2001). [14] Nemhouser, G.L, Rinnooy Kan, A.H.G. and Todd, M.J. (Eds.): Optimization, Handbooks in Operations Research and Management Science Vol.1, North-Holland, pp.709, (1989). [15], : GA, Vol.15, No.2, , (2000). [16] Rinnooy Kan, A.H.G. and Timmer, G.T. : Stochastic Global Optimization Methods. Part I: Clustering Methods, Mathematical Programming, Vol.39, 27 56, (1987). [17] Rinnooy Kan, A.H.G. and Timmer, G.T. : Stochastic Global Optimization Methods. Part II: Multi Level Methods, Mathematical Programming, Vol.39, 57 78, (1987). [18] Schöen, F. : Random and Quasi-Random Linkage Methods in Global Optimization, Journal of Global Optimization, Vol.13, No.4, , (1998). [19] Timmer, G.T.: Global optimization: A stochastic approach, Ph.D. Dissertation, Econometric Institute, Erasmus University, Rotterdam, Holland, pp.175, (1984). [20] Törn, A. and Žilinskas, A. Global Optimization, Lecture Notes in Compter. Science. 350, Springer-Verlag, p.255, (1989). [21] :,, pp.263, (2006).

第3章非線形計画法の基礎

第3章非線形計画法の基礎 3 February 25, 2009 1 Armijo Wolfe Newton 2 Newton Lagrange Newton 2 SQP 2 1 2.1 ( ) S R n (n N) f (x) : R n x f R x S f (x ) = min x S R n f (x) (nonlinear programming) x 0 S k = 0, 1, 2, h k R n ɛ k