핵심 인사이트 (3줄 요약)

  1. 본질: 진화 알고리즘 (Evolutionary Algorithm) 은 자연의 진화 원리(선택, 교차, 돌연변이)를 모방한 메타휴리스틱 — 기울기 정보 없이 불연속·비볼록 탐색 공간을 탐색한다.
  2. 가치: 해의 인코딩만 정의하면 어떤 최적화 문제도 적용 가능하지만, 공짜 점심 없음 정리 (No Free Lunch Theorem) 가 "모든 문제에 최선인 알고리즘은 없다"고 말하듯 문제 구조에 맞는 선택이 중요하다.
  3. 판단 포인트: 기울기 기반(빠른 수렴, 미분 가능 필요) vs 진화 기반(느린 수렴, 범용) — 신경망 하이퍼파라미터 최적화, 조합 문제, 공학 설계에서 진화 알고리즘이 실용적 대안이다.

Ⅰ. 개요 및 필요성

메타휴리스틱 (Metaheuristic): 특정 문제 구조를 이용하지 않고 일반적 탐색 원리로 좋은 해를 찾는 알고리즘군.

대표 알고리즘들:

알고리즘영감주요 연산
GA (Genetic Algorithm)다윈 진화론선택·교차·돌연변이
PSO (Particle Swarm Optimization)새떼·물고기떼속도·위치 업데이트
SA (Simulated Annealing)금속 담금질확률적 이동 수락
ACO (Ant Colony Optimization)개미 페로몬페로몬 기반 경로
CMA-ES (Covariance Matrix Adaptation)진화 전략공분산 적응

왜 필요한가?

  • 목적 함수가 미분 불가능 (블랙박스 함수)
  • 불연속·다봉 탐색 공간
  • 제약이 복잡하여 LP/IP 모델화 어려움
  • 병렬 탐색으로 다양한 해 동시 유지

📢 섹션 요약 비유: 진화 알고리즘은 "시험 없이 우수한 유전자 고르기"다 — 어떤 특성이 최적인지 몰라도, 많은 개체를 만들어 좋은 것끼리 교배하다 보면 자연스럽게 우수한 해가 나타난다.

Ⅱ. 아키텍처 및 핵심 원리

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

초기 세대 (Population) 생성
        │
        ▼
┌────────────────────────────────────────┐
│  ① 적합도 평가 (Fitness Evaluation)   │
│     각 염색체에 f(x) 계산              │
│                                        │
│  ② 선택 (Selection)                   │
│     적합도 높은 개체 선택 (부모)        │
│     토너먼트, 룰렛 휠, 엘리트 선택     │
│                                        │
│  ③ 교차 (Crossover)                   │
│     두 부모 염색체를 섞어 자식 생성     │
│     1점, 2점, 균등 교차               │
│                                        │
│  ④ 돌연변이 (Mutation)               │
│     낮은 확률로 임의 유전자 변경       │
│     탐색 다양성 유지                  │
└────────────────────────────────────────┘
        │
        ▼
수렴 조건 (최대 세대 또는 최적값 안정) 까지 반복
        │
        ▼
최적 개체 = 해답

GA 연산 상세

염색체 인코딩 (Chromosome Encoding):

이진 인코딩: [1, 0, 1, 1, 0, 0, 1]
실수 인코딩: [2.3, -1.5, 0.7, 4.1]
순열 인코딩: [3, 1, 4, 2, 5]  (TSP 경로)
트리 인코딩: 표현식 트리 (프로그래밍 합성)

교차 연산:

1점 교차 (1-point):
  부모1: [1 0 1 1 | 0 0 1]
  부모2: [0 1 1 0 | 1 1 0]
  자식:  [1 0 1 1 | 1 1 0]

2점 교차:
  부모1: [1 | 0 1 1 0 | 0 1]
  부모2: [0 | 1 1 0 1 | 1 0]
  자식:  [1 | 1 1 0 1 | 0 1]

선택 방법:

  • 룰렛 휠: 적합도 비례 선택 (편향 있음)
  • 토너먼트: k개 랜덤 선택 후 최선 채택 (덜 편향)
  • 엘리트주의: 최상위 e%는 다음 세대 보존

