어제 만든 가방 채우기는 물건이 같은 부피의 같은 가치가 있는 물건이 끝없이 나열되어있고 가방에 크기에 알맞게 넣는 알고리즘이었다. 이번에는 중복없이 한개씩 제공되는 물건중에 무엇을 챙겨야 할 지 결정하는 알고리즘이다. (원래는 이게 목적이었는데 어제 중요한걸 빼먹어 버렸다.)

여행

예로들어 어디론가 놀러 가거나 급박한 상황이 발생했을때 물건에 다음과 같이 부피와 가치를 지정할 수 있을 것이다.

  • 지도, 부피:2, 가치:3
  • 침낭, 부피:4, 가치:5
  • 물통, 부피:2, 가치:6
  • 에너지바, 부피:1, 가치:4

그 외 더욱 많은 물건이 있으나 가방의 크기는 단지 10칸 뿐이다. 가장 합리적이고 완벽에 가까운 소지품을 꾸린다고 가정을 해보는 것이다. 가령 어제 만든 코드는 에너지바만 잔뜩 챙기고 떠나버리는 거지만 이번에는 단 하나씩만 선택하는 코드다.

어제 만든 코드에서 추가된 내용은 단지 중복으로 넣는 것을 방지하는 것 뿐이다.

1
2
3
4
5
6
7
chromo = [
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]]
    ]

먼저 염색체 배열을 하나 더 늘려주었다. 마지막 배열에는 물건의 인덱스 값을 집어넣을 것이다. 랜덤으로 값을 추출할때 인덱스 값도 고려하여 물건을 뽑게될 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
for i in range(5):
    limit_check = 0
    for j in range(5):
        item_select = random.randint(0,len(item)-1)
        while item_select in chromo[i][2]:
            item_select = random.randint(0,len(item)-1)
        if limit_check + item[item_select][0] < bag_limit+1 :
            limit_check + item[item_select][0]
            chromo[i][0][j] = item[item_select][0]
            chromo[i][1][j] = item[item_select][1]
            chromo[i][2][j] = item_select
        else :
            break

초기 세대를 생성할때 중복없이 물건을 무작위로 뽑게된다. 중복을 방지하는 핵심 코드는 다음과 같다.

1
2
3
item_select = random.randint(0,len(item)-1)
while item_select in chromo[i][2]:
    item_select = random.randint(0,len(item)-1)

랜덤으로 뽑은 숫자가 염색체 3번째 배열에 존재하는 숫자가 아닐때까지 뽑게된다. 변이에도 같은 방법을 사용하여 중복을 방지했으나 결과값엔 중복된 결과가 잔뜩 나왔다. 이유는 교차할때 중복된 물건인지 체크하지 않았기 때문이었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if random.random() > mutation :
    temp = random.randint(0,1)
    if limit_check + chromo[select[temp]][0][j] < bag_limit+1 :
        if chromo[select[temp]][2][j] in chromo[i][2] :
            # break or continue
        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]
        new_chromo[i][2][j] = chromo[select[temp]][2][j]
    else :
        for k in range(j,5):
            new_chromo[i][0][k] = 0
            new_chromo[i][1][k] = 0
            new_chromo[i][2][k] = -1
        break

중복된 인덱스일때 break를 넣으면 중복도 안되고 무게 초과도 안되지만 유전도 안된다. continue를 넣으면 중복은 가끔 되고 무게도 가끔 넘는다(?)… 어디를 어떻게 손봐야할지 모르겠다. break를 넣어도 값이 나오긴 하지만 글쎄… continue로 해결보고 싶은데… 어떻게 시도해도 값이 넘거나 무게가 넘거나 둘 중 하나의 문제가 꼭 발생한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import random
import copy
import numpy

chromo = [
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]]
    ]
new_chromo = [
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]],
    [[0,0,0,0,0],[0,0,0,0,0],[-1,-1,-1,-1,-1]]
]

evoluation = [0,0,0,0,0]
select = [0,0]
mutation = 0.05
bag_limit = 10
item = [[3,3],[5,2],[2,4],[1,1],[4,2],[5,4],[3,2],[3,4],[1,2],[3,7]]

for i in range(5):
    limit_check = 0
    for j in range(5):
        item_select = random.randint(0,len(item)-1)
        while item_select in chromo[i][2]:
            item_select = random.randint(0,len(item)-1)
        if limit_check + item[item_select][0] < bag_limit+1 :
            limit_check += item[item_select][0]
            chromo[i][0][j] = item[item_select][0]
            chromo[i][1][j] = item[item_select][1]
            chromo[i][2][j] = item_select
        else :
            break

generation = 0
print("Generation",generation,chromo)

while(1):
    for i in range(5):
        for j in range(5):
            if chromo[i][0][j] == 0 :
                break
            evoluation[i] += float(chromo[i][1][j]) / chromo[i][0][j]

    print evoluation

    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] < bag_limit+1 :
                    if chromo[select[temp]][2][j] in chromo[i][2] :
                        break
                    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]
                    new_chromo[i][2][j] = chromo[select[temp]][2][j]
                else :
                    for k in range(j,5):
                        new_chromo[i][0][k] = 0
                        new_chromo[i][1][k] = 0
                        new_chromo[i][2][k] = -1
                    break
            else :
                item_select = random.randint(0,len(item)-1)
                while item_select in chromo[i][2]:
                    item_select = random.randint(0,len(item)-1)
                if limit_check + item[item_select][0] < bag_limit+1 :
                    limit_check += item[item_select][0]
                    new_chromo[i][0][j] = item[item_select][0]
                    new_chromo[i][1][j] = item[item_select][1]
                    new_chromo[i][2][j] = item_select
                else :
                    break

    for i in range(5):
        evoluation[i] = 0

    chromo = copy.deepcopy(new_chromo)
    generation += 1
    print("Generation",generation,chromo)

    if generation > 1000:
        break
WRITTEN BY

배진오

소비적인 일보단 생산적인 일을 추구하며, 좋아하는 일을 잘하고 싶어합니다 :D
im@baejino.com