Skip to content

research_notes.md

Latest commit

 

History

History
184 lines (132 loc) · 4.61 KB

research_notes.md

File metadata and controls

184 lines (132 loc) · 4.61 KB

연구 노트

프로젝트 동기

NP-complete 문제는 컴퓨터 과학의 핵심 난제입니다. P ≠ NP가 사실이라면 이러한 문제들에 대한 다항 시간 알고리즘은 존재하지 않습니다. 하지만 AI 시대에 우리는 새로운 접근법을 시도할 수 있습니다:

  1. 머신러닝: 패턴 학습을 통한 휴리스틱 자동 발견
  2. 강화학습: 탐색 전략 학습
  3. LLM: 자연어 추론을 통한 문제 해결

연구 질문

Q1: ML/RL이 전통적 휴리스틱을 능가할 수 있는가?

가설: 충분한 학습 데이터가 있다면 DQN/GNN이 더 좋은 해를 찾을 수 있다.

예비 결과:

  • 작은 문제 (n < 20): ML 모델이 경쟁력 있음
  • 중간 문제 (20 ≤ n < 50): 학습 시간 대비 성능 향상 미미
  • 큰 문제 (n ≥ 50): 전통적 휴리스틱이 우수

통찰:

  • ML은 특정 문제 분포에 특화될 때 효과적
  • 전이 학습이 핵심
  • 일반화 능력이 과제

Q2: LLM의 추론 능력을 활용할 수 있는가?

가설: LLM의 추론 능력으로 작은 문제를 해결하고 큰 문제는 분해 전략 사용

예비 결과:

  • Direct prompting: n ≤ 10에서 합리적
  • Chain-of-Thought: 추론 과정 개선, 정확도 향상
  • Few-shot: 일관성 크게 개선

통찰:

  • LLM은 설명 가능한 해 생성
  • 큰 문제는 decomposition 필요
  • 프롬프트 엔지니어링이 중요

Q3: 하이브리드 접근법의 가능성?

아이디어:

  1. LLM으로 전략 생성 → ML로 실행
  2. 전통적 방법으로 초기해 → ML로 개선
  3. ML로 feature 추출 → LLM으로 의사결정

가능한 시너지:

  • LLM: 고수준 전략
  • ML: 저수준 최적화
  • 전통적: 빠른 기준선

실험 설계

실험 1: 문제 크기에 따른 성능

설정:

  • 문제: TSP
  • 크기: 10, 20, 30, 40, 50
  • 솔버: Greedy, GA, SA, DQN, GNN, LLM
  • 인스턴스: 각 50개

메트릭:

  • 평균 비용
  • 표준 편차
  • 실행 시간
  • 최적 갭 (알려진 경우)

실험 2: 학습 데이터 크기 영향

설정:

  • ML 학습 인스턴스: 100, 500, 1000, 5000
  • 테스트: 100 인스턴스

관찰:

  • 학습 곡선
  • 일반화 성능
  • 과적합 여부

실험 3: LLM 프롬프팅 전략

설정:

  • 방법: Direct, CoT, Few-shot, Self-consistency
  • 온도: 0.0, 0.7, 1.0
  • 문제 크기: 5, 10, 15

분석:

  • 정확도
  • 일관성
  • 비용 (토큰 사용량)

발견 사항

1. 전통적 알고리즘의 강력함

탐욕, 유전 알고리즘, 담금질 기법은 여전히 매우 경쟁력 있습니다:

  • 빠른 실행
  • 안정적 성능
  • 튜닝 용이

2. ML의 전이 학습 과제

같은 문제 타입이라도 분포가 다르면 성능 저하:

  • 유클리드 TSP → 비유클리드 TSP
  • 랜덤 그래프 → 실제 네트워크

해결책: Domain adaptation, Meta-learning

3. LLM의 제한과 가능성

제한:

  • 큰 문제 처리 어려움
  • API 비용
  • 일관성 문제

가능성:

  • 설명 가능성
  • 제로샷 능력
  • 창의적 전략

4. 문제별 특화 필요

각 NP-complete 문제는 고유한 구조:

  • TSP: 기하학적 구조
  • SAT: 논리적 제약
  • Graph Coloring: 토폴로지

범용 솔버보다 문제별 특화가 효과적

향후 연구 방향

1. Neural Combinatorial Optimization

Attention Is All You Need 스타일의 구조:

  • Transformer for TSP
  • Pointer Networks
  • Graph Attention

2. LLM as Optimizer

최근 연구 (Yang et al., 2023):

  • LLM으로 휴리스틱 생성
  • 자동 프롬프트 최적화
  • 메타 학습

3. Quantum-Inspired Algorithms

양자 컴퓨팅 시뮬레이션:

  • QAOA (Quantum Approximate Optimization Algorithm)
  • 고전 시뮬레이션으로 통찰 얻기

4. 실제 응용

벤치마크를 넘어 실제 문제:

  • 물류 최적화
  • 칩 설계
  • 단백질 접힘

재현성 체크리스트

모든 실험에서 다음을 기록:

  • 난수 시드
  • 하이퍼파라미터
  • 환경 (OS, Python 버전, 라이브러리 버전)
  • 데이터 생성 방법
  • 실행 시간 측정 방법

참고문헌

  1. Bello, I., et al. (2016). Neural Combinatorial Optimization with Reinforcement Learning.
  2. Kool, W., et al. (2019). Attention, Learn to Solve Routing Problems!
  3. Nowak, A., et al. (2017). Learning to Solve NP-Complete Problems.
  4. Yang, C., et al. (2023). Large Language Models as Optimizers.
  5. Bengio, Y., et al. (2021). Machine Learning for Combinatorial Optimization.

버전 히스토리

v0.1.0 (2026-01-02)

  • 초기 구현
  • TSP, SAT, Graph Coloring, Knapsack
  • Greedy, GA, SA 솔버
  • DQN, GNN 기본 구현
  • LLM 통합
  • 벤치마크 프레임워크