황금분할 탐색

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 기본 원리
- 2.1. 탐색 점 선택
- 2.2. 종료 조건
3. 알고리즘
- 3.1. 반복 알고리즘
- 3.2. 재귀 알고리즘
4. 관련 알고리즘
- 4.1. 피보나치 탐색
- 4.2. 이분법
참조

1. 개요

황금분할 탐색은 단봉 함수의 최소값을 효율적으로 찾는 방법으로, 탐색 구간을 황금비를 이용하여 점진적으로 줄여나간다. 이 알고리즘은 평가된 점의 수에 관계없이 최소값이 두 점으로 정의된 구간 안에 있다는 원리를 기반으로 한다. 탐색 점을 선택할 때 황금비를 활용하여 각 단계에서 탐색 구간의 길이를 일정 비율로 축소하며, 종료 조건에 따라 탐색을 완료한다. 황금분할 탐색은 반복 알고리즘과 재귀 알고리즘으로 구현될 수 있으며, 피보나치 탐색 및 이분법과 같은 관련 알고리즘이 존재한다.

더 읽어볼만한 페이지

황금비 - 비트루비우스적 인간
레오나르도 다 빈치가 그린 비트루비우스적 인간은 인체 비례 연구를 바탕으로 비트루비우스의 건축 이론에 나타난 인체 비례를 시각적으로 구현하여 인체와 우주의 조화를 나타내는 르네상스 시대 예술과 과학 융합의 상징이다.
황금비 - 오각별
오각별은 슐레플리 기호 {5/2}로 표시되는 가장 단순한 별 다각형으로, 황금비와 관련 있으며 고대부터 현대까지 다양한 상징으로 사용된다.
피보나치 수 - 레오나르도 피보나치
레오나르도 피보나치는 힌두-아라비아 숫자 체계를 유럽에 소개하고 피보나치 수열을 제시하여 중세 수학 발전에 기여했으며, 상업 발달을 돕는 《산반서》를 저술하고 황금비와 관련된 피보나치 수열이 다양한 분야에서 활용되도록 했다.
피보나치 수 - 피보나치 힙
피보나치 힙은 최소 힙 속성을 가진 트리들의 집합으로, 각 노드의 차수를 특정 로그 값 이하로 유지하여 효율적인 삽입, 병합, 최소값 검색 연산을 지원하며, 다익스트라 알고리즘과 같은 그래프 알고리즘의 성능 향상에 활용된다.
검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.

황금분할 탐색
개요
유형	수치 최적화 알고리즘
분야	수학, 컴퓨터 과학
발명자	잭 키퍼
최초 개발 연도	1953년
목적
목표	단봉 함수의 극값을 찾음
방법	구간 축소
세부사항
필요한 함수 속성	단봉성
수렴 속도	선형
수렴 비율	황금비 (대략 0.618)
계산 복잡도	각 반복마다 함수 평가 1회
장점	구현 용이 함수가 미분 불가능하거나 잡음이 있는 경우에도 적용 가능
단점	수렴 속도가 느림
활용
응용 분야	매개변수 추정 기계 학습 모델 튜닝 공학 설계 최적화
관련 알고리즘
관련 알고리즘	이분법 피보나치 탐색 Brent 방법

2. 기본 원리

단봉 함수의 최소값을 찾는 경우를 예로 들어 설명한다(최대값을 찾는 경우도 유사하다). 황금분할 탐색은 최소값을 찾는 구간을 점진적으로 줄여나가는 효율적인 방법이다. 핵심은, 이미 함수값이 계산된 점들에 더하여, 새로운 점에서의 함수값을 계산하여 최소값이 존재하는 구간을 좁혀나가는 것이다.

위 그림은 최소값을 찾는 과정의 한 단계를 보여준다. 세로축은 $f(x)$ 의 함수값, 가로축은 ''x''를 나타낸다. 이미 $x_1$ , $x_2$ , $x_3$ 세 점에서 $f(x)$ 의 값이 계산되어 있고, $f_2$ 가 $f_1$ 또는 $f_3$ 보다 작으므로, 최소값은 $x_1$ 과 $x_3$ 사이의 구간 안에 존재한다.

