유전 알고리즘 2.유전 알고리즘 구현하기

전 시간에 유전 알고리즘과 유전에 대하여 이야기했는데, 이번 시간에는 유전 알고리즘을 파이썬을 이용하여 직접 구현해 보겠습니다.

 

1.요구조건

유전 알고리즘을 이용하여 모든 문제를 풀 수 있는 것은 아니다.

1) 해를 유전자의 형식으로 표현할 수 있어야 한다.

2) 이 해가 얼마나 적합한지를 적합도 함수를 통해 계산할 수 있어야 한다.

3) 해의 특성을 숫자의 배열이나 문자열과 같은 자료 구조로 표시할 수 있어야 한다.

 

2. 숫자의 합이 20이 되게 만들기

다음 숫자 카드 중 세 개를 골라서 합이 20이 되도록 만들어 보자.

각 숫자카드는 유전자로 가정한다. 세 개의 카드를 뽑아 그 합을 구한 뒤 20이 되는지 확인한다. 예를 들어 (1, 5, 3)의 카드를 뽑았다면 합은 9이고 20에서 9의 차이는 11이 되는데 이것을 적합도라고 한다. 적합도가 0이 되면 문제를 해결하는 것이다.

 

3. 1세대(객체 생성(4개) → 자연선택(2개) → 교차번식(4개))

1) 주사위 던지기 구현

import numpy as np
np.random.seed(220329) 
dice = np.array([1, 5, 6, 8, 3, 7, 3, 5, 9, 0], dtype=np.int32)

def throw_dice(array):
  value = np.random.choice(array, 1)
  return value

print(throw_dice(dice))

코드설명

1 - import numpy as np : 넘파이(numpy) 라이브러리를 사용, 별칭을 np로 사용

2 - np.random.seed(숫자) : 마인크래프트 시드 부여처럼 랜덤에 시드를 부여하면 다른 사람이 똑같은 시드로 사용했을 때 같은 결과를 만들어낼 수 있다.

3 – dice : 주사위로 던진 카드값을 넘파이 array(배열) 형태로 구현함.

5 – throw_dice(array) : 주사위 던지기 함수 구현

6 – np.random.choice(array, 1) : array 배열에서 임의의 수 1개를 추출

9 – throw_dice 함수에 dice를 전달하여 결과를 출력함.

 

 

2) 유전자를 가진 객체 생성하기

위의 예제처럼 (1, 5, 3) 식의 유전자로 구성된 객체를 생성해야 한다.

def create_genome():
  genome = np.array([])
  for i in range(3):
    value = throw_dice(dice)
    genome = np.concatenate([genome, value], axis=0)
  return genome

print(create_genome()) # [7, 6, 9]

코드설명

2 - genome : 유전자 정보를 저장할 객체 genome 생성

4 – value : throw_dice 함수를 통해 주사위의 카드값을 가져온다.

5 – np.concatenate([genome, value], axis=0) axis=0을 기준으로 genome과 value를 합친다.

 

1) axis는 ‘축’을 뜻한다. 우리는 현재 가로-세로로 자료가 되어 있는 행렬(Matrix) 자료구조를 사용하고 있다. 아래 그림을 참고해 보자.

 

2) concatenate 메소드는 배열을 결합해주는 것인데 여기에 설명하기에는 여백이 너무 좁다. https://pybasall.tistory.com/33 여기 글을 읽어보자.

 

 

3) 유전체 객체 4개 생성

3개의 유전자를 가진 객체 4개를 생성해 보자.

# 1세대 유전체 객체 4개 생성
gen_list = np.array([])
for i in range(4):
  value = create_genome()
  gen_list = np.concatenate([gen_list, value], axis=0)

print(gen_list)
gen_list = np.reshape(gen_list, (-1, 3))
print(gen_list)

코드설명

2 – gen_list : 유전체 4개를 담을 빈 배열 생성

