오랜만에 GA 관련 포스팅 입니다.
예전에 한번 설명 드렸지만, GA 는 원래 Bit 형태의 유전자를 이용해서 연산을 하게 됩니다.
이 Bit 형태의 유전자를 이용해서 연산을 하게 되면,
Bit -> Real Number -> Bit 의 변환과정을 거쳐서 적합도평가(Fitness Evaluation)가 이루어집니다.
결과적으로 변환 과정의 해상도(Bit 의 갯수를 얼마나 더 확장시키는지)가 성능에 어느정도 영향을 미치는 꼴이 됩니다. 이 문제에 대해 간단한 예제로 설명하자면 밑의 More 부분을 클릭하시면 됩니다.
그래서 학자들 사이에서는
Binary 로 이용해서 변환과정을 거치는 것만으로도 실수 최적화에 성공할 수 있다.
VS
실수 최적화 문제는 실수자체를 이용해서 최적화 시키는 것이 더 좋은 결과가 나온다.
Binary 로 이용해서 변환과정을 거치는 것만으로도 실수 최적화에 성공할 수 있다.
VS
실수 최적화 문제는 실수자체를 이용해서 최적화 시키는 것이 더 좋은 결과가 나온다.
의 두가지 논점으로 갈라지게 되었습니다.
GA 에 대해 오래 연구하신 분들께서는 위의 의견에 동의를 하시는 편이시고, GA 외에도 ES(Evolutionary Strategies)나 다른 C.I.분야에 대해서 연구하신 분들께서는 아래쪽 의견에 동의를 하시는 편 입니다.
저 같은 경우에는 Rosenbrock 이나 Griewangk 과 같은 Benchmark 문제를 두가지 접근방식으로 해결해 본 결과 아랫쪽 의견에 더 동의하는 편 입니다.
만약 우리가 실수 연산을 이용하고자 한다면, 그에 맞는 CX 와 MUT 연산자를 이용 해야 할 필요가 있습니다. 기존의 Bit 방식의 접근으로는 실수 유전자를 이용하는 의미가 떨어지게 되기 때문입니다.
그래서 오늘은 실수 유전자를 이용하는 CX 연산자 중에서 가장 기본적 연산자인 Arithmetical Crossover[Michalewicz 1996] 에 대해서 살펴보도록 하겠습니다.
--------------------------------------------------------------------------------------------
Arithmetical Crossover[Michalewicz 1996]
역시 본론 부터 말씀드리자면 기본 적인 연산자 답게 크게 어려움은 없습니다.
여기서 기억하실 것은 λ(lamda) 값 입니다.
일반 적으로 0~1 사이의 실수값으로 표현되는 λ(lamda) 값에 의해 유전자가 미묘하게 수정되게 됩니다.
그림의 예를 통해 어떻게 수정되는지 표현해보겠습니다.
GA 에 대해 오래 연구하신 분들께서는 위의 의견에 동의를 하시는 편이시고, GA 외에도 ES(Evolutionary Strategies)나 다른 C.I.분야에 대해서 연구하신 분들께서는 아래쪽 의견에 동의를 하시는 편 입니다.
저 같은 경우에는 Rosenbrock 이나 Griewangk 과 같은 Benchmark 문제를 두가지 접근방식으로 해결해 본 결과 아랫쪽 의견에 더 동의하는 편 입니다.
만약 우리가 실수 연산을 이용하고자 한다면, 그에 맞는 CX 와 MUT 연산자를 이용 해야 할 필요가 있습니다. 기존의 Bit 방식의 접근으로는 실수 유전자를 이용하는 의미가 떨어지게 되기 때문입니다.
그래서 오늘은 실수 유전자를 이용하는 CX 연산자 중에서 가장 기본적 연산자인 Arithmetical Crossover[Michalewicz 1996] 에 대해서 살펴보도록 하겠습니다.
--------------------------------------------------------------------------------------------
Arithmetical Crossover[Michalewicz 1996]
역시 본론 부터 말씀드리자면 기본 적인 연산자 답게 크게 어려움은 없습니다.
여기서 기억하실 것은 λ(lamda) 값 입니다.
일반 적으로 0~1 사이의 실수값으로 표현되는 λ(lamda) 값에 의해 유전자가 미묘하게 수정되게 됩니다.
그림의 예를 통해 어떻게 수정되는지 표현해보겠습니다.
(*) 그림이 조금 깨지면 클릭 하셔서 보시면 됩니다.
위에 보시면 아시겠지만 아주 단순한 알고리즘 입니다.
λ 값에 의한 변화라고 볼 수 있습니다.
λ 값의 범위가 0 ~ 1 사이로 제한되면 Convex CX
λ 값의 범위가 -0.5 ~ 1.5 사이로 제한되면 Affine CX
라고 부릅니다.
여기서 Convex 범위를 갖게 되면 유전자의 값들이 항상 원래 의도하고자 하는 유전자의 범위를
벗어나지 않게 됩니다만, Affine 범위를 갖게되면 유전자가 자칫 값이 커져버려서 범위를 벗어나곤 합니다.
그렇기에 범위를 벗어나는 것을 막아주어야 하는데, 일반적으로 두가지 방법이 있습니다.
유전자 차원에서 매번 값의 검색을 통해 Error 값을 나타내는 것
적합도 차원에서 값이 벗어날 경우 Error 값을 나타내는 것
이 있습니다. 저의 경우에는 후자를 사용해서 값을 통제했습니다.
결론적으로, Arithmetical CX 방식은 λ값을 통해 유전자 값들을 미묘하게 흔들어 주는 방식입니다.
이 방식은 구현도 매우 쉬운편이고, 효과도 그럭저럭 나쁘지 않은 편이기에 기본적인 GA에서 많이 쓰입니다.
사실 제가 조금 변형한 GA 를 올릴까 했습니다. 하지만 부족한 것이 너무 많기에 아직은 올리기에 부끄러울 지경입니다. 적어도 기본적인 SGA 보다는 압도적인 성능을 보여야 한다고 생각하는게 제 생각이기에 아직은 올릴 시기가 아닌 듯 싶네요. 그래서 제가 프로그래밍 하고 있는 GA 에 이용되고 있는 몇가지 연산자들에 대해서 천천히 설명하고, 새로 구현되는 내용들에 대해서 언급을 다 한후에 완성된 것을 올려보겠습니다. 보고 공부하기 좋은 GA 를 구현하려고 노력하고 있습니다 ^^
위에 보시면 아시겠지만 아주 단순한 알고리즘 입니다.
λ 값에 의한 변화라고 볼 수 있습니다.
λ 값의 범위가 0 ~ 1 사이로 제한되면 Convex CX
λ 값의 범위가 -0.5 ~ 1.5 사이로 제한되면 Affine CX
라고 부릅니다.
여기서 Convex 범위를 갖게 되면 유전자의 값들이 항상 원래 의도하고자 하는 유전자의 범위를
벗어나지 않게 됩니다만, Affine 범위를 갖게되면 유전자가 자칫 값이 커져버려서 범위를 벗어나곤 합니다.
그렇기에 범위를 벗어나는 것을 막아주어야 하는데, 일반적으로 두가지 방법이 있습니다.
유전자 차원에서 매번 값의 검색을 통해 Error 값을 나타내는 것
적합도 차원에서 값이 벗어날 경우 Error 값을 나타내는 것
이 있습니다. 저의 경우에는 후자를 사용해서 값을 통제했습니다.
결론적으로, Arithmetical CX 방식은 λ값을 통해 유전자 값들을 미묘하게 흔들어 주는 방식입니다.
이 방식은 구현도 매우 쉬운편이고, 효과도 그럭저럭 나쁘지 않은 편이기에 기본적인 GA에서 많이 쓰입니다.
(*) 마치며...
사실 제가 조금 변형한 GA 를 올릴까 했습니다. 하지만 부족한 것이 너무 많기에 아직은 올리기에 부끄러울 지경입니다. 적어도 기본적인 SGA 보다는 압도적인 성능을 보여야 한다고 생각하는게 제 생각이기에 아직은 올릴 시기가 아닌 듯 싶네요. 그래서 제가 프로그래밍 하고 있는 GA 에 이용되고 있는 몇가지 연산자들에 대해서 천천히 설명하고, 새로 구현되는 내용들에 대해서 언급을 다 한후에 완성된 것을 올려보겠습니다. 보고 공부하기 좋은 GA 를 구현하려고 노력하고 있습니다 ^^