다음 단계는 새로운 ''x'' 값인 $x_4$ 에서 함수를 평가하는 것이다. $x_4$ 는 가장 큰 구간인 $x_2$ 와 $x_3$ 사이에서 선택하는 것이 가장 효율적이다. 그림에서 함수값이 $f_{4a}$ 라면 최소값은 $x_1$ 과 $x_4$ 사이에 존재하고, 새로운 세 점은 $x_1$ , $x_2$ , $x_4$ 가 된다. 만약 함수값이 $f_{4b}$ 라면 최소값은 $x_2$ 와 $x_3$ 사이에 존재하고, 새로운 세 점은 $x_2$ , $x_4$ , $x_3$ 이 된다. 어떤 경우든, 함수의 최소값을 포함하는 더 좁은 탐색 구간을 확정할 수 있다.

탐색 점의 선택과 알고리즘의 종료 조건에 관한 더 자세한 내용은 하위 섹션을 참고한다.

2. 1. 탐색 점 선택

황금 분할 탐색에서 새로운 탐색 점

x_4

는 효율성을 위해 다음과 같은 조건을 만족하도록 선택된다.

새로운 탐색 구간의 길이는 이전 탐색 구간의 길이에 상관없이 일정해야 한다. 즉, $x_1$ 부터 $x_4$ 까지의 길이(''a'' + ''c'')와 $x_2$ 부터 $x_3$ 까지의 길이(''b'')는 같아야 한다. 이를 위해, $x_4 = x_1 + (x_3 - x_2)$ 와 같이 $x_4$ 를 선택한다.
$x_1$ , $x_2$ , $x_3$ 간격의 비율은 다음 단계의 세 점인 $x_1$ , $x_2$ , $x_4$ 또는 $x_2$ , $x_4$ , $x_3$ 의 간격 비율과 동일하게 유지되어야 한다. 이렇게 간격 비율을 일정하게 유지하면 탐색 구간이 균일하게 좁혀지면서 수렴 속도가 빨라진다.

이러한 조건을 만족시키기 위해,

x_1

,

x_2

,

x_3

의 간격 비율은 다음과 같이 황금비 φ (피)로 결정된다.

:

\varphi= \frac{1+\sqrt{5}}{2}= 1.618033988\ldots

:

\frac{b}{a}=\varphi

2. 2. 종료 조건

응용 분야에 따라 다양한 종료 조건을 적용할 수 있다. 구간 Δ''X'' = ''X''₄ − ''X''₁는 최소 ''X'' 추정의 절대 오차를 나타내며, 알고리즘을 종료하는 데 사용할 수 있다. Δ''X''의 값은 각 반복마다 ''r'' = ''φ'' − 1의 비율로 감소하므로, 절대 오차 Δ''X''에 도달하는 데 필요한 반복 횟수는 대략 ln(Δ''X''/Δ''X''₀) / ln(''r'')이며, 여기서 Δ''X''₀는 Δ''X''의 초기 값이다.

매끄러운 함수는 최소값 근처에서 평평하기(1차 도함수가 0에 가까움) 때문에, 최소값의 위치를 찾는 데 너무 큰 정확성을 기대하지 않도록 주의해야 한다. Numerical Recipes in C에 제공된 종료 조건은

x_1

,

x_2

,

x_3

및

x_4

사이의 간격을 테스트하는 것을 기반으로 하며, 상대적 정확도 경계 내에 있을 때 종료된다.

:

|x_3 - x_1| < \tau \big(|x_2| + |x_4|\big),

여기서

\tau

는 알고리즘의 허용 오차 매개변수이고,

|x|

는

x

의 절댓값이다. 이 검사는 중심 값을 기준으로 한 브래킷 크기를 기반으로 하는데, 그 이유는

x

의 상대 오차가 전형적인 경우

f(x)

의 제곱된 절대 오차에 대략적으로 비례하기 때문이다. 같은 이유로, Numerical Recipes 텍스트는

\tau = \sqrt{\varepsilon}

을 권장하며, 여기서

\varepsilon

는

f(x)

의 필요한 절대 정밀도이다.

3. 알고리즘

황금 분할 탐색은 단봉 함수의 최소값(또는 최대값)을 찾는 효율적인 방법이다. 최소값을 찾는 경우, 근을 찾는 것과 달리 세 점이 필요하다. 황금 분할 탐색은 최소값을 포함하는 간격을 점진적으로 줄여나간다. 핵심은 평가된 점의 수에 관계없이 최소값은 지금까지 평가된 가장 작은 값을 가진 점에 인접한 두 점으로 정의된 간격 안에 있다는 것이다.

