유전 알고리즘(Genetic Algorithm) - 스스로 길을 찾는 AI를 만들어보았다

https://youtu.be/Yr_nRnqeDp0

어느 날 유튜브 알고리즘에서 해당 영상이 뜨게 되었고 스스로 학습하는 AI라는 것에 흥미를 느껴 개발을 시작하게 되었다.

해당 영상에서는 '유전 알고리즘'을 이용하여 AI에게 그네를 더 넓은 폭으로 움직이도록 탈 수 있도록 학습하게 하였다.

 

그렇다면 개발을 시작하기 전 '유전 알고리즘'의 원리부터 알아보자

 

유전 알고리즘이란

유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 한다. -위키피디아 글 인용

 

조금 더 쉽게 정리하면 최적해를 찾기 위해 탐색을 반복해가며 더 좋은 해를 찾아가는 알고리즘이라고 할 수 있을 것 같다.

즉 유전 알고리즘을 구현하기 위해선 '해'를 유전자의 형식으로 표현할 수 있어야 하고 '더 좋은 해'를 구분하기 위한 적합도 함수를 짤 수 있어야 한다.

 

유전자의 형태는 여러 형태가 있을 수 있지만 가장 설명하기 쉽고 간단한 배열로 설명할 것이다.

 

유전 알고리즘을 구현할 때 우선 초기 해 집단은 랜덤으로 구성된다. 그 후 적합도 함수에 따라 우수한 해들을 선택하고 선택한 유전자들 중 보통 2개를 합쳐 교배하여 후대 유전자를 만든다. 그리고 그 과정에서 낮은 확률로 변이를 일으키고 현재 유전자를 후대 유전자로 교체하는 과정을 반복해야 한다.

 

이때 변이가 필요한 이유는 지역최적점에 빠지지 않게 하기 위해서인데 변이를 통하여 한 경로만 탐색하지 않고 여러 경로를 탐색하여 더 좋은 경로가 있는지 확인할 수 있다.

 

유전 알고리즘 과정 정리

선택(Selection)

선택의 종류는 매우 다양한데 예를 들면 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.

해의 선택 방식에 따라 최적해를 구하는 속도가 빨라지고, 지역 최적점에 빠지지 않게 할 수 있으므로 선택의 과정은 매우 중요하다 할 수 있다.

일반적으로 선택을 하는 방식은 가장 좋은 해일수록 선택될 확률이 높아진다. 반대로 말하면 나쁜 해라도 선택될 가능성이 있다는 것을 의미하고 이를 통해 지역 최적점에 빠지지 않게 할 수 있다.

 

균등 비례 룰렛 휠 선택

유전자의 적합도에 비례하여 선택될 확률을 결정하는 선택 방식이다. 주로 전체 적합도 합에서 본인 적합도를 나누어 확률을 결정한다.

 

토너먼트 선택

K개의 랜덤한 해를 고르고 그 중 가장 적합도가 높은 해를 결정하는 방식이다.

음수인 적합도값에도 사용할 수 있다.

 

순위 기반 선택

적합도 점수를 기준으로 정렬하여 순위가 높을수록 선택될 확률을 높게 하는 방식이다.

ex) 1위 : 40%, 2위 : 30%, 3위 : 20%, 4위 10%

필자는 해당 방식을 사용했다.

 

교배, 교차(Crossover)

유전자를 교차하여 다음 세대의 유전자를 만드는 과정이다. 일반적으로 두 개의 유전자를 선택하여 교차 연산을 수행하며 이렇게 생성된 유전자는 각각의 부모 유전자의 교차 연산을 통한 서로 겹치지 않는 유전인자를 받아 새로운 유전자를 구성한다.

교차 연산에는 N-점 교차, 일정 교차, 산술 교차 등이 있다.

 

N-점 교차

해당 방식처럼 N개의 점을 골라 해당 점을 지날 때마다 다른 부모의 유전 인자를 가져가는 방식이다.

 

일정 교차

비트열 등을 이용한 마스크를 사용하여 일정한 형태로 교차하는 방식이다.

필자는 해당 방식을 사용했다.

 

산술 교차

실수 값이 사용되는 경우에 사용하며, 각 인자에 대해 두 부모 인자의 평균값을 사용한다.

 

변이

