Previous Contents/Genetic Programming

유전 프로그래밍에서 트리간의 유사도 측정방식에 대한 고찰

shhyun 2007. 11. 22. 11:20
유사 - [명사]{주로 일부 명사 앞에 쓰여} 서로 비슷함.

그렇습니다. 유사하다는 말을 서로 비슷하다는 말입니다.
비슷하다? 그럼 비슷하다는 말은?

비슷하다
[형용사]
『(…과)』 {‘…과’가 나타나지 않을 때는 여럿임을 뜻하는 말이 주어로 온다} 두 개의 대상이 크기, 모양, 상태, 성질 따위가 똑같지는 아니하지만 전체적 또는 부분적으로 일치하는 점이 많은 상태에 있다. {명사의 단독형 뒤에 쓰여}
1 정체가 확인되지 아니한 어떤 대상에 대하여 누구 또는 무엇이라고 짐작되는 상태에 있다.
2 비교가 되는 대상과 어느 정도 일치되지만 다소 미흡한 면이 있다.

네 그렇습니다. 크기, 모양, 상태, 성질 따위가 똑같지는 않지만, 전체적 또는 부분 적으로 일치하는 점이 많은 상태에 있다 라고 하고 있습니다.

일반적으로 진화 연산에서 각 개체군의 유사함을 평가하는데에 이용되는 방식은 크게 두가지 방식이라고 할 수 있겠습니다.

그것은 Genotype 과 Phenotype 의 형태에서 유사함을 평가하는 것 입니다.

여기서 Genotype 은 순수한 그 개체 자신을 나타내는 것이고,
Phenotype 은 개체가 어떤 적합도 함수를 거쳐서 결과물로서 나타나는 것을 말합니다.

Phenotype 을 통한 개체의 유사성 분류는 크게 문제될 것이 없습니다. 일반적인 적합도 함수를 이용한다면, 두개 이상의 값이 나타나지 않습니다. (물론 동시진화기법 (Co-evolution) 을 이용할 경우에는 달라질 수 있습니다만, 이것은 특이한 경우로 분류하겠습니다.) 그러므로, 적합도의 값의 차이, 즉, 유클리디안 거리를 통한 유사도 분류가 가능합니다.

Phenotype 을 통한 유사성 분류방식은 초기 진화연산 기법에서 많이 이용된 방식 이었습니다. 하지만 금방 단점이 나타나게 되었죠.

가장큰 단점은 아마도 이것이겠지요.

" 완전 다른 개체일 경우에도 비슷한 개체로 분류될 수 있다. "

그렇습니다. 여러분 께서 만약에 GA의 대표적 벤치마크 문제인 f3deceptive 문제를 접해 보셨다면, 무슨 의미인지 확실하게 이해하실 수 있을 것입니다.
000011000 는 1.8 의 적합도를 가집니다.
111000001 또한 1.8 의 적합도를 가집니다.

과연 위의 두 개체를 비슷한 개체라고 부를 수 있을까요?

이렇듯, 개체의 특성 자체가 반영되지 않은 상태에서 단지 적합도 만을 가지고 유사성을 논하는 것은 매우 큰 오류를 범하는 것을 확인할 수 있습니다.

그래서 많은 학자들이 Genotype 상태에서의 유사성 분류에 대한 기준을 마련하기 시작했습니다.

수많은 유전연산 기법들은 그들만의 표현양식(Representation)에 따라 그 유사성 분류 방식이 다를 수 밖에 없습니다. Bit String 표현 기법을 갖는 GA 의 경우에는 해밍거리 를 통한 측정방식이 있습니다. 각각의 위치한 비트를 비교하여 몇개의 비트가 서로 다른 비트 값을 갖는지를 이용하여 측정하는 방식입니다. Real Number 로 표현되는 GA 나 ES 의 경우에는 각각의 개체에 대해 유클리디언 거리측정을 통하면 그 차이를 측정할 수 있죠.

하지만 GP 의 트리는 아직까지도 확실한 유사성 분류 기준이 없습니다. 트리구조의 유사성을 분류하는 수학적인 기준도 아직까지 없는 것으로 알고 있습니다.

여기서 짚고 넘어가야 할 게 있는데, 왜 유사성을 분류하는 것이 중요한지에 대한 것입니다. 예전에 GA 나 GP 등의 진화연산에서 중요하게 생각하는 문제중의 하나가 조기수렴 문제라고 언급한 적이 있었습니다. 이는 거의 모든 개체가 한 점으로 수렴해 나가는 현상을 말한다고 말씀 드린 적이 있습니다. 이것은 일반적으로 Phenotype 의 관점에서 봤을 때, 한 점으로 수렴하는 현상을 말 합니다. 하지만, Phenotype 의 관점에서는 한점에 수렴 했다 하더라도, Genotype 의 관점에서는 수 많은 곳으로 분포해 있을 수 있는 것입니다. 이 가능성은 개체들을 여러곳으로 분산시킬 수 있는 다른 효과를 기대해 볼 수 있습니다.

즉, 유사성 분류기준, 혹은 유사성 측정에 대한 것은 조기수렴을 현상을 돌파할 수 있는 또다른 가능성을 제시해 줄 수 있다고 생각합니다.

다시 본론으로 돌아가서 트리구조의 유사성 측정에 대해 생각해 보도록 하겠습니다.

과연 우리가 어떨 때 이 트리가 유사하다고 생각할 수 있을까요?

제 생각은 이렇습니다.

1. 트리의 깊이가 비슷하다.
2. 트리의 퍼진 형태가 비슷하다.
3. 트리에 분포되어 있는 함수의 형태가 비슷하다.
4. 마지막으로 트리가 가진 적합도도 비슷하다.

한마디로 이렇습니다. 우리가 트리가 유사하다라고 하는 것은 트리의 겉 모양을 보고 "아 이것은 생긴게 비슷하다." 라고 할 수 있고, "트리를 거쳐 처리된 결과물이 비슷하다" 라고도 할 수 있습니다.

하지만, 이것에는 어느정도 괴리가 있습니다.
저 말들 중에 비슷하다 라는 것을 어떻게 표현할 것인가?

그래서 이런 방식을 제안해 보고자 합니다.
트리의 깊이, 터미널 노드의 개수(트리의 퍼진정도), 트리에 분포되어 있는 함수들
이 세가지 기준에 트리가 가진 적합도까지 추가하여

퍼지를 통한 분류 기법을 이용해보고자 합니다.
아직은 추상적이기 때문에, 조금 더 많이 구체화 시켜야 합니다만,
인간의 주관으로서 비슷하다라고 느끼는 것을 표현할 수 있다면,
그것을 통한 조기 수렴의 극복 및 새로운 연산기법의 적용이 가능 할 것 같습니다.