Skip to content

algorithms.md

Latest commit

 

History

History
370 lines (278 loc) · 6.95 KB

algorithms.md

File metadata and controls

370 lines (278 loc) · 6.95 KB

알고리즘 상세 설명

전통적 휴리스틱 알고리즘

1. Greedy Algorithm (탐욕 알고리즘)

원리: 각 단계에서 현재 최선의 선택을 하는 방식

TSP 예시: Nearest Neighbor

path = [시작 도시]
while 방문하지 않은 도시가 있음:
    현재 도시에서 가장 가까운 미방문 도시 선택
    path에 추가
return path

장점:

  • 빠른 실행 속도 O(n²)
  • 구현이 간단
  • 합리적인 근사해 제공

단점:

  • 최적해 보장 없음
  • 지역 최적에 빠질 수 있음

2. Genetic Algorithm (유전 알고리즘)

원리: 생물의 진화를 모방한 탐색 알고리즘

프로세스:

1. 초기 개체군 생성 (무작위 해들)
2. 적합도 평가 (각 해의 품질)
3. 선택 (좋은 해들을 부모로)
4. 교차 (부모 해들을 조합)
5. 돌연변이 (무작위 변형)
6. 2-5 반복

연산자:

선택 (Selection):

  • Tournament Selection
  • Roulette Wheel Selection

교차 (Crossover):

  • TSP: Order Crossover (OX)
  • 이진 벡터: Single-point Crossover

돌연변이 (Mutation):

  • TSP: 두 도시 위치 교환
  • SAT: 비트 플립

파라미터:

  • 개체군 크기: 50-200
  • 세대 수: 100-1000
  • 교차 확률: 0.7-0.9
  • 돌연변이 확률: 0.01-0.1

장점:

  • 다양한 문제에 적용 가능
  • 지역 최적 탈출 가능
  • 병렬화 용이

단점:

  • 수렴 속도가 느릴 수 있음
  • 파라미터 튜닝 필요

3. Simulated Annealing (담금질 기법)

원리: 금속 담금질 과정을 모방한 확률적 탐색

알고리즘:

current = 초기_해
best = current
temperature = 초기_온도

while temperature > 최소_온도:
    neighbor = 이웃_해_생성(current)
    delta = cost(neighbor) - cost(current)
    
    if delta < 0:  # 더 좋은 해
        current = neighbor
        if cost(current) < cost(best):
            best = current
    else:  # 더 나쁜 해
        if random() < exp(-delta / temperature):
            current = neighbor  # 확률적 수락
    
    temperature *= cooling_rate

return best

온도 스케줄:

  • 지수 냉각: T = T₀ × αᵗ (α = 0.95)
  • 선형 냉각: T = T₀ - βt

이웃 해 생성:

  • TSP: 2-opt (두 간선 교환)
  • SAT: 단일 비트 플립
  • Graph Coloring: 단일 정점 색상 변경

장점:

  • 지역 최적 탈출 가능
  • 이론적 보장 (충분한 시간)
  • 구현 간단

단점:

  • 냉각 스케줄 튜닝 필요
  • 느린 수렴

머신러닝 기반 알고리즘

1. Deep Q-Network (DQN)

원리: 강화학습으로 가치 함수 학습

구조:

상태(State) → 신경망 → Q값(각 행동의 가치)

학습 알고리즘:

# Experience Replay
for episode in episodes:
    state = 초기_상태
    for step in steps:
        # Epsilon-greedy 정책
        if random() < epsilon:
            action = random_action()
        else:
            action = argmax(Q(state))
        
        next_state, reward = env.step(action)
        
        # 버퍼에 저장
        buffer.push(state, action, reward, next_state)
        
        # 학습
        if len(buffer) > batch_size:
            batch = buffer.sample(batch_size)
            loss = (Q(s,a) - (r + γ×max Q(s',a')))²
            optimize(loss)
    
    # Epsilon 감소
    epsilon *= decay

핵심 기법:

  • Experience Replay: 과거 경험 재사용
  • Target Network: 안정적 학습
  • Epsilon-greedy: 탐험-활용 균형

