@2009 Fall, Computer Aided Ship Design

(1)

2009 Fall, Computer Aided Ship Design – Part1 Optimal Ship Design

@ SDAL

Advanced Ship Design Automation Lab.

http://asdal.snu.ac.kr Seoul

National Univ.

Naval Architecture & Ocean Enginee ring

@ SDAL

2009 Fall, Computer Aided Ship Design – Part1.Optimal Ship Design

Ch.2 Unconstrained optimization method 2.2 Golden Section Search method

(one dimensional search method)

- Ch.2 Unconstrained Optimization Method

(2)

@ SDAL

2.2 Golden Section Search method

- 최소값이 위치하는 구갂 탐색 (1/2)

 최소값이 위치하는 구갂 탐색

 황금 분핛법은 최소값이 위치하는 초기 구갂을 알고 시작해야 핚다.

 과 에서의 함수값 과 를 계산하여 이

보다 작으면 이동량을 의 증가치를 택핚다.

즉, 증분이 이전 증가의 1.618배이다. (Fibonacci sequence)

 0

    f ( 0 ) f (  ) f (  ) )

0 (

f 1 . 618 

f(  )



0 5.236

2 4…

16.326

9.472

3

 q = 0

2.618

1



 

 0 ;

₀

q

...

, 2 , 1 , 0

, ) 618 . 1 (

0



 



q

j

q 

... 

) 618 . 1 ( 326

. 16 )

618 . 1 ( 472 . 9

; 4

4

0 4

4









j

q     

j









³

0 3

3

5 . 236 ( 1 . 618 ) 9 . 472 ( 1 . 618 )

; 3

j

q     

j









²

0

2

2 . 618 1 . 618 ( 1 . 618 ) 5 . 236 ( 1 . 618 )

; 2

j

q     

j









¹

0

1

1 . 618 2 . 618 ( 1 . 618 )

; 1

j

q     

j

2/51

(3)

@ SDAL

 에서의 함수값이 와 에서의 값보다 작다면,

최소점은 두 구갂, 즉 와 사이에 있다.

 최소점이 졲재하는 구갂의 상핚과 하핚은

2.2 Golden Section Search method

- 최소값이 위치하는 구갂 탐색 (2/2)

 1

 q  _q _ ₂  _q

) ( )

( ), (

)

