Search algorithm - Golden section search 설명, 코드 구현

이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.

Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.

이전 글에서 Unimodality 에 대한 내용을 언급했습니다. 다루고 있는 함수가 Unimodal 하고 local minimum 을 찾고자 한다면, 아래 그림처럼 local minimum 이 존재할 것으로 생각되는 함수의 정의역의 범위를 줄여나가면 local minimum 에 도달하는 것을 보장할 수 있습니다.

타겟 함수의 형태를 모를때 함수의 Unimodality 가 확실하다면 함수의 형태가 ①, ② 중 어느 형태인지와는 상관 없이 왼쪽 그림의 경우 [a, x_1] 사이에는 local minimum 이 없을 것이 보장됩니다. 마찬가지로 오른쪽 그림에서도 [x_2, b] 에는 local minimum 이 존재하지 않음이 확실합니다.

황금분할탐색법(Golden section search) 은 이런 두 점의 비교를 통해서 해가 존재하는 구간을 줄여나가는 탐색 알고리즘입니다.

Golden section search 설명

Golden section search 의 이론적인 내용을 잘 정리한 영상이 있어서 삽입했습니다. 아래에는 위 영상에서 언급하지 않거나, 보여주지 않는 증명 혹은 유도과정에 대해서 적었습니다.

황금비 1.1618··· 을 유도하는 과정

양 변에 Φ 를 곱해서 정리하면,

2차 함수 근의 공식을 통해

알고리즘의 종료 조건

Golden section search 는 제 생각에 굉장히 Heuristic 한 학문이라고 생각됩니다. 정확한 해를 구하는 것이 아니라, 사용자가 정의한 임계치를 만족하는 근사해를 찾는 과정이기 때문입니다. 그렇기 때문에 위 영상에서 제시하는 방법 외에도 더 계산하기 편한 종료조건을 사용할 수도 있습니다.

예를 들어 아래 수식처럼

현재 연산 단계에서 해가 보장된 구간 [x_l, x_u] 에 대해 구간의 양 끝 x_u, x_l 의 차이의 절대값이 임의의 충분히 작은 수 ε 보다 작거나 같다면 iteration 을 더 진행한다고 해도 보장된 구간의 변화의 크기가 크지 않기 때문에 충분히 근사해를 구했다고 할 수 있을 것입니다.

Fibonacci search 와의 비교 및 수렴률 증명

링크를 참조해주세요

Golden section search 코드 구현

핑계일 뿐이지만, 제대로된 코딩 수업을 들어본 적이 없기 때문에 코드가 개똥 같을 수 있습니다.

def myEquation4(x):
    return -1 * (x**2)

def golden_initial(a, b):
    #golden section search 의 최초 시작점 4개를 계산하기 위한 함수
    #x_l: x_low
    #x_h: x_high
    if a < b:
        x_l = a
        x_h = b
    else:
        x_l = b
        x_h = a

    x1 = x_h - 0.618 * (x_h - x_l)
    x2 = x_l + 0.618 * (x_h - x_l)
    return x1, x2, x_h, x_l

def golden_search(x1, x2, x_h, x_l, my_func, iteration):

    print("iteration:", str(iteration).ljust(3), "x_low:", str(x_l).ljust(25), "x1:", str(x1).ljust(25), "x2:", str(x2).ljust(25), "x_high:", str(x_h).ljust(25))
    iteration = iteration + 1

    if abs(my_func(x1) - my_func(x2)) < 0.00001:
        print('case close')
        print("iteration:", str(iteration).ljust(3), "x_low:", str(x_l).ljust(25), "x_high:", str(x_h).ljust(25), "x1:", str(x1).ljust(25), "x2:", str(x2).ljust(25))
        print("x*:", str((x_l+x_h)/2).ljust(25), "minimum value: ", my_func((x_l+x_h)/2))
        print("Final interval of uncentainty:", (0.618 ** iteration)*(x_h - x_l))
    elif my_func(x1) > my_func(x2):
        #print('case1')
        x_l = x1
        x1 = x2
        x2 = x_l + 0.618 * (x_h - x_l)
        golden_search(x1, x2, x_h, x_l, my_func, iteration)
    elif my_func(x1) <= my_func(x2):
        #print('case2')
        x_h = x2
        x2 = x1
        x1 = x_h - 0.618 * (x_h - x_l)
        golden_search(x1, x2, x_h, x_l, my_func, iteration)

#alpha, beta 에는 첫 interval 의 양 끝을 넣어주세요.
x1, x2, x_h, x_l = golden_initial(alpha, beta)
golden_search(x1, x2, x_h, x_l, myEquation4, 0)

Golden section search 설명 Golden section search 뜻 Golden section search 구현 Golden section search 코드

황금분할탐색 설명 황금분할탐색 뜻 황금분할탐색 구현 황금분할탐색 코드