4 – value : 유전체 1개 생성 (7, 6, 9) 이런식으로 생성됨.

5 – concatenate 메서드를 이용하여 가로로 연결, 이를 4번 시행함.

7 – 결과를 확인해 보면 [3. 1. 8. 6. 8. 8. 6. 3. 9. 8. 0. 7.] 출력,

8 – np.reshape를 이용하면 배열을 2차원(가로, 세로)로 만들 수 있다. reshape는 굉장히 많이 사용하는 메서드인데 ★자료를 더 찾아보고 반드시 공부★하길 바란다.

=> reshape 전 gen_list는 (12, ) 형태의 배열인데 유전자 3개가 들어 있는 유전체 4개를 생성하기 위해서는 (4, 3) 형태로 만들어야 한다. (가로, 세로) 모양. 따라서 (-1, 3)을 하면 세로의 개수는 3개로 유지하면서 나머지는 알아서 만들어라 라는 뜻으로 받아들이고 배열을 재배치한다. ( 궁금하면 https://domybestinlife.tistory.com/149 참고) 결과값을 확인해 보면 (12, ) → (4, 3)으로 재배치되었다.

 

<출력결과>
[3. 1. 8. 6. 8. 8. 6. 3. 9. 8. 0. 7.]
[[3. 1. 8.]
 [6. 8. 8.]
 [6. 3. 9.]
 [8. 0. 7.]]

 

 

4) 적합도 계산

우리의 목표는 카드의 합이 20이 되는 것이 목표이므로 적합도 식은 이렇게 정의해 보자.

접합도 = |20 - 객체의 요소(유전자숫자)합|

# 적합도 계산
def Appropriate(list_gen):
  appro_list = np.array([])
  for gen in list_gen:
    gen_sum = np.sum(gen)
    appro = np.array([np.abs(20-gen_sum)])
    appro_list = np.concatenate([appro_list, appro], axis=0)
  return appro_list

print(Appropriate(gen_list))

코드설명

2 – Appropriate(list_gen) : 적합도 계산 함수 정의, 위에서 생성한 4개의 유전자 객체를 담은 배열인 list_gen을 입력받는다.

3 – appro_list : 계산된 적합도를 담을 배열 생성

4 – for gen in list_gen: 4개의 유전자 객체를 한 개씩 꺼내 반복문을 실행한다.

5 – gen_sum : np.sum() 메서드를 이용해 객체의 숫자끼리의 합을 진행한다.

(예시 np.sum([3, 1, 8]) = 12)

6 – appro : 객체의 숫자 합을 이용해 적합도 계산, 절대값은 np.abs() 메서드를 이용한다.

7 – appro_list : 계산된 적합도를 np.concatenate 메서드를 이용해 가로로 이어 붙인다.

8 – return appro_list : 객체 4개에 대한 적합도를 반환한다.

 

 

5) 자연선택 구현하기

적합도가 작은 객체는 숫자 합이 20에 가깝다는 뜻이다. 자연선택을 ‘적합도가 0에 가까운 유전자 객체 2개만 살아남기’로 설정하자. 4개 중 2개만 살아남아 자손을 번식할 수 있는 기회를 갖게 되고, 나머지 2개는 생존에 불리하여 번식을 하지 못하게 된다. 이를 코드로 구현해 보자

# 개체 중 적합도가 가장 작은 2개의 객체 선택하기
def Select_appropriate(list_gen):
  list_appro = Appropriate(list_gen)
  argsort = list_appro.argsort()
  two_genlist = np.array([])
  two_genlist = np.concatenate([two_genlist, list_gen[argsort[0]]], axis=0)
  two_genlist = np.concatenate([two_genlist, list_gen[argsort[1]]], axis=0)
  two_genlist = np.reshape(two_genlist, (-1, 3))
  return two_genlist