( _q ₁ f _q ₂ f _q ₁ f _q

f  _   _  _  

 q  _q _ ₂



 ^











 ²

0 2

0 ) 618 . 1 ( ,

) 618 . 1 (

q

j

j q

l q

j

j q

u     



상한 하한

 _q-2  _q-1  _q

f( 

)



0 … 16.326

2.618

 _q-2

5.236

 _q-1

9.472

 _q

= = =

f( 

)



상한

( 

_u

)

하한

( 

_l

)

최소값이 존재하는 구간 최소값이 존재하는 구간



 ₀

…

1.0 1.618

1.0:1.618 = 0.382:0.618

( 

_a

)

1 1

0 , (1.618)

q

j

a q

j

  _ ^ 



  

3/51

(4)

@ SDAL

2.2 Golden Section Search method

- Fibonacci sequence

Fibonacci sequence

정의:

F ₀  0; F ₁  1; F _n  F _n _ ₁  F _n _ ₂ , n  2, 3,

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

 ¹  ¹ ⁵

, 1.6180339887

5 2

n n

F n  

   

  

일반항:

 

¹

1 1

lim lim 1

1

n n n

n n

n

F F

 



^



^

 



  

 

 

1 1 1

1

1 lim

1

n n

n n n n

n

 



 





 





 

  

 

¹

1

1 1 lim

1 1

n

n n

  





 

  

   

 

   

  

 

1  1



   

 

 





1 lim ⁿ ,

n n

F

F 

 



특성:

1 1 

   

4/51

(5)

@ SDAL

(1 -  )I ^(k) =(1/3)I ^(k)

 I ^(k) =(2/3)I ^(k)



_b

I ^(k)



_l



_u

(a)

2.2 Golden Section Search method

- 최소값이 위치하는 구갂의 세분화

 최소값이 위치하는 구갂의 세분화

 최소값이 위치하는 구갂 I

^(k) 를  : 1-  로 내분하는 점을 양끝으 로부터 각각 구핚다.

 구핚 점들에서의 함수값을 비교하여 구갂을 세분화핚다.

 아래 그림과 같이 양끝 점에서 대칭으로 위치핚 두 점으로부터 같은

갂격

 I

^(k)만큼 떨어짂

점



_a 와



_b 를 잡는다.

 그 점에서의 함수값을 계산하여 큰 쪽의 구갂을 버리고, 남은 구갂을

새로운 구갂으로 정핚다.

(1 -  )I ^(k) =(1/3)I ^(k)  I ^(k) =(2/3)I ^(k)



_a

<  = 2/3일 경우의 예>

f(

_a) < f(_b)라고 가정하면

최소값이 존재하는 구간은

다음과 같이 변경됨

 _q-2  _q

f( 

) 최소값이 존재하는 구간

 ⁼ _l  ⁼ _u

이 구간을 반복적으로

세분화함

I ^(k+1) =  I ^(k) =(2/3)I ^(k)



_l



(b) 

_u



 I ^(k+1) (1 -  )I ^(k+1)



_b





_a





_l

 

_a

 

_b

 

_u

 

최소값이 존재하는 구간이 변경될 때마다 f(_a), f(_b)에서의 함수값을 새로 구해야 함

<문제 제기>

이전 구간에서의 함수값을 활용할 수 없을까?

5/51

(6)

@ SDAL

2.2 Golden Section Search method

- 최소값이 위치하는 구갂의 세분화

f(

_a) < f(_b)라고 가정하면

최소값이 존재하는 구간은

다음과 같이 변경됨

 I ^(k+1)

(1 -



)I^(k+1)

 _b 

(1 -  )I ^(k)  I

^(k)

 _a

(1 -



)I^(k)

 I

^(k)

I

^(k)

 _l  _u

(a)

I ^(k+1) =  I ^(k)

 _l   _u 

(b)

0 )

1 (

⁽ ⁾

)

(

  

  I

^k

 I

^k



 최소값이 위치하는 구간의 세분화

 최소값이 위치하는 구간 I

^(k)

를

 : 1- 

로 내분하는 점을 양끝으로부터 각각 구한다.

1. f(

_a)를 다음 구간 I^(k+1)

에서 사용하려 함

2. 

_a

가 I

^(k+1)

구간의

_a

 혹은 

_b

 와 일치 하도록  를 결정



_a



a



 I

^(k+1) (1 -



)I^(k+1)

 _a 

) 1 ( )

(

( 1 )

) 1

(   I

^k

   I

^k^

) ( )

(

( 1 )

) 1

(   I

^k

    I

^k

) ( )

(k k

I I  

3-1. 

_a

가 

_a

 와 일치한다고 가정



=1이므로 우리가 원하는 값이 아님

3-2. 

_a

가 

_b

 와 일치한다고 가정 

_a

 

_b



) 1 ( )

)

(

1 (   I

^k

  I

^k^

) ( )

)

(

1 (   I

^k

     I

^k

0

2

   1 



618 . 1 , 618 .

0 

  ₀ _. ₆₁₈

 _b

6/51

(7)

@ SDAL

2.2 Golden Section Search method

- 최소값이 위치하는 구갂의 세분화

f(

_a) > f(_b)라고 가정하면

최소값이 존재하는 구간은

다음과 같이 변경됨

 I ^(k+1)

(1 -



)I^(k+1)

 _b 

(1 -  )I ^(k)  I

^(k)

(1 -



)I^(k)

 I

^(k)

 _b

I ^(k+1) =  I ^(k)

 _l   _u 

(b)

0 )

1 (

⁽ ⁾

)

(

  

  I

^k

 I

^k



1. f(

_b)를 다음 구간 I^(k+1)

에서 사용하려 함

2. 

_b

가 I

^(k+1)

구간의

_a

 혹은 

_b

 와 일치 하도록  를 결정



_b



b



 I

^(k+1) (1 -



)I^(k+1)

 _a 

) 1 ( )

(

( 1 )

) 1

(   I

^k

   I

^k^

) ( )

(

( 1 )

) 1

(   I

^k

    I

^k

) ( )

(k k

I I  

3-1. 

_b

가 

_b

 와 일치한다고 가정



=1이므로 우리가 원하는 값이 아님

3-2. 

_b

가 

_a

 와 일치한다고 가정 

_b

 

_a



) 1 ( )

)

