Previous Contents/Genetic Programming 5

CGP(Cartesian Genetic Programming)

CGP는 본래 논리 회로에 대해서 많이 사용되기 때문에, 별 관심이 없다가 최근에 몇가지 가능성을 보고 찾게된 이론이다. Linear GP 나 CGP 등 사실 Tree 기반의 GP 보다 구현이 쉽기 때문에 찾아보게 된 이유도 있다. 우선 기법에 대해 살펴보면 아래와 같다. 기존의 Tree 기반의 Genetic Programming과는 약간 다른 Integer String 으로 개체를 구성한다. 하나의 개체는 아래의 그림과 같이 구성할 수 있는데, (1) (2) 는 입력을 의미하고, (3) 은 해당 노드의 연산자를 의미한다. 즉, 1, 2 로 부터의 입력을 3 의 처리를 거쳐 output 1 을 만들어내는 식인데, 이때 CGP 에서 출력은 사용자가 지정하는 것이 아니라 자동으로 지정되는 형태를 갖는다. 이..

GP에서 ADFs에 대한 이야기

Automatically Defined Functions(ADFs)? J. R. Koza 의 94년에 발간된 Genetic Programming II 에 보면 나오는 용어입니다. 말 그대로 풀이하면 자동적으로 정의된 함수들 쯤 될꺼 같습니다. 그 책의 내용에 따르면 이 기법을 사용하게 되면 트리 안에서 어떤 강제적인 흐름을 가지는 구조물을 위치시키게 되고, 이 구조물은 트리 안에서 반복적으로 사용될 수 있게 된다고 하고 있습니다. GP 는 터미널 노드와 함수 노드를 사용하여 일정한 흐름의 프로그램을 만들어내죠. 이 ADFs 라는 녀석은 그 일정한 흐름의 프로그램들의 한 부분을 ADFs 라는 하나의 구조물안에 가두어서 반복적으로 사용할 수 있는 효과를 가지게 됩니다. 한마디로 어떤 구조가 반복적으로 사용되..

Homologous CX Operator for lil-gp

Homologous CX 연산자는 기본적으로 동일 구조를 가진 서브트리들 간의 교환만 허용하는 연산자 입니다. 즉, 위의 그림에 Tree1 과 Tree 2 에서, 1-1, 2-2, 3-3, 6-4, 7-7 간의 교환만을 허용한다는 이야기 입니다. 이 연산자의 출발점은 생물체의 교배에 있어서 동일 형질의 유전자 만을 교환한다는 것으로 기억하고 있습니다. 예로서 팔의 유전자와 다리의 유전자를 교환해서는 이상형질이 나타날 수 있다는 것을 들 수 있겠습니다. 실제로 몇가지 테스트 문제에 대해 실험해 보면 매우 빠른 속도로 연산이 이루어지고, 코드의 증가 또한 기본 연산자에 비해서 매우 적게 증가하는 것을 확인할 수 있었습니다. 본 소스코드에 어떤 오류가 있을지는 모르겠습니다만, 혹시 참고하실 분은 첨부된 소스를..

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

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

1. Genetic Programming 이란?

오늘은 간단하게 Genetic Programming(GP) 에 대해서 정리해볼까 합니다. GP 라는건 GA 에서 파생되었다고도 할 수 있는 또다른 Evolutionary Computation 의 한 종류 입니다. Genetic Algorithm 에서는 유전자 형태를 Binary 또는 Real Type 의 조합을 이용했습니다. 하지만 Genetic Programming 에서는 유전자 형태를 Tree 구조를 이용합니다. 그림으로 표현해보면 다음과 같습니다. 그림1. GA 와 GP 의 표현의 차이점 GA 와 GP 는 보시는 것과 같이 표현에 차이를 두고 있습니다. CX나 MUT 역시 존재하지만 표현상의 차이로 인해 조금 다른 방식으로 이루어 집니다. CX 방식의 차이에 대해서 그림으로 표현해보면 다음과 같습니..