NEAT(NeuroEvolution of Augmenting Topologies)

NEAT(NeuroEvolution of Augmenting Topologies) 알고리즘은 신경망의 구조와 가중치를 동시에 진화시키는 혁신적인 진화 알고리즘이다. Kenneth O. Stanley와 Risto Miikkulainen이 제안한 NEAT은 신경망이 단순한 구조에서 출발해 점진적으로 복잡한 구조로 발전할 수 있도록 설계되었다. 이는 전통적인 유전 알고리즘이 고정된 구조에서 가중치만 최적화하는 것과는 차별화된 접근이다.

NEAT 알고리즘의 주요 개념

1. 초기화 및 기본 아이디어:
   • NEAT은 매우 단순한 신경망(예: 입력층과 출력층만 있는 구조)에서 시작하여 점진적으로 새로운 노드와 연결을 추가하며 네트워크를 발전시킨다.
   • 신경망의 성능을 평가하는 피트니스 함수(fitness function)를 사용하여 진화를 이끌어 간다.
2. 유전자 표현:
   • NEAT은 신경망을 유전자의 형태로 표현한다. 각 유전자는 노드(Node genes)와 연결(Connection genes)으로 구성된다.
   • 노드 유전자는 신경망의 뉴런을 나타내며, 입력, 은닉, 출력 노드로 구분된다.
   • 연결 유전자는 뉴런 간의 연결(시냅스)과 해당 가중치를 나타내며, 연결의 활성화 여부도 포함된다.
3. 유전자 교배 및 변이:
   • 교배(Crossover): 두 부모 신경망의 유전자를 조합하여 자손을 생성한다. NEAT은 유전자 일치(matching) 및 불일치(non-matching) 문제를 해결하기 위해 혁신 번호(innovation number)를 사용하여 유전자를 정렬한다. 이는 네트워크의 구조가 변화하더라도 교배가 일관되게 이루어질 수 있도록 도와준다.
   • 변이(Mutation): 새로운 노드를 추가하거나 기존 노드를 제거하고, 새로운 연결을 추가하거나 기존 연결을 비활성화하는 방식으로 이루어진다.
4. 구조적 혁신:
   • NEAT의 중요한 특징 중 하나는 "구조적 혁신"입니다. 기존 구조에 새 노드나 연결을 추가하여 네트워크의 복잡성을 증가시키는 과정을 포함한다. 이 혁신은 각기 다른 네트워크가 고유의 구조를 가지도록 하며, 이를 통해 다양한 탐색이 가능해진다.
5. 종(speciation)과 보호:
   • NEAT은 서로 다른 신경망 구조를 가진 개체들이 경쟁하지 않고 각각의 종으로 나뉘어 경쟁하도록 한다. 이는 복잡한 네트워크가 너무 빨리 도태되지 않도록 보호하는 역할을 한다.
   • 이를 통해 신경망이 점진적으로 발전할 수 있는 환경을 조성하며, 개체군이 다양한 해법을 탐색할 수 있게 한다.
6. 적응과 발전:
   • NEAT의 진화 과정은 여러 세대를 거치며 진행된다. 각 세대에서 최고의 적합도를 가진 개체들이 생존하여 다음 세대의 부모가 된다.
   • 새로운 구조적 변화가 성능 향상에 기여할 때 그 변화가 유지되며, 그렇지 않을 때는 도태된다.

NEAT 알고리즘의 장점과 응용

• 장점:
  • 신경망 구조와 가중치를 동시에 최적화할 수 있어 복잡한 문제에서도 효과적으로 작동한다.
  • 구조적 다양성 덕분에 국부 최적해에 빠지지 않고 전역 최적화를 수행할 가능성이 높다.
  • 초기에는 단순한 구조로 시작하여 점진적으로 복잡한 구조로 발전하기 때문에 계산 자원의 사용이 효율적이다.
• 응용:
  • 로봇 제어, 게임 AI, 강화 학습, 이미지 및 신호 처리 등 다양한 분야에서 활용되고 있다.
  • 특히, 문제의 특성상 네트워크 구조를 미리 정의하기 어려운 경우에 효과적이다.

NEAT 알고리즘은 그 독창적인 진화 방식 덕분에 신경망 학습과 최적화의 강력한 도구로 자리잡고 있다. 각기 다른 문제에 유연하게 적용될 수 있는 이 알고리즘은 여전히 활발히 연구되고 있으며, 다양한 변형으로 발전하고 있다.

 