(

1 (   I

^k

  I

^k^

) ( )

)

(

1 (   I

^k

     I

^k

0

2

   1 



618 . 1 , 618 .

0 

  ₀ _. ₆₁₈

I

^(k)

 _l  _u

(a)  _a

 최소값이 위치하는 구간의 세분화

 최소값이 위치하는 구간 I

^(k)

를

 : 1- 

로 내분하는 점을 양끝으로부터 각각 구한다.

7/51

(8)

@ SDAL

2.2 Golden Section Search method

- 황금분핛법 알고리즘 요약 (1/3)

 단계 1 : 최소점이 졲재하는 구갂 탐색

에서 미소의 이동량 를 선정하고

을 만족하는 를 정하고, 다음의 식으로 상핚과 하핚을 결정핚다.

여기서, 갂격 을 정핚다.

 단계 2 : 와 를 계산핚다. 이 때, 이고 이다.

 단계 3 : 와 를 비교하여 그 결과에 따라 단계 4, 5, 6 으로 갂다.

) ( )

( ), (

)

( _q ₁ f _q ₂ f _q ₁ f _q

f  _   _  _  

q



 ^











 ²

0 2

0 ) 618 . 1 ( ,

) 618 . 1 (

q

j

j q

l q

j

j q

u     



l

I   u   )

( _a

f  f (  _b )  _a   _l  0 . 382 I

l I

b    0 . 618



 

) ( _a

f  f (  _b )

(1 -  )I

^(k)



I^(k)



_a

(1 -  )I

^(k)



I^(k)



_b I^(k)



_l



_u

8/51

(9)

@ SDAL

2.2 Golden Section Search method

- 황금분핛법 알고리즘 요약 (2/3)

 단계 4 : 이면, 최적점 는 과 사이에 있다.

세분화된 구갂의 새로운 핚계는 이고 이다.

또핚 이다. 에서 를 계산 하고 단계 7로 갂다.

 단계 5 : 이면, 최적점 는 과 사이에 있다.

세분화된 구갂의 새로운 핚계는 이고 이다.

또핚 이다. 에서 를 계산하 고 단계 7로 갂다.

) ( )

( _a f _b

f     ^*  _l  _b

l

l 

 '   _u '   _b

a

b 

 '   _a '   _l '  0 . 382 (  _u '   _l ' ) f (  _a ' )

) ( )

( _a f _b

f     ^*

a

l 

 '   _u '   _u

b

a 

 '   _b '   _l '  0 . 618 (  _u '   _l ' ) f (  _b ' )

 a  _u

 I

^(k+1)

(1 -  )I

^(k+1)



_b



(1 -  )I

^(k)

 I

^(k)



_a

(1 -  )I

^(k)

 I

^(k)



_b

I

^(k)



_l



_u

I

^(k+1)

=  I

^(k)



_l

 

_u



 I

^(k+1)

(1 -  )I

^(k+1)



_a



9/51

(10)

@ SDAL

2.2 Golden Section Search method

- 황금분핛법 알고리즘 요약 (3/3)

 단계 6 : 이면, 라 두고 단계 7로 갂다.

 단계 7 : 만일 새로운 세분화된 구갂 이 충분히 작아서

수렴 기준을 만족하면(즉, ), 라 두고 최적화 과정을 마친다. 그렇지 않으면, 의 Prime( ) 부호 를 삭제하고 단계 3으로 돌아갂다.

) ( )

( _a f _b

f     _l   _a ,  _u   _b

) ' '

'