PSO (Particle Swarm Optimization, 입자 군집 최적화) 구조

각 입자 i의 위치 xᵢ, 속도 vᵢ:

vᵢ(t+1) = ω·vᵢ(t) + c₁·r₁·(pBestᵢ - xᵢ(t))
                    + c₂·r₂·(gBest - xᵢ(t))

xᵢ(t+1) = xᵢ(t) + vᵢ(t+1)

ω: 관성 가중치 (inertia weight, 0.4~0.9)
c₁: 개인 최적 당김 계수 (cognitive, 보통 2.0)
c₂: 전체 최적 당김 계수 (social, 보통 2.0)
pBestᵢ: 입자 i의 개인 최적 위치
gBest: 전체 최적 위치

탐색 공간 시각화:

        gBest★            ← 전체 최적
         ↑    ↑
  pBest○ │   ○pBest     ← 각 입자의 개인 최적
     ↗  │  ↗
   ●    │  ●            ← 현재 위치 (입자들)
  (v↗)  │  (v↗)

📢 섹션 요약 비유: PSO의 각 입자는 "목적지를 찾는 새떼 한 마리"다 — 개인 최선 경험(pBest)과 떼 전체의 최선 위치(gBest)를 참고하며 날아가, 결국 무리 전체가 최적 지점으로 수렴한다.

Ⅲ. 비교 및 연결

진화 알고리즘 상세 비교

알고리즘특징강점약점
GA교차·돌연변이조합 최적화 강함파라미터 민감
PSO속도 기반연속 공간, 빠름조기 수렴
SA확률적 수용탈출 능력냉각 스케줄 민감
CMA-ES공분산 적응연속 블랙박스 최강고차원 불리
DE (Differential Evolution)차분 변이실수 최적화 강함파라미터 3개

공짜 점심 없음 정리 (No Free Lunch Theorem)

Wolpert & Macready (1997):

"모든 가능한 문제에 대해 평균 성능을 비교하면, 모든 최적화 알고리즘의 성능은 동일하다."

→ 특정 문제 클래스에서 A가 B보다 나으면, 다른 문제 클래스에서는 B가 A보다 낫다.

실용적 함의: 문제 구조를 이용한 알고리즘 설계가 범용 알고리즘보다 항상 유리.

CMA-ES (Covariance Matrix Adaptation Evolution Strategy)

현재 연속 공간 블랙박스 최적화의 황금 기준:

다변수 정규분포 N(m, σ²·C)에서 샘플링
적합도에 따라:
  m (평균) 업데이트 → 탐색 방향
  C (공분산) 업데이트 → 탐색 형태
  σ (스텝 크기) 업데이트 → 탐색 크기

인구 개체 없이 분포 자체를 학습.

📢 섹션 요약 비유: CMA-ES는 "점점 더 좋은 방향을 기억하는 탐험대"다 — 좋은 결과가 나온 방향으로 탐색 분포의 모양(공분산)을 점점 늘려가며 수렴한다.

Ⅳ. 실무 적용 및 기술사 판단

신경망 하이퍼파라미터 최적화

탐색 공간:
  학습률: [1e-5, 1e-1] (로그 스케일)
  배치 크기: {32, 64, 128, 256}
  레이어 수: [1, 10] (정수)
  드롭아웃율: [0.0, 0.5]
  활성화 함수: {ReLU, GELU, Swish}

진화 알고리즘 흐름:
  개체 = 하이퍼파라미터 설정
  적합도 = 검증 정확도
  교차 = 두 설정의 일부 교환
  돌연변이 = 일부 파라미터 랜덤 변경

Neural Architecture Search (NAS): GA/강화학습으로 신경망 구조 자체를 탐색 (EfficientNet, DARTS).

TSP (Traveling Salesman Problem) — 유전 알고리즘

n = 100개 도시
염색체: 순열 (방문 순서)
교차: Order Crossover (OX)
돌연변이: 두 위치 교환 (Swap Mutation)

