basic genetic algorithm / 유전 알고리즘 입문 (예제)
유전 알고리즘은 찰스 다윈의 ‘자연 선택' 개념을 구현한 알고리즘 입니다.
그는 저서 <종의 기원>에서 다음과 같이 주장했습니다.
- 각 개체들은 자신들의 정보(특성)을 후손에게 전달(상속)하고 싶어한다.
- 하지만 자연은 개체들이 서로 다른 특성을 가지도록 한다. (100퍼센트 동일한 자식을 낳지 않는다. 조금씩 변화를 준다.)
- 자식은 아무나 낳지 못한다. 적자생존, 즉 환경과 더 잘 맞는 특성을 가진 개체들만 살아남아 더 많은 자손을 낳는다.
- 이러한 과정이 반복되어 진화가 일어난다.
진화과정이 계속적으로 아주 오랫동안 진행이 되면, 단세포에서 진화를 거듭하여 지금의 인류가 탄생했듯이 환경에 아주 잘 적응된 종이 나타날 수 있습니다.
유전 알고리즘
1. begin
유전 알고리즘은 개체들이 모인 집단에서 시작합니다. 각 개체(노드)는 1과 0에 의한 바이너리 형태(무조건은 아니지만 바이너리로 표현되는 것이 좋다고 합니다)로 표현이 됩니다. 이런 개체들이 집단을 형성하고 있습니다.
2. 적합도 계산
적합도(fitness)는 주어진 환경에 얼마나 적합한지를 나타냅니다. 적합도를 구하는 함수는 환경에 따라 달라집니다.
3. selection
상위 n%를 선택합니다. 적자생존의 원리에 따라 환경에 더 적합한 개체들이 살아남습니다. n의 값은 설계에 따라 달라집니다.
4. 유전 연산
선택된 개체들은 유전 연산을 통해 후손을 생산합니다. 유전 연산에는 교배(crossover), 돌연변이(mutation)이 있습니다.
5. 반복
새로운 집단이 형성되면 다시 앞의 과정들을 반복합니다. 반복은 목표로하는 적합도를 찾을 때 까지 혹은 특정 값의 이상을 찾을 때까지 반복합니다.
Crossover, 교배
DNA 염색체가 꼬여서 어머니의 유전 형질의 반, 아버지의 유전 형질의 반을 가지게 되는 것과 비슷한 원리입니다.
Mutation 돌연변이
돌연변이가 언제 나타날 지 알 수 없습니다. 약 0.04프로 확률로 돌연변이가 발생한다고 합니다. 문제에 따라서 돌연변이는 좋은 영향을 주기도 하고 나쁜 영향을 주기도 합니다. 돌연변이 연산은 종류가 매우 다양합니다.
위의 그림처럼 랜덤한 위치의 값이 바뀔 수도 있고,
특정한 위치의 값이 복제(duplication) 될 수도 있고, 삭제(deletion) 될 수도 있습니다. 또한 특정 위치 부터 특정 위치까지의 순서가 반대로 뒤집힐 수도(Inversion) 있고 두 개체의 특정 부분끼리 서로 스위칭(Translocation)되기도 합니다.
유전 알고리즘 활용 예
영상은 그네 타는 법을 유전 알고리즘으로 해결하는 과정을 보여줍니다.
가장 흔드는 폭이 컸던 4명을 선택해서 자식을 생산하고 그 4 명을 다음 세대에도 포함시킵니다. 몇 명을 선택해서 어떻게 자식을 생산할지, 이런 것들은 정해진 것이 아닙니다. 문제에 따라, 상황에 맞게 적절하게 값을 정하면 됩니다.
교차와 돌연변이도 넣었다고 하네요. 22세대 쯤 되면 조금 엉성하지만 어느정도 그네를 타고 있는 모습을 볼 수 있습니다.
programming GA
기본적인 genetic algorithm 의 pseudo code 입니다. 이를 바탕으로 간단한 문제를 genetic algorithm으로 풀어보겠습니다.
예제 : 금괴 담기
10kg을 담을 수 있는 가방이 있습니다. 다음과 같이 6개의 금괴가 존재할 때, 금괴들이 10kg을 넘지 않으면서 가장 값어치가 높도록 금괴들을 선택하여 가방에 담아야 합니다.
gold 1 : ( 4kg, $6 )
gold 2 : ( 4kg, $7 )
gold 3 : ( 3kg, $5 )
gold 4 : ( 2kg, $4 )
gold 5 : ( 1kg, $3 )
gold 6 : ( 6kg, $9 )
개체 : size 6인 배열. 각 인덱스는 금괴 번호, 배열의 값은 1( 해당 금괴를 선택 ) 또는 0 ( 해당 금괴를 선택하지 않음 )
적합도 계산 : 개체가 선택한 금괴들의 총합이 10이하여야 하며, 금괴들의 값어치가 적합도에 해당. 클수록 좋다.
금괴에 해당하는 Gold 클래스와 개체에 해당하는 Chromosome 클래스를 생성했습니다. Chromosome의 sum은 선택한 금괴들의 총합이며, val는 값어치의 총합입니다.
GAController는 적합도 계산, selection, 유전 연산을 수행하는 클래스 입니다.
select_ratio는 전체 집단에서 selection 할 비율을 뜻하고,
population_size 는 집단의 크기 입니다.
mutation_ratio는 돌연변이가 발생할 확률이고, max_w는 문제의 조건인 10kg을 의미합니다. flag는 특정 적합도를 만족해서 알고리즘을 끝내기 위해 사용하는 flag 입니다.
tmp_list는 유전 연산이 수행되고 생성된 자식들을 임시로 저장하는 list 입니다.
deletion_list는 선택되지 못한 개체들을 임시로 저장하는 list 입니다.
best_unchange_cnt 는 max value를 갖는 노드가 몇 세대 동안이나 갱신이 되지 않았는지 count 합니다. 정답을 모른다는 가정하에 문제를 풀어야 하기 때문에 best_unchange_cnt가 40이 되면 알고리즘을 끝내도록 했습니다. 즉, 40 세대 동안 max value를 갖는 노드가 등장하지 않으면 정답을 찾았다고 보았습니다.
최초의 집단을 생성하는 메서드 입니다. 개체의 각 값은 랜덤하게 선택하되 금괴들의 총합이 10이 넘지 않아야 합니다.
mutation 연산은 전체 집단에서 랜덤하게 하나의 개체를 선택하여 해당 개체의 랜덤한 위치의 값을 변경합니다.
crossover는 선택된 개체들을 대상으로 수행됩니다. 선택된 개체들의 모든 가능한 쌍을 crossover합니다. 가능한 두 쌍을 모두 구하기 위해 조합 (combination ) 알고리즘을 사용했습니다. crossover 할 두 크로모좀이 선택되면, 앞에서 부터 2개의 값을 서로 교환합니다. 만약 교환 했는데 sum이 10을 넘어간다면 그 다음 것을 교환합니다.
하나라도 교환이 되었다면 tmp_list에 추가합니다.
결과
10번 정도 시도하면 7~8번 정도 정답을 찾아냅니다. 어떻게 하면 정확성을 더 높일 수 있을지 생각해보고 알고리즘을 수정해보면 좋을 것 같습니다.
전체코드는 아래에 있습니다. 한 번 도전해 보세요!