( I   _u   _l



 '

I  ^*  (  _u '   _l ' ) / 2 ' , ' , ' ,

' _a _b _u

l   

 _'

 I

^(k+1)

(1 -  )I

^(k+1)



_b



(1 -  )I

^(k)

 I

^(k)



_a

(1 -  )I

^(k)

 I

^(k)



_b

I

^(k)



_l



_u

I

^(k+1)

=  I

^(k)



_l

 

_u



 I

^(k+1)

(1 -  )I

^(k+1)



_a



10/51

(11)

@ SDAL

Golden Section Search method Program Guide (1)

1단계 : 최소값이 존재하는 구간 찾기

f( 

)

0  2.618 5.236 9.472

4 2

1 q = 0 …

16.326

3  ⁼ _l  ⁼ _a  ⁼ _u

최소값이 존재하는 구간

2단계 : 과 를 계산

(단, )

) ( _a

f  f (  _b )

I

I _a _l

l

b    0 . 618 ,     0 . 382



I

 _l  _a  _u _

f( 

)

상한 하한

 _b

0.618I 0.382I

//Input : 초기 위치(initial_x), 증분값 (delta)

//output : 최소값이 존재하는 구간의 x좌표 (x[0],x[1],x[2]

**void findMinValueExistSection(double initial_x, double delta, double *x)** {

//초기값에서 1.618δ배씩 증가시키면서 최소 구간을 탐색함 //x[1]보다 x[2]가 클 때 종료 시킴

}

11/51

(12)

@ SDAL

Golden Section Search method Programming Guide (2)

3단계 : 과 f (  _a ) f (  _b ) 를 비교

) ( )

( _a f _b

f   

①

) ( )

( _a f _b

f   

②

) ( )

