정올반 9.2 유전 알고리즘을 이용한 자동주행 시뮬레이션

정올반 보고서 1일차 [유전 알고리즘을 이용한 자동주행 시뮬레이션]

 

유전 알고리즘과 코코스2D를 이용한 자동주행 시뮬레이션이다.

 

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

 

유전 알고리즘은 부모의 유전 정보 중에 우월한 유전자를 교배시켜 더 우수한 다음 세대를 만들어 학습하는 알고리즘이다.

 

이 자동주행 시뮬레이션의 학습과정은 이렇다.

1. 바퀴각도, 주행시간으로 이루어진 염색체 10개를 랜덤 생성한다.

2. 주행하다가 벽에 부딪치면 부딪히기 전까지의 각 염색체의 적합도를 구한다.

   적합도: 안 부딪치고 최대한 멀리 간 데이터 값. 공식은 주행시간*거리/진행한 데이터개수

3. 부모 염색체 중에 적합도 상위 10% 염색체끼리만 모아서 다음 세대로 교차시켜 넘긴다. 이때 염색체들은 랜덤으로 배열된다.

4. 교차 진행과정에서 각 데이터마다 1% 확률로 돌연변이가 발생한다. 돌연변이가 발생한 유전자는 랜덤 데이터로 재설정된다.

 

이런 식으로 부딪치지 않는 좋은 길을 학습하며 목적지를 찾는 시뮬레이션이다.

지금 과정이라면 빙글빙글 도는 일도 생기는데 이럴 경우를 위해 돌연변이가 있는 것이며, 우월한 돌연변이가 발생해서 경로를 바꾼다.

실제 유전과정에서도 그렇듯 유전 알고리즘에서도 우월한 돌연변이로 인해 적합도가 급증하며 진화한다. 돌연변이가 학습에 있어서 중요한 역할을 한다는 의미이다.

 

 

이 자동주행 시뮬레이션의 단점은 시간이 너무 오래 걸린다는 것이다. 코너가 2개인 간단한 맵 자동주행을 하는데 약 5시간이나 들었다고 한다.

제가 이 논문을 제대로 이해한 것이라면 이 자동주행 시뮬레이션에 시간이 너무 많이 걸리는 이유는 이런 것 같다고 생각한다.

 

1. 랜덤한 값들 중에 우연히 정확한 길을 가는 값(부딪히지 않고 주어진 길을 따라가는 것)이 나와도 그 데이터의 길이가 끝나면, 그리고 우연하게도 그 데이터의 길이가 짧게 생성되었다면 그냥 교차시켜서 다른 값으로 바꿔버린다. → 쓸데없이 계산을 또 함

2. 사실 유전 알고리즘이라 어쩔 수 없다...

 

 

여기서 생각해봤는데, 여기서는 데이터의 길이도 랜덤이고 교차도 랜덤이다. 만약 데이터의 길이를 랜덤이 아니라 적당히 짧게 만들어 놓고 벽에 부딪혔을 때 부딪친 그곳에서 자동차의 앞 방향으로 랜덤한 10개의(혹은 그 이상, 그 이하) 데이터를 만든 다음 가장 적합도가 높은 코스로 가는 건 어떨까? 실행 시간을 조금 줄일 수 있을 것 같다.

근데 너무 많이 탐색하면 메모리가 터지니까 해결방법을 생각해 보았다. 이리저리 부딪치면서 가는게 마치 시각장애인이 걷는 것 같아서 시각장애인이 자립보행을 위해 쓰는 반향정위를 베이스로 변형시켜 보았다.

 

1. 각 염색체의 적합도를 모아서 데이터의 전체 적합도를 구하는 공식을 만든다.

2. 코스를 탐색하다가 벽에 부딪치면 1번의 공식으로 전체 적합도를 구한다.

3. 앞 방향으로 뻗어나간 10개의 데이터에서 나온 전체 적합도 중에 가장 높은 방향으로 이동한다. 적합도가 제일 높아서 선택된 데이터 외의 각 염색체가 담긴 데이터는 제거한다.

4. 만약 운 좋게 올바른 코스로 뻗어나가면 너무 많이 가서 데이터가 엄청 길어질 수 있으므로 처음부터 데이터의 크기를 적당히 잡는다.

5. 벽에 부딪치지 않고 끝까지 간 데이터가 한 개 이상 있으면 그 중에서 랜덤하게 골라서 간다.

6. 양 방향도 괜찮을듯한데 그러면 제대로 온 뒤쪽이랑 좋은 코스인 앞쪽은 무조건 높은 전체 적합도가 나오기 때문에 앞쪽만 탐색하는 것으로 했다. 혹시 앞이 막다른 길이라도 5번을 반복하다보면 유턴할 수 있기 때문이다.

 

 

쓰다보니까 알게 된 건데 원래 논문에서도 제대로 된 길을 갔다면 적합도가 100이 나와 교차해도 100인 데이터가 우월하기 때문에 그대로 가는...건가...? 논문에 대한 이해가 부족한 것 같은데 만약 그렇다면 시간을 조금 줄이겠다고 쓴건 다 필요 없을 것 같다. 사실 저 방법을 코딩할 수 있을지도 모르겠고 이미 나와 있는 알고리즘일수도 있다. 들을 때는 뭔가 알 것 같았는데 지금은 자꾸 헷갈리기만 한다. 그냥 발표 들으면서 생각했던 내용.