함수 f(x)의 최소값을 찾는 단계를 예로 들면, f(x)의 값은 세 점 x₁, x₂, x₃에서 이미 평가되었다고 가정할 때, f₂ 가 f₁ 또는 f₃ 보다 작으면 최소값은 x₁ 과 x₃ 사이의 간격 안에 존재한다.

다음 단계는 새로운 x 값인 x₄ 에서 함수를 평가하는 것이다. x₄ 는 가장 큰 간격인 x₂ 와 x₃ 사이에서 선택하는 것이 가장 효율적이다. 만약 f₄a > f(x₂) 이면 최소값은 x₁ 과 x₄ 사이에 있고, 새로운 점의 삼중항은 x₁, x₂, x₄ 가 된다. 반대로 f₄b < f(x₂) 이면 최소값은 x₂ 와 x₃ 사이에 있고, 새로운 점의 삼중항은 x₂, x₄, x₃ 이 된다.

새로운 탐색 간격은 x₁ 과 x₄ 사이 (길이 a + c) 또는 x₂ 와 x₃ 사이 (길이 b)가 된다. 황금 분할 탐색은 이 간격들이 같도록 요구하며, 이를 위해 x₄ = x₁ + (x₃ - x₂) 로 선택한다.

x₂ 의 위치는 x₁, x₃ 에 상대적으로 결정되는데, 황금 분할 탐색은 이 점들이 후속 삼중 점 x₁, x₂, x₄ 또는 x₂, x₄, x₃ 과 동일한 간격 비율을 갖도록 간격을 선택한다. 이렇게 함으로써 각 단계에서 간격 너비가 동일한 상수 비율로 축소된다.

수학적으로, 간격 비율은 다음과 같이 표현된다.

f(x₄) 가 f₄a 인 경우: c/a = a/b
f(x₄) 가 f₄b 인 경우: c/(b-c) = a/b

이 두 식에서 c 를 제거하면 (b/a)² - b/a = 1, 즉 b/a = φ 가 된다. 여기서 φ는 황금비로, φ = (1 + √5) / 2 = 1.618033988... 이다.

황금 분할 탐색 알고리즘은 반복 알고리즘과 재귀 알고리즘 두 가지 형태로 구현될 수 있다. 반복 알고리즘은 반복문을 사용하여 탐색 구간을 좁히고, 재귀 알고리즘은 함수를 재귀적으로 호출하여 탐색 구간을 좁힌다.

3. 1. 반복 알고리즘

초기 탐색 구간 [x₁, x₄]와 최소화할 함수 f(x)|f(x)^영어를 설정한다. 내부 점 x₂를 계산하고, 해당 점에서의 함수값 F₂를 계산한다. 이때 두 간격의 길이는 c : r 또는 r : c의 비율을 가지는데, 여기서 r = φ - 1, c = 1 - r이며, φ는 황금비이다.

세 점 x₁, x₂, x₄를 사용하여 수렴 기준이 충족되었는지 확인한다. 만약 충족되었다면, 이 세 점을 이용하여 최솟값에서의 X를 추정하고 반환한다.

수렴 기준이 충족되지 않았다면, 세 점에서 다른 내부 점 x₃과 그 함수값을 계산한다. 세 간격은 c:cr:c의 비율을 갖게 된다.

다음 반복을 위한 세 점은 F가 최소인 점과 X에서 그에 가장 가까운 두 점을 선택한다.

위의 과정을 반복한다.

3. 2. 재귀 알고리즘

python

import math

invphi = (math.sqrt(5) - 1) / 2 # 1 / phi

invphi2 = (3 - math.sqrt(5)) / 2 # 1 / phi^2

def gssrec(f, a, b, tol=1e-5, h=None, c=None, d=None, fc=None, fd=None):

"""황금 분할 탐색, 재귀적.

구간 [a, b]에 단일 국소 최소값을 갖는 함수 f가 주어지면, gss는

최소값을 포함하는 부분 구간 [c, d]를 반환하며, d-c <= tol입니다.

예시:

>>> f = lambda x: (x - 2) ** 2

>>> a = 1

>>> b = 5

>>> tol = 1e-5

>>> (c, d) = gssrec(f, a, b, tol)

>>> print (c, d)

1.9999959837979107 2.0000050911830893

"""