GA 결과: 최적해의 2~5% 이내
정확해 알고리즘(Held-Karp): O(n²·2ⁿ) → n=100 불가능
GA: O(pop × gen × n) → 실용적

기술사 판단 포인트

  1. "GA와 경사하강의 선택 기준은?" → 미분 가능 연속 → 경사하강 / 불연속·조합·블랙박스 → GA/PSO
  2. "공짜 점심 없음 정리의 실무 의미는?" → 범용 알고리즘은 없으므로 문제 도메인 지식 활용 필수
  3. "PSO와 GA의 차이는?" → PSO: 연속 탐색 공간에서 빠른 수렴 / GA: 이산 조합 문제에 더 적합

📢 섹션 요약 비유: NAS(Neural Architecture Search)는 "AI가 AI 구조를 설계"하는 것이다 — 인간이 수작업으로 설계하던 신경망 구조를 GA/RL로 자동 탐색해 더 효율적인 구조를 발견한다.

Ⅴ. 기대효과 및 결론

진화 알고리즘은 기울기 없이 탐색하는 최적화의 마지막 수단이자 강력한 대안이다.

실무 적용 시 선택 가이드:

목적 함수가 미분 가능?
  YES → 경사하강법 (Adam, L-BFGS)
  NO  → 진화 알고리즘 / 시뮬레이티드 어닐링

연속 공간?
  YES → PSO, CMA-ES, DE
  NO  → GA (이진/순열 인코딩)

전역 최적 중요?
  이론적 보장 필요 → 볼록 최적화 (LP, QP)
  근사 해 허용 → 진화 알고리즘

현대 응용: AutoML, NAS, 로봇 공학, 분자 설계 (신약 개발), 안테나 설계 모두에서 진화 알고리즘이 인간 전문가를 능가하는 해를 발견하고 있다.

📢 섹션 요약 비유: 진화 알고리즘은 "답을 몰라도 시행착오로 최선을 찾는 수학적 다윈주의"다 — 수백만 년의 진화를 수천 번의 반복으로 압축해, 인간이 직관으로 찾기 어려운 최적 설계를 자동으로 발굴한다.

📌 관련 개념 맵

개념핵심 연산적합 문제
GA (유전 알고리즘)선택·교차·돌연변이조합 최적화, 이산
PSO (입자 군집)속도·위치 업데이트연속 탐색 공간
SA (시뮬레이티드 어닐링)확률적 수락조합, 국소 탐색
CMA-ES공분산 적응연속 블랙박스 최고
NASGA + 신경망 구조AutoML, 딥러닝
공짜 점심 없음범용 최강 없음알고리즘 선택 지침

📈 관련 키워드 및 발전 흐름도

[브루트 포스 탐색 — 모든 해를 직접 확인]
    │
    ▼
[메타휴리스틱 (Metaheuristic) — 구조 없이 좋은 해 탐색]
    │
    ▼
[진화 알고리즘 — 선택·교차·돌연변이로 탐색]
    │
    ├─▶ [GA (Genetic Algorithm) — 조합 최적화 중심]
    │
    └─▶ [PSO (Particle Swarm Optimization) — 연속 공간 빠른 수렴]
                │
                ▼
            [CMA-ES / NAS — 공학 설계·신경망 구조 최적화]

진화 알고리즘은 브루트 포스와 경사 기반 최적화의 한계를 넘어, 조합 문제와 블랙박스 설계에 맞는 범용 탐색 틀로 발전했다.

👶 어린이를 위한 3줄 비유 설명

  1. GA는 "우수한 유전자 경쟁": 좋은 특성을 가진 부모끼리 교배하면, 세대를 거듭할수록 더 좋은 자손이 나타난다.
  2. PSO는 "목적지 찾는 새떼": 각 새가 자신이 지금껏 발견한 최고 위치와 떼 전체의 최고 위치를 참고하며 날아가 최적 지점을 발견한다.
  3. 공짜 점심 없음은 "만능 알고리즘 없음": 모든 문제를 동시에 잘 푸는 알고리즘은 존재하지 않으니, 문제에 맞는 알고리즘을 골라야 한다.