파이썬에서 만들었던 유전 알고리즘을 자바스크립트로 단순히 번역해 본 결과물이다. 자바스크립트에 익숙해 지고 싶어서 해봤는데 의외로 시간이 오래 걸렸다. 약간의 기초적인 지식은 알고 있다고 생각했는데 … 아니었나보다.

파이썬에 있는 numpy.argsort()가 없어서 일단 애먹었고, 자바스크립트 정렬에서도 좀 애를 먹었다. 문자 정렬은 잘되는데 숫자 정렬은 정렬에 또 다른 조취를 취해 주어야 한다. 해결한 과정은 하단에 기록하도록 해야겠다.

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
var 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, 0]];
var 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]];

var evalution = [0, 0, 0, 0, 0];
var evalution_sort = [0, 0, 0, 0, 0];
var select = [0, 0];
var generation = 0;
var mutation = 0.05;

var dominent = prompt("Dominent Genome : ");

for (var i = 0; i < 5; i++) {
    for (var j = 0; j < 10; j++) {
        chromo[i][j] = Math.floor(Math.random() * 10);
    }
}

generation++;
document.write("Generation " + generation + " : <br>");
for (var i = 0; i < 5; i++) {
    document.write("[" + chromo[i] + "]<br>");
}

while (1) {
    for (var i = 0; i < 5; i++) {
        var m_sum = 0;
        for (var j = 0; j < 10; j++) {
            if (chromo[i][j] > dominent) {
                m_sum += chromo[i][j] - dominent;
            }
            else {
                m_sum += dominent - chromo[i][j];
            }
        }
        evalution[i] = m_sum;
    }

    var done = false;
    for (var i = 0; i < 5; i++) {
        if (evalution[i] == 0) {
            done = true;
            break;
        }
    }
    if (done) break;

    evalution_sort = evalution.slice();
    evalution_sort.sort(function (a, b) { return a - b });

    for (var i = 0; i < 2; i++) {
        select[i] = evalution.indexOf(evalution_sort[i]);
        if (select[0] == select[1] && i == 1) {
            select[i] = evalution.indexOf(evalution_sort[i], select[0] + 1);
        }
    }

    document.write("Evaluation : " + evalution + "<br>Select Chromosome : " + select + "<br>");

    for (var i = 0; i < 5; i++) {
        for (var j = 0; j < 10; j++) {
            if (Math.random() < mutation) {
                new_chromo[i][j] = Math.floor(Math.random() * 10);
            }
            else {
                new_chromo[i][j] = chromo[select[Math.floor(Math.random() * 2)]][j];
            }
        }
    }

    chromo = JSON.parse(JSON.stringify(new_chromo));

    generation++;
    document.write("Generation " + generation + " : <br>");
    for (var i = 0; i < 5; i++) {
        document.write("[" + chromo[i] + "]<br>");
    }

    if (generation > 1000) {
        break;
    }
}

문제를 해결한 과정

  • argsort가 없어서 적합도 배열을 복사하여 정렬한 다음 indexOf 함수를 이용하였으나 중복된 염색체가 선택되는 문제가 있었다. 그래서 선택된 염색체가 같은 경우 이전에 선택된 익덱스 뒤부터 검색할 수 있게끔 하였다.
    1
    2
    3
    
    if (select[0] == select[1] && i == 1) {
      select[i] = evalution.indexOf(evalution_sort[i], select[0] + 1);
    }
    
  • sort를 이용하여 정렬하면 기본적으로 오름차순으로 정렬이 되는데 2자리 이상은 잘 정렬되지만 갑자기 제일 작아야하는 1자리 숫자가 뒤에 나오는 현상이 있었다. 그래서 적합도가 10 이하로 내려가지 않아서 당황스러웠다. 찾아보니 유니코드 기반으로 정렬을 한다고 한다. 그래서 숫자는 약간의 조취를 취해주어야 한다고 한다.
    1
    
    evalution_sort.sort(function (a, b) { return a - b });
    
  • 자바스크립트도 대입으로 복사를 하는 경우 기본적으로 얕은 복사가 진행된다. 자바스크립트에서 깊은 복사를 하는 방법은 두가지가 있었다. 두가지의 정확한 차이를 모르겠으나 염색체에 JSON을 쓰지 않으면 제대로된 결과값이 나오지 않았고, 적합도에 JSON을 사용하면 제대로 된 결과가 나오지 않았다. 나중에 한번 비교를 해봐야 할 듯.
    1
    2
    
    evalution_sort = evalution.slice();
    chromo = JSON.parse(JSON.stringify(new_chromo));
    
WRITTEN BY

배진오

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