조합 최적화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 대표적인 문제
4. 방법
5. NP-최적화 문제 (NPO)
6. 응용 분야
7. 관련 학술지
참조

1. 개요

조합 최적화는 이산 집합에서 가장 좋은 해를 찾는 것을 목표로 하는 최적화 문제이다. 0-1 최적화 문제는 해가 이진 벡터인 경우에 해당한다. 조합 최적화의 대표적인 문제로는 외판원 문제, 차량 경로 문제, 배낭 문제 등이 있으며, 선형 계획법, 정수 계획법, 여덟 퀸 문제 등도 포함된다. 이러한 문제를 해결하기 위해 지역 탐색, 담금질 기법, 유전 알고리즘, 개미 집단 최적화 등 다양한 방법이 사용된다. NP-최적화(NPO) 문제는 조합 최적화 문제의 한 종류로, 근사 가능성에 따라 여러 하위 클래스로 나뉜다. 조합 최적화는 물류, 공급망 최적화, 네트워크 설계 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

조합 최적화 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다.
조합 최적화 - 정수 계획법
정수 계획법은 선형 계획법의 한 분야로, 해가 정수 값을 가져야 하는 제약 조건이 추가된 최적화 문제이며, 다양한 분야에 응용되고 정확한 알고리즘 또는 휴리스틱 방법을 통해 해결할 수 있다.
계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.
이론 컴퓨터 과학 - 알고리즘
알고리즘은 문제 해결을 위한 명확하고 순서화된 유한 개의 규칙 집합으로, 알콰리즈미의 이름에서 유래되었으며, 수학 문제 해결 절차로 사용되다가 컴퓨터 과학에서 중요한 역할을 하며 다양한 방식으로 표현되고 효율성 분석을 통해 평가된다.
이론 컴퓨터 과학 - 자동화된 추론
자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.

조합 최적화
개요
분야	수학 최적화
하위 분야	조합론 알고리즘 계산 복잡도 이론
정의
목표	유한한 대상 집합에서 최적의 대상을 찾는 것
적용 분야	운영 연구 물류 암호학 이산 수학 이론 컴퓨터 과학
특징
문제 복잡도	대부분의 문제는 NP-hard
해결 방법	문제 특성 활용 알고리즘 설계 근사 알고리즘 휴리스틱
예시
예시 문제	최단 경로 문제 최소 비용 신장 트리 문제 배낭 문제 여행하는 외판원 문제 최대 유량 문제 스케줄링 문제 할당 문제 포장 문제 커버링 문제
관련 주제
관련 분야	선형 계획법 정수 계획법 볼록 최적화 네트워크 최적화 알고리즘 게임 이론

2. 정의

조합 최적화는 가능한 해가 이산 집합에 속하거나 이산적인 것으로 변환될 수 있고, 가장 좋은 해를 찾는 것이 목적인 최적화 문제이다.^[1] 그 목적은 최적해의 집합이 이산적이거나 이산적인 것으로 줄일 수 있는 문제에서 가장 좋은 해결책을 찾는 것이다.^[1]

해결책이 이진 벡터인 경우에는 0-1 최적화 문제라고도 한다.^[1]

2. 1. 약식 정의

조합 최적화는 가능해가 이산 집합에 속하거나 이산적인 것으로 변환될 수 있고, 가장 좋은 해를 찾는 것이 목적인 최적화 문제이다.^[1] 그 목적은 최적해의 집합이 이산적이거나 이산적인 것으로 줄일 수 있는 문제에서 가장 좋은 해결책을 찾는 것이다.^[1]

해결책이 이진 벡터인 경우에는 '''0-1 최적화 문제'''라고도 한다.^[1]

2. 2. 엄밀한 정의

조합 최적화 문제의 인스턴스는

(X, P, Y, f, \mathrm{extr})

요소의 튜플로 쓸 수 있다. 여기서 각 기호는 아래와 같은 뜻이다.

''X'' - 문제 공간 (이 공간상에서 ''f''와 ''P''가 정의된다)
''P'' - 유효성을 나타내는 술어
''Y'' - 가능해의 집합
''f'' - 목적 함수
extr - 극단값 (보통 최솟값이나 최댓값)

2. 3. 0-1 최적화 문제

해가 이진 벡터인 경우에는 '''0-1 최적화 문제'''라고도 한다.^[1]

3. 대표적인 문제

