개발 유전알고리즘(Genetic Algorithm) 2017/09/07 13:51 by 제가개발자입니다죄송

요즘 인공지능은 딥러닝의 시대이다.
하지만 이전에는 굉장히 다양한 인공지능 알고리즘들이 있었다. 그 중 하나인 유전알고리즘에 대해 설명해려고 한다.
 
 기본적으로 인공지능들은 판별문제, 최적화문제 등에 특화되어 있고 유전알고리즘 역시 최적화 문제를 해결하는데 주로 사용될 수 있다.

 우선 영상을 하나 보자
영상 썸네일

유전적 알고리즘으로 이족보행을 학습시켰다

바쁜 사람들은 3분부터


 이렇듯 유전 알고리즘은 그 이름에서 알 수 있듯, 이번 세대에서 좋은 형질을 다음세대로 넘겨가며 점차 주어진 상황에 잘 적응하도록 만드는 알고리즘이다.

 유전 알고리즘에서 쓰이는 용어들은 다음과 같다.


유전자 (Gene) : 염색체를 구성하는 요소
염색체 (Chromosome) : 여러개의 유전자의 모음으로 하나의 형질을 표현한다.
개체 (Individual) : 염색체 여러개로 구성된 하나의 개체를 말한다.
개체군 (Population) : 개체들이 이루어진 한 세대를 뜻한다.


 생물의 용어들을 이용해서 인간으로 비유하면,
인간의 각 DNA 염기들을 유전자 (Gene), 그 유전자들의 모음을 염색체 (Chromosome).성염색체 X 와 Y같은...
그리고 성 염색체를 포함하여 23쌍의 염색체 모음을 하나의 인간이라고 볼 수 있다.
 마지막으로, 그런 인간들의 집단인 인구를 개체군 (Population) 으로 볼 수 있다.


 유전 알고리즘의 기본적인 로직은 다음과 같다.

1. 자연발생
2. 적합도 검사
3. 진화 및 돌연변이
4. 다음 세대의 적합도 검사

 매우 간단하다.

 여기서 새로운 용어가 나오는데, 바로 적합도 검사(Fitness test) 이다.
이 적합도 검사는 해당 개체들이 얼마나 목적(해 찾기)에 부합하는지를 나타내는 기준이다.

 적합도 검사를 통해 훌륭한 유전자들을 가진 개체들을 교배를 통해 유전자를 섞고, 다음 세대로 넘기고, 확률적으로 돌연변이를 발생시키며 이를 반복하다보면, 점점 적합도 검사에 높은 등급을 받는 개체들이 나타날 것이다.

 이제 코드로 살펴보자.

 예제 코드로 합이 100이 되는 숫자 10개를 찾아보는 유전 알고리즘을 작성했다. 
개체는 유전알고리즘의 기본을 이해하는데 필요없으므로 만들지 않았다.

1. 유전자
 public class SumGene implements Gene {
public int number;

public SumGene(int number) {
this.number = number;
}

public static SumGene createRandomGene() {
return new SumGene((int) (Math.random() * 100));
}

@Override
public SumGene makeRandomGene() {
return SumGene.createRandomGene();
}

@Override
public String toString() {
return Integer.toString(number);
}
}

유전자는 별게 없다. 1부터 100까지 숫자를 담을 수 있는 변수 하나.

2. 염색체
public class SumChromosome extends ArrayList<SumGene> {
private static final int size = 10;
private static final double MUTATION_RATIO = 0.001d; 
public SumChromosome() {
}

public static SumChromosome createRandom() {
SumChromosome chromosome = new SumChromosome();
for (int i = 0; i < size; ++i) {
chromosome.add(SumGene.createRandomGene());
}

return chromosome;
}

protected void mutate(MutationType type) {
while (Math.random() < MUTATION_RATIO) {
switch (type) {
case REVERSE:
mutateByReverse();
break;
case SWAP:
mutateBySwap();
}
}
}

private void mutateByReverse() {
int index = (int) (Math.random() * size());
Gene gene = get(0).makeRandomGene();
set(index, (T) gene);
}

private void mutateBySwap() {
int first = (int) (Math.random() * size());
int second = (int) (Math.random() * size());
Collections.swap(this, first, second);
}

@Override
public void fitnessTest() {
int sum = 0;
for (SumGene gene : this) {
sum += gene.number;
}

fitness = Math.abs(100 - sum);
}
}

염색체는 10개의 유전자를 가지고 있다.
그리고 적합성 검사를 위해 10개의 유전자의 합을 100과의 차를 절대값으로 만든 것으로 0에 가까울수록 적합도가 높다.
mutate 함수는 돌연변이인데 보통 0.1%정도로 설정하는데 값이 높을 수록 부모와는 다른 자식이 나타난다.
돌연변이는 각 문제에 맞춰 원하는대로 만들 수 있다.