print("유전 객체 4개")
print(gen_list)
print("각 적합도 계산")
print(Appropriate(gen_list))
genlist_two_origin = Select_appropriate(gen_list)
print("적합도가 가장 작은 2개 선택")
print(genlist_two_origin)

코드설명

2 – Select_appropriate(list_gen) : 적합도에 따라 유전자 객체를 2개 선택하는 함수로 유전자 객체 4개인 list_gen을 입력으로 받는다.

3 – list_appro : 입력받은 유전자 객체 4개인 list_gen에 대한 적합도 배열이다.

4 – argsort : 배열 요소의 크기 순서(오름차순)로 index를 반환한다.

 

5 – two_genlist : 적합도가 작은 2개의 유전자 객체를 담을 배열 선언

6, 7의 list_gen[argsort[0]], list_gen[argsort[1]] : 적합도가 가장 작은 2개의 유전자 객체를 반환함. 원리를 살펴보면 아래와 같다.

 

6, 7 np.concatenate를 이용해 적합도가 작은 2개의 배열을 결합한다.

8 – 배열을 1차원에서 2차원으로 변경(reshape) 한다. 6,7,8에 대한 원리는 아래와 같다.

 

 

 

6) 유전자 객체 2개의 교차 구현하기

생존한 유전자 객체는 자손을 남긴다. 일반적인 유전 물질은 감수분열하여 부모의 유전물질을 반반씩 받는다. 자식은 부모와 비슷하지만 다른 이유는 이것이다. 간단하게 구현하기 위해 자손을 남길 때 부모의 물질 중 일부를 서로 교차하여 자손을 생성하는 것으로 표현한다. 만약 두 번째 유전자를 서로 교차했을 때, 이를 그림으로 표현하면 아래와 같다.

# 유전자 객체 2개의 교차 구현하기
def intersect_genorm(list_gen, state):
  temp_list = np.array([])
  for gen in list_gen:
    value = gen[state]
    value = np.array([value])
    temp_list = np.concatenate([temp_list, value], axis=0)
  
  copy_list = list_gen.copy()
  copy_list[0][state] = temp_list[1]
  copy_list[1][state] = temp_list[0]
  return copy_list

print("두번째 자리 교차 전")
print(genlist_two_origin)

intersect_gen = intersect_genorm(genlist_two_origin, 1) # 두 번째 자리 교차
print("두번째 자리 교차 후")
print(intersect_gen)

코드설명

2 – intersect_genorm(list_gen, state) : 유전자 객체를 교차하는 함수로 정의한다. list_gen은 2개의 유전 객체 배열이고 state는 교차 위치이다. 0은 첫 번째, 1은 두 번째, 2는 세 번째 위치를 의미한다. (state는 교차 위치 인덱스 번호이다.)

3 – temp_list : 교차할 유전자를 담을 빈 배열을 선언한다.

4~7 list_gen에 대한 for 문을 돌려 state의 인덱스 번호에서 유전 정보를 빼 내고 np.concatenate 함수를 이용하여 1차원 배열로 결합한다. 실행 과정은 아래와 같다.

 

9 – copy_list = list_gen.copy() : list_gen 객체를 카피한다. 만약 카피(copy())를 하지 않으면 list_gen을 직접 참조하는 문제가 발생하여 카피해야 한다.

10~11 copy_list 의 교체 위치의 값을 temp_list의 요소 값으로 교체해 준다.

아래 그림을 참고해 보자.

 

 

 

 

4. 2세대(객체 (4개) → 자연선택(2개) → 교차번식(4개) + 돌연변이)

1세대에서 객체 4개에 대해 적합도에 따라 자연선택을 하여 2개를 만든 후, 번식을 하여 2명의 자손을 낳아 다시 4개가 되었다. 부모(객체 2개)와 자식(객체 2개)에 대해 다시 자연선택과 교차를 실시한다.

 

1) 부모와 자식을 합쳐 객체 4개 만들기