교차 과정에서 지역 최적점에 빠지지 않기 위해 낮은 확률로 인자 값을 랜덤 한 값으로 변환하는 것을 의미한다.

정적 변이와 동적 변이가 존재하는데 정적 변이는 변이될변이 될 확률이 고정이지만 동적 변이는 세대를 지날수록 변이 될 확률이 점점 낮아진다.

동적 변이를 사용하는 이유는 세대가 지날 수록 최적해에 가까워졌을 것이라고 판단했기 때문일 것이다.

 

 

유전 알고리즘의 기본적인 원리 설명은 끝났으니 결과물을 확인해 보자

해당 프로젝트는 https://github.com/s53809/Genetic-Algorithm를 통하여 열람, 다운로드할 수 있다.

프로젝트 구조 간단 정리

해당 프로젝트에서는 크게 3개의 시스템으로 유전 알고리즘을 이용한 길 찾기 프로그램을 설계하였다.

유전 알고리즘의 전반적인 연산을 담당하는 GenerationManager.cs 와 GenerationManager에서 받아온 정보를 가지고 이동하고 최적해를 계산하여 다시 GenerationManager로 전달하는 EntityController.cs, 그리고 몇 세대인지, 해당 세대에서 가장 최적의 결괏값을 가졌던 유전자의 정보를 사용자에게 보여주는 UIManagement.cs 가 있다.

 

Entity

Entity는 실제로 탐색하는 객체들이며 GenerationManager에서 들어온 정보를 토대로 움직이고 그에 따라 최적해를 계산하는 간단한 연산을 수행한다.

빨간색 객체들이 Entity이다.

 

GenerationManager

유전 알고리즘 연산을 수행하는 메인 시스템으로 유전자들을 생산하고, 선택, 교차, 변이, 교체 등 여러 연산을 수행하며 각 Entity에게 유전자 정보를 전달하는 역할을 한다.

Setting 헤더에 포함된 해당 변수들은 사용자로부터 Entity 객체의 개수, 변이 확률, 행동 변화 간격 시간, 행동(유전자) 개수, 움직임 속도를 입력받게 할 수 있다.

 

 

 

 

 

 

Init()에서는 초기 해 집단을 랜덤으로 구성하기 위하여 생성된 함수이다.

Select()에서는 선택 연산을 위한 함수,

DestroyObj ()에서는 교차 연산이 끝나고 새로운 유전자로 교체하기 위해 기존 Entity 객체들을 삭제하는 함수이다.

Crossover()에서는 교차 연산을 위한 함수이지만 선택, 교차, 변이의 과정이 모두 들어가 있다. 또한 선택 연산을 위하여 유전자 정보들을 정렬하기 위하여 정렬되는 대상인 EntityController에 IComparable <EntityController> 인터페이스를 상속시켜 원하는 순서대로 정렬되게끔 설계하였다. ICompareable 인터페이스에 관해서는 요긴하게 써먹을 수 있기 때문에 모르고 있었다면 찾아보는 것을 추천한다.

 

 

 

 

 

 

 

 

 

 

UIManagement

세대 정보와 해당 세대에서의 최적해의 정보를 사용자에게 표시하는 시스템이다.

 

결과물

https://youtu.be/LlMiof0 cqHo

느낀 점

유전 알고리즘을 공부하면서 시행착오가 많았다.

불필요한 움직임으로 인하여 내가 생각했던 것과 같은 매우 효율적인 움직임을 300세대를 거쳐도 나오지 않았으며 내가 설계한 알고리즘에 따르면 세대를 지나면 지날수록 지역 최적점에 수렴하기 쉬워졌기 때문에 도착지까지 도달하는 시간이 단축되는 빈도가 점점 줄어들었다.

교차 방법을 N-점 교차에서 일정 교차로 교체해보기도 하고 변이 확률을 늘려보았지만 개선되긴 하였으나 결국엔 세대를 지나면 지날수록 효율적인 움직임을 위해 변이에 의존하는 수밖에 없었다. 왜 사람들이 AI 분야에서 유전 알고리즘 대신 다른 알고리즘을 쓰는지 어느 정도 체감이 되었던 것 같다.

하지만 처음으로 AI라는 분야를 다뤄보면서 스스로 학습하여 경로를 찾아가는 AI를 구현했다는 사실이 나에겐 너무 신기했고 재밌었다.