• 메타휴리스틱 이론, 메타휴리스틱 기법에 대해 작성한 글입니다

---

Overview

Operations Research

• OR
• 수학적 모델링이나 통계 분석, 최적화 기법 등을 이용해 복잡한 의사결정 문제에서 최적해 혹은 근사최적해를 찾아내 이익, 성능, 수익 등을 최대화하거나 손실, 위험, 비용 등을 최소화하는 현실적인 문제를 해결할 때 사용
• 2차 세계 대전에서 기원
  • Scheduling
  • Transportation
  • Inventory management
  • Warehousing
  • Facility allocation
  • Energy distribution
• 예제
  • 의자는 15BF, 6시간 노동력이 필요하고 식탁은 24BF, 5시간의 노동력이 필요
  • Maximize profit => z = 12X + 10Y
    • Chair : 12달러, Table : 10달러
  • Subjected to
    • 15X + 24Y <= 300
    • 6X + 5Y <= 120

OR 구성 요소

• 목적 함수(Objective function)
• 결정 변수(Decision variables)
  • 목적 함수식이나 제약조건에서 미지수로 나타나는 변수
• 제약 조건(Constraints)

Types of Solutions and Constraints

• Solutions
  • Infeasible : 모든 제약조건에 만족하는 solution이 없는 경우
  • Feasible
  • Optimal
  • Near-Optimal
• Constraints
  • Hard constraints : 필수 제약조건
  • Soft constraints

Continuous vs Combinatorial

Continuous

• 연속적 문제
• 결정 변수가 연속적인 문제

Combinatorial

• 결정 변수가 이산적인 문제
• 이산적 문제, 조합 최적화 문제
• 정수 계획법(Integer Programming : 결정 변수가 정수인 최적화 문제)이 대표적
• 예시
  • Traveling Salesman Problem(TSP)
  • Vehicle Routing Problem(VRP)
  • Knapsack PRoblem(KP)
  • Quadratic Assignment Problem(QAP)

P vs NP Problems

• P problem : 짧은 다항식 문제
• NP problem : 짧은 non-deterministic 문제

메타휴리스틱

• 휴리스틱
  • 합리적인 계산 비용으로 최적 또는 거의 최적의 솔루션을 찾는 기술
• 메타휴리스틱
  • 특정 문제에 특화되지 않고 자연에서 영감을 얻은 경험적 방법
• NP Problem은 문제가 커지면서 점점 더 어려워짐
• 자주 사용되는 메타휴리스틱 방법
  • Genetic Algorithm(GA)
  • Tabu Search(TS)
  • Ant Colony Optimization(ACO)
  • Partical Swarm Optimization(PSO)
  • Simulated Annealing(SA)

Search Techniques

• Local search vs global search
  • local : 이웃에 기반함, 그리드 서치
  • global : search space
• Deterministic vs stochastic
  • deterministic : non-random
• 참고 링크
• Continuous Problem
  • 특정 인풋으로부터 어떤 output이 나오는 함수
  • Minimization or maximization 문제
  • Himmelblau’s function
• Combination Problem
  • discrete elements의 조합 문제
  • Minimization or maximization 문제
  • TSP 문제
    • 5개의 도시 : A, B, C, D, E
    • minimum route : D-A-E-C-B (최소 거리)
    • 다른 것도 가능 : A-D-C-E-B

Neighborhood vs Population Search

• Neighborhood search
  • 
  • local search
  • 계산적으로 어려운 최적화 문제를 해결하는 휴리스틱 방법론
  • 잠재적 솔루션을 취하고 주변 환경(일종의 이웃)을 체크
  • Simulated Annealing and Tabu Search
• Population Based Search
  • 각 iteration에서 솔루션의 population를 사용하는 방법
  • 잠재성이 있는 솔루션을 Evaluate
  • 랜덤하게 다른 솔루션을 생산하기 위한 솔루션을 선택
  • Genetic Aglorithm, Evolutionary Strategies, Particle Swarm Optimization

메타휴리스틱은 어떻게 작동하는가?

• Random initial solution
• Neighborhood search
  • 초기 솔루션부터 근처를 돌아다니며 실행
  • 모든 스텝을 evaluate
  • 각 스텝의 목적 값(objective value)를 추적
• Population-Based search
  • 랜덤 초기 솔루션을 여러개 생성
  • 더 “나은” 솔루션을 생성
  • Diverse

Reference

• 휴리스틱 이론 - 위키피디아

카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)