유전알고리즘최적화 (Genetic Algorithm Optimization)
쉽게 풀면
여러 세대에 걸쳐 환경에 잘 적응한 개체가 살아남고 자손을 남기면서 종 전체가 점점 더 나아지는 자연의 진화 과정을 떠올려 보면 됩니다. 유전알고리즘은 여러 후보 해를 마치 하나의 개체군처럼 다루며, 성능이 좋은 해를 우선적으로 골라 서로 섞고 약간씩 변형시키는 과정을 반복합니다. 이 과정을 여러 세대 반복하면 초기에는 엉성했던 해들이 점점 더 좋은 해로 수렴해 갑니다. 정확한 공식을 몰라도 해를 평가만 할 수 있으면 적용할 수 있다는 점이 특징입니다.
왜 중요한가
산업공학에서 다루는 스케줄링, 설비 배치, 경로 설계 등의 문제는 경우의 수가 매우 많아 모든 조합을 다 검토하기 어려운 경우가 많습니다. 유전알고리즘은 이런 복잡한 문제에서도 비교적 짧은 시간 안에 실용적으로 괜찮은 해를 찾아낼 수 있어, 정확한 최적해를 구하기 어려운 대규모 조합 최적화 문제에 널리 활용됩니다. 미분 불가능하거나 탐색 공간이 매우 넓어 경사하강법 같은 전통적 최적화 기법을 적용하기 어려운 조합 최적화 문제(외판원 문제, 일정 계획 등)에서 실용적인 근사해를 찾는 데 널리 활용됩니다.
논문에서는 이렇게 쓰입니다
가능한 작업 순서 하나하나를 하나의 해 후보로 표현하고, 진화 과정을 모사해 더 짧은 작업시간을 갖는 순서를 찾아냈다는 뜻입니다.
진화 기반 탐색 방법을 다목적 문제에 확장 적용해 여러 목표의 균형점들을 함께 찾았다는 의미입니다.
조금 더 깊게 보면
유전알고리즘은 해를 염색체 형태로 표현하고, 적합도가 높은 개체를 우선 선택하는 선택 연산, 두 해를 섞는 교차 연산, 무작위로 일부를 변형하는 돌연변이 연산을 반복 적용합니다. 이런 확률적 탐색 방식은 지역해에 갇히지 않고 넓은 탐색공간을 살펴볼 수 있게 해주며, 대표적인 메타휴리스틱 기법 중 하나로 분류됩니다. 유전 알고리즘은 다윈의 자연선택 원리를 모사해 해(solution) 집단을 염색체로 표현하고, 선택·교차(crossover)·돌연변이(mutation) 연산을 반복하며 적합도(fitness)가 높은 해를 세대를 거듭해 진화시키는 메타휴리스틱 기법입니다.
주의할 점
구한 해가 이론적으로 전역 최적해임을 보장하지는 않으며, 교차·돌연변이 방식이나 파라미터 설정에 따라 성능 차이가 크게 날 수 있습니다.