b
i+1b
i+17
Global Pattern Move
Local Pattern Search
기준점
2.3 2.3 직접 직접 탐사법 탐사법
- - Hooke & Jeeves Hooke & Jeeves 의 의 직접 직접 탐사법의 탐사법의 과정 과정 (1) (1)
1. Initial Local Search : x 1 방향에 대해서는 목적 함수 값의 개선이 없음 . 그런데 x 2 방향에 대해서는 개선이 있음 . 따라서 가 새로운 기준점으로 선정됨
2. 직전의 2개의 기준점
방향으로 , 에서 이 두 점과 같은 거리만큼 떨어져 있는 임시점 를 구함
3. 점에서 함수값의 개선이 이루어졌으므로 이 점으로부터 Local Pattern Search를 수행하여 새로운 기준점 를 구함
4. 직전의 2개의 기준점 방향으로 , 에서 이 두 점과 같은 거리만큼 떨어져 있는 임시점 를 구함
b 2
2 1 , b b
t 20
t 20
b 3 3
2 , b
b t
b 2
b 3
선박기본설계개론
선박기본설계개론 , 2006.3 , 2006.3
NAOE/SNU51
서울대학교
서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기
51/252
2.3 2.3 직접 직접 탐사법 탐사법
- - Hooke & Jeeves Hooke & Jeeves 의 의 직접 직접 탐사법의 탐사법의 과정 과정 (2) (2)
5. 에서 함수 값의 개선이 없음.
따라서 기준점 로 돌아가서 Local Pattern Search를 수행함.
탐색 결과 를 찾음 6. 직전의 2개의 기준점
방향으로 , 에서 이 두 점과 같은 거리만큼 떨어져 있는 임시점 을 구함 . 이 점에서 함수 값이
개선되므로 Local Pattern
Search를 수행하여 를 구함
7. 직전의 2개의 기준점 방향으로 , 에서 이 두 점과 같은
거리만큼 떨어져 있는 임시점 을 구함 . 이 점에서 함수 값의 개선이 없음 . 따라서 기준점 로 돌아가서 Local Pattern Search를 수행함.
그런데 Local Pattern Search 결과 구해진 이 이전의 기준점 와 동일하므로 모든 Step Size 반으로 줄인 후 위의 과정을 반복함
4
3 b
b , b 4
t 40
) ( 40
5 t
b =
5 4 , b
b b 5
t 50
b 6
b 5
t 30
b 3
b 4
b 5
2.3 2.3 직접 직접 탐사법 탐사법
- - Hooke & Jeeves Hooke & Jeeves 의 의 직접 직접 탐사법의 탐사법의 알고리즘 알고리즘 요약 요약 (1) (1)
1) Local Pattern Search
1. 기준점(Base Point) 에서의 함수 f 의 값을 계산한다.
2. 점 에서의 함수 f 의 값을 계산한다. 여기서 은 Input Step Size이며 이다 . 함수 값의 개선이 있는 점을 이라 놓고 이로부터 계속 탐사를 진행한다 .
3. 점 에서의 함수 f 의 값을 계산한다. 여기서 는 역시 Input Step
Size이며 이다 . 그리고 함수 값의 개선이 있는 점을
이라 놓는다 .
4. 나머지 좌표 축에 대해 위와 같은 Local Pattern Search 과정을 수행하고 새로운 기준점(New Base Point)을 설정한다. 즉, Local Pattern Search 과정이 끝나면
새로운 기준점이 선정된다 . 선정된 새로운 기준점 는 이다 .
5. 새로운 기준점과 그 직전 기준점의 방향으로 Global Pattern Move를 수행한다.
b 1 1
1 ± δ
b δ 1
δ 2
] T
0 ,..., 0
, [ 1
1 = δ
δ t 11
2 11 δ t ±
] T
0 ,..., ,
0 [ 2
2 = δ
δ t 12
b 2 b 2 = t 1
n선박기본설계개론
선박기본설계개론 , 2006.3 , 2006.3
NAOE/SNU53
서울대학교
서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기
53/252
2.3 2.3 직접 직접 탐사법 탐사법
- - Hooke & Jeeves Hooke & Jeeves 의 의 직접 직접 탐사법의 탐사법의 알고리즘 알고리즘 요약 요약 (2) (2)
2) Global Pattern Move
1. Local Pattern Search에 의해 얻어진 2개의 기준점을 연결하는 방향을 따라 제일 마지막 기준점에서 이 두 기준점 사이의 거리만큼 떨어져 있는 점을 임시 기준점 (Temporary Point)로 설정하고(“Global Pattern Move”), 임시점에서의 함수 f 의 값을 계산한다. Global Pattern Move에 의해 선정된 임시 기준점은 다음과 같다 .
2. 만일 이 임시점에서 함수 f 의 값이 개선된다면 이 점에서부터 다시 Local
Pattern Search를 수행한다. 만일 함수 f 의 값이 개선되지 않는다면 그 직전의 기준점으로 돌아가 Local Pattern Search를 수행한다.
3) Closing Conditions
1. 만일 Local Pattern Search를 수행한 후에도 이 되어 어떠한 개선이 이루어지지 않는다면 모든 를 로 바꾸어 위 과정을 반복한다 .
2. 만일 모든 가 보다 작으면 탐사 과정을 마친다 .
n n
n n
n
n
b b b b b
t + 1 , 0 = + 2 ( + 1 − ) = 2 + 1 −
n
n
b
b +1 = δ
iδ
i/ 2
δ
iε
iHooke &
Hooke & Jeeves Jeeves 의 의
직접 직접 탐사법 탐사법 (Local Pattern Search) (Local Pattern Search) 의 의 구현 구현 예 예
// [Input] del : 설계점에 대한 이동폭, x : 현재의 설계점, fmin_pre : 이전 설계점에서의 함수값, variables_no : 설계 변수의 수 // [Output] 개선된 설계점과 이 점에서의 목적 함수값
double LocalPatternSearch(double* del, double* x, double fmin_pre, int variables_no) {
double* temp_x = new double[MAX_DV_NUM];
double fmin, temp_function_value;
int i;
fmin = fmin_pre;
for (i = 0; i < variables_no; i++) temp_x[i] = x[i];
for (i = 0; i < variables_no; I++) { temp_x[i] = x[i] + del[i];
temp_function_value = f(temp_x, variables_no);
if (temp_function_value < fmin) {
fmin = temp_function_value;
} else {
del[i] = 0.0 - del[i];
temp_x[i] = x[i] + del[i];
temp_function_value = f(temp_x, variables_no);
if (temp_function_value < fmin) {
fmin = temp_function_value;
}
else temp_x[i] = x[i];
} }
for (i = 0; i < variables_no; i++) { x[i] = temp_x[i];
}
delete[] temp_x;
return fmin;
}
선박기본설계개론
선박기본설계개론 , 2006.3 , 2006.3
NAOE/SNU55
서울대학교
서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기