주요 변형 알고리즘은 다음과 같다.

1. HyperNEAT (Hypercube-based NeuroEvolution of Augmenting Topologies)

• 설명: NEAT의 확장으로, 신경망의 연결 가중치를 진화시키는 대신, 연결 가중치를 결정하는 패턴(CPPN)을 진화시킨다. HyperNEAT은 특히 대칭성, 반복성, 고차원 패턴 인식이 필요한 문제에서 강점을 발휘한다.
• 응용 분야: 로봇 제어, 이미지 처리, 고차원 신경망 설계 등에서 많이 사용된다.

2. ES-HyperNEAT (Evolvable Substrate HyperNEAT)

• 설명: HyperNEAT의 또 다른 확장 버전으로, 입력 노드와 출력 노드의 위치뿐만 아니라, 중간 은닉 노드의 위치와 분포를 진화적으로 학습한다. 이를 통해 신경망의 구조를 보다 세밀하게 조정할 수 있다.
• 특징: 하위 신경망의 배치를 자동으로 설계하여 더욱 정교한 네트워크를 생성할 수 있다.

3. Novelty Search NEAT

• 설명: 전통적인 피트니스 기반 선택 대신, NEAT의 변형으로 "새로움(Novelty)"을 기준으로 개체를 선택한다. 기존의 목표 지향적 탐색에서 벗어나 다양한 행동을 보이는 개체들을 선호하여 탐색의 다양성을 증가시킨다.
• 응용 분야: 탐색 공간이 복잡하거나 국부 최적해에 빠질 위험이 높은 문제, 창의적 설계 문제 등에서 사용된다.

4. rtNEAT (Real-Time NEAT)

• 설명: 실시간으로 신경망을 진화시키기 위해 개발된 NEAT의 변형으로, 로봇이나 실시간 게임 환경에서 사용할 수 있도록 설계되었다. 실시간으로 신경망을 교체하고 적응시키는 방식으로, 학습 과정이 끊김 없이 진행된다.
• 응용 분야: 실시간 제어, 게임 AI, 로봇 제어 등 실시간 적응이 중요한 분야에서 사용된다.

5. Cooperative Coevolution NEAT

• 설명: 개체들을 독립적인 부분으로 나누고, 각 부분이 협력하여 문제를 해결하는 방식이다. 예를 들어, 각각의 부분 신경망이 전체 네트워크의 일부를 담당하게 하여 협력적으로 학습한다.
• 특징: 복잡한 문제를 여러 부분으로 나누어 해결함으로써 학습 효율성을 높일 수 있다.

6. HyperNEAT-D (Developmental HyperNEAT)

• 설명: HyperNEAT의 확장으로, 신경망의 연결이 시간에 따라 동적으로 변화할 수 있도록 하는 알고리즘이다. 이는 생물학적 신경망의 발달 과정을 모방하며, 구조의 시간적 변화를 모델링한다.
• 특징: 구조의 발달과 환경 적응을 시뮬레이션할 수 있다.

7. Adaptive HyperNEAT

• 설명: HyperNEAT의 변형으로, 네트워크의 구조를 학습하는 동안 환경의 변화를 동적으로 반영한다. 주어진 문제의 특성에 따라 신경망이 변화하며 적응할 수 있다.
• 응용 분야: 변화하는 환경에서의 적응 문제, 로봇의 환경 적응 등에 사용된다.

8. Phased Pruning and Complexifying NEAT (PP&CN)

• 설명: NEAT 알고리즘의 진화와 구조 복잡화 과정에서 불필요한 노드와 연결을 제거하는 방식을 추가하여 네트워크를 간소화한다. 이는 과도한 복잡화를 방지하고, 효율성을 유지하면서 학습 성능을 향상시킨다.
• 특징: 신경망의 간결함을 유지하면서 성능 최적화를 추구한다.

이들 알고리즘은 NEAT의 기본 원리를 바탕으로 다양한 문제에 대응할 수 있도록 확장되고 변형된 버전들이다. 각각의 알고리즘은 특정 문제 유형에 대해 더 나은 성능을 발휘하도록 설계되어 있으며, 진화적 신경망 학습의 다양성과 응용 가능성을 크게 확장하고 있다.