최적화 도출을 위한 유전자 알고리즘

정보통신기술과 산업이 발전함에 따라 기업들은 무한경쟁에서 살아남기 위해 최적의 의사결정을 내려야 하는 상황에 직면하고 있습니다. 

실제로 최적의 투자안 선택, 최적의 조직관리, 최적의 서비스 제공, 최고 품질의 제품개발, 최소비용의 산업공정 기획 등 광범위한 분야에서 최적 의사결정이 점점 중요한 이슈가 되고 있지요. 이러한 최적의 의사결정을 위해 각 분야의 관련 전문가들은 다양한 조건 속에서 최적화(Optimization) 문제를 해결하기 위해 노력하고 있습니다.

최적화라는 말은 “어떠한 제약조건 하에서 우리가 찾고자 하는 정답에 가장 가까운 것을 찾는 과정”이라는 뜻으로 해석할 수 있습니다. 주변에서 일어나는 크고 작은 사회현상들은 다양한 요소들에 의해서 결정되며 사회는 점점 복잡해지고 있는데요. 이러한 사회현상들 속에서 정답을 찾아낼 가능성은 점점 줄어들기 때문에 정답은 아니지만, 정답에 가장 근접한 것 혹은 가장 좋은 것을 찾는 최적화 문제는 예전부터 매우 중요한 이슈가 되고 있는 것입니다. 

 최적화 이론의 연구

이러한 최적화 이론은 오래 전부터 수학의 한 분야로서 유럽과 미국에서 다양한 분야의 학자들에 의해 연구되어 왔는데요. 제2차 세계대전 이후 산업, 군사, 행정 등의 여러 조직에 적극적으로 활용되기 시작하면서 본격적인 학문 분야로 자리매김했다고 합니다. 

l 곡사포(좌), 각종 군수물자들(우) (출처: https://catalog.archives.gov/id/196328)

실제로 미국의 제2차 세계대전 승리를 이끈 주요 요인 중 하나로 미군의 무한대 군수물자 투입을 꼽는 사람들이 있습니다. 하지만 군수물자라는 것은 무한대로 투입될 수 없기에 미국의 승리에는 무한대의 군수물자 투입처럼 보이게 한 최적화된 군수물자 운용이 큰 역할을 했다고 할 수 있습니다. 이는 유한한 자원이라는 제약조건 하에서 최적화된 군수물자 운용 스케쥴링을 도출함으로써 최적화 분석이 군사 분야에 큰 도움을 준 사례라고 할 수 있습니다.

 최적화를 위한 알고리즘

최적화를 위한 알고리즘은 목표로 하는 최적화 값 (일반적으로 최댓값 혹은 최솟값)을 각 탐색 범위 내에서 조절함으로써 주어진 비용함수(cost function) 값을 최소화 또는 최대화하는 해를 찾아내는 방법을 지칭합니다. 

최적화 알고리즘은 찾고자 하는 해의 요구 수준에 따라 크게 전역 최적화 기법(global optimization method)과 지역 최적화 기법(local optimization method)으로 나눌 수 있습니다. 

전역 최적화 기법은 다소 시간이 걸리더라도 전체 탐색영역에서 가장 좋은 해를 찾는 것을 목표로 하며, 지역 최적화 기법은 단시간에 일부 탐색영역 내에서 가장 좋은 해를 찾는 것을 목표로 합니다.

l 최적화 산출 (출처: http://blog.clarity.fm/dont-test-optimize)

이러한 최적화 기법들에는 다양한 방법론들이 있는데요. 그 중 매우 유용한 전역 최적화 기법으로 알려진 유전자 알고리즘(Genetic Algorithm)을 소개하고자 합니다.

 유전자 알고리즘

유전자 알고리즘은 생물계의 진화를 설명하는 다윈의 적자생존 이론을 기본 개념으로 하는 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법입니다. 

유전자 알고리즘에서는 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차 변형함으로써 점점 더 좋은 해들을 만들어 내는 과정을 거치게 됩니다. 

여기에서 해들을 나타내는 자료구조는 유전자입니다. 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있지요. 이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있습니다. 

유전자 알고리즘은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로 자연과학, 공학 및 인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있습니다. 

l 유전자 알고리즘의 다양한 응용분야

유전자 알고리즘은 일반적으로 선택(selection), 교차(crossover), 그리고 돌연변이(mutation) 이렇게 세 가지 종류의 유전자 조작(genetic operation) 과정을 사용하여 최적해를 탐색해 나갑니다. 

아래 그림에서 볼 수 있는 것처럼 무작위로 생성된 초기집단(일반적으로 이진수 코드로 구성된 일차원의 배열들로 표현됨)으로부터 앞서 언급한 세 가지 유전자 조작을 사용하여 실험자가 설정한 종료조건이 만족될 때까지 선택, 교차, 돌연변이 조작과정을 계속 반복하여 최적해를 탐색해 나가게 되는 것이지요. 

선택조작 과정은 최종 목표로 하는 적합함수(fitness function)를 최적화시키는 해를 확률적으로 발전시키는 단계로서, 초기집단으로부터 발전된 집단을 형성시키게 됩니다. 교차조작 과정은 유전자 알고리즘에서 가장 중요한 단계로 발전된 집단에 속해있는 배열들 간에 이진수 코드를 교차시키는 역할을 합니다. 

마지막으로 돌연변이조작 과정에서는 각 배열들 자신이 가지고 있는 코드를 무작위로 바꾸게 됨으로써 자손집단(offspring set)을 형성시킵니다. 이렇게 생성된 자손집단에 포함된 배열을 적합함수에 적용해 우리가 찾고자 하는 최적해를 탐색해 나가게 되는 것입니다.

l 유전자 알고리즘의 최적해 탐색 (출처: 김영민, 안재준, 2016. ‘탄소배출권 거래시장 특성을 반영한 배출권가격 예측모델 개발’, Entrue Journal of Information Technology)

지금까지 최적화와 유전자 알고리즘에 대해서 간략하게 알아 보았습니다. 유전자 알고리즘은 아직까지도 매우 인기 있는 최적화 기법 중 하나로써 지역 최적화를 해결할 수 있는 강력한 방법론이라는 장점을 가지고 있습니다. 

하지만, 환경이 시시각각 변하는 문제에 대해서는 상대적으로 경직될 수 밖에 없는 한계를 가지고 있습니다. 그러나 이 역시도 다른 방법론들과 Hybrid 하는 방법 등을 모색하여 진화를 거듭하고 있기에 앞으로도 관심 있게 지켜볼 만한 최적화 알고리즘이라고 할 수 있습니다. 

글 ㅣ 안재준 교수ㅣ 연세대학교 정보통계학과 

* 해당 콘텐츠는 저작권법에 의하여 보호받는 저작물로 LG CNS 블로그에 저작권이 있습니다.

* 해당 콘텐츠는 사전 동의없이 2차 가공 및 영리적인 이용을 금하고 있습니다.