왜 GA를 사용하는가?

Root Finding과 Optimization의 차이점

Root Finding과 Optimization은 비슷해 보이지만 본질적으로 다른 문제입니다.

• Root Finding: 함수의 영점을 찾는 문제로, 함수 값이 0이 되는 점을 찾는 것입니다. 즉, ( f(x) = 0 )을 만족하는 ( x )를 찾는 문제입니다.
• Optimization: 함수의 도함수의 영점을 찾는 문제입니다. 즉, 함수의 기울기가 0이 되는 점, 즉 함수의 최소값(또는 최대값)을 찾는 것입니다. 여기서 최소값은 반드시 전역 최소값일 필요는 없으며, 지역 최소값에 빠질 수 있는 위험이 존재합니다.

---

기존 최적화 방식들의 한계

1. Exhaustive Search (완전 탐색)

   • 설명: Cost surface에서 샘플링한 점들을 모두 탐색하는 방법입니다. 샘플링이 촘촘할수록 더 정확하게 탐색할 수 있습니다.
   • 문제점: 변수의 개수나 샘플링 간격이 증가함에 따라 탐색할 조합이 기하급수적으로 늘어나게 되어 시간이 오래 걸립니다. 이를 해결하려면 처음에는 크게 샘플링하고, 유망한 영역에 대해서는 점차 샘플링을 촘촘히 하는 방법을 사용할 수 있습니다. 하지만 이 방법은 global minimum을 놓칠 위험이 있습니다.

2. Analytical Optimization (해석적 최적화)

   • 설명: 미적분을 사용하여 수학적으로 접근하는 방법입니다. Exhaustive Search에 비해 더 우아하고 빠릅니다.
   • 문제점: 이 방법은 연속 함수에만 적용 가능하며, 이산적 문제에는 잘 적용되지 않습니다. 또한, 다변수의 경우 극값을 찾는 것이 어려워지며, 기울기 계산이 불가능한 경우에는 사용하기 어렵습니다. 빠르게 최솟값으로 하강하지만, 로컬 미니멈에 빠질 위험이 높습니다. 이러한 단점으로 인해 실제 최적화 문제를 해결하는 데 실용적이지 않습니다.

3. Nelder-Mead Downfill Simplex Method

   • 설명: 미적분을 사용하지 않는 방법으로, Simplex라는 가장 기본적인 기하학적 도형을 이용하여 최솟값을 찾습니다.
   • 문제점: 이 방법은 글로벌 미니멈을 찾지 못할 수 있습니다. 초기 위치에서 하강하면서 최저점을 찾지만, 초기 위치가 잘못되면 지역 미니멈에 빠질 수 있습니다. 여러 번 실험을 통해 초기 위치를 다르게 설정할 수 있지만, 글로벌 미니멈을 보장하지 않습니다.

4. Line Minimization을 기반으로 한 최적화 방법

   • 설명: 최적화 문제에서 각 변수에 대해 한 번에 하나씩 최적화하는 방법입니다. 예를 들어, 3차원 문제라면 x, y, z 각각에 대해 최적화를 수행한 후, 이를 반복하여 전체 최적화 과정을 진행합니다. 즉, x축 이동 → y축 이동 → z축 이동을 반복하는 방식입니다.
     ex) Newton’s Method, DFP, BFGS
   • 문제점: 수렴 속도가 빠르지만, 각 반복에서 헤시안 행렬을 계산하거나 그 근사치를 추정하는 데 많은 계산 비용이 소모됩니다. 또한, 로컬 최적화에 빠질 위험이 존재합니다.

---

위 기존 방법들의 단점

이러한 방식들은 랜덤한 시작 지점에서 최적화가 진행되는 방식입니다. 각 방식은 여러 가지 문제점을 가지고 있습니다. 예를 들어, 로컬 미니멈에 빠질 위험이 있으며, 글로벌 미니멈을 찾기 어렵고, 계산 비용이 많이 들거나, 수렴 속도가 느린 경우가 많습니다. 이로 인해 최적화 과정에서 다양한 한계가 존재합니다.

---

자연선택

자연선택은 생물학적으로 환경에 더 적합한 개체들이 생존하고 번식하여 유리한 형질을 자손에게 전달하는 과정입니다. 이 과정에서 유전자는 부모 → 자식으로 전달됩니다. 이러한 방식으로 유전자형과 표현형이 결정됩니다.

유전자형(Genotype)과 표현형(Phenotype)

• 유전자형(Genotype): 개체가 가진 유전자의 구성을 의미합니다. 예를 들어, 눈 색깔을 결정하는 유전자가 AA, Aa, aa와 같은 형태로 존재할 수 있습니다.
• 표현형(Phenotype): 유전자형에 의해 실제로 나타나는 특성을 말합니다. 예를 들어, AA와 Aa는 눈 색깔이 갈색으로 나타날 수 있지만, aa는 파란색 눈을 가질 수 있습니다.

유전자 전달 과정 (감수분열)

• 감수분열(Meiosis): 생식세포인 정자와 난자를 만들 때 유전자가 절반으로 줄어들며, 이 과정에서 유전적 다양성이 발생합니다. 교차(crossing over)로 유전자들이 서로 섞이며 다양성을 더욱 증가시킵니다.

멘델의 유전 법칙

1. 분리의 법칙 (Law of Segregation)
   부모의 두 대립 유전자가 자식에게 각각 독립적으로 전달된다는 법칙입니다.

2. 독립의 법칙 (Law of Independent Assortment)
   서로 다른 유전자들이 독립적으로 유전된다는 법칙입니다. 즉, 하나의 유전자형이 다른 유전자형에 영향을 미치지 않습니다.

---

GA(유전자 알고리즘)와 자연선택의 유사성

GA(Genetic Algorithm)는 자연선택을 모방하여 최적화 문제를 해결하는 방법입니다. GA는 적합도 함수에 따라 더 나은 솔루션을 생성하고, 이를 교배, 돌연변이, 선택 등의 과정을 통해 반복적으로 개선합니다. 이 과정에서 자연선택과 비슷한 방식으로 가장 유리한 해결책을 찾게 됩니다.

GA의 장점

• 연속적이거나 이산적인 변수에 모두 적용 가능.
• 도함수 필요 없음: 도함수가 계산 불가능하거나 어려운 함수에서도 동작합니다.
• 많은 변수들에 대한 최적화가 가능.
• 병렬 컴퓨팅에 적합: 여러 개체를 동시에 처리할 수 있어 빠르게 처리 가능합니다.
• 복잡한 cost surface에도 적용 가능: 로컬 미니멈에 빠지지 않도록 다양한 영역을 탐색할 수 있습니다.
• 여러 솔루션 제공: 다양한 해결책을 동시에 탐색하여 최적화 문제를 해결합니다.

GA는 이러한 특성 덕분에 많은 현실적인 최적화 문제에 적용할 수 있으며, 기존의 방법들보다 더 유연하고 강력한 장점을 제공합니다.

참고 도서: Practical Genetic Algorithms - Book by Randy L. Haupt and Sue Ellen Haupt