'유전 알고리즘 학습' 시리즈파이썬(Python) - 유전 알고리즘 - 기본

배진오

@baealex

가야 할 때가 언제인가를 분명히 알고 가는 이의 뒷모습은 얼마나 아름다운가.

우선 나는 걱정스럽다. 여기에 적혀진 글과 코드는 그저 이론을 이용해 나만의 방식으로 구현해 본 것이다. 생명공학에 대한 지식 역시 매우 부족하므로 그저 유전이라는 개념을 응용했다고 생각해 주길 바란다. 나열된 코드를 끈임없이 의심하고 절대적으로 신뢰하지 않길 바란다. 기본적인 내용은 이 블로그를 참고했다. 내가 읽어 본 책에 나와있는 것과 유사한 내용인데 좀 더 정리가 잘 된 내용인 것 같다. 간단하게 정리하면 이렇다.

용어의 정리
  • 염색체 : 유전 정보를 담은 문자열
  • 유전자 : 문자열의 유전 정보
  • 교차 : 두 개의 염색체를 조합
  • 돌연변이 : 확률적으로 유전자의 정보가 바뀜
  • 자손 : 교차와 돌연변이로 생성된 염색체
알고리즘의 흐름
  1. 최초 염색체 생성
  2. 세대 적합도 평가
  3. 세대 교차 및 돌연변이
  4. 다음 세대 적합도 평가

목표 적합도를 달성했다면 종료하고 달성하지 못했다면 2번으로 돌아간다. 단 어려운 문제의 경우 목표치를 선정하기 어려우므로 반복 횟수를 제한하는 것이 일반적이다.


이론 적용기

유전 알고리즘의 이론은 대략 알겠는데 이걸 어떻게 적용해야할까 싶은 생각이 든다. 그래서 일단 이론을 접목하되 가장 접근하기 쉬운 방법으로 코드를 구현하고자 하였다. 목표는 0-9라는 유전자를 10개 가진 염색체를 생성하고 1이라는 유전자를 우성 유전자로 평가하여 진화하도록 말이다.


적합도 평가

1이라는 유전자를 우성으로 만드려면 어떤식으로 적합도를 평가해야 할까?

if gene > dominant:
    evaluation_vlaue += gene - dominant
else:
    evaluation_vlaue += dominant - gene

나의 경우는 유전자가 숫자라는 간단한 개념이므로 우성과의 거리를 측정하여 크기가 가장 작은 염색체에게 높은 점수를 주었다. 결과적으로 모든 유전자가 1인 염색체가 등장한다면 적합도 평가 점수는 0이 되므로 이는 동시에 종료 조건이 된다.


돌연변이

처음 코드를 작성했을때 5세대 정도가 지나면 비슷한 염색체끼리 합쳐져 나중에는 똑같은 염색체만 남아 계속해서 똑같은 염색체만 만들어지는 현상이 있었다. 지역 최적화라는 용어가 떠올랐는데 내가 한가지 간과하고 있던건 돌연변이에 대한 설정이었다. (근친이 이렇게 위험합니다)

mutation = 0.01 
...
    for i in range(5) :
        for j in range(10) :
            if random.random() < mutation :
                new_chromosome[i][j] = random.randint(0,9)
            else :
                new_chromosome[i][j] = chromosome[parent_cromo_index[random.randint(0,1)]][j]
...

부모의 유전자를 적절히 섞다가 특정 확률로 전혀 새로운 유전자를 염색체 내부에 삽입되도록 하였다. 0.01로 설정하니 아까처럼 비슷한 염색체가 남았을때 좀 더 괜찮은 염색체가 생성되면 그 염색체처럼 변화했다. 좀 더 급격하게 변할 수 있도록 0.1로 설정했더니 염색체가 너무 과도하게 변하여 결국 랜덤으로 숫자가 생성되는 수준이었다.


깊은 복사

돌연변이까지 추가했으나 1에는 근접하지만 절대 1만 나오는 경우가 없었다. 적합도가 갑자기 올라가기도하고... 평생을 돌리면 나오기야 하겠지만 그러면 결국 랜덤으로 때려맞추는 수준에 불과하다.

(0, 'Gen : ', [[7, 1, 3, 0, 7, 9, 1, 8, 8, 1], [1, 4, 8, 4, 5, 9, 0, 4, 6, 0], [7, 7, 7, 5, 5, 7, 3, 2, 7, 2], [7, 1, 2, 1, 9, 4, 9, 8, 4, 9], [3, 1, 3, 5, 4, 9, 7, 0, 3, 5, 0]])
(1, 'Gen : ', [[1, 4, 8, 4, 4, 9, 0, 0, 3, 0], [1, 4, 3, 4, 5, 9, 7, 0, 6, 0], [3, 4, 8, 4, 4, 9, 0, 4, 3, 5], [1, 1, 3, 4, 4, 9, 7, 4, 6, 0], [1, 1, 3, 4, 5, 9, 0, 4, 3, 5]])
(100, 'Gen : ', [[0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2]])
(1000, 'Gen : ', [[1, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1]])

알고리즘엔 문제가 없었으나 가장 큰 문제가 되었던건 파이썬 대한 이해였다. 파이썬에는 메모리를 참조하여 같은 값을 가지는 얇은 복사와 다른 메모리를 참조하는 깊은 복사가 있는데, 리스트에선 기본적으로 앝은 복사가 일어나므로 변이가 일어났을 경우 그게 다음 세대에게 큰 영향을 주고 있었다. 따라서 copy 라이브러리를 이용하여 염색체 복사를 깊은 복사로 변경하였더니 성공적으로 동작하였다.


소스코드
import random
import numpy
import copy

def evalution(chromos):
    evalution_value = [0 for __ in range(5)]
    
    dominant = 1

    for i in range(5):
        m_sum = 0
        for j in range(10):
            if chromos[i][j] > dominant:
                m_sum += chromos[i][j] - dominant
            else:
                m_sum += dominant - chromos[i][j]
        evalution_value[i] = m_sum
    
    return evalution_value

if __name__ == '__main__':
    chromos     = [[0 for __ in range(10)] for __ in range(5)]
    new_chromos = copy.deepcopy(chromos)

    mutation = 0.01
    
    parent_cromo_index = [0, 0]
    generation = 0

    # 1 Generation
    for i in range(5):
        for j in range(10):
            chromos[i][j] = random.randint(0, 9)

    generation += 1

    while True:
        if generation > 1000:
            # Force stop
            break

        evalution_value = evalution(chromos)
        
        for i in range(2):
            parent_cromo_index[i] = numpy.argsort(evalution_value)[i]

        done = False
        for i in range(5):
            if evalution_value[i] == 0:
                done = True
                break
        if done == True:
            break

        # 염색체 교차 및 돌연변이
        for i in range(5):
            for j in range(10):
                if random.random() < mutation:
                    new_chromos[i][j] = random.randint(0, 9)
                else:
                    new_chromos[i][j] = chromos[parent_cromo_index[random.randint(0, 1)]][j]

        chromos = copy.deepcopy(new_chromos)

        print("=============================")
        print(generation, "Gen : ", chromos)
        print('evalution value :', evalution_value)
        print('selected parent :', parent_cromo_index)

        generation += 1
        
    print("Done!!!")
😥 작성된 댓글이 없습니다!
댓글을 작성하기 위해 로그인이 필요합니다.