유전 알고리즘을 만들때 가장 먼저 해야할 일은 항상 evoluation 함수를 만드는 것이며 evaoluation 함수는 추악한 오리와 아름다운 백조를 분리하는 작업이다.

저번에 만들었던 소스코드는 굉장히 간단한 내용이었기에 큰 어려움이 없었다. 조금더 유전 알고리즘에 익숙해지기 위해서 새로운 소스코드를 작성하고자 한다.

Project2.

배낭에 가장 효율적인 물건 채우기

  • 가방의 공간은 10으로 한정
  • 각 물건의 부피와 가치
    • 3, 3
    • 5, 2
    • 2, 4
    • 1, 1
    • 4, 2
    • 5, 4
    • 3, 2
    • 3, 4
  • 알고리즘 구성
    1. 최초 세대 생성
    2. 적합도 평가
    3. 교배 및 돌연변이
    4. 적합도 평가
    5. 만번반복
  • Evoluation 함수
    • 물건의 부피당 가치를 환산

이번에는 완료조건을 따로 만들지 않으려고 한다. 사실은 귀찮아서… ㅎ

Source Code.

먼저 최초세대를 생성하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
chromo = [[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]]]
new_chromo = [[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]],[[0,0,0,0,0],[0,0,0,0,0]]]

#가방 무게 제한
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

가방의 크기는 10으로 제한을 주었고 염색체는 3차원 배열로 구성되어 크기 배열과 가치 배열을 각각 가지고 있다.

1
[[[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]]]

아이템은 정상적으로 들어가는 것 같다. 이제 각 염색체의 부피당 가치를 환산하여 적합도를 평가하고 가장 적합한 두 염색체를 선택하여 교차시킬 것이다.

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
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
[1, 5, 1, 1, 1], [1, 2, 1, 1, 1]

하나 또 잊고 있었던게 물건을 중복되지 않게 넣게 했어야 하는데… 이건 뭐 2차원 염색체 진화에 불과하지 않은가… 또 어제 만들었던 유전자들은 좋은건 바로바로 적용하는데 얘네는 우성이 나와도 묻혀버리는 경우가 많아서 되려 퇴화하기도 했다. 교차할때 뭔가 새로운 시도를 해야할 듯… 중복되지 않는거랑 교차에 새로운 방법을 넣는건 내일 해보자!


중복이 없는 상황이니 언뜻 봐도 부피 2에 가치 4인 애들로 가득 채워져야 하는데 저렇게 선택을 했다는게 의심스러워 적합도 평가하는 부분을 봤더니 역시나

1
2
evoluation[i] += float(chromo[i][0][j]) / chromo[i][1][j]
evoluation[i] += float(chromo[i][1][j]) / chromo[i][0][j]

반대로 했었다. 뭐 반대로 했어도 사실 큰 문제가 없는게 어찌됬든 가장 가치있는 물건을 찾아 넣는 것이니 그렇다만 조건문에서 가방을 제한한다는게 가치를 제한한 꼴이 되었다. 어찌 되었든 바꾸고보니 애들이(?) 큰 문제없이 진화해 주는 듯 하다. 중복으로 선택 못하게만 만들면 될 듯! 소스코드 원문

WRITTEN BY

배진오

하고싶은 건 다 하면서 사는게 목표
im@baejino.com

comments powered by Disqus