최적화 기본 사항

완료됨

최적화 문제를 이해하려면 먼저 몇 가지 용어를 익혀야 합니다.

  • 비용 함수: 최소화되어야 하는 수학적 함수입니다. 광물 운반의 경우 비용 함수는 두 공간 컨테이너 간 무게 차이입니다. 다른 시나리오에서는 이동 거리나 금전적 비용일 수 있습니다.
  • 검색 공간: 최적화 문제에 적합한 솔루션이 모두 포함된 공간입니다. 이 검색 공간의 각 지점은 문제에 유효한 솔루션이지만 반드시 최저 비용 솔루션에 해당하는 최저점일 필요는 없습니다.

비용 함수와 검색 공간을 합쳐서 최적화 지형 이라고도 합니다. 두 개의 연속 변수를 포함하는 문제의 경우 지형에 비유하는 것이 매우 직접적입니다.

몇 가지 지형을 살펴보고 QIO에 적합한 후보를 알아보겠습니다.

하나의 반듯한 지형

하나의 반듯한 계곡처럼 보이는 다음의 비용 함수 플롯을 생각해 보세요.

하나의 반듯한 계곡처럼 보이는 최적화 지형 플롯.

이러한 종류의 문제는 초기 출발점에서 시작하여 비용이 더 낮은 솔루션으로 과감하게 움직이는 ‘기울기 하강’과 같은 기법으로 쉽게 해결됩니다. 몇 번 움직이고 나면 솔루션은 전역 최솟값으로 수렴합니다. 전역 최솟값은 최적화 지형의 최저점입니다. 이처럼 간단한 문제를 해결하는 데는 QIO가 다른 기법에 비해 이점이 있지는 않습니다.

구조화된 험난한 지형

QIO는 지형에 언덕과 계곡이 많아서 험난한 문제에 가장 적합합니다. 다음은 두 개의 연속 변수를 고려하는 예제입니다.

꼭대기와 계곡이 많은 최적화 지형의 플롯.

이 시나리오에서 가장 큰 난제 중 하나는 차선의 특정한 국소 최솟값에서 막히지 않도록 하는 것입니다. 험난한 지형에는 계곡이 많을 수 있습니다. 각 계곡에는 최저점이 있으며, 이는 국소 최솟값입니다. 이러한 점 중 하나는 전체에서 최소이며, 해당 점을 전역 최솟값이라고 합니다.

이처럼 험난한 지형은 QIO가 다른 기법을 능가할 수 있는 상황을 보여줍니다.

분산된 임의의 지형

지금까지는 반듯하고 들쭉날쭉한 비용 함수에 대해 논의했지만, 만약 아예 구조가 없다면 어떨까요? 다른 다이어그램에는 그러한 지형이 나타나 있습니다.

임의로 분산된 지점을 나타낸 최적화 지형 플롯.

이 경우, 솔루션의 위치는 완전히 임의로 정해지며 알고리즘은 무작위 검색보다 나은 방법이 아닐 수 있습니다.

비용 함수를 작성하려면 어떻게 해야 하나요?

앞에서 설명한 대로, 비용 함수는 최소화하려는 수량을 나타냅니다. 주요 목적은 문제의 각 구성을 단일 숫자에 매핑하는 것입니다. 이렇게 매핑하면 최적화 프로그램에서 손쉽게 잠재적 솔루션을 비교하고 어떤 것이 더 좋은지 결정할 수 있습니다.

문제 관련 비용 함수를 생성하는 비결은 선택한 비용에 영향을 주는 시스템 매개 변수를 인식하는 것입니다. 채굴 임무에서 비용은 두 컨테이너 간 무게 차이입니다. 해당 비용에 영향을 주는 요소는 컨테이너에 대한 각 광물 덩어리의 할당입니다.

원칙적으로 비용 함수는 수치 연산 함수인 $f = f(x_0, x_1, \dots)$일 수 있습니다. 여기서 함수 변수 $x_1, x_2, \dots$는 다양한 구성을 인코딩합니다.

예를 들어 앞에서 언급한 반듯한 지형은 두 개의 연속 변수 $f(x, y) = x^2 + y^2$의 이차 함수를 사용하여 생성할 수 있습니다. 그러나 특정 최적화 방법에서는 비용 함수를 특정 형식으로 지정해야 할 수도 있습니다. 예를 들어, Azure Quantum 해결기는 ‘이진 최적화 문제’를 예상합니다. 해당 문제 유형의 경우 구성은 $x_i \in \{0, 1\}$를 사용하여 이진 변수를 통해 표현해야 합니다.

특정 광물 덩어리가 첫 번째 또는 두 번째 컨테이너에 적재되는지 여부 같은 대부분의 문제는 자연스럽게 이 형식으로 표현하는 것이 적합합니다.

PUBO(Polynomial Unconstrained Binary Optimization, ‘다항식 비제약 이진 최적화’)는 이진 변수를 통한 다항식인 비용 함수를 나타냅니다. ‘비제약’은 유효한 변수 할당에 대한 추가 제한을 적용하지 않아 해결기 작업을 간소화함을 의미합니다.

다음 모듈 Azure Quantum을 사용하여 작업 매장 일정 최적화 문제 해결에서는 이러한 제한을 해결하고 PUBO 설정에서 제약 조건을 표현하는 방법을 알아봅니다. PUBO 문제의 특별한 하위 집합은 수준 2의 다항식 비용 함수를 사용하는 QUBO(Quadratic Unconstrained Binary Optimization, ‘이차 비제약 이진 최적화’) 문제입니다. Azure Quantum 해결기는 기본적으로 모든 수준의 PUBO에서 작동하지만 Azure에서 사용할 수 있는 다른 공급자는 QUBO 문제에만 사용할 수 있습니다.

‘이징(Ising)’ 문제라고 하는 문제가 발생할 수도 있습니다. 경우에 따라 $\{0, 1\}$ 대신 $\{-1, 1\}$ 값을 이진 변수에 제공하는 것이 더 편리합니다. 그러지 않으면 해당 문제는 PUBO 문제와 동일하게 작동합니다.

요약

복잡하고 구조화된 지형이 QIO에 대해 가장 잘 작동하는 방식을 보여 주는 요약

요약하자면 기존의 다른 최적화 알고리즘에 비해 QIO가 제대로 작동하는 데 필요한 조건은 다음과 같습니다.

  • 최적화 지형은 들쭉날쭉하되, 구조화되어 있어야 합니다. 해당 지형은 현실 문제에서 빈번하게 발생합니다.
  • 변수의 수가 너무 적으면, 단순한 알고리즘으로도 이미 충분합니다. 수백 개의 변수가 포함된 문제의 경우, QIO는 기존에 사용되었던 방법에 비해 자릿수 개선을 이루었습니다.
  • 선택한 비용 메트릭에 영향을 주는 문제 매개 변수는 비용 함수의 변수를 통해 표현해야 합니다. 이진 변수를 통해 비용 함수를 다항식으로 표현하여 PUBO 문제를 가져옵니다.