외판원 문제: 주어진 모든 도시를 한 번씩 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제이다.^[10]
차량 경로 문제
최소 비용 걸침 나무 문제
선형계획법 (해의 공간이 어떤 변수를 기본 변수로 할 것인지 고르는 것과 같다면)
여덟 퀸 문제 (제약 만족 문제의 일종. 이러한 문제에 표준 조합 최적화 알고리즘을 적용할 때는 문제 전체가 만족되었는지 여부를 나타내는 불 변수 하나보다는 만족되지 않은 제약 조건의 수를 최적화하는 목적 함수를 주로 사용한다.)
배낭 문제
할당 문제
최적 적재 문제
중국 우체부 문제
폐쇄 문제
제약 만족 문제
절단 문제
지배 집합 문제
정수 계획법
작업장 스케줄링
메트릭 k-중심점 / 정점 k-중심점 문제
선형 시스템에서 최소 관련 변수
최소 신장 트리
간호사 스케줄링 문제
링 스타 문제
집합 커버 문제
인재 스케줄링
차량 재스케줄링 문제
무기 목표 할당 문제
최단 경로 문제
최대 유량 문제
최소 컷 문제
최대 매칭 문제
열 모듈러 함수 최소화
열 모듈러 함수 최대화

4. 방법

조합 최적화 문제를 해결하기 위해 다양한 방법들이 사용된다. 이러한 방법들은 크게 일반적인 방법, 특정 문제에 대한 방법, 그리고 휴리스틱 및 메타휴리스틱으로 분류할 수 있다.

일반적인 방법: 분기 한정법, 분기 및 절단법, 동적 계획법, 타부 탐색 등은 다양한 조합 최적화 문제에 널리 적용될 수 있다. 하지만 이러한 방법들은 항상 최적의 해를 찾거나 빠른 시간 안에 해결책을 제시하는 것을 보장하지는 않는다.
특정 문제에 대한 방법: 선형 계획법 이론을 통해 해결 가능한 문제들이 있다. 예를 들어 최단 경로 문제, 흐름 네트워크 문제, 신장 트리 문제, 매칭 문제 등이 이에 해당한다.^[5]
휴리스틱 및 메타휴리스틱: 지역 탐색, 담금질 기법, 타부 탐색, 유전 알고리즘, 개미 집단 최적화 등은 최적해를 보장하지는 않지만, 비교적 좋은 해를 빠르게 찾을 수 있는 방법들이다.

NP-완전 문제의 경우, P=NP가 아닌 이상 다항 시간 내에 해결하기 어려울 것으로 예상된다.^[6] 이러한 문제들을 해결하기 위해, 최적에 가까운 해를 찾는 근사 알고리즘이나, 실제 사례에서 잘 동작하는 알고리즘을 찾는 연구가 진행되고 있다.^[5]

4. 1. 일반적인 방법

분기 및 한정법(임의의 시점에 중단하여 휴리스틱으로 사용할 수 있는 정확한 알고리즘), 분기 및 절단법(경계를 생성하기 위해 선형 최적화를 사용), 동적 프로그래밍(제한된 탐색 창이 있는 재귀 솔루션 구성) 및 타부 탐색(탐욕형 교환 알고리즘)과 같이 널리 적용 가능한 접근 방식이 있다. 그러나 일반 탐색 알고리즘은 최적의 해를 먼저 찾도록 보장되지 않으며 빠르게(다항 시간 내에) 실행되도록 보장되지도 않는다. 일부 이산 최적화 문제는 NP-완전이므로, 외판원 문제(결정)와 마찬가지로^[6], P=NP가 아닌 한 다항 시간 내에 풀리지 않을 것으로 예상된다.

일반적인 탐색 방법은 다음과 같다.

탐색 방법	설명
분기 한정법	탐색 공간을 분할하고 각 부분 문제의 하한/상한을 계산하여 불필요한 탐색을 제거하는 방법이다.
동적 계획법	문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 재사용하는 방법이다.
탐욕법	현재 상황에서 가장 좋아 보이는 것을 먼저 선택하며 진행하는 방법이다.
깊이 우선 탐색	그래프에서 깊이를 우선하여 탐색하는 방법이다.
너비 우선 탐색	그래프에서 너비를 우선하여 탐색하는 방법이다.
균일 비용 탐색	비용이 가장 적은 경로를 우선적으로 탐색하는 방법이다.
양방향 탐색	시작점과 도착점에서 동시에 탐색을 진행하여 중간에서 만나는 경로를 찾는 방법이다.

4. 2. 특정 문제에 대한 방법

선형 계획법 이론으로 해결 가능한 조합 최적화 문제의 예시로는 최단 경로 및 최단 경로 트리, 흐름 및 순환, 신장 트리, 매칭, 매트로이드 문제가 있다.^[5]

최단 경로 문제
* 다익스트라 알고리즘
* 벨만-포드 알고리즘
최소 신장 트리
* 프림 알고리즘
* 크루스칼 알고리즘
최대 유량 문제·최소 컷 문제
* 포드-풀커슨 알고리즘
* 에드몬드-카프 알고리즘
외판원 문제
* 최근접 이웃법
* 크리스토피데스 알고리즘

