우선 나는 걱정스럽다. 여기에 적혀진 글과 코드는 그저 이론을 이용해 나만의 방식으로 구현해 본 것이다. 생명공학에 대한 지식 역시 매우 부족하므로 그저 유전이라는 개념을 응용했다고 생각해 주길 바란다. 나열된 코드를 끈임없이 의심하고 절대적으로 신뢰하지 않길 바란다. 기본적인 내용은 이 블로그를 참고했다. 내가 읽어 본 책에 나와있는 것과 유사한 내용인데 좀 더 정리가 잘 된 내용인 것 같다. 간단하게 정리하면 이렇다.
용어의 정리
- 염색체 : 유전 정보를 담은 문자열
- 유전자 : 문자열의 유전 정보
- 교차 : 두 개의 염색체를 조합
- 돌연변이 : 확률적으로 유전자의 정보가 바뀜
- 자손 : 교차와 돌연변이로 생성된 염색체
알고리즘의 흐름
- 최초 염색체 생성
- 세대 적합도 평가
- 세대 교차 및 돌연변이
- 다음 세대 적합도 평가
목표 적합도를 달성했다면 종료하고 달성하지 못했다면 2번으로 돌아간다. 단 어려운 문제의 경우 목표치를 선정하기 어려우므로 반복 횟수를 제한하는 것이 일반적이다.
이론 적용기
유전 알고리즘의 이론은 대략 알겠는데 이걸 어떻게 적용해야할까 싶은 생각이 든다. 그래서 일단 이론을 접목하되 가장 접근하기 쉬운 방법으로 코드를 구현하고자 하였다. 목표는 0-9라는 유전자를 10개 가진 염색체를 생성하고 1이라는 유전자를 우성 유전자로 평가하여 진화하도록 말이다.
적합도 평가
유전 알고리즘을 만들때 가장 먼저 해야할 일은 항상 evoluation 함수를 만드는 것이며 evaoluation 함수는 추악한 오리와 아름다운 백조를 분리하는 작업이다.
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!!!")
가방 채우기
조금 더 유전 알고리즘과 친해지기 위해서 가방에 효율적인 물건을 채우는 것을 구현해보자.
- 가방의 공간은 10으로 한정
- 각 물건의 가치와 크기
- 3, 3
- 5, 2
- 2, 4
- 1, 1
- 4, 2
- 5, 4
- 3, 2
- 3, 4
- 알고리즘 구성
- 최초 세대 생성
- 적합도 평가
- 교배 및 돌연변이
- 적합도 평가
- 만번반복
- Evoluation 함수
- 물건의 부피당 가치를 환산
소스코드
먼저 최초 세대를 생성하였다. 가방의 크기는 10으로 제한하고 물건에 해당하는 염색체들은 2차원 배열로 구성하여 [가치, 크기] 값을 각각 가지도록 하였다.
chromo = [[[0 for __ in range(5)] for __ in range(2)] for __ in range(5)]
new_chromo = [[[0 for __ in range(5)] for __ in range(2)] for __ in range(5)]
#가방 무게 제한
bag_limit = 10
#물건의 [가치, 크기]
item = [[3,3],[5,2],[2,4],[1,1],[4,2],[5,4],[3,2],[3,4]]
for i in range(5):
limit_check = 0
check = False
for j in range(5):
item_select = random.randint(0,7)
for k in range(2):
if k == 0 :
limit_check += item[item_select][k]
if limit_check > bag_limit :
check = True
break
chromo[i][k][j] = item[item_select][k]
if check == True :
break
print(chromo)
[
[
[5, 5, 0, 0, 0],
[2, 4, 0, 0, 0]
],
[
[3, 3, 3, 0, 0],
[2, 4, 3, 0, 0]
],
[
[3, 5, 0, 0, 0],
[3, 4, 0, 0, 0]
],
[
[2, 5, 3, 0, 0],
[4, 4, 2, 0, 0]
],
[
[3, 4, 3, 0, 0],
[4, 2, 4, 0, 0]
]
]
아이템은 정상적으로 들어가는 것 같다. 이제 각 염색체의 부피당 가치를 환산하여 적합도를 평가하고 가장 적합한 두 염색체를 선택하여 교차시킬 것이다.
while(1):
# 적합도 평가
for i in range(5):
for j in range(5):
if chromo[i][0][j] == 0 :
break
evoluation[i] += float(chromo[i][0][j]) / chromo[i][1][j]
# 우성 염색체 선택
for i in range(2):
select[i] = numpy.argsort(evoluation)[i+3]
# 교차 및 돌연변이
for i in range(5):
limit_check = 0
for j in range(5):
# 교차
if random.random() > mutation :
temp = random.randint(0,1)
if limit_check + chromo[select[temp]][0][j] < 10 :
limit_check += chromo[select[temp]][0][j]
new_chromo[i][0][j] = chromo[select[temp]][0][j]
new_chromo[i][1][j] = chromo[select[temp]][1][j]
else :
for k in range(j,5):
new_chromo[i][0][k] = 0
new_chromo[i][1][k] = 0
break
# 돌연변이
else :
temp = random.randint(0, len(item)-1)
if limit_check + item[temp][0] < 10 :
limit_check += item[temp][0]
new_chromo[i][0][j] = item[temp][0]
new_chromo[i][1][j] = item[temp][1]
else :
break
# 적합도 초기화
for i in range(5):
evoluation[i] = 0
# 염색체 복사
chromo = copy.deepcopy(new_chromo)
generation += 1
print("Generation",generation,chromo)
if generation > 10000:
break
컴퓨터가 선정한 잇! 아이템은 다음과 같았다.
[1, 5, 1, 1, 1], [1, 2, 1, 1, 1]
하나 잊고 있었던게 물건을 중복되지 않게 넣게 했어야 하는데... 이건 뭐 2차원 염색체 진화에 불과하지 않은가... 또 숫자 유전자들은 좋은건 바로바로 적용하는데 이 친구들은 우성이 나와도 묻히고 퇴화하기도 했다. 교차할 때 뭔가 새로운 시도를 해야할 것 같다.
중복없는 물건 채우기
이번에는 중복없이 한개씩 제공되는 물건중에 무엇을 챙겨야 할 지 결정하는 알고리즘이다. (원래는 이게 목적이었는데 어제 중요한걸 빼먹어 버렸다.) 예로들어 어디론가 놀러 가거나 급박한 상황이 발생했을때 물건에 다음과 같이 부피와 가치를 지정할 수 있을 것이다. (배열로 하니까 실수를 많이 하는 것 같아서 딕셔너리 형태로 바꾸었다)
items = [
{'size': 3, 'value': 3, 'name': 'Desktop'},
{'size': 2, 'value': 3, 'name': 'Labtop'},
{'size': 1, 'value': 2, 'name': 'Map'},
{'size': 1, 'value': 3, 'name': 'Candy'},
{'size': 4, 'value': 6, 'name': 'Sleeping Bag'},
{'size': 1, 'value': 5, 'name': 'Cell Phone'}
]
그 외 더욱 많은 물건이 있으나 가방의 크기는 단지 10칸 뿐이다. 가장 합리적이고 완벽에 가까운 소지품을 꾸린다고 가정을 해보는 것이다. 가령 어제 만든 코드는 에너지바만 잔뜩 챙기고 떠나버리는 거지만 이번에는 단 하나씩만 선택하는 코드다.
어제 만든 코드에서 추가된 내용은 단지 중복으로 넣는 것을 방지하는 것 뿐이다.
chromos = [
{
'size' : [0, 0, 0, 0, 0],
'value': [0, 0, 0, 0, 0],
'index': [-1, -1, -1, -1, -1]
} for __ in range(5)
]
먼저 염색체 배열을 하나 더 늘려주었다. 마지막 배열에는 물건의 인덱스 값을 집어넣을 것이다. 랜덤으로 값을 추출할때 인덱스 값도 고려하여 물건을 뽑게될 것이다.
for i in range(5):
limit_check = 0
for j in range(5):
selected_item_index = random.randint(0, len(items)-1)
while selected_item_index in chromos[i]['index']:
selected_item_index = random.randint(0, len(items)-1)
if limit_check + items[selected_item_index]['size'] <= bag_size_limit:
limit_check += items[selected_item_index]['size']
chromos[i]['size'][j] = items[selected_item_index]['size']
chromos[i]['value'][j] = items[selected_item_index]['value']
chromos[i]['index'][j] = selected_item_index
else:
break
초기 세대를 생성할때 중복없이 물건을 무작위로 뽑게된다. 중복을 방지하는 핵심 코드는 다음과 같다.
selected_item_index = random.randint(0, len(items)-1)
while selected_item_index in chromos[i]['index']:
selected_item_index = random.randint(0, len(items)-1)
랜덤으로 뽑은 숫자가 염색체 3번째 배열에 존재하는 숫자가 아닐때까지 뽑게된다. 변이에도 같은 방법을 사용하여 중복을 방지했으나 결과값엔 중복된 결과가 잔뜩 나왔다. 이유는 교차할때 중복된 물건인지 체크하지 않았기 때문이었다. 완성된 코드는 이곳에서 확인해 볼 수 있다. (사실 완성은 아직...)
Ghost