토픽 77 / 82

유전 알고리즘 (GA, Genetic Algorithm)

생물의 자연 선택과 유전 메커니즘을 모방하여 해 집단을 진화시키며 최적해에 수렴하는 메타휴리스틱 최적화 알고리즘

목적: NP-hard 문제 근사해, 탐색 공간이 큰 최적화 문제 해결

특징: 집단 기반, 확률적, 병렬 탐색, 다목적 최적화 가능

동작 원리: ① 초기 집단 생성 → ② 적합도 평가 → ③ 선택 → ④ 교차 → ⑤ 변이 → ⑥ 세대 반복

인코딩: 이진(비트열), 실수(연속값), 순열(TSP), 트리(GP)

선택: 룰렛 휠(확률적), 토너먼트(k개 비교), 랭크 기반(순위 비례)

교차: 1점/2점/균일 교차, OX(Order Crossover): 순서 보존, PMX(Partially Mapped Crossover): 부분 매핑

변이: 비트 플립(이진), 스왑/역위(순열), 가우시안(실수)

장점: 전역 탐색 능력, 병렬 탐색, 다양한 문제 적용

단점: 파라미터 민감(인구 크기, 교차율, 변이율), 수렴 느림, 최적 미보장

적용사례: TSP, 스케줄링, 신경망 구조 탐색(NAS), 로봇 제어

비교: GA(집단/진화/범용) vs SA(단일/담금질/구현간단) vs PSO(집단/군집/연속최적화)

연관: 메타휴리스틱, 진화 알고리즘, NP-hard, 최적화