PE Notes · AI

유전 알고리즘

해 집단을 선택·교차·돌연변이로 진화시켜 근사 최적해를 찾는 메타휴리스틱입니다. 연산자 유형과 탐색–활용 균형, NAS·스케줄링 쓰임새를 정리합니다.

2026-09-12

닫힌 해가 없고 탐색 공간이 넓은 조합·비선형 문제에서, 기울기만으로는 길이 막힙니다. 은 생물의 선택·재조합·변이를 연산자로 옮겨, 후보 해 을 세대마다 바꿉니다. 최적 보장은 없습니다. 가족의 한 갈래입니다.

정의

후보 해를 염색체(비트열·실수 벡터)로 인코딩한 뒤, 로 점수를 매기고 다음 세대를 만듭니다. 개체 하나는 해 하나이고, 집단은 그 세대의 후보 집합입니다.

절차는 짧습니다. 무작위 초기 집단 → 적합도 평가 → 선택 → 교차 → 돌연변이 → 다음 세대. 수렴하거나 세대 한도에 닿을 때까지 평가로 돌아갑니다.

교차는 1점(한 지점에서 교환), 2점(중간 구간 교환), 균일(유전자마다 독립)으로 가릅니다. 이진 인코딩의 돌연변이는 비트 뒤집기가 기본입니다.

기울기가 없어도 목적함수만 있으면 붙습니다. 집단 다양성으로 을 빠져나오기 쉽습니다. 대신 적합도 평가를 반복하므로 비용이 크고, 인코딩·교차율·돌연변이율에 성능이 흔들립니다. 수렴 보장도 없습니다.

비교축	유전 알고리즘	담금질 (SA)	입자군집 (PSO)
해의 단위	집단	단일 해	군집의 위치·속도
탐색 손	교차·돌연변이	온도 스케줄	이웃·전역 최적 추적
맞는 문제	이산·혼합, 구조 탐색	연속 국소 탈출	연속 파라미터

스케줄링·경로(TSP), 포트폴리오, 하이퍼파라미터, 에 자주 붙습니다. 조기 수렴이 보이면 돌연변이율을 올리거나 다양성 보존을 따로 둡니다.