실제 문제 해결을 위한 하이브리드 접근 방식

Scientific Reports 13권, 기사 번호: 11777(2023) 이 기사 인용

418 액세스

2 알트메트릭

측정항목 세부정보

품목을 쓰레기통에 효율적으로 포장하는 것은 일반적인 일상 작업입니다. 빈 포장 문제(Bin Packing Problem)라고도 알려진 이 문제는 산업계와 물류계의 폭넓은 관심에 힘입어 인공지능 분야에서 집중적으로 연구되어 왔습니다. 수십 년 동안 실제 사용 사례에 가장 가까운 3차원 빈 포장 문제를 포함하여 많은 변형이 제안되었습니다. (1) 패키지 및 빈 크기, (2) 중량 초과 제한, (3) 서로 다른 현실적인 특성을 고려하여 실제 3차원 빈 패킹 문제(Q4RealBPP)를 해결하기 위한 하이브리드 양자 고전적 프레임워크를 소개합니다. 품목 카테고리 및 (4) 품목 주문에 대한 기본 설정. Q4RealBPP를 사용하면 산업 및 물류 부문에서 높이 평가되는 제한 사항을 고려하여 실제 지향적인 3dBPP 인스턴스를 해결할 수 있습니다.

한정된 수의 용기에 제품을 포장하는 작업을 최적화하는 것은 생산 및 유통 분야에서 중요한 일상 업무입니다. 포장과 용기의 특성에 따라 일반적으로 BPP(Bin Packing Problems)1로 알려진 다양한 포장 문제가 공식화될 수 있습니다. 이 범주 내에서 1차원 BPP(1dBPP)는 가장 간단한 BPP로 간주되며2, 모든 항목을 가능한 한 적은 수의 컨테이너에 담는 것이 목표입니다. 물류 및 산업3의 실제 상황을 처리하기 위해 다양한 제약 조건을 갖춘 다양한 변형이 제안되었습니다. 각 패키지가 높이, 너비, 깊이의 세 가지 차원을 갖는 3차원 BPP(3dBPP)4는 가장 잘 알려져 있고 가장 까다로운 변형입니다. 여러 연구5,6,7에서 강조된 바와 같이, 3dBPP는 많은 산업 환경에서 실질적인 관심을 갖고 있습니다. 최근에는 팔레트 적재8, 도로 운송9, 항공 화물10 등과 같은 다양하고 실용적인 애플리케이션을 보유하도록 공식화되었습니다. 복잡성으로 인해 3dBPP는 새로 개발된 방법 및 메커니즘을 테스트하기 위한 벤치마크로 반복적으로 사용됩니다11,12 .

또 다른 측면에서, 양자 컴퓨팅은 아직 초기 단계에 있지만 연구자와 실무자에게 다양한 종류의 실제 최적화 문제를 해결하기 위한 혁신적인 패러다임을 제공하므로 과학계로부터 많은 관심을 받았습니다13,14,15,16. 특히, 양자 어닐러는 최근 산업17, 물류18 및 경제19 분야에서 영감을 받은 다양한 최적화 문제에 적용되었습니다. 그러나 BPP가 최적화 문제로 고전적으로 널리 연구되었음에도 불구하고 양자 커뮤니티에서 수행되는 BPP에 대한 연구는 여전히 부족합니다.

양자 컴퓨팅 분야의 BPP에 대한 선구적인 작업은 1dBPP20을 해결하기 위한 하이브리드 양자-고전적 방법을 제시합니다. 이 솔버는 두 개의 모듈로 구성됩니다. (1) 하나의 구성을 채우기 위해 실행 가능한 구성 세트를 검색하는 양자 서브루틴 단일 빈 및 (2) 양자 서브루틴에 의해 제공된 하위 집합을 사용하여 완전한 솔루션을 구축하는 고전적인 계산 경험적 방법입니다. 개발된 양자 서브루틴의 성능을 심화시키기 위해 무작위 샘플링 및 무작위 보행 기반 휴리스틱에 대해 추가 테스트를 수행했습니다. 이 두 논문 외에도 원자력 산업 관련 문제를 1dBPP로 공식화하여 D-Wave 양자 어닐러를 사용하여 이를 해결하는 추가 연구도 있습니다. 또 다른 연구에서는 BPP 관련 문제를 해결하기 위한 대안으로 양자 영감을 받은 진화 계산 기술을 보여줍니다. 양자 영감 기술은 양자 물리학을 활용하여 작업을 정의하고 클래식 컴퓨터에서 실행되도록 설계된 특정 클래스의 진화 알고리즘입니다. 따라서 어떤 양자 머신에서도 실행될 수 없습니다.

1dBPP와 달리 양자 영역에서 3dBPP를 처리하는 것은 두 가지 관련 근거로 인해 훨씬 ​​더 어렵습니다. (1) 현실 세계의 제약 조건을 고려할 때 증가하는 복잡성과 (2) 초기 상태 결맞음과 오류로 인해 용량이 여전히 제한되어 있는 현재 상용 양자 컴퓨터의 개발은 매우 제한된 문제를 해결하는 데 장애가 될 수 있습니다. 본 논문에서는 Q4RealBPP(Quantum for Real Bin Packing Problem)로 명명된 실제 지향 3dBPP를 위한 하이브리드 양자-고전 컴퓨팅 프레임워크를 제시합니다. 제안된 프레임워크는 D-Wave의 CQM(Leap Constrained Quadratic Model) 하이브리드 솔버(LeapCQMHybrid27)를 사용합니다. 동시에 Q4RealBPP는 기존 code28을 기반으로 구축되었습니다. 이 참조 코드는 이 작업에서 개발된 다음 두 가지 주요 기여를 위한 길을 닦은 훌륭한 시작점입니다.