3. 개체군
public class SumPopulation extends Population<SumChromosome> {
private static int size = 10;
private EvolutionFunction evolutor = new EvolutionFunction<>();

private Comparator<SumChromosome> fitnessComparator = new Comparator<SumChromosome>() {
@Override
public int compare(SumChromosome o1, SumChromosome o2) {
if (o1.fitness < o2.fitness) {
return -1;
}
return 1;
}
};

private SumPopulation() {
}

public static SumPopulation createRandom() {
SumPopulation population = new SumPopulation();

for (int i = 0; i < size; ++i) {
population.add(SumChromosome.createRandom());
}

population.fitnessTest();
population.sort();

return population;
}

@Override
public void evolve() {
add(evolutor.crossover(get(0), get(1), CrossoverType.RANDOM));
add(evolutor.crossover(get(0), get(1), CrossoverType.CROSS));
add(evolutor.crossover(get(0), selectRandomChromosome(), CrossoverType.RANDOM));
add(evolutor.crossover(get(1), selectRandomChromosome(), CrossoverType.RANDOM));
add(evolutor.crossover(get(0), SumChromosome.createRandom(), CrossoverType.RANDOM));
add(evolutor.crossover(get(1), SumChromosome.createRandom(), CrossoverType.CROSS));

for (int i = 0; i < size - 7; ++i) {
add(SumChromosome.createRandom());
}
removeRange(1, size() - 11);
fitnessTest();
sort();
generation++;
}

public void sort() {
Collections.sort(this, fitnessComparator);
}

public void fitnessTest() {
for (Chromosome chromosome : this) {
chromosome.fitnessTest();
}
}
}

 가장 핵심되는 진화 함수를 개체군에 넣어두었다. 개체군의 숫자는 10으로 설정해두었다.
아까도 말했지만 진화의 순서는 자연발생 -> 적합도검사 -> 진화 및 돌연변이 -> 적합도검사 의 반복이다.
코드를 보면 생성후에 적합도검사와 정렬을 하도록 했다. 정렬은 적합도가 0에 가까울수록 좋은 거기 때문에 작을수록 위로 오게 설정했다.

 보통은 가장 좋은 녀석을 다른 녀석들과 교배시키게 되는데, 여기서는 1등 녀석을 다음세대로 그대로 넘기고, 1등과 2등을 두가지 다른 방식으로 교배를 시키고, 1등과 다른 녀석을 교배시키고, 또 1등과 새로 만든 녀석을 교배시킨다. 그리고 적당히 자연발생한 녀석을 추가한다.
 그리고 개체군의 숫자는 10으로 설정해뒀으므로 그만큼만 남기고 나머지는 없앤다.

 굉장히 대충만든것 같지만... 맞다. 진화 방법은 문제에 따라 적당히 설정하면 된다. 대충 길만 맞으면 언젠가는 적합한 값을 찾아낼 것이기 때문에 상관없다. 

 적합도 검사와 진화의 방법, 돌연변이를 잘 설정하지 못하더라도 계속해서 반복하면 유전알고리즘은 적당한 해답을 찾아낼 것이다. 물론 잘 설정하면 몇번의 진화만으로 좋은 값을 찾아낼 것이다.

 교배과정은 다음과 같다.

1번 염색체 : fitness : 196 // 0 64 51 18 27 36 11 32 48  
2번 염색체: fitness : 283 // 72 18 51 13 80 34 42 37 29 7

적합도 196과 283의 염색체가 있다.이를 하나씩 교차시키는 방법으로 교배시키게 되면

    0 18 51 13 27 34 11 37 9 7

 위와 같은 염색체가 생성될 것이다. 총합은 207인데 목표값인 100과의 차이를 보면 107으로 적합도가 엄청나게 개선된 것을 알 수 있다. 여기서 만약 돌연변이로 3번째 값인 51이 0이 되어버리면 적합도가 56으로 바뀔 수도 있다.

 이런식으로 좋은 유전자를 가진 녀석들을 기반으로 진화를 거듭하다보면 적합도가 점점 줄어들어 결국에는 적당한 해를 찾게 될 것이다.

4. 돌려보자
public class Test {
public static void main(String args[]) {
SumPopulation population = SumPopulation.createRandom();
population.fitnessTest();
System.out.println(population);
for (int i = 0; i < 100; ++i) {
population.evolve();
System.out.println(population);
}
}
}

 100번의 진화과정을 지켜보자.
