[2기 강남 김주영] 쉽고 즐거운 유전자 알고리즘 #1

안녕하세요. 강남 소프트웨어 멤버십 19-1기이자 엘리트멤버 2기 김주영이라고 합니다. 저는 자연환경의 현상을 바탕으로 만들어진 알고리즘들에 대한 연구를 좋아하는데, 그 중 많이 알려진 유전 알고리즘에 대해서 소개 해드릴까 합니다.

유전 알고리즘의 매력이라면, 자연세계의 진화과정에 기초한 계산 모델이라는 점입니다. 우리가 공학적 문제를 해결하기 위한 주제로도 정말 좋은 알고리즘이지만, 재밌게 놀기에도 좋은 알고리즘 이라는 걸 말씀드리고자 이 글을 준비했습니다.

1. 유전 알고리즘의 매력..

“기린은 왜 목이 길까? 왜 짧은 목 기린은 없을까?” 라는 일반적으로 많이 알려진 진화 과정에서부터 “왜 원숭이 같은 동물들은 우두머리가 많은 암컷을 거느릴까?” 하는 초등학생이나 할 법한 질문, 그리고 나아가서는 “지금과 조금 다른 환경에서의 인류는 어떻게 진화했을까?” 하는 상상까지 유전자 알고리즘을 통해 해결해 볼 수 있을법한 문제들입니다.

물론 이런 것들 말고도 의료영상의 분할에 유전 알고리즘을 접목해보고, 네트워크의 병목 현상을 막을 수 있는 효율적인 네트워크의 구성을 상상해본다던지 하는 공학적 문제 해결에도 얼마든지 사용할 수 있습니다.

한마디로 “풍부한 상상력만 있다면, 이것저것 상상한 대로 많이 만들어보고 경험할 수 있는 분야가 바로 유전 알고리즘” 이라고 말씀드리고 싶습니다.

우선은 그 첫 번째 시간으로 유전 알고리즘의 기초에 대해서 먼저 설명드리겠습니다.

2. 유전 알고리즘이란?

유전 알고리즘에 대한 설명은 위키피디아의 글을 첨부하겠습니다.

"유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다." - wikipedia "유전 알고리즘“

유전 알고리즘의 특징이라면, 생물학 시간에 배웠던 유전정보에 대한 이야기입니다. 부모의 유전정보들이 자식에게 골고루 분포된다는 점이죠. 우리가 부모님의 모습을 닮았듯이 (누구는 아버지를 더 닮고, 누구는 어머니를 더 닮고, 또 누군가는 잘 섞여서) 유전 알고리즘의 해들도 자신의 부모해들을 빼닮아 있습니다. TV동물의 세계에서도 많이 봐왔듯이 ‘우월한 동물들이 성공적으로 짝짓기를 수행하고, 자식을 낳으며 자신의 우수한 유전자를 가능한 많이 퍼뜨립니다.’

그게 유전 알고리즘의 전부(?)입니다.

2. 유전 알고리즘의 시작 (용어 설명)

2.1 유전자(gene)

유전 알고리즘을 구상하기 전에 먼저 유전자(해)의 모양을 정의해야합니다.

보통은 String으로 구성해서 표현하고는 합니다.

각 칸은 유전정보를 뜻합니다. 예를 들어 첫 번째 칸은 쌍꺼풀의 유무를 뜻한다던가 하는 식입니다. (단순히 0과1로만 구성하거나, 꼭 String 일 필요는 없습니다. 다만 가장 보편적인 방법을 설명드리고자 합니다.)

이제 저 위의 7칸 유전정보를 묶어서 하나의 유전자로 칭합니다.

각 해들은 자신만의 유전정보를 가지고, 주어진 환경에 대처해나갈 것입니다.

2.2 세대(generation)

세대란 유전자들의 생성과 소멸을 담는 하나의 주기를 뜻합니다. 평소에 우리 사회에서 사용하는 세대와 뜻이 동일합니다. 해들이 생성되서 자식해를 생성할 때 까지의 시간을 뜻하고, 1세대 해집합, 2세대 해집합 등으로 각 세대를 대표하는 단어로 사용됩니다. 자식인간 세상의 1세대가 30년 정도라면, 우리의 프로그램에서의 1세대는 전체 루프 한번이 될 수 있습니다.

2.3 적합도 함수(fitness fuction)

