유전자 알고리즘 입니다..

유전자들을 교배시켜 후손을 낳게하는데 가능한 우성유전자가 후대에 전달되도록 합니다. 우성유전자는 환경에 잘 적응하고 살아남는 유전자를 의미합니다. 

그러나 꼭 우성만이 살아 남는게 아니고 후손 중 돌연변이(변종, 뮤턴트)를 임의로 발생시켜 결과에 변화를 줍니다. 

어떤 경우에는 우성의 후손보다 돌연변이를 거친 후손이 더 나은 결과를 보여주기도 합니다. 

Nonlinear problem에 대한 최적해를 찾기에는 현실적으로 어려우므로

경험적 해법(Heuristic)을 통한 괜츈한 Feasible 값만 찾아도 Good~ 인 경우인거죠.

현실의 문제에서는 '가능한 해'를 찾는 것 조차도 아주 어려운 경우가 대부분일겁니다.

-해를 서치하는 공간이 커질 수록 서치 시간이 exponentially 증가, NP-Hard 케이스인 TSP (Traveling Salesman Problem) 같은 경우 (참조 : http://the2384.blog.me/10106444843) 적절한 node 수를 가진 문제에 대한 다양한 접근법이 존재합니다.

위의 TSP처럼 경험적 해법은 대부분 특정 Problem에 종속적인 것입니다.

그러나 Genetic Algorithm 처럼 다양한 Problem에 접근할 수 있는 경험적 해법의 방법론 같은 것이 있습니다.

이것을 Meta-Heuristic 이라고 하며

대표적으로 Genetic Algorithm(유전해법), Tabu Search(타부서치), 모의실험 벼림해법(Simulated Annealing) 등이 있습니다.

간략히 유전해법 설명드리자면, (꼬소님께서 핵심을 잘 말씀해주셨지만)

해를 표현하는 Gene 설계

적절한 구간을 부모 집단으로 설정

교배를 통한 세대 반복

돌연변이 룰을 정하여 세대 반복 시 일부 돌연변이 실시(한 방향으로 서치하는 것을 막기 위함)

세대 반복은 해가 좋아지는 방향으로 가도록 계속 조정

--> 결국은 모든 해를 찾는 것이 아니라 일부를 찾으면서 좋은 해가 나오도록 하는 방법론

--> 서치 시간을 단축하면서 좋은 해를 찾고 싶은 것.

부족하나마 이 정도로만...

사족 : 한 15년 전에 공부한 내용을 갖고 썰을 풀은 것이므로 약간의 오류가 있을 수 있습니다. 양해 부탁드립니다.

저 실험에서 유전학적 오류는 몇 가지가 있습니다.

1. 유전변이의 변이폭은 F2 세대에서 가장 높습니다. 그런데 F2세대에서 우성 인자형으로 판단되는 인위 선발을 통해 전개한 후대 세대에서 교차만으로는 비디오의 결과처럼 나타날수 없습니다. 그 이유는 요한센의 순계설을 뒤집는 가정입니다. 

2. 실험 초기 가정에서 그네 왕복 주기에 관여하는 32개의 유전자라면 32개의 유효 유전자가 관여하는 표현형의 유전수는 64개체가 아니라 4,294,967,296 개체를 전개해야 원하는 열성 동형 개체가 표현되기 때문에 선발을 실험 설계 자체가 성립되지 않습니다. 이진수의 단순 확률 계산이 아닙니다. 멘델 유전학에 근거하여 후대 유전성이 우/열성이냐와 실험자가 원하는 Nonlinear한 특성이 우성이냐 열성이냐는 전혀 별개의 문제입니다. 따라서 F2 전개에서 64개체만 전개해서는 절대로 원하는 표현형을 찾을 수 없습니다. 특히나 32개라면 QTLs이기 때문에 더더욱 그러하며 그게 유전학적으로 pleiotropism나 polygene 및 epistasis이 없다는 가정하에 그러하지만 실제 inheritance에서는 비일비재합니다. 

3. 돌연변이를 이야기했는데, 인위 돌연변이와 같이 변이 작성없이 자연 돌연변이는 대부분 열성 인자형이며, 유효 유전자가 32개인 경우 64개체의 집단에서는 발현되지도 않고 선발한다는 건 이론상으로도 불가능합니다. 또한 Hardy-Weinberg에 따라 집단내 극분포를 하기 때문에 설사 표현형으로 발현된다고 해도 집단 교배로는 이를 선발하여 고정하는 건 열성인자형이기 때문에 20세대로 순계화한다는 건 불가능합니다. 신의 능력으로 원하는 목표형질을 가진 개체를 선발하고 이를 교배하고 후대 유전시킨다고 해도(유효 인자가 32개인 QTLs을 이런 과정을 해낸다면 노벨상입니다), 적어도 40세대 이상 전개해야 합니다. 그러나 열성인자는 후대에 masking 되기 때문에 전개 집단의 크기는 2배로 늘어나는데, 유효 인자가 32개이니 SSD법으로 선발한다고 실험 설계를 해도 4,294,967,296 집단(이번엔 개체가 아닌 집단이며 SSD이니 선발은 더더욱 어렵고, SSD를 안쓰면 군간 개체수만큼 실험 크기는 증가합니다)을 전개해야 하며 이는 적어도 F3에서는 해야 합니다. 그래야 F4부터 실험적으로 전개되니까요. 한마디로 실험처럼 유전 알고리즘을 작성하면 실제 유전현상과 전혀 다른 결과가 나옵니다.

전 그냥 잼 있겠다 정도로 생각하고 얘기한 건데...무슨 말인지 하나도 모르겠삼~ ㅋㅋ

ㅎㅎㅎ

행복주식회사님께서는 말그대로 Gene 쪽으로 말씀하신것 같습니다. 그 방면은 제가 잘 모르고요.

그냥 어떤 Problem에 대해 정답을 찾기위한 한가지 방법론 이라고 생각하시면 좋을 것 같습니다.

사실 제 논문 주제여서 계속 댓글을 달고는 있는데...

(사실은 유전해법은 그냥 방법론이고... 문제는 VRP에다가 GA, SA, TABU, fides론, Choi방법론 ..... 토탈 16개 정도로 VRP를 돌렸더랬죠 )

유전해법 안 좋아요. 암만 해봐도 타부서치 능가 못하더라고요. 생물학적인 거랑 별로 사실 관계도 없고요... 말이 그렇다는거..

(제 생각)

뭐 별 중요한 이슈도 아니고....

그냥 그렇더라는 말씀...

(왜 이딴걸 연구하라고 주제를 던져주신 교수님이 원망스럽.... 워... 요... )