Search algorithm - Fibonacci search 설명, 코드 구현

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

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

Fibonacci search 아이디어

피보나치 탐색(Fibonacci search)은 황금분할탐색(Golden section search)과 기본적인 아이디어는 똑같습니다. 황금분할탐색이 황금률(Golden ratio)를 사용했다면 피보나치 탐색은 피보나치 수열(Fibonacci number or Fibonacci sequence)을 사용한다는 점이 가장 큰 차이입니다.

황금분할탐색 설명 링크

이 글을 읽고 있다면 피보나치 수나 피보나치 수열에 대해서는 이미 알고 있으리라 생각하고 이에 대한 설명은 하지 않겠습니다.

(혹시 모르신다면 이 링크의 글을 읽어주세요)

출처: 논문 A comprehensive assessment of maximum power point tracking techniques under uniform and non-uniform irradiance and its impact on photovoltaic systems: A review

황금분할탐색 설명글의 동영상 앞부분 8분가량을 보셨다면 따로 설명하지 않더라도 바로 윗 그림을 이해하실 수 있을겁니다.

Fibonacci search 알고리즘 순서

1. N 회 f(x) 계산이 가능하다고 가정한다.

2. 피보나치 수열을 만든다.

3. 최초 해의 구간 [a, b] 를 결정하고 x_1, x_2를 계산한다.

4. f(x_1), f(x_2) 를 계산한다.

5. f(x_1), f(x_2) 를 비교하여 최적값이 없는 해의 구간을 제거한다.

맨 위의 그림으로 5. 과정을 설명하면, 최초 구간 [v_3, v_4] 에서 f(v_1) ＞ f(v_2) 이기 때문에 구간 [v_3, v_1] 에는 최적값이 존재하지 않으므로 해의 구간에서 제외되고 새로운 해의 구간 [v_1, v_4] 에서 탐색을 새로 시작합니다.

6. N = N-1, a = a_new, b_b_new, 이를 수식으로 다시 표현하면

7. 1번으로 돌아가 N = 2 이 될때까지 재반복

Golden section search 와의 비교 및 수렴률 증명

링크를 참조해주세요

Fibonacci search 코드 구현

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

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

def fibonacci(step):
    #피보나치 수열을 만들기 위한 함수
    fibonacci_list = []
    f0 = 1
    f1 = 1
    fibonacci_list.append(f0)
    fibonacci_list.append(f1)
    k = 0
    for i in range(step):
        fibo_tmp = fibonacci_list[k] + fibonacci_list[k+1]
        fibonacci_list.append(fibo_tmp)
        k = k + 1
    print("fibonacci number list: ", fibonacci_list)
    return fibonacci_list

def fibonacci_search(fibonacci_list, a, b, my_func, iteration, index_number):
    #a, b : initial boundary
    #index_number: 피보나치 수열 리스트의 뒤에서부터 읽어오기 위한 index, F_N 의 N 의 기능을 함(실제 숫자는 다름)
    iteration = iteration + 1
    #assert a < b, 'wrong interval'
    x1 = a + fibonacci_list[-1 * (index_number + 2)] / fibonacci_list[-1 * index_number] * (b - a)
    x2 = b - fibonacci_list[-1 * (index_number + 2)] / fibonacci_list[-1 * index_number] * (b - a)
    print("iteration:", str(iteration-1).ljust(3), "a:", str(a).ljust(25), "b:", str(b).ljust(25), "x1:", str(x1).ljust(25), "x2:", str(x2).ljust(25), "fx1:", str(my_func(x1)).ljust(25), "fx2:", str(my_func(x2)).ljust(25))

    if abs(my_func(x1) - my_func(x2)) < 0.00001:
        print('case close')
        print("iteration:", str(iteration).ljust(3), "a:", str(a).ljust(25), "b:", str(b).ljust(25), "x1:", str(x1).ljust(25), "x2:", str(x2).ljust(25))
        print("x*:", str((a+b)/2).ljust(25), "minimum value: ", my_func((a+b)/2))
        print("Final interval of uncentainty:", (1 / fibonacci_list[-1]) * (b - a))
        return

    if index_number > len(fibonacci_list)-3:
        print('case close')
        print("iteration:", str(iteration).ljust(3), "a:", str(a).ljust(25), "b:", str(b).ljust(25), "x1:", str(x1).ljust(25), "x2:", str(x2).ljust(25))
        print("x*:", str((a + b) / 2).ljust(25), "minimum value: ", my_func((a + b) / 2))
        print("Final interval of uncentainty:", (1/fibonacci_list[-1])*(b - a))
        return

    if my_func(x1) > my_func(x2):
        index_number = index_number + 1
        fibonacci_search(my_list, x1, b, my_func, iteration, index_number)
    elif my_func(x1) <= my_func(x2):
        index_number = index_number + 1
        fibonacci_search(my_list, a, x2, my_func, iteration, index_number)

my_list = fibonacci(74)
fibonacci_search(my_list, alpha, beta, myEquation4, 0, 1)

Fibonacci search 설명 Fibonacci search 뜻 Fibonacci search 코드 Fibonacci search 구현

피보나치 탐색 설명 피보나치 탐색 뜻 피보나치 탐색 코드 피보나치 탐색 구현