적합도는 현재 상태에 얼마나 유전자가 잘 적응하는지를 점수화 시키는 함수입니다. 이 점수가 현재 해가 얼마나 우수한 해인지를 뜻하게 됩니다. 유전자 알고리즘에서 개인적으로 가장 중요하다고 생각하는 점이 이 적합도 함수인데, 유전자 알고리즘에 적용될 문제는 반드시 적합도 함수를 통해서 점수매김이 가능한 문제여야 합니다. ( 밑의 예제에서는 이미 알려진 해를 이용해서 적합도를 계산했지만, 일반적인 공학문제에서는 알려진 해가 없는 문제에 많이 적용되기 때문에 적합도를 다른 방법으로 산출해야 합니다.) '죄수의 딜레마' 문제에서 처럼 유전자들을 서로 경쟁시켜 적합도를 산출하거나, 혹은 문제의 배경이 되었던 수식이나 환경에 대한 결과로 적합도를 매기는 방법을 사용하기도 합니다.

3. 유전 알고리즘의 구현

유전 알고리즘은 크게 4가지 흐름으로 구성되어 있습니다.

3.1 선택(Select)

선택 : 우수한 유전자를 선택하여, 부모해로 지정합니다. 선택은 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등의 여러 가지 일반적인 방법들이 존재하는데, 제가 예제에서 사용한 룰렛 휠 선택에 대해서만 간단히 설명드리고 나머지 이론들은 추후에 재밌는 예제와 곁들여 설명드리겠습니다.

룰렛휠 선택은 위의 그림과 같이 적합도의 비율에 맞춰 각 유전자 별 선택확률을 높이는 방법입니다. 높은 적합도를 가질수록 선택의 확률이 높아집니다. 선택에 있어서 중요한 문제 중 하나는 해의 다양성을 유지할 수 있어야 한다는 것입니다. 현재 환경에서 가장 잘 적응됐다고 판단되는 유전자라고 할지라도, 유전자들의 다양성이 유지되지 않는다면, 전역적으로 최적을 검색할 수 가 없습니다. 후에 설명드릴 '변이'도 유전자(해)의 다양성 유지를 목적으로 수행됩니다.

3.2 교차(Cross)

교차 : 생명체가 부모 사이에서 자식이 태어나듯, 선택된 부모해들의 자식해를 생성합니다. 두 부모해들의 유전정보를 섞는 방법들 중 일반적으로 1점 교차, 다점(2점, 3점 등) 교차, 균등 교차, 싸이클 교차, 순서 교차, PMX(Partially matched Crossover), 산술적 교차, 휴리스틱 교차, 간선 재결합등이 사용됩니다. 예제의 2점교차를 먼저 설명 드리겠습니다.

2점 교차는 두 점을 임의로 선택하여 그것을 기준으로 두 유전자로부터 번갈아 정보를 받아오는 방법입니다. 어떤 유전자는 부모1의 유전정보를 많이 물려받을 수 도 있고, 또 반대의 경우가 생길 수 도 있습니다. 교차방법은 두 부모의 유전정보가 얼마나 복잡하게 섞일 것이냐를 정하는 단계이지, 어떻게 해야 더 좋은 결과가 나올지 예상하고 자식을 생산하는 단계가 아닙니다.

1점 교차의 방법에는 그 기준이 되는 점이 하나만 생성을 하며, 각 기준점의 위치는 매 교차마다 랜덤하게 설정합니다.

3.3 변이

변이 : 변이는 돌연변이의 생성을 뜻합니다. 자연환경에 의해서 발전하는 모습의 유전정보가 아닌, 임의의 유전정보 위치에 임의의 값을 넣어주어, 돌연변이가 탄생하게 하는 단계입니다. 생성된 돌연변이가 우연히 환경에 더 잘 적응하게 된다면, 선택과 교차 등에 의해 더 많은 자손을 번창 시킬 것이고, 그와 다르게 환경에 적응 하지 못하다면, 금방 도태될 것입니다. 보통 1/100, 0.5/100 의 작은 확률로 변이를 발생시킵니다.

3.4 대치

선택 - 교차 - 변이 를 통해 생산된 새로운 해집단을 이용해 기존의 해집단에서 품질이 나쁜 유전자를 품질이 좋은 유전자로 바꾸는 연산입니다. 대치연산을 통해서 전체적인 해 집단의 품질이 좋아지며, 일반적으로 부모세대에서 가장 우수한 해는 대치되지 않고 다음 세대에서도 보존됩니다(Elitism; 엘리티즘)

3. 유전 알고리즘 예제 1

이제 예제를 통해서 유전 알고리즘에 대해서 알아보고자 합니다. 간단한 예제를 위해서 c# Console을 이용하여 구현을 하였고 다들 한번씩 해보시는 것도 괜찮으실 것 같네요.

3.1. 배경

0과1로 이루어진 유전자를 이용해 정해진 해(0000011111)로의 수렴을 알아보자.

3.1 유전자 설계

• 0과 1로 이루어진 길이 10의 문자열