(a, b) = (min(a, b), max(a, b))

if h is None:

h = b - a

if h <= tol:

return (a, b)

if c is None:

c = a + invphi2 * h

if d is None:

d = a + invphi * h

if fc is None:

fc = f(c)

if fd is None:

fd = f(d)

if fc < fd: # 최댓값을 찾으려면 fc > fd

return gssrec(f, a, d, tol, h * invphi, c=None, fc=None, d=c, fd=fc)

else:

return gssrec(f, c, b, tol, h * invphi, c=d, fc=fd, d=None, fd=None)

```

재귀 알고리즘은 함수를 재귀적으로 호출하여 탐색 구간을 좁혀 나가는 방식으로 작동한다. `gssrec` 함수는 이러한 재귀적 방식을 구현한 예시이다.

매개변수:

`f`: 최소값을 찾을 함수.
`a`, `b`: 탐색 구간의 양 끝점.
`tol`: 허용 오차 (종료 조건).
`h`, `c`, `d`, `fc`, `fd`: 재귀 호출 시 내부 계산에 사용되는 값들 (일반적으로 직접 지정할 필요 없음).

작동 방식:

1. 구간 `[a, b]`의 크기 `h`가 허용 오차 `tol`보다 작거나 같으면, 현재 구간 `[a, b]`를 최소값을 포함하는 구간으로 반환하고 재귀를 종료한다.

2. `c`와 `d`가 `None`이면, 황금비를 이용하여 구간 `[a, b]` 내에 두 점 `c`와 `d`를 계산한다.

3. `fc`와 `fd`가 `None`이면, 각각 `c`와 `d`에서의 함수값 `f(c)`와 `f(d)`를 계산한다.

4. `fc`와 `fd`를 비교하여, 더 작은 함수값을 갖는 쪽에 따라 다음 탐색 구간을 결정한다.

`fc < fd` (최소값을 찾는 경우): `[a, d]`를 새로운 탐색 구간으로 설정하고, `d`는 새로운 `c`가 된다.
`fc > fd` (최대값을 찾는 경우): `[c, b]`를 새로운 탐색 구간으로 설정하고, `c`는 새로운 `d`가 된다.

5. 4번에서 결정된 새로운 탐색 구간과 업데이트된 값들을 이용하여 `gssrec` 함수를 재귀적으로 호출한다.

재귀 호출의 깊이가 깊어질수록 탐색 구간 `[a, b]`는 점점 작아지며, 종료 조건 (`h <= tol`)이 만족되면 재귀 호출이 종료되고 최소값을 포함하는 구간이 반환된다.

4. 관련 알고리즘

황금분할 탐색과 매우 유사한 알고리즘으로 피보나치 탐색과 이분법이 있다. 피보나치 탐색은 정수 수열 인덱스만 탐색하면서 황금 분할 탐색의 탐색 위치를 근사하기 위해, 해를 피보나치 수가 되는 구간의 길이를 사용하여 묶는 방식이다. 피보나치 탐색은 1953년 잭 키퍼에 의해 처음 고안되었다. 이분법은 함수의 영점을 찾는 데 사용되며, 탐색 구간은 각 단계에서 황금비가 아닌 2의 비율로 감소한다.

4. 1. 피보나치 탐색

피보나치 탐색은 단일 국소 최소값 또는 국소 최대값을 갖는 값의 수열의 극값(최소 또는 최대)을 찾는 데 사용되는 알고리즘이다. 이 알고리즘은 황금분할 탐색과 매우 유사하지만, 탐색 위치를 근사하기 위해 피보나치 수를 사용한다. 탐색 구간의 길이는 피보나치 수가 되도록 묶인다. 이러한 이유로, 황금 분할 탐색의 수열 변형은 ''피보나치 탐색''이라고 불린다.

피보나치 탐색은 1953년 잭 키퍼에 의해 구간 내에서 단봉 함수의 최대값(최소값)을 찾기 위한 미니맥스 탐색으로 처음 고안되었다.

4. 2. 이분법

이분법은 함수의 영점을 찾는 데 사용되는 알고리즘이다. 황금분할 탐색과 유사하지만, 영점을 찾기 위해 세 점이 아닌 두 점만 필요하다. 탐색 구간은 각 단계에서 황금비가 아닌 2의 비율로 감소한다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com