유전자 알고리즘의 개념 및 역사

 ■ 유전자 알고리즘의 개념 및 역사

 

유전자 알고리즘은 1970년대 미시간 대학의 존 홀랜드 교수에 의해 처음 소개 되었습니다. 인공지능의 한 종류로 크게 보면 기계 학습을 통해 주로 최적화 문제에서 많이 활용되고 있습니다. 현실세계의 문제들 특히 여러 분야의 최적화 문제는 사람이 직접 계산하거나, 엑셀과 같은 프로그램을 통해 수식을 만들어 계산하는데는 시간과 비용이 많이 소요됩니다.

이런 한계를 극복하기 위해 유전학을 활용해 현실세계의 문제를 해결하고자 하는 것에서 시작했습니다. 전역적인 해를 찾는 문제 해결 방법론으로 성능을 인정받아 다양한 분야에서 응용이 이루어지고 있습니다. 유전자 알고리즘은 진화론에서 나오는 이론과 같습니다. 생명체가 진화하는 모습과 같이 각 해집단의 품질을 높여가는 방식을 말합니다. 주로 변이, 선택, 진화, 교차 등 유전학적 용어를 그대로 채용한 부분이 많이 있어 유전자 알고리즘 또는 유전 알고리즘이라고 많이 불립니다. 유전자 알고리즘은 최적해를 찾는 과정을 알 수가 없습니다. 결과값을 찾는게 목적이라 이 부분이 한계로 지적받고 있는데, 세대 수를 얼마만큼 반복할 것인지를 잘 결정하는게 중요합니다.

 

■ 유전 알고리즘 용어

 

생물학에서는 유전 정보를 담당하는 개체를 염색체라 하고, 염색체들이 모여서 이룬 개체의 집단을 해집단이라고 합니다. 염색체 상의 각 인자는 유전자이며, 유전자 알고리즘에서 가장 작은 단위 입니다. 각 유전자는 염색체의 특정 위치에 존재하여, 그 장소를 유전자 자리라는 좌표에 의해 규정됩니다. 유전 알고리즘에서 쓰이는 용어에 대한 정확한 이해가 가장 필요합니다. 처음에는 단순히 개체, 염색체, 유전자 이런 용어들이 매우 쉬운거 같은데 막상 코딩을 하는 과정에서 초기 개체 설정, 적합도 함수 설정, 선택, 교차, 변이를 설정하다보면 많은 혼란이 옵니다. 그리고 코딩을 하기 전에 엑셀이나 다른 툴을 써서 용어와 설정 값에 대한 정리를 하는 것을 추천 드립니다.

 

■  유전자 알고리즘 순서

 

유전자 알고리즘은 해집단 설정, 적합도 설정, 선택, 교차, 변이 순으로알고리즘이 진행됩니다. 유전자 알고리즘에서 가장 핵심부분은 적합도 설정부분으로 적합도를 어떻게, 얼마나 적절하게 설정하는게 따라 유전자 알고리즘의 품질이 결정됩니다. 여기서 유전자 알고리즘의 품질이란 유전자 알고리즘의 해가 지역적인 해로 빠지지않고 전역적인 해를 얼마만큼 잘 찾는가 입니다. 쉽게 설명하면 각 세대를 반복하면 각 세대를 대표하는 것이 아닌 전체 해집단을 대표하는 해를 찾는 겁니다. 유전자 알고리즘을 구성하면서 가장 큰 오류가 지역적인 해를 찾는 것으로 알고리즘이 실행되지 않는 오류는 아니지만, 목표한 바와 다른 결과값이 나올 수 있기때문에 항상 조심해야합니다. 

 유전 알고리즘 방법론을 쓰기 앞서 해결하고자 하는 문제가 유전 알고르즘에 적합한지부터 잘 판단해야합니다. 다른 방법론을 써서 해결할 수 있거나, 유전 알고리즘에 적합하지 않을 수도 있습니다. 그리고 자신이 가진 여러 환경을 고려해야합니다. 지금은 컴퓨터 하드웨어가 많이 좋아졌지만, 컴퓨터 하드웨어가 뒷받침 되지않으면 큰 규모의 유전 알고리즘을 실행하는데 어려움이 있을 수도 있습니다. 그리고 어떤 프로그래밍 언어로 유전 알고리즘을 구성할 것인지에 대한 생각도 미리 해야할 필요가 있습니다. 전 파이썬으로 실행을 했었는데 다른 분들은 매틀랩으로 더 쉽게 하는 것도 경험했습니다. 저는 파이썬 공부와 유전 알고리즘 방법론에 대한 공부가 필요해서 했지만, 유전 알고리즘이 주 목적이면 더 효율적인 방법을 찾는 것을 추천드립니다.

 

유전자 알고리즘은 경로 문제, 최적의 주기를 찾는 문제, 경영 문제에서 최적화 문제에서 많이 활용되고 있습니다. 특히 여행자 경로문제가 유명합니다. 제가 공부할때는 개념적인 부분에 대한 설명이 매우 어려웠습니다. 저는 코딩을 전문적으로 하는게 아니라 유전 알고리즘의 방법론이 필요해서 급하게 공부하다 보니 많은 어려움이 있었습니다. 좀 더 쉽게 자세한 설명이 있었으면 좋았겠다 싶어서 포스팅을 합니다. 제가 글 솜씨가 부족해 쉽지는 않겠지만 제가 이해한 선에서는 쉽게 설명하려고 노력하겠습니다.