# 4개의 객체 중 적합도가 가장 작은 유전 객체 2개 + 유전 객체 2개 교차 구현한 것 합치기
def combine_genome(list_1, list_2):
  return np.concatenate((list_1, list_2), axis=0)

combine_gen = combine_genome(genlist_two_origin, intersect_gen)
print("1세대 두번째 자리 교차 전 + 교차 후")
print(combine_gen)

genlist_two_origin은 자연선택에 따라 살아남은 객체 2개[[6,8,8], [6,3,9]] 이고

intersect_gen은 genlist_two_origin의 교차에 의한 자손 번식 객체 2개 [[6,3,9], [6,8,9]]이다.

np.concatenate() 함수를 이용하여 둘을 다시 결합해 준다.

 

2) 자연선택

# 4개의 개체 중 적합도가 가장 작은 2개 고르기
print("1세대 두번째 자리 교차 전 + 교차 후")
print(combine_gen)
print("각 적합도 계산")
print(Appropriate(combine_gen))
genlist_two = Select_appropriate(combine_gen)
print("적합도가 가장 작은 2개 선택")
print(genlist_two)

4개의 객체(부모 2개 + 자식 2개)에 대해 적합도를 통한 자연선택을 실시한다.

경쟁 결과 부모의 적합도는 각각 2, 2, 자식의 적합도는 3, 3, 이므로 생성된 자식은 자연선택에서 제외되었고 부모가 살아남았다.

 

 

3) 교차하기

# 세 번째 자리끼리 교차
intersect_gen = intersect_genorm(genlist_two, 2)
print("세 번째 자리 교차 후")
print(intersect_gen)

1세대의 부모가 낳은 자식들은 2세대에서 살아남지 못했다. 이번엔 세 번째 자리끼리 교차를 해 보자. 부모가 [[6,8,8,], [6,3,9]] 이므로 자식은 [[6,6,9], [7,6,9]]이다.

 

 

4) 돌연변이 일으키기

돌연변이는 객체의 3 번째 유전자 숫자를 무작위로 변경한다. 돌연변이는 실제로 진화의 큰 축을 담당한다. 이를 파이썬 코드로 어떻게 표현할 수 있을까? 1~12의 숫자를 가진 정12면체 주사위를 굴려 주사위 숫자가 3, 5, 7이 나온다면 돌연변이를 일으킨다고 가정하자.

# 주사위 숫자가 3, 5, 7 일 때 돌연변이 일으키기
def Mutation(list_gen):
  mutant_list = list_gen.copy()
  num_dice = np.random.choice(np.arange(1, 13), 1)
  print(num_dice[0])
  if num_dice[0] == 3 or num_dice[0] == 5 or num_dice[0] == 7:
    print("돌연변이 발생")
    for mutant in mutant_list:
      mutant_dice = throw_dice(dice)
      print("주사위 숫자 카드번호", mutant_dice[0])
      mutant[2] = mutant_dice[0]
  else:
    print("돌연변이 없음")
  return mutant_list

print(intersect_gen)
mutante_gen = Mutation(intersect_gen)
print(mutante_gen)

코드설명

2 – Mutation(list_gen) : 돌연변이를 일으킬 함수를 선언한다. 돌연변이 대상 함수는 list_gen이다.

3 – mutant_list : list_gen을 카피하여 돌연변이를 일으킬 대상 배열을 생성

4 – num_dice : 주사위를 굴렸을 때 나온 값이며 배열로 되어 있다.

np.arange(1, 13)은 [1,2,3,4,5,6,7,8,9,10,11,12]를 의미한다. 이 중 1개를 선택한다.

6 – 만약 주사위 값이 3 또는(or) 5 또는(or) 7이라면 if문에 진입한다.

8~11 mutant_dice : 주사위를 던져 나온 카드 값으로 돌연변이 값이다.

원래 객체의 3번째 자리 유전자 숫자인 mutant[2]를 mutant_dice로 변경한다.

