주의: 아직 작성중인 글입니다; 글의 내용이 계속해서 변경될 수 있습니다.

NeuroEvolution of Augmenting Topologies(NEAT)는 NeuroEvolution 알고리즘 중 하나로, Neural Network의 Topology와 Weight를 Genetic Algorithm을 이용해서 동시에 학습한다. NeuroEvolution의 가장 큰 장점은 Backpropagation을 사용하지 않기 때문에 Recurrent Network를 만들 때에도 FeedForward Network를 만드는 것 이상의 고민이 필요하지 않다는 것과, 학습 데이터가 명확히 존재하지 않는 Reinforcement Learning에 사용할 수 있다는 것이다(물론 Q-Learning과 같은 것이 존재하긴 하지만 일단 넘어가자).

NEAT 알고리즘은 기존의 NeuroEvolution 알고리즘과 비교해서 더 나은 성능(높은 성공률, 적은 계산량, 더 단순한 네트워크)을 보여주는데(논문 저술 당시), 이 포스트를 통해 NEAT 알고리즘이 어떻게 이루어져있는지 간단하게 살펴보자.

NEAT의 구성 요소

Growth

NEAT에선 네트워크가 Mutation(돌연변이)를 겪을 때마다 복잡해질 수 있다. 즉, 세대가 지날 수록 네트워크가 (그 복잡도 면에서) 성장한다고 볼 수 있다. 이러한 돌연변이는 크게 두 종류로 나눌 수 있다:

  • Link Mutation
    • New connection
      연결되지 않은 두 개의 노드를 선택하고, 그 두 노드를 연결한 다음 랜덤한 가중치를 준다.
    • New random weight
      랜덤한 연결을 골라서, 새로운 연결을 만들 때처럼 가중치를 랜덤한 값으로 초기화한다.
    • Weight perturbation
      랜덤한 연결을 고르고, 그 가중치를 적당히 변형한다(e.g. 일정한 값을 더하기).

  • Node Mutation
    랜덤한 연결을 고른 다음, 연결의 중간에 새로운 노드를 추가한다.
    이후 원래의 연결을 두 개로 나누고 원래 있던 연결은 비활성화하는데, 새로운 정점으로 들어가는 연결의 가중치는 1로 하고 새로운 정점에서 나가는 연결의 가중치는 원래 존재하던 연결의 가중치로 해서 새로운 정점의 영향이 최소화되도록 한다. 즉, 다음과 같은 변화가 일어난다:

    $$ \newcommand\rarrow[1]{\stackrel{#1}{\rightarrow}} v_\text{in} \rarrow{w_0} v_\text{out} \Rightarrow \begin{cases} v_\text{in} ~~ \rarrow{w_1} v_\text{new} ~~~ (w_1 = 1) \\ v_\text{new} \rarrow{w_2} v_\text{out} ~~ (w_2 = w_0) \\ \color{gray}{v_\text{in} ~~ \rarrow{w_0} v_\text{out} ~~~ \text{(disabled)}} \end{cases} $$

Starting Minimally

NEAT에서 네트워크는 세대가 지날수록 복잡해지기 때문에 처음 시작할 때 입력과 출력 노드만 존재하는 상태에서, 노드 사이에는 아무런 연결도 없는 채로 시작한다. 이는 결과적으로 NEAT가 최소한의 구조를 갖으면서 필요한 기능을 수행하는 네트워크를 찾아내는 데에 도움을 주고, 최적화를 진행하는 동안 탐색 범위를 줄이는 데에도 아주 중요한 역할을 한다. 노드와 연결을 랜덤하게 추가한 네트워크를 초기 개체들로 해서 시작할 경우 해당 노드나 연결이 사용되지 않는 경우에도 이를 제거하기 위해서는 추가적인 시간이 소요되고, 이런 과도하게 복잡한 네트워크가 좋은 적합도를 가질 경우 이는 웬만해서는 알고리즘이 종료될 때까지 제거되지 않을 수도 있다.

Historical Marking

TODO: Historical Marking, allelomorph

Genetic Encoding

TODO: Genetic Encoding , innovation #

Speciation

보통 네트워크의 구조가 변경될 경우, 이 구조가 충분히 최적화되기 전에 적합도가 낮다는 이유로 도태되어버릴 가능성이 있기 때문에 이를 보호하기 위해 NEAT에는 ‘종’의 개념이 도입되었다. 이는 조상 표시를 이용해서 구현되는데,

Crossover

TODO: Crossover

변형 NEAT

TODO: Randomly initialized NEAT
TODO: Nonmating NEAT
TODO: Performance comparison between various simplified NEAT methods.

마치며

…