4. 3. 휴리스틱 및 메타휴리스틱

다음은 조합 최적화 문제를 해결하는 데 사용되는 발견 탐색 방법(메타휴리스틱 알고리즘)들이다.

지역 탐색
담금질 기법
타부 탐색
유전 알고리즘
개미 집단 최적화
반응 탐색
무리 지능
GRASP

Local Search^영어(지역 탐색)는 현재 해의 이웃 해들을 탐색하면서 더 좋은 해를 찾아가는 방법이다. Best-First Search^영어(최상 우선 탐색), A* 알고리즘, Simulated Annealing^영어(담금질 기법)은 확률적으로 나쁜 해를 허용하면서 지역 최적해에 갇히는 문제를 해결하는 방법이다. Tabu Search^영어(타부 탐색)은 최근에 탐색한 해를 타부 리스트에 저장하여 중복 탐색을 피하고 지역 최적해에서 벗어나는 방법이다. Genetic Algorithm^영어(유전 알고리즘)은 자연 선택과 유전의 원리를 모방하여 해 집단을 진화시키는 방법이다. Ant Colony Optimization^영어(개미 집단 최적화)는 개미의 집단 행동을 모방하여 최적 경로를 찾는 방법이다. Reactive Search^영어(반응 탐색), Greedy Randomized Adaptive Search Procedure^영어(GRASP)도 사용되는 휴리스틱 및 메타휴리스틱이다.

5. NP-최적화 문제 (NPO)

'''NP-최적화 문제'''(NPO)는 다음과 같은 추가 조건을 가진 조합 최적화 문제이다.^[8]

모든 가능한 해 $y\in f(x)$ 의 크기는 주어진 인스턴스 $x$ 의 크기에서 다항식으로 제한된다.
언어 $\{\,x\,\mid\, x \in I \,\}$ 및 $\{\,(x,y)\, \mid\, y \in f(x) \,\}$ 는 다항식 시간 내에 인식될 수 있다.
$m$ 은 다항 시간으로 계산 가능하다.

이는 해당 결정 문제가 NP에 속함을 의미한다. 컴퓨터 과학에서 흥미로운 최적화 문제는 일반적으로 위와 같은 속성을 가지며 따라서 NPO 문제이다. 문제가 최적의 해를 다항 시간 내에 찾는 알고리즘이 존재하는 경우 P-최적화(PO) 문제라고 추가로 불린다.

NPO는 근사 가능성에 따라 다음과 같은 하위 클래스로 나뉜다.^[8]

'''NPO(I):''' FPTAS와 같다. 배낭 문제를 포함한다.
'''NPO(II):''' PTAS와 같다. Makespan 스케줄링 문제를 포함한다.
'''NPO(III):''' 최적 비용의 최대 ''c''배(최소화 문제의 경우) 또는 최적 비용의 최소 $1/c$ (최대화 문제의 경우)의 비용으로 솔루션을 계산하는 다항 시간 알고리즘을 가진 NPO 문제의 클래스이다. MAX-SAT 및 메트릭 TSP를 포함한다.
'''NPO(IV):''' 입력 크기의 로그에서 다항식인 비율로 최적 솔루션을 근사하는 다항 시간 알고리즘을 가진 NPO 문제의 클래스이다. 집합 커버 문제를 포함한다.
'''NPO(V):''' 최적 솔루션을 n에 대한 어떤 함수로 제한된 비율로 근사하는 다항 시간 알고리즘을 가진 NPO 문제의 클래스이다. TSP 및 클리크 문제를 포함한다.

6. 응용 분야

물류^[2]
공급망 최적화^[3]
최적의 항공 노선 네트워크 (스포크 및 목적지) 개발
택시 회사에서 요금을 픽업하기 위해 어떤 택시를 배차할지 결정
소포를 배달하는 최적의 방법 결정
사람들에게 작업을 최적으로 할당
수도 분배 네트워크 설계
지구과학 문제 (예: 저수지 유량)^[4]

7. 관련 학술지

참조

_[1] 서적
_[2] 논문 Combinatorial optimization and Green Logistics https://hal.archives[...] 2019-12-26
_[3] 논문 Sustainable supply chain network design: An optimization-oriented review https://hal.archives[...] 2019-12-26
_[4] 논문 Estimating fluid flow rates through fracture networks using combinatorial optimization https://www.scienced[...] 2020-09-16
_[5] 서적
_[6] 웹사이트 Approximation-TSP https://www.csd.uoc.[...] 2022-02-17
_[7] 서적 Complexity and Approximation Springer
_[8] 서적 Algorithmics for Hard Problems Springer
_[9] 간행물 On the Approximability of NP-complete Optimization Problems Royal Institute of Technology, Sweden
_[10] 문서

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com