Genetic Algorithm 

 

유전 알고리즘 (Genetic Algorithm) 이란 자연계에 있어서 생물의 유전 (Genetics) 과 진화 (Evolution) 의 메카니즘을 공학적으로 모델화하는 것에 의해 생물이 갖는 환경에서의 적응능력을 취급하는 것이고, 1975년에 John Holland 가 저서 "Adaptation on Natural and Artificial Systems" 에 처음 소개한 자연도태 의 원리를 기초로 한 최적화 (Optimization) 방법이다. Genetic algorithm 은 탐색 (Search), 최적화 및 기계학습 (Machine Learning) 을 위한 도구로 많이 사용한다

definition   term   history  site   lab   book   demo   paper

생물은 세포로 구성되고 세포에는 핵이 있으며 그 핵 중에는 염색체 (Chromosome) 라는 것이 있다. 사람의 체세포의 경우에는 46개의 염색체가 있고, 염색체는 주로 DNA로 구성되어 있다.  이 DNA 는 4종류의 염기라고 부르는 화학 물질이 중요한 구성 요소며, DNA가 가지는 정보는 이들 4종류의 염기의 구성 방법에 있다. DNA 는 2중 나선구조로 되어 있으며, 이들이 복잡하게 겹쳐져서 염색체를 구성하고 있다. 유전자 (Gene) 란 유전정보를 담당하는 DNA 를 말한다. 특정의 유전자는 염색체의 특정 위치에 존재한다. 결국 유전정보는 염색체상에서의 위치 (유전자 위치) 와 염기의 배열에 의해 표현되는 것이다

부모로 부터 유전자에 의해 생물로서의 정보 전달이 행해지면 다음세대에는 각 개체 중에서도 보다 우수한 즉, 환경에 적응도가 높은 개체의 유전 정보가 우선적으로 전해진다. 적응도가 낮은 개체는 수명이 짧고, 증식할 수 없게 되기 때문이다. 동시에 적응도가 낮은 종족도 자연 도태되어 간다. 이러한 원리에 기초하여 세대를 거듭해 가면 차례로 환경에 적응도가 높은 개체가 많아진다. 이것이 유전 (Genetics) 과 진화 (Evolution) 의 기본적인 원리이다.

Genetic algorithm 은 풀고자하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성하게 된다. 즉 풀고자 하는 문제에 대한 가능한 해들을 염색체로 표현한 다음 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성한다. 각각의 가능한 해를 하나의 유기체 (Organism) 또는 개체  (Individual) 로 보며 이들의 집합을 개체군 (Population) 이라 한다. 하나의 개체는 보통 한 개 또는 여러 개의 염색체로 구성되며 염색체를 변형하는 연산자들을 유전연산자 (Genetic Operator) 라 한다. 기본적인 연산자는 다음의 3가지가 있다. 선택 (Selection, 집단 중에서 적응도의 분포에 따라서 다음의 단계로 교배를 행하는 개체의 생존 분포를 결정한다. 적응도의 분포에 기초하고 있기 때문에 적응도가 높은 개체일수록 보다 많은 자손을 남기기 쉽게 된다), 교배 (Crossover, 2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시킨다), 돌연변이 (Mutation, 유전자의 어떤 부분의 값을 강제적으로 변화시킨다),

유전 알고리즘을 이용하여 어떤 문제에 대한 해를 찾기 위해서는 먼저 두 가지의 준비 작업이 필요하다. 하나는 풀고자 하는 문제에 대한 가능한 해를 염색체의 형태로 표현 (encoding) 하는 것이다. 또 다른 하나는 각 염색체가 문제를 해결하는데 얼마나 좋은지를 측정하기 위한 평가함수 즉 적합함수 (Fitness Function) 을 결정하는 것이다. 유전자 알고리즘의 전형적인 구조는 다음과 같다. (문병로 2003)

    n 개의 초기 염색체 생성 ;

    repeat {

           for = 1  to   {

          두 염색체 p1, p2 선택 ;

          offspringi = crossover (p1, p2) ;

          offspringi = mutation (offspringi) ;

                          }

      offspring1, ..., offspringk 를 population 내의 개의 염색체와 대치 ;

            } until (정지 조건 만족) ;

    남은 해 중 최상의 염색체를 return ;

유전 알고리즘 또는 진화알고리즘 (Evolutionary Algorithm) 은 자연세계의 진화 과정을 컴퓨터 상에서 시뮬레이션 함으로써 복잡한 실세계의 문제를 해결하고자 하는 계산모델이다. ... 진화 알고리즘은 염색체를 표현하는 방법과 사용되는 유전 연산자의 종류 및 특성에 따라서 다시 여러 가지 모델로 구분된다. 그 하나는 흔히 GA 라고 하는 협의의 유전 알고리즘으로서 여기서는 보통 고정된 길이의 이진 스트링을 염색체로 사용한다. 이에 반해 진화전략 (Evolution Strategy) 은 실수의 값을 취하는 유전자들로 구성된 벡터를 염색체로 사용한다. 그밖에도 그래프와 트리를 염색체 표현에 사용하는 진화프로그래밍 (Evolutionary Programming) 과 유전프로그래밍 (Genetic Programming) 등이 있다. 사용되는 연산자로 EP 와 ES 는 돌연변이 (mutation), GA 와 GP 는 교차 (crossover) 연산자를 주로 사용한다. 역사적으로 EP, ES, GA 는 1960년대와 70년대에 개발되었으며 GP 는 90년대에 들어와 연구되기 시작한 분야이다 ...... (장병탁 1995)

유전 알고리즘의 응용예 이다 .... 조합적 최적화 (Combinatorial Optimization) 는 유전 알고리즘의 응용 예들 중 가장 많은 결과를 낸 것들 중의 하나이다. 가장 관심을 끄는 연구 분야는 비결정 난해 (NP-hard) 군에 속하는 문제들일 것이다. 유전 알고리즘이 도전한 대표적인 문제 또는 문제군을 몇 가지 나열하면 순회판매원 문제 (Travelling Salesman Problem), 작업공정 스케줄링 (job shop scheduling), 네트웍 레이아웃, VLSI CAD 레이아웃, 채널 라우팅, DB 질의 최적화, 자동차 스케쥴링, 그래프 분할, 최대 완전 그래프 문제, 스타이너 (Steiner) 트리 최적화, 부하 밸런스 (load balancing) 문제, 시간표 문제 (timetabling), 이차원 배정 문제 (quadratic assignment problem), 단백질 구조 최적화 (protein folding) 등 한정된 공간에 나열하기 힘들 정도로 많다 .... (문병로 2003)