( _a f _b

f  ^ 

③

라 두고 단계 4로 간다.

b u

a

l   

  , 

I

 _l  _a  _u _

f( 

)

상한 하한

 _b

0.618I 0.382I

4단계 : 구간 ( I '   _u '   _l ' ) 의 길이가 Tolerance보다 작으면 종료한다. 아닐 경우 2단계로 돌아간다.

최적점 는 과 사이에 있다.

세분화된 구간의 새로운 한계는 이고 이다.

또한 이다. 에서 를 계산하고 단계 4로 간다.



*



_l



_b

l

l 

 ' 

b

u 

 ' 

a

b 

 ' 

) ' ' ( 382 . 0 '

' _l _u _l

a   

    f (  _a ' )

최적점 는 과 사이에 있다.

세분화된 구간의 새로운 한계는 이고 이다. 또한 이다.

에서 를 계산하고 단계 4로 간다.



*



_a



_u

b

a 

 '   _u '   _u

a

l 

 ' 

) ' ' ( 618 . 0 '

' _l _u _l

b   

    f (  _b ' )

12/51

(13)

@ SDAL

Golden Section Search method Programming Guide (3)

// [Input]

// x[0]: 최소값이 졲재하는 영역의 하핚 // x[2]: 최소값이 졲재하는 영역의 상핚

// x[1]: x[0] < x[1] < x[2]인 동시에 f(x[0]) > f(x[1]) and f(x[2]) > f(x[1])인 점 // [Output]

// xmin: f를 최소로 하는 점과 이 점에서의 목적 함수값

double GoldenSectionSearch(double *x, double (*f)(double), double *xmin) {

double TOLERANCE = 1.0e-6;

double f1, f2, a0, a1, a2, a3;

a0 = x[0]; a3 = x[2];

if (fabs(x[2] – x[1]) > fabs(x[1] - x[0])) {

a1 = x[1]; a2 = x[1] + (1.0 - 0.618) * (x[2] - x[1]); } else { a2 = x[1]; a1 = x[1] - (1.0 - 0.618) * (x[1] - x[0]); } f1 = (*f)(a1); f2 = (*f)(a2);

while (fabs(a3 - a0) > TOLERANCE ) {

if (f2 < f1) { a0 = a1; a1 = a2; a2 = 0.618 * a1 + (1.0 - 0.618) * a3;

f1 = f2; f2 = (*f)(a2); }

else { a3 = a2; a2 = a1; a1 = 0.618 * a2 + (1.0 - 0.618) * a0;

f2 = f1; f1 = (*f)(a1); }

}

if (f1 < f2) { *xmin = a1; return f1; }

else { *xmin = a2; return f2; }

}

13/51

(14)

@ SDAL

Golden Section Search method Programming Guide (4)

#include <stdio.h>

#include <math.h>

double f1(double x);

double f2(double

x);

void FindSection(double

x_start, double x_delta, double **(*ObjFunc)(double),**

double

*x);

double GoldenSectionSearch(double *x, double

**(*f)(double), double** *xmin);

int main() {

double

init_x = 0;

double

delta = 1;

double

*x = new double [3];

double

*xmin = 0;

double

f_min;

//f1

FindSection(init_x,delta,f1,x);

f_min = GoldenSectionSearch(x,f1,xmin);

//f2

f_min = GoldenSectionSearch(x,f2,xmin);

//f3

f_min = GoldenSectionSearch(x,f3,xmin);

return 0;

}

//f(x)=x^2

double f1(double x)

{

**return x*x;**

}

//f(x)=sin x

double f2(double x)

{

return sin(x);

}

//f(x)=x^3-x^2+x-1

x) {

return pow(x,3) - pow(x,2) + x - 1;

}

14/51

(15)

@ SDAL

Expansion of Golden Section Search method

- 목적 함수가 다변수 함수일 때 탐색 방향이 주어질 경우

목적 함수 식 탐색 방향 시작 위치

1변수 함수 double (*f)(double x) 하나의 변수만 입력

1변수 함수이므로 탐색 방향은 이미

주어져 있음

double x_start

다변수 함수 double (*f)(double *x, int n) 여러 개의 변수를 입력 받고, 변수의 개수도 입력

탐색 방향을 Vector 형태로 주어야 함

double *x_start

double f(double

x);

void FindSection(double

x_start, double x_delta, double (*f)(double), double *x);

double **GoldenSectionSearch(double *section, double**

(*f)(double), double *xmin);

double f(double

*x, int n);

void **FindSection(double x_start, double x_delta, double**

(*f)(double*, int), double **x);

double GoldenSectionSearch(double

**section, double (*f)(double*, int), double *xmin);

15/51

(16)

@ SDAL

Unconstrained optimization problem

 황금분핛법을 이용하여 다음 2변수 함수의 최소점을 구하시오. 단, 시작 점 x ⁽⁰⁾ = (0, 0), convergence tolerance  = 10 ^-6 , 탐색 방향은 (1.0, - 1.5)이다.

2 2 2

1 2

1 , ) 2 2

( x x x x x x x x

f     

Minimize

 미지수 2개인 최적화 문제

4 2 0 2 4

4

2

0

2

4

4 2

0 2

4

0 50 100

4

2

0

2

4

f (x

₁, x₂)

x

₂

x

₁

x ₁ x ₂

- Ch.2 Unconstrained Optimization Method ^16/51

(17)

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.2 Unconstrained optimization method 2.3 Direct Search Method

(직접 탐사법)

Hooke & Jeeves Direct Search method Nelder & Mead Simplex method

(18)

@ SDAL

 기준점에서의 Local Pattern Search와 최적해 방향으로 가속화하 는 Global Pattern Move를 이용해 최적해를 찾는 방법

b

1

b

2 2

t

0

3

t

0

b

3

b

4 ⁴ ⁵

0

b

t 

x

1

x

2

5

t

0

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method

7 Global Pattern Move

Local Pattern Search

기준점

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

18/51

(19)

@ SDAL

2.3 Direct Search Method

- Example of Hooke & Jeeves Direct Search Method (1/5)

x

1

x

2

b

1

b

2 2

t

0

1. „Local Pattern Search‟ at point b ¹

•x ₁ 방향 탐색

목적 함수 개선이 없음  x ₁ 방향 이동 없음

•x ₂ 방향 탐색

목적 함수 개선이 있음  +x ₂ 방향 이동

•최종 이동 후 base point b ² 정의

2. „Global Pattern Move‟ at point b ²

•b

² 에서 b ¹ 을 대칭시켜 임시점 t ₀ ² 를 구함

•t ₀ ² 에서 목적 함수 값이 b ² 보다

개선되었으므로 t ₀ ² 에서 Local Pattern Search 수행

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

19/51

(20)

@ SDAL

2.3 Direct Search Method

- Example of Hooke & Jeeves Direct Search Method (2/5)

x

1

x

2

b

1

b

2 2

t

0

3

t

0

b

3

3. „Local Pattern Search‟ at point t ₀ ²

•x ₁ 방향 탐색

목적 함수 개선이 있음  +x ₁ 방향 이동

•x ₂ 방향 탐색

목적 함수 개선이 있음  +x ₂ 방향 이동

•최종 이동 후 base point b ³ 정의

4. „Global Pattern Move‟ at point b ³

•b

³ 에서 b ² 을 대칭시켜 임시점 t ₀ ³ 를 구함

•t ₀ ³ 에서 목적 함수 값이 b ³ 보다 개선되지 않았으므로 b ³ 에서 Local Pattern

Search 수행

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

20/51

(21)

@ SDAL

2.3 Direct Search Method

- Example of Hooke & Jeeves Direct Search Method (3/5)

x

1

x

2

b

1

b

2 2

t

0

3

t

0

b

3

b

4

t

⁰⁴

5. „Local Pattern Search‟ at point b ³

•x ₁ 방향 탐색

목적 함수 개선이 있음  +x ₁ 방향 이동

•x ₂ 방향 탐색

목적 함수 개선이 없음  x ₂ 방향 이동 없음

•최종 이동 후 base point b ⁴ 정의

6. „Global Pattern Move‟ at point b ⁴

•b

⁴ 에서 b ³ 을 대칭시켜 임시점 t ₀ ⁴ 를 구함

•t ₀ ⁴ 에서 목적 함수 값이 b ⁴ 보다

개선되었으므로 t ₀ ⁴ 에서 Local Pattern Search 수행

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

21/51

(22)

@ SDAL

2.3 Direct Search Method

- Example of Hooke & Jeeves Direct Search Method (4/5)

x

1

x

2

b

1

b

2 2

t

0

3

t

0

b

3

b

4

t

⁰⁴

7. „Local Pattern Search‟ at point t ₀ ⁴

•x ₁ 방향 탐색

목적 함수 개선이 없음  x ₁ 방향 이동 없음

•x ₂ 방향 탐색

목적 함수 개선이 없음  x ₂ 방향 이동 없음

•목적 함수의 개선이 없으므로 현재 위치를 base point b ⁵ 로 정의

8. „Global Pattern Move‟ at point b ⁵

•b

⁵ 에서 b ⁴ 을 대칭시켜 임시점 t ₀ ⁵ 를 구함

•t ₀ ⁵ 에서 목적 함수 값이 b ⁵ 보다 개선되지 않으므로, b ⁵ 에서 Local Pattern Search 수행

 b

5

t

⁵0

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

22/51

(23)

@ SDAL

2.3 Direct Search Method

- Example of Hooke & Jeeves Direct Search Method (5/5)

x

1

x

2

b

1

b

2 2

t

0

3

t

0

b

3

b

4

t

⁰⁴

9. „Local Pattern Search‟ at point b ⁵

•x ₁ 방향 탐색

목적 함수 개선이 없음  x ₁ 방향 이동 없음

•x ₂ 방향 탐색

목적 함수 개선이 없음  x ₂ 방향 이동 없음

•목적 함수의 개선이 없으므로 현재 위치를 base point b ⁶ 로 정의

•b

⁵ = b ⁶ 이므로 step size를 ½ 로 줄이고 Local Pattern Search 수행

 b

5

t

⁵0

2. Global Pattern Move 3. Local Pattern Search

1. Base Point가 계산 됨

 b

6

23/51

(24)

@ SDAL

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method : Local Pattern Search rule (1/2)

① x

_i

양의 방향 탐색

- 이동 후의 점 에서

함수값이 더 크다면

Local Pattern Search의 일반적 규칙

함수값이 더 작다면

- x_i

양의 방향으로 Step size만큼 탐색 점을

이동시킨 후 함수값을 비교한다

b ^k

- 이동 전의 점으로 돌아와

x

_i 음의 방향으로 탐색을 한다.

b ^k F

- 이동 후의 점에서

x

_i+1방향으로 탐색을 시작한다.

b ^k S

② x

_i

음의 방향 탐색

- x_i

음의 방향으로 Step size만큼 탐색 점을 이동시킨 후 함수값을 비교한다

(x_i양의 방향으로 탐색이 실패할 경우에만

음의 방향으로 탐색을 실시한다.)

b ^k F

함수값이 더 크다면

함수값이 더 작다면

- 이동 전의 점으로 돌아와

x

_i+1

방향으로 탐색을 시작 한다.

b ^k F

- 이동 후의 점에서

x

_i+1

방향으로 탐색을 시작 한다.

b ^k F

F

S

- i를 1부터 변수의 개수 n까지 증가시키면서 탐색한다.

- n번째 변수까지 탐색을 마치면 그 점을 새로운 Base Point b

^k+1로 정의한다.

(F: Fail, S: Success)

24/51

(25)

@ SDAL

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method : Local Pattern Search rule (2/2)

b ^k

 Local Pattern Search

(F: Fail, S: Success)

F F

S

b ^k S

S <Case 3>

b ^k

F F

b ^k Step/2

b ^k+1 b ^k+1

b1

b2 2

t0

3

t0

b3

b4 ⁴ ⁵

0 b

t



x

1

x

2

5

t0

⁷

Global Pattern Move

Local Pattern Search

기준점

Case 1 Case 2

Case 3

* 위 첨자 k는 step 번호를 의미 한다.

25/51

(26)

@ SDAL

2개의 좌표 축(x ₁ , x ₂ )을 가진 경우의 Local Pattern Search 예시

(x ₁

방향 탐색)

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method Algorithm summary (1) 1) Local Pattern Search (총 n개의 좌표 축을 가짂 경우에 대하여)

b

1

1. 기준점(Base Point) b¹에서의 함수 f 의 값을 계산한다.

2. 점 b¹±δ₁ 에서의 함수 f 의 값을 계산한다. 여기서 δ₁은 Input Step Size이며 δ₁ = [δ₁, 0, 0, …, 0]^T로 표현되는 n개의 원소를 가지는 벡터이다. 함수 값의 개선이 있는 점을

t ₁ ¹

이라 놓고 이로부터 계속 탐사를 진행한다.

3. 점

t ₁ ¹

±δ₂ 에서의 함수 f 의 값을 계산한다. 여기서 δ₂는 역시 Input Step Size이며 δ₂ = [0, δ₂, 0, …, 0]^T 이다.

그리고 함수 값의 개선이 있는 점을

t ₂ ¹

이라 놓는다.

x

1

x

2

1  t 1

2개의 좌표 축(x ₁ , x ₂ )을 가진 경우의 Local Pattern Search 예시

(x ₂

방향 탐색)

b

1 x

1

x

2

1  t 1 1

t 2

26/51

(27)

@ SDAL

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method Algorithm summary (2) 1) Local Pattern Search (총 n개의 좌표 축을 가진 경우에 대하여)

4. 나머지 좌표 축에 대해 위와 같은 Local Pattern Search 과정을 수행하고 새로운 기준점(New Base Point)을 설정한다. 즉, Local Pattern Search 과정이 끝나면 새로운 기준점이 선정된다. (선정된 새로운 기준점 b² = t_n¹)

5. 새로운 기준점과 그 직전 기준점의 방향으로 Global Pattern Move를 수행한다.

27/51

(28)

@ SDAL

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method Algorithm summary (3)

2) Global Pattern Move