이를 순서대로 그림으로 표현해 보자.

 

 

 

 

5. 3세대(객체 (4개) → 자연선택(2개) → 1세대와 비교해 보기)

2세대에서 객체 4개에 대해 적합도에 따라 자연석택을 하여 2개를 만들 후, 번식을 하였고 이 과정에서 돌연변이가 발생하여 자식 2명은 변이가 되었다. 부모(객체 2개)와 자식(객체 2개)에 대해 다시 자연선택과 교차를 실시하고 1세대와 비교해 본다.

 

1) 부모와 자식을 합쳐 객체 4개 만들기

# 4개의 객체 중 적합도가 가장 작은 유전 객체 2개 + 유전 객체 2개 교차 구현한 것 합치기
combine_gen = combine_genome(genlist_two, mutante_gen)
print("돌연변이 발생 전 2개 + 발생 후 2개")
print(combine_gen)

genlist_two는 자연선택에 따라 살아남은 부모 객체 2개[[6,8,8], [6,3,9]] 이고

mutante_gen은 교차와 돌연변이에 의한 번식한 자식 객체 2개 [[6,8,6], [6,3,3]]이다.

앞에서 정의한 combine_genome 함수를 이용하여 둘을 다시 결합해 준다.

 

 

2) 자연선택

# 4개의 개체 중 적합도가 가장 작은 2개 고르기
print("돌연변이 발생 전 2개 + 발생 후 2개")
print(combine_gen)
print("적합도 계산")
print(Appropriate(combine_gen))
genlist_two = Select_appropriate(combine_gen)
print("적합도가 가장 작은 2개 선택")
print(genlist_two)

4개의 객체(부모 2개 + 자식 2개)에 대해 적합도를 통한 자연선택을 실시한다.

경쟁 결과 부모의 적합도는 각각 2, 2, 자식의 적합도는 0, 8 이므로 적합도가 0인 자식과 2인 부모([6,8,8])이 살아남았다.

 

 

3) 교차하기

# 첫 번째 자리끼리 교차
intersect_gen = intersect_genorm(genlist_two, 0)
print("첫 번째 자리 교차 후")
print(intersect_gen)

이번엔 첫 번째 자리끼리 교차를 해 보자. 부모가 [[6,8,6,], [6,8,8]] 이므로 자식은 [[6,8,6], [6,8,8]] 그대로이다.

 

 

4) 1세대와 비교하기

1세대에서 자연선택으로 살아남은 객체 2개와 3세대 교차로 태어난 객체 2개와 적합도를 비교해 보자.

#1세대 genlist_two_origin 과 3세대 결과인 genlist_two와 적합도를 비교해 보자.
print("1세대 적합도 가장 작은 2개와 적합도")
print(genlist_two_origin)
print(Appropriate(genlist_two_origin))
print("3세대 적합도 가장 작은 2개와 적합도")
print(intersect_gen)
print(Appropriate(intersect_gen))

1세대 : [[6. 8. 8.], [6. 3. 9.]] 적합도는 각각 [2. 2.]

3세대 : [[6. 8. 6.], [6. 8. 8.]] 적합도는 각각 [0. 2.] → 적합도가 줄어들었다!

 

 

 

6. 여러 세대를 반복 훈련할 수 있는 코드 작성하기

자연선택 → 번식(교차) → (확률적 돌연변이) → 반복을 하다보면 객체 숫자합이 20이 가까워지지 않을까? 이를 구연해 보자. 그 전에 돌연변이 함수를 재정의해야 한다. ★유전 알고리즘에서 중요한 변인(hyperparameter)중 하나는 돌연변이를 발생 확률★ 이다. 돌연변이가 너무 크면 적합도로 수렴이 잘 되지 않을 가능성이 높고 돌연변이가 너무 낮으면 훈련에 많은 시간이 필요하다. 훈련을 여러 번 돌려보면서 적당한 돌연변이 확률을 찾아야 한다.