장점:

  • 대규모 문제에 확장 가능
  • 전이 학습 가능
  • 자동 특징 학습

단점:

  • 학습 시간 오래 걸림
  • 하이퍼파라미터 민감
  • 안정성 문제

2. Graph Neural Network (GNN)

원리: 그래프 구조를 직접 처리하는 신경망

구조:

그래프 → GNN 레이어들 → 노드/그래프 임베딩 → 예측

메시지 전달 (Message Passing):

for layer in layers:
    for node in graph:
        # 이웃 정보 수집
        messages = [transform(neighbor) for neighbor in node.neighbors]
        
        # 집계
        aggregated = aggregate(messages)  # sum, mean, max
        
        # 업데이트
        node.embedding = update(node.embedding, aggregated)

레이어 종류:

  • GCN: Graph Convolutional Network
  • GAT: Graph Attention Network
  • GraphSAGE: Sampling-based GNN

적용:

  • TSP: 도시 = 노드, 거리 = 간선
  • Graph Coloring: 직접 적용
  • SAT: 변수-절 이분 그래프

장점:

  • 그래프 구조 직접 활용
  • 귀납적 학습 (새 그래프에 일반화)
  • 해석 가능한 attention

단점:

  • 학습 데이터 필요
  • 계산 비용 높음
  • 큰 그래프에서 메모리 문제

LLM 기반 알고리즘

1. Direct Prompting

방법: 문제를 직접 LLM에 질문

프롬프트 예시:

다음 TSP 문제를 해결해주세요:
도시 개수: 5
거리 행렬:
  0   10  15  20  25
  10  0   35  40  30
  ...

최적 경로를 JSON 형식으로 제시하세요:
{"solution": [0, 1, 2, 3, 4]}

장점:

  • 구현 간단
  • 설명 포함 가능

단점:

  • 큰 문제에 제한
  • 일관성 낮음

2. Chain-of-Thought (CoT)

방법: 단계별 추론 유도

프롬프트 구조:

문제 설명
↓
"단계별로 해결해주세요:"
1. 문제 분석
2. 전략 수립
3. 해 구성
4. 검증
↓
최종 해

예시:

TSP를 단계별로 해결하세요:

1. 분석: 5개 도시, 완전 그래프
2. 전략: Nearest Neighbor 휴리스틱 사용
3. 구성:
   - 도시 0에서 시작
   - 가장 가까운 도시 1 방문
   - ...
4. 검증: 모든 도시 방문, 거리 = 105

최종: [0, 1, 3, 4, 2]

장점:

  • 더 정확한 결과
  • 추론 과정 확인 가능
  • 오류 감소

단점:

  • 토큰 사용량 증가
  • 느린 응답

3. Few-Shot Learning

방법: 예제를 제공하여 학습 유도

프롬프트 구조:

예제 1:
문제: [작은 TSP]
해: [최적해]
설명: [해결 과정]

예제 2:
문제: [다른 작은 TSP]
해: [최적해]
설명: [해결 과정]

이제 다음 문제를 같은 방식으로 해결하세요:
문제: [실제 문제]

장점:

  • 학습 효과
  • 형식 일관성
  • 품질 향상

단점:

  • 긴 프롬프트
  • 높은 비용

알고리즘 선택 가이드

문제 크기별

작은 문제 (n < 20):

  • 동적 프로그래밍
  • Branch & Bound
  • LLM (Few-shot)

중간 문제 (20 ≤ n < 100):

  • Greedy
  • Genetic Algorithm
  • Simulated Annealing
  • GNN

큰 문제 (n ≥ 100):

  • Greedy
  • DQN (학습 후)
  • 휴리스틱 조합

품질 요구사항별

최적해 필요:

  • Exact 알고리즘 (작은 문제)
  • Genetic Algorithm (충분한 시간)

빠른 근사해:

  • Greedy
  • LLM (Direct)

균형:

  • Simulated Annealing
  • GNN (학습 후)

자원별

계산 자원 풍부:

  • Genetic Algorithm
  • DQN 학습
  • GNN 학습

제한적 자원:

  • Greedy
  • Pre-trained 모델

API 사용 가능:

  • LLM (GPT-4)