온라인 최적화
Online optimization온라인 최적화는 최적화 이론의 한 분야로서 컴퓨터 과학과 운영 연구에서 더 인기 있는 분야로서 미래에 대한 지식이 없거나 불완전한 최적화 문제를 다루고 있다(온라인).이러한 종류의 문제는 온라인 문제로 표시되며, 완전한 정보가 가정되는 고전적 최적화 문제와 반대되는 것으로 간주된다(오프라인).온라인 최적화에 대한 연구는 한 조각씩 입력하여 순차적으로 복수의 의사결정이 이루어지는 온라인 문제와 한 번만 의사결정이 이루어지는 온라인 문제로 구분할 수 있다.한 번만 결정을 내리는 유명한 온라인 문제는 스키 대여 문제다.일반적으로 온라인 알고리즘의 출력은 항상 최적이며 입력 전체를 미리 알고 있는 해당 오프라인 알고리즘의 솔루션(경쟁력 분석)과 비교된다.
많은 상황에서 현재의 결정(예: 자원 배분)은 미래에 대한 불완전한 지식이나 미래에 대한 분배적 가정이 신뢰할 수 없는 상태에서 이루어져야 한다.이러한 경우 온라인 최적화를[1] 사용할 수 있는데, 이는 강력한 최적화, 확률적 최적화, 마르코프 의사결정 프로세스와 같은 다른 접근법과는 다르다.
온라인 문제
온라인 알고리즘의 개념을 예시하는 문제는 캐나다 여행자 문제다.이 문제의 목적은 일부 가장자리가 신뢰할 수 없고 그래프에서 제거되었을 수 있는 가중 그래프에서 목표값에 도달하는 비용을 최소화하는 것이다.그러나 가장자리가 제거(실패)되었다는 것은 가장자리의 끝점 중 하나에 도달했을 때에만 여행자에게 나타난다.이 문제의 가장 나쁜 경우는 단순히 모든 신뢰할 수 없는 가장자리가 실패하고 문제가 일반적인 최단 경로 문제로 줄어든다는 것이다.경쟁 분석의 도움을 받아 문제에 대한 대체 분석을 할 수 있다.이 분석 방법을 위해 오프라인 알고리즘은 어떤 에지가 고장날지 미리 알고 있으며, 목표는 온라인과 오프라인 알고리즘의 성능 비율을 최소화하는 것이다.이 문제는 PSPACE-완전이다.
솔루션으로 두 개 이상의 온라인 알고리즘을 제공하는 많은 공식적 문제가 있다.
- k-server 문제
- 작업소 스케줄링 문제
- 업데이트 문제 나열
- 도적 문제
- 비서 문제
- 검색 게임
- 스키 대여 문제
- 선형검색문제
- 포트폴리오선택문제[2]
참고 항목
참조
- ^ 감옥, 패트릭, 그리고 마이클 R.바그너.온라인 최적화.Springer 출판사, Incorporated.
- ^ Dochow, Robert (2016). Online Algorithms for the Portfolio Selection Problem. Springer Gabler.