1. Local Pattern Search에 의해 얻어진 2개의 기준점을 연결하는 방향을 따라 제일 마지막 기준점에서 이 두 기준점 사이의 거리만큼 떨어져 있는 점을 임시

기준점(Temporary Point)로 설정하고(“Global Pattern Move”), 임시점에서의 함수

f 의 값을 계산한다. Global Pattern Move에 의해 선정된 임시 기준점은 다음과 같다.

k k

k

k b b b b b

t ₀ ^ ¹   2 ( ^ ¹  )  2 ^ ¹ 

b 2 2

t 0

3 t 0

b 3

b 4 2개의 좌표 축을 가진 경우의

Global Pattern Move의 예시

임시 기준점에서의 함수 값이

개선되지 않은 경우

2. 만일 이 임시점에서 함수 f 의 값이 개선된다면

이 점에서부터 다시

Local Pattern Search를 수행한다. 함수 f 의 값이 개선되지 않는다면 그 직전의 기준점으로 돌아가

Local Pattern Search를 수행한다.

28/51

(29)

@ SDAL

2.3 Direct Search Method

- Hooke & Jeeves Direct Search Method Algorithm summary (4)

b 2 2

t 0

3 t 0

b 3

b 4 2개의 좌표 축을 가진 경우의

Global Pattern Move의 예시

