미미틱 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

미미틱 알고리즘(memetic algorithm)은 혼합형 유전 알고리즘의 대표적인 형태이다. 리처드 도킨스의 저서 이기적 유전자에서 처음 사용된 "밈(meme)"에서 유래되었다. 최적해를 구하기 위해서 일반적인 유전 알고리즘과 지역 최적화 알고리즘을 함께 이용하는데, 유전 알고리즘의 교차와 변이에 의해서 지역 최적점 근처에 있게 된 해를 지역 탐색 기법을 통해 지역 최적점에 가까이 가도록 미세 조정을 하는 방법이다. 유전 알고리즘은 탐색 능력이 뛰어나 지역 최적점 근처의 해를 얻을 수는 있지만, 이러한 근사해를 미세하게 조정해서 정확한 지역 최적해를 얻는 능력은 부족하기 때문에 이를 보완하기 위해 지역 탐색 기법을 사용한다. 일반적으로 미미틱 알고리즘은 지역 최적화와 결합하지 않은 유전 알고리즘에 비해 빠른 시간에 적합도가 더욱 높은 해를 찾아낸다. 미미틱 알고리즘은 주로 혼합형 유전 알고리즘과 같은 뜻으로 쓰이고 있으나, 유전 알고리즘 이외의 진화 연산 기법과 지역 탐색 기법을 결합하는 경우에는 미미틱 알고리즘이라고 부르는 것이 적절하다. 미미틱 알고리즘에 대비하여, 지역 탐색 기법과 결합하지 않은 원래의 유전 알고리즘을 순수 유전 알고리즘이라고 부른다.

처음 미미틱 알고리즘이라는 용어를 고안한 사람은 모스카토(Moscato)이다.[1]

참고문헌[편집]

  1. Moscato, P. (1989년). On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. 《Caltech Concurrent Computation Program》 (report 826).