복잡한 최적화 문제 해결을 가속화하는 머신 러닝

복잡한 최적화 문제 해결을 가속화하는 머신 러닝

복잡한 최적화 문제 해결을 가속화하는 머신 러닝? 산타클로스에게는 마법의 썰매와 9마리의 용감한 순록이 선물 배달을 도와줄 수 있지만, 페드엑스와 같은 회사의 경우 홀리데이 패키지를 효율적으로 라우팅하는 최적화 문제가 너무 복잡하여 전문 소프트웨어를 사용하여 해결책을 찾는 경우가 많습니다. 혼합 정수 선형 프로그래밍으로 되어 있는 솔버라고 불리는 이 소프트웨어는 대규모 최적화 문제를 작은 조각으로 나누고 일반 알고리즘을 사용하여 최상의 솔루션을 찾습니다. 그러나 해결사가 솔루션에 도달하는 데는 몇 시간, 심지어 며칠이 걸릴 수도 있습니다. 이 프로세스는 너무 부담스러워서 회사는 종종 소프트웨어를 중간에 중단해야 하며, 이상적이지는 않지만 정해진 시간 내에 생성할 수 있는 최선의 솔루션을 받아들여야 합니다. MIT와 ETH 취리히의 연구원들은 머신 러닝을 사용하여 속도를 높였습니다. 그들은 잠재적 솔루션이 너무 많아 풀리는 데 막대한 시간이 걸리고 전체 프로세스가 느려지는 MILP 솔버의 주요 중간 단계를 확인했습니다. 연구진은 이 단계를 단순화하기 위해 필터링 기술을 사용한 다음 머신 러닝을 사용하여 특정 유형의 문제에 대한 최적의 솔루션을 찾았습니다. 데이터 기반 접근 방식을 통해 회사는 자체 데이터를 사용하여 당면한 문제에 맞게 범용 MILP 해결사를 조정할 수 있습니다. 이 새로운 기술은 정확도 저하 없이 MILP 솔버의 속도를 30~70%까지 높였습니다. 이 방법을 사용하여 최적의 솔루션을 더 빨리 얻거나, 특히 복잡한 문제의 경우 다루기 쉬운 시간 내에 더 나은 솔루션을 얻을 수 있습니다. 이 접근 방식은 차량 호출 서비스, 전력망 운영자, 백신 접종 배포업체 또는 까다로운 리소스 할당 문제에 직면한 모든 기관과 같이 MILP 솔버를 사용하는 모든 곳에서 사용할 수 있습니다. 윈슬로우 토목 및 환경 공학 경력 개발 조교수이자 정보 및 의사 결정 시스템 연구소 및 데이터, 시스템 및 사회 연구소 회원이자 선임 저자인 캐시 우는 다음과 같이 설명했습니다. 때때로 최적화와 같은 분야에서는 사람들이 솔루션을 순전히 기계 학습 또는 순전히 고전적인 것으로 생각하는 것이 매우 일반적입니다. 저는 우리가 두 가지 장점을 모두 누리고 싶다고 굳게 믿고 있으며, 이는 하이브리드 접근 방식을 매우 강력하게 구현한 것이라고 밝혔습니다. 캐시 우는 IDSS 대학원생인 시루이 리와 CEE 대학원생인 웬빈 오우양, ETH 취리히 대학원생인 맥스 파울루스와 함께 이 논문을 집필했습니다. 이 연구는 신경 정보 처리 시스템 컨퍼런스에서 발표될 예정입니다. 하지만 해결하기 어려운 문제도 존재합니다. MILP 문제에는 기하급수적으로 많은 잠재적 해결책이 있습니다. 예를 들어서 여행 중인 영업사원이 여러 도시를 방문한 후 원래 도시로 돌아갈 수 있는 가장 짧은 경로를 찾고자 한다고 가정해 보겠습니다. 어떤 순서로든 방문할 수 있는 도시가 많으면 잠재적 솔루션의 수가 우주의 원자 수보다 많을 수 있습니다. 이러한 문제를 NP-하드라고 하는데, 이는 이를 해결할 수 있는 효율적인 알고리즘이 없을 가능성이 매우 낮다는 것을 의미합니다. 문제가 충분히 커지면 차선의 성능을 달성할 수 있기를 바랄 수밖에 없다고 캐시 우는 설명했습니다. MILP 솔버는 추적 가능한 시간 내에 합리적인 솔루션을 달성할 수 있는 다양한 기술과 실용적인 트릭을 사용합니다. 일반적인 솔버는 분할 정복 접근 방식을 사용하며, 먼저 분기라는 기술을 사용하여 잠재적 솔루션의 공간을 더 작은 조각으로 분할합니다. 그런 다음 솔버는 커팅이라는 기술을 사용하여 이러한 작은 조각을 더 빨리 검색할 수 있도록 조입니다. 커팅은 실행 가능한 솔루션을 제거하지 않고도 검색 공간을 강화하는 일련의 규칙을 사용합니다. 이러한 규칙은 다양한 종류의 MILP 문제를 위해 생성된 분리기로 알려진 수십 개의 알고리즘에 의해 생성됩니다. 캐시 우와 그녀의 팀은 사용할 분리기 알고리즘의 이상적인 조합을 식별하는 과정 자체가 기하급수적으로 많은 솔루션의 문제라는 사실을 발견했습니다. 이에 대해서 분리막 관리는 모든 해결사의 핵심 부분이지만, 이는 문제 공간에서 과소평가된 측면입니다. 이 작업의 기여 중 하나는 분리막 관리의 문제를 기계 학습 작업으로 파악하는 것이라고 그녀는 설명했습니다. 다음으로 솔루션 공간 축소에 대해서 설명하겠습니다. 캐시 우와 그녀의 협력자들은 이 분리막 검색 공간을 13만 개 이상의 잠재적 조합에서 약 20개의 옵션으로 줄이는 필터링 메커니즘을 고안했습니다. 이 필터링 메커니즘은 한계 수익률 감소 원칙을 기반으로 하며, 가장 큰 이점은 소수의 알고리즘 세트에서 얻을 수 있으며 추가 알고리즘을 추가해도 큰 개선 효과가 없다는 것입니다. 그런 다음 머신 러닝 모델을 사용하여 나머지 20개 옵션 중에서 가장 적합한 알고리즘 조합을 선택합니다. 이 모델은 사용자의 최적화 문제에 특정한 데이터 세트로 학습되므로 사용자의 특정 작업에 가장 적합한 알고리즘을 선택하는 방법을 학습합니다. 페드엑스와 같은 회사는 이전에 라우팅 문제를 여러 번 해결한 적이 있으므로, 과거 경험에서 수집한 실제 데이터를 사용하면 매번 처음부터 시작하는 것보다 더 나은 솔루션을 제공할 수 있습니다. 강화 학습의 한 형태인 컨텍스트 밴디트로 알려진 모델의 반복 학습 프로세스에는 잠재적인 솔루션을 선택하고, 얼마나 좋은지 피드백을 받은 다음 더 나은 솔루션을 찾기 위해 다시 시도하는 것이 포함됩니다. 이 데이터 기반 접근 방식은 정확도 저하 없이 MILP 솔버를 30%에서 70%까지 가속화했습니다. 또한, 더 간단하고 오픈 소스인 솔버와 더 강력한 상용 솔버에 적용했을 때도 속도 향상은 비슷했습니다. 향후 캐시 우는 모델 학습을 위해 레이블이 지정된 데이터를 수집하는 것이 특히 어려울 수 있는 훨씬 더 복잡한 MILP 문제에 이 접근 방식을 적용하고자 합니다. 아마도 더 작은 데이터 세트로 모델을 훈련시킨 다음 훨씬 더 큰 최적화 문제를 해결하기 위해 모델을 조정할 수 있을 것이라고 그녀는 말합니다. 연구자들은 또한 학습된 모델을 해석하여 다양한 분리기 알고리즘의 효과를 더 잘 이해하는 데 관심이 있습니다. 지금까지 복잡한 최적화 문제 해결을 가속화하는 머신 러닝에 대해서 알아봤습니다.