[인공지능] Genetic 알고리즘 (유전 알고리즘)

Genetic Algorithm (유전 알고리즘)

Stochastic beam search 의 변형

current state 에 action 을 취함으로서 successor를 만들어내는 Stochastic beam search 와는 달리 두 개의 state 를 합침으로서 새로운 successor를 생성

Population : k 개의 랜덤 생성된 state

Individual : 각 state

individual 은 string 으로 표현됨

 

Next Population 의 생성

• 랜덤으로 생성된 k(여기선 4)개의 state(population) 에 대해 fitness function 으로 평가

• 평가 점수가 높을 수록 부모로 선택될 확률이 높으며 부모로 선택되면 이들끼리 crossover 되며 offspring(자손)을 낳음

• 낳아진 자손을 랜덤으로 약간씩 수정하여 돌연변이를 만들어냄

Fitness function 

cost function 과 반대되는 개념으로, goal state 에 가까울수록 높은 값을 갖도록 하는 평가 함수

 

단일 action 으로는 도달할 수 없는(여러 action 을 거쳐야만 하는) state 간의 이동을 crossover 로는 가능케함으로서 검색 속도를 올림

state 를 문자열로 표현하는 방법은 다양하므로 표현한 방법에 맞게 적절히 crossover 해줘야 오류가 생기지 않음

 

예를 들어 4queen 문제로 3201 를 2진수로 표현하여 11100001 로 표현한 경우 2자리씩 끊어서 하나의 queen 의 위치를 의미하므로 2의 배수 자리 단위로 crossover 를 해야함