임시 기준점에서의 함수 값이

개선되지 않은 경우

3) Closing Conditions

1. 만일 Local Pattern Search를 수행한 후에도 b^k+1 = b^k 이 되어 어떠한 개선이 이루어지지 않는다면 모든 δ_i를 δ_i/2로 바꾸어 위 과정을 반복한다.

2. 만일 모든 δ_i 가 ε_i보다 작으면 탐사 과정을 마친다.

29/51

(30)

@ SDAL

Unconstrained optimization problem

 어느 선박의 상대적 건조비를 L/B와 C_B의 함수로 다음 그림과 같이 표시핛 수 있 다고 하면 건조비가 최소가 되는 L/B와 C_B의 값을 Hooke & Jeeves의 탐사법과 Nelder & Mead의 Simplex 방법을 이용하여 최적점을 구하고 그 과정을 그림에 각각 표시하시오.

 Hooke & Jeeves의 탐사법

 출발점: L/B = 1, C

_B = 0.1

 출발점의 step size: (L/B) = 0.5, (C

_B ) = 0.1

 Nelder & Mead의 Simplex 방법

 출발 모서리점: (L/B, CB) = (1, 0.1), (1.5, 0.1), (1.5, 0.2)

 중지 기준: 0.01

C _B

L/B 0.1

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0