• 평가함수는 각 자리가 맞으면 +1, 틀리면 0    
  예) 1110100101 : 첫번째~다섯번째의 0의 갯수 + 여섯번째~마지막자리의 1의 갯수 = 3

• 한 세대당 100개의 유전자가 총 1000세대 동안 재생산된다

• 다이나믹한 효과를 위해 초기 값을 모두 1111100000로 두어 평균 적합도를 0으로 시작한다.

• 룰렛휠 선택법, 2점 교차연산법, 0.01%의 변이확률로 수행하고, 대치는 모든 유전자를 대상으로 새롭게 만들어진 100개의 자식 유전자로 세대를 구성한다.

3.2 결과 그래프

3.3 결과 토의

파란 선은 한 세대의 평균 적합도를 빨간 점선은 세대 내의 최고 적합도를 뜻합니다. 평균 0으로 시작되었던 해들이 유전자 알고리즘을 거치면서 점점 최고적합도인 10으로 수렴하는 형태를 보입니다. 약 650세대 정도에서 진화를 멈춥니다.

엘리티즘을 적용하지 않았기 때문에 돌연변이(0.01%확률의 유전정보 하나의 변경)로 발생된 세대내의 최고해는 다른 해와 교배를 거치면서 최고해가 유지되지 못하고 도태됐지만, 우월했던 유전정보는 자식에게 전해져 최적값으로 수렴하는데 도움이됩니다.

조금 아쉬운 부분은 돌연변이를 발생시키는 코드의 부분에서 각 해마다의 0.01% 확률을 독립적용하여 선택된 해의 유전정보 한부분만을 수정한 내용입니다. 이 부분에서 해마다의 0.01%가 아니라, 유전정보마다 0.001%의 확률로 적용을 해본다면 한 유전자에서도 두개 이상의 유전정보가 수정된 돌연변이가 탄생할 수 있어 수렴에 더욱 도움을 줄 것으로 보입니다.

3.4 기타

아무래도 너무 빨리 수렴한 감이 있고, 해가 수렴하기 위한 조건이 비교적 간단해서 추가 예제의 구현이 필요했습니다. 기본적인 아이디는 같지만, 수렴 조건을 조금 복잡하게 수행해봅시다.

 

4. 유전 알고리즘 예제 2

 4.1 배경

0~9로 이루어진 유전자를 이용해 최적해(0123456789)로 수렴하는 알고리즘 구현

4.2 유전자 설계

• 0과 9로 이루어진 길이 10의 문자열 (초기값 : 0000000000 , 적합도 : 1)
• 기본적인 구상은 예제1과 동일
• 돌연변이 발생 확률 부분을 해 0.01% 확률이 아닌 유전정보마다 0.001%(0.002) 확률로 수정 (좀 더 큰 돌연변이 확률로 인한 수렴정도를 비교 관찰하기 위한 0.002 )

4.3 결과 그래프

4.3.1. 0.001%의 돌연변이 확률

 

 

4.3.2. 0.002%의 돌연변이 확률

4.4 결과 토의

2배의 확률 차이로 인해서 수렴정도가 눈에 띄게 향상 했습니다. 물론 이 예제의 경우에는 초기값 적합도가 0에 가깝고, 이미 알려진 최적해를 이용해 적합도

 

를 구했기 때문에 돌연변이의 등장이 반가운 입장입니다. 돌연변이의 확률은 정하기 나름이지만, 높은 돌연변이 확률은 세대 변화 진폭이 줄어든 후에는 수렴을 방해하기 때문에 확률 설정에 신중해야 합니다.

1번 그래프는 아직 최적해로의 수렴을 성공하지 못했지만, 2번 그래프는 최적해로의  수렴을 거의 마치기 직전 상태까지 진행되었습니다. 그래프의 전반적인 모양도 2번그래프가 더욱 급속도로 수렴하는 양상을 보입니다.

 

5. 마치며

위의 예제들을 통해서 유전 알고리즘의 수렴 결과를 확인 할 수 있었습니다. 유전 알고리즘의 소개에 걸맞은 예제가 되었는지 잘 모르겠군요. 저도 같이 공부하는 입장이라서 모든 답변을 해드릴 순 없겠지만, 궁금한 점이나 오류 지적에 대한 내용은 ohgreat11@gmail.com 으로 보내주시거나, 댓글을 달아 주시면 충실히 답변 드리겠습니다.

다음에는 이렇게 쉬운 예제가 아닌 더 복잡하고 재미있는 예제로 다시 찾아뵙겠습니다. 이 글이 유전알고리즘에 대해 처음시작하는 분들을 위해서 좋은 참고자료가 되길 바랍니다.