1. Introduction
TSP나 할당문제 등 몇몇 최적화 문제에는 그 문제의 정확한 해를 찾거나 근사하기 위한 효율적인 알고리즘이 알려져 있다. 하지만, 그렇지 않은 경우도 존재한다. 이런 최적화 문제들의 해를 찾는 데에는 보통 EXP time이 소요되며, 근사하는 방법도 딱히 알려져 있지 않다. 그래도 널리 알려진 최적화 방법을 이용하면 값을 충분히 좋은 근사 해를 얻을 수 있다. 이런 방법에는 gradient descent, simulated annealing 그리고 genetic algorithm 등이 있다. 이중 simulated annealing과 genetic algorithm은 randomized search로 분류할 수 있다. 본문에서는 randomized search에 관해 다루고자 한다.
2. Randomized Search
Randomized search는 randomize에만 의존하는 탐색 방법으로 작동 방식이 간단하고 구현 난도가 낮아 자주 이용된다. Randomize에만 의존한다고 해서 무식하게 무작위 해 후보를 뽑아두고 그중 가장 적합한 것을 고르는 방식은 아니다. 보통 몇 개의 step을 이용하며, 확률적으로 최적화를 진행한다. 다음 챕터부터는 가장 널리 알려진 randomized search인 genetic algorithm과 simulated annealing에 대해 설명하겠다. 또, 편의를 위해 목적함수는 아래와 같이 설정하겠다.
$$ \mbox{minimize } f(\mathbf{x})=\sum_{i}^N \mathbf{x}_i \mathbf{w}_i \ \ \ \ \ \ (2.1.)$$
3. Genetic Algorithm
Genetic algorithm(유전 알고리즘, GA)은 처음에 무식하게 해 후보들을 만들어 놓고, 이 후보들 중 가장 적합한 것들을 이용해서 새로운 해 후보들을 만드는 방식이다. 여기서 목적에 적합하다는 것은 설정한 목적함수의 값으로 확인한다. \((2.1.)\)을 기준으로 하면, 목적함수의 값이 작을수록 적합한 후보이다.
\(\mbox{Heuristic 3.1. }\) \(f(\mathbf{x})\)가 상대적으로 작은 \(\mathbf{w}\)를 parent로 하여 새로운 해 후보를 만들면 더 \(f(\mathbf{x})\)가 작은 \(\mathbf{w}\)를 찾을 수 있을 것이다.
GA는 위 휴리스틱을 기반으로 작동한다. 이제 우리는 생물의 유전에 대해 생각해보자. 하나의 개체가 여러 개의 자손을 만드는 경우도 있고, 두 개의 개체가 여러 자손을 만드는 경우도 존재한다. GA에서 두 개의 해 후보를 통해 다른 해 후보를 만들 때는 '교차'라 불리는 방식을 이용한다. 하나의 해 후보를 통해 다른 해 후보를 만드는 경우에는 이런 방식이 필요 없다.
3.1 Crossover
GA에서 교차(crossover)는 두 개의 해 후보를 통해 새로운 해 후보를 만드는 것이다. 교차를 하는 방법에는 여러 가지가 있으며, 상황에 맞게 골라서 이용하면 된다.
3.1.1 Using Crossover Point
먼저, crossover point를 이용하는 방법을 설명하겠다. crossover point란, GA에서 교차를 일으킬 부분을 나누는 역할을 한다. 이 방법은 특정 부분을 서로 바꾸고 나머지를 재배열하는 방법이다. 외판원 문제와 같이 유전자가 cycle의 형태인 경우에도 이용할 수 있다는 장점이 있다.
3.1.2. Random Choice
새로운 해 후보를 만들 때 이용할 두 해 후보를 \(\mathbf{w}_A\), \(\mathbf{w}_B\)라 하고 새롭게 만들어진 해 후보를 \(w_C\)라 하자. 그러면 \(\mathbf{w}_{C,i}\)를 아래와 같이 결정할 수 있다.
$$\mathbf{w}_{C,i} = \mbox{randomChoice}(\mathbf{w}_{A,i},\mathbf{w}_{B,i}) \; \mbox{for all } 1 \le i \le N $$
3.2. Mutation
Mutation은 무작위로 어떤 해 후보 \(x\)의 \(\mathbf{w}_{x,i}\)값을 바꾸는 작업을 의미한다. 이 작업을 한 후에 \(f(\mathbf{x})\)가 하기 전 보다 커질 수 있지만, local minima에 수렴하지 않도록 돕는 역할을 한다. 보통 하나의 \(i\)를 무작위로 선택하여 \(\mathbf{w}_{x,i}\)를 변경하거나 \(i\), \(j\)를 선택하여 \(\mathbf{w}_{x,i}\)와 \(\mathbf{w}_{x,j}\)를 교환하는 방법을 이용한다. 물론, \(\mbox{k}\)개의 indices를 선택하여 shuffle해도 상관은 없다.
참고) 보통 교환이나 shuffle은 routing problem에서 쓰이는 방법이다.
4. Simulated Annealing
Simulated Annealing(담금질 기법, SA)는 후보 해의 값을 무작위로 변경시키는 작업을 통해 함수를 최적화하는 방법이다.
\( \mbox{Heuristic 4.1. }\) 무작위로 \(\mathbf{w}\)를 변경하고, 변경시킨 상태의 \(f(\mathbf{x})\)가 변경하기 전보다 작다면, 변 변경한 채로 두고, 그렇지 않다면 확률적으로 변경을 취소한다. 또, step을 진행할수록 변경이 취소될 확률을 높인다면 global optima에 수렴할 가능성이 높을 것이다.
위 휴리스틱이 사실 SA의 전부이다. 온도 감률, 볼츠만 상수, 온도 등 여러 변수와 상수들이 존재하지만 위에서 설명한 사항을 구현하기 위함이며, 이 상수들을 자유롭게 선택해 주면 되기 때문에 특별히 저 변수들의 이름이 가지는 의미는 없다. 해당 상수에 관한 내용은 링크를 참고하길 바란다.
5. SA/GA
이 챕터에서는 위 두 알고리즘을 섞는 방법에 대해서 설명한다. GA의 경우 다른 optimizaiton method와 함께 이용하기 좋다. 특히, multi-step optimization이라면 더욱 그렇다. 본문에서는 multi-step optimization과 GA를 함께 이용하는 방법에 대해서만 다룬다.
5.1. Epigenetic
Epigenetic(후성유전)은 GA의 crossover 단계 이전에 multi-step optimization method를 이용하여 \(\mathbf{w}\)를 최적화하는 작업이다. 이때 추가적으로 이용하는 multi-step optimization method는 어떤 것을 이용해도 좋다.
5.2. Using SA
SA는 randomize에 의존한 알고리즘이기 때문에 GA의 변이 부분을 SA처럼 구현해도 괜찮다. 또, SA의 온도 부분을 GA 전체에 걸쳐 변화하게 만드는 방법도 있다. 물론, 5.1. 에서 설명한 방법에 SA를 적용해도 좋다.
6. Pros and Cons
Randomized search는 확실히 좋은 방법이다. 간단한 아이디어와 구현을 이용하고 어떤 문제든 이용하기 좋은 강력한 알고리즘이기 때문이다. 다만, randomize에 의존한다는 점이 단점으로 작용할 수 있다. 조합 최적화 문제를 생각해 보자. 해가 될 수 있는 경우의 수가 많지 않을 때 randomized search는 빠르게 해를 수렴시켜 준다. 하지만, 경우의 수가 커지면 그만큼 randomize를 통해 실제 해와 가까운 해를 찾을 가능성이 낮아지고, 빠르게 해를 찾기 힘들어진다. 또, 해를 수렴시키기 힘들 수 있다. Randomized search는 적당히 해를 찾을 범위를 줄여주기는 하지만 목적함수를 수렴시키기 위해서는 부가적으로 다른 최적화 방법을 찾는 것이 좋다.
7. Conclusion
Randomized search는 randomize에 의존하는 탐색 방법으로 genetic algorithm과 simulated annealing이 그 예시이다. 최적화 문제를 해결할 때 많이 이용되지만, 조합 최적화 문제의 경우 해가 될 수 있는 경우의 수가 커지면 randomized search는 효율적인 방법이 아니게 된다. 다만, Machine Learning과 같은 분야에서는 상대적으로 조합 최적화 문제보다 제약조건이 간단하고 해를 찾기 쉽기 때문에 충분히 효율적으로 작동한다.
'Algorithms > Optimization Theory' 카테고리의 다른 글
| Function Optimization using a Ternary Search (0) | 2023.08.18 |
|---|