실제로 돌려보면 매번 다른 결과가 나오는데, 이번 결과는 굉장히 잘 나왔다.

 각 세대별로 가장 적합성이 높은 녀석을 출력해 본 결과다.

Generation : 0
fitness : 242 // 염색체 :  95 8 52 6 64 49 13 0 12 43 

Generation : 1
fitness : 136 // 염색체 :  51 73 5 26 20 16 9 3 32 1 

Generation : 2
fitness : 123 // 염색체 :  51 8 5 6 20 49 9 0 32 43 

Generation : 3
fitness : 68 // 염색체 :  51 8 5 26 20 16 9 0 32 1 

.
.
.

Generation : 28
fitness : 63 // 염색체 :  51 3 5 26 20 16 9 0 32 1 
.
.
.
Generation : 73
fitness : 34 // 염색체 :  11 35 5 26 20 16 9 0 9 3 

Generation : 74
fitness : 0 // 염색체 :  11 3 5 26 20 16 9 0 9 1 

무려 74번의 진화만에 완벽한 값을 찾아냈다.

 일반적으로 유전알고리즘으로 최적의 해를 찾아내는 것은 굉장히 오래걸릴 수 있으므로 보통은 적당한 오차범위를 설정해서 그 범위 안의 값이 나오면 진화를 종료시킨다.
 예를들면 현재의 목표는 10개의 숫자의 합이 100이지만, 95~105 정도만 되면 그만두게 할 수도 있다.

 즉 유전알고리즘은 완벽한 해를 찾기보다는 적당히 좋은 값을 찾기 위해 범용적으로 쓸 수 있는 알고리즘이라고 할 수 있다.

이제 여러분은 유전알고리즘의 기본을 쓸 수 있게 되었으니 이 알고리즘을 쓸 만한 곳을 찾아 사용하면 된다. 돌릴 때마다 매번 다른 결과가 나오는 유전알고리즘에 매력을 느낄 것이다.

덧글

  • 바죠 2017/09/09 19:25 # 삭제 답글

    포스팅 잘 보았습니다. 특히, 동영상 자료가 아주 인상적입니다.

    제가 나름대로 정리한 유전 알고리듬을 소개합니다. 아래의 URL 참조 바랍니다.
    http://incredible.egloos.com/4856511

    특히, 전통적인 유전 알고리듬은 변이와 교차를 반드시 동시에 사용하는 것입니다.
    이러한 유전 알고리듬이 매우 일반적인 알고리듬이라고 알려져 있습니다. 많은 문제 풀이에 광범위하게 적용이 가능합니다.
    다만, 세대를 지나면서 해들이 거의 유사한 형식의 해들이 동시에 만들어지게 되면 유전 알고리듬의 효율성이 급격히 떨어지게 됩니다.
    이 부분이 잘 알려진 유전적 표류에 해당하는 것입니다.

    해들 사이의 다양성을 확보하지 않으면 이러한 상태가 쉽게 발생합니다.
    즉, 대치할 때 특별한 주의가 필요합니다. 나아가 새로운 장치가 필요합니다.
    따라서, 다양한 해들이 자동적으로 유전 알고리듬에서 생성되도록 하는 것이 매우 중요합니다.
    이점에 대해서는 아래에 URL에 표시된 CSA 알고리듬 참고 바랍니다.
    보다 강력한 유전 알고리듬이 될 수 있습니다. 즉, 계산할 때마다 동일한 해를 얻어낼 수 있습니다. 감사합니다.
    http://incredible.egloos.com/6208916
    http://incredible.egloos.com/7133499
  • 제가개발자입니다죄송 2017/09/09 19:39 #

    앗.... 제가 제가 crossover 함수를 빠트렸군요....
    말씀하신 돌연변이는 crossover 함수 안에서 실행하고 있는데 그부분이 빠졌네요 ㅠㅠ

    제 글은 유전알고리즘을 처음접하는 분들을 상대로 최대한 쉽게 써본 내용이라 복잡하고 심화된 내용은 빠져 있습니다.
    사람들이 인공지능들을 너무 어렵게만 보는 것 같아서 좀 쉽게 설명해 보고 싶어서 포스팅 한 내용이라 좀 더 심도깊은 내용을 원하시는 분들은 바죠님의 글들을 참고하시면 좋을 것 같네요.
  • 하마집사 2017/12/21 13:25 # 답글

    어머나.... 제가 대왕초보라 하나도 모르겠네요 하하하^^;;
  • 제가개발자입니다죄송 2017/12/21 15:12 #

    다음에는 좀 더 이해하기 쉽도록 써볼게요 ㅠㅠ
댓글 입력 영역