C# 유전 알고리즘을 적용한 최적의 길찾기

생물의 진화과정 인 자연선택(natural selection)과 유전법칙을 모방한 확률적 탐색기법을 이용하여 최적의 길찾기를 C# 으로 구현해 보았습니다. 

 

1. 소스 프로그램 :

Genetic_Algorithm.zip

0.28MB

2. 알고리즘 순서는 아래와 같습니다. 

 

 (1) 노드 생성 ( 2차원 좌표상의 특정위치 )

 (2) 각각의 노드들을 랜덤하게 연결하여 하나의 유전자를 생성 

 (3) 여러개의 유전자(프로그램에서는 10개)를 모아서 하나의 유전자 그룹을 생성 

 (4) 유전자 그룹의 각각의 유전자마다 Fitness 값을 계산한 후 최적의 Fitness 값을 가진 유전자를 선정

 (5) 유전자 그룹의  각 유전자 Fitness 값을 이용해서 각각의 유전자의 가중치를 적용하여 룰렛휠을 생성 

 (6) 룰렛휠의 돌려서 2개의 유전자를 선택하여 Crossover하여 하나의 새로운 유전자 생성 

 (7) 새로 생성된 유전자에 돌연변이 생성 ( 1% 확율 )

 (8) ( 6,7)번을 10회 반복하여 새로운 유전자 그룹을 만들고 기존 부모 유전자 그룹은 파기 

 (9) 유전자 그룹의 각각의 유전자마다 Fitness 값을 계산한 후 최적의 Fitness 값을 가진 유전자를 선정

 (10) 기존보다 최적의 유전자가 없을 경우 최악의 유전자를 기존 최적의 유전자와 교체 

 (11) 5번부터 다시 반복 

 

3. 실행 결과 프로그램 

 (1) 빨간색 점이 시작 위치이고 모든 노드들을 경유하여 다시 제자리로 돌아오게 되는 경로를 찾게 됩니다. 

 (2) reset : 노드 재 생성 

 (3) Operate : 수동 세대 전환 

 (4) start : 자동 연속 세대 전환

 (5) stop : 자동 전환 멈춤