기존 돌연변이 확률의 경우 3, 5, 7 이므로 약 25%이다. 너무 큰 것 같다. 주사위 값이 5일때만 돌연변이를 발생한다고 하면 1/12 이므로 약 8.33%이다. 이 돌연변이 확률도 큰 값인데 일단 이렇게 진행해 보자.

#돌연변이 다시 정의(너무 많음), 주사위숫자가 5일때만 실행
def Mutation(list_gen):
  mutant_list = list_gen.copy()
  num_dice = np.random.choice(np.arange(1, 13), 1)
  if num_dice[0] == 5 :
    # 돌연변이를 일으킬 위치(인덱스 0, 1, 2)를 랜덤하게 생성
    mutant_state = np.random.choice(np.arange(0, 3), 1)
    for mutant in mutant_list:
      mutant_dice = throw_dice(dice)
      mutant[mutant_state[0]] = mutant_dice[0]
  return mutant_list

# 1세대 유전체 객체 4개 생성
gen_list = np.array([])
for i in range(4):
  value = create_genome()
  gen_list = np.concatenate([gen_list, value], axis=0)

genlist_four = np.reshape(gen_list, (-1, 3))
genlist_two_origin= Select_appropriate(genlist_four)
print('genlist_two_origin', genlist_two_origin)

epochs = 100

코드설명

돌연변이 발생 함수를 제외하고 객체 생성과정은 동일하다.

5 – if num_dice[0] == 5: 주사위 값이 5일 때만 돌연변이가 발생한다.

7 – mutante_state : 돌연변이를 일으킬 위치도 랜덤하게 설정한다.

20 – genlist_two_origin = 4개의 객체 중 적합도에 따라 선택된 2개의 유전자 객체이다.

훈련 전 4개의 객체 중 적합도에 따라 2개를 선택해서 관찰하기 위한 것이다.

23 – epochs : 훈련 횟수를 100회로 설정한다. 즉 100세대까지 훈련시킨다는 뜻이다.

for epoch in range(epochs):
  genlist_two= Select_appropriate(genlist_four)
  change_num = np.random.choice(3, 1)
  intersect_gen = intersect_genorm(genlist_two, change_num[0]) 
  intersect_gen = Mutation(intersect_gen)
  genlist_four = combine_genome(genlist_two, intersect_gen) 

genlist_last_two= Select_appropriate(genlist_four)
print('genlist_last_two', genlist_last_two)

코드설명

여기 있는 코드들은 한 줄 한 줄 매우 매우 중요하다.

• 1 – 설정한 epochs 만큼 반복한다.
• 2 – 처음 생성한 객체 4개인 genlist_four에 대해 적합도에 따라 2개를 선택하고 이를
• genlist_two로 선언한다.
• 3 – np.random.choice(3, 1)은 0, 1, 2, 숫자 중에 1개를 선택한다는 뜻이다.
• 4 – genlist_two에 대해 교차를 진행한다. 교차 위치는 change_num에서 설정한 값으로 한다. 즉, 교차의 위치는 0, 1, 2 중 랜덤이다.
• 5 – 돌연변이를 실시한다. 확률에 따라 돌연변이가 될 수도, 안될 수도 있다. 돌연변이가 됬는지 안됬는지 당장 보기는 어렵지만 일단 intersect_gen 으로 정의한다.
• 6 – 부모 객체인 genlist_two와 교차 및 돌연변이가 발생한 자식 개체 intersect_gen을 결합하여 genlist_four로 다시 정의한다.
• 8 – epochs 만큼 반복하면 for문을 빠져나온다. 마지막 genlist_four에 대한 적합도가 가장 작은 객체 2개를 선택하고 확인해 본다.

결과를 확인해보자.

 

 

6. 전체 코드

GeneSimulator-1.ipynb

0.02MB

 

 

 

 

다운받아서 쓰시면 됩니다