목적 함수의 contour line(f = const.)

미지수 2개인 최적화 문제 

- Ch.2 Unconstrained Optimization Method ^30/51

@2009 Fall, Computer Aided Ship Design

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.2 Unconstrained optimization method 2.2 Golden Section Search method

(one dimensional search method)

@ SDAL

2.2 Golden Section Search method

- 최소값이 위치하는 구갂 탐색 (1/2)

 최소값이 위치하는 구갂 탐색

 0

    f ( 0 ) f (  ) f (  ) )

0 (

f 1 . 618 

f(  )



 q = 0



 

 0 ;

q

...

, 2 , 1 , 0

, ) 618 . 1 (





 



q

q

j

j

q 

... 

) 618 . 1 ( 326

. 16 )

618 . 1 ( 472 . 9

; 4













q     













5 . 236 ( 1 . 618 ) 9 . 472 ( 1 . 618 )

; 3

q     













2 . 618 1 . 618 ( 1 . 618 ) 5 . 236 ( 1 . 618 )

; 2

q     













1 . 618 2 . 618 ( 1 . 618 )

; 1

q     

@ SDAL

2.2 Golden Section Search method

- 최소값이 위치하는 구갂 탐색 (2/2)

 1

 q  q  2  q

) ( )

( ), (

)

 q  _q _ ₂  _q

( _q ₁ f _q ₂ f _q ₁ f _q

f  _   _  _  

 q  _q _ ₂

 ^

 ²

 _q-2  _q-1  _q

 _q-2

 _q-1

 _q

 ₀

  _ ^ 

F ₀  0; F ₁  1; F _n  F _n _ ₁  F _n _ ₂ , n  2, 3,

 ¹  ¹ ⁵