Mạng thần kinh đồ thị từ vật lý giải bài toán tối ưu tổ hợp

Các bài toán tối ưu kết hợp là những bài toán phức tạp với một tập hợp lớn những giải pháp khả thi nhưng rời rạc. Một số những ví dụ nổi tiếng bậc nhất của bài toán dạng này là các bài toán người bán hàng di chuyển, đóng gói thùng và các bài toán về lập lịch điều độ sản xuất...

Các nhà nghiên cứu tại Phòng thí nghiệm Các giải pháp lượng tử Amazon, một phần của Phòng thí nghiệm Các công nghệ máy tính tiên tiến và thông minh AWS mới đây đã phát triển một công cụ kết hợp các bài toán tối ưu tổ hợp, trên cơ sở các mạng thần kinh đồ thị (GNNs). Cách tiếp cận này do Schuetz, Brubaker và Katzgraber phát triển, xuất bản trên tạp chí Nature Machine Intelligence, có thể hữu dụng để tối ưu cho vô số các bài toán trong thế giới thực.

“Công trình của chúng tôi đã được truyền cảm hứng từ những nhu cầu của khách hàng”, Martin Schuetz, một trong số các tác giả của nghiên cứu này, trao đổi với TechXplore. “Trong công việc hàng ngày ở Phòng thí nghiệm Các giải pháp Lượng tử Amazon, chúng tôi tương tác với nhiều khách hàng trên nhiều lĩnh vực dọc của họ về cuộc hành trình để có được sự sẵn sàng lượng tử…, chuẩn bị cho một tương lai khi công nghệ mới nổi này được thương mại hóa thực sự. Phần lớn khách hàng đều dùng những trường hợp liên quan đến những bài toán tối ưu tổ hợp”.

Trong bối cảnh của công việc dịch vụ khách hàng, các bài toán tối ưu tổ hợp có thể xuất hiện ở nhiều hình thức khác biệt. Hai ví dụ nổi tiếng của dạng bài toán này là bài toán tối ưu danh mục đầu tư trong tài chính và bài toán lên lịch điều độ sản xuất. Thuật ngữ tối ưu danh mục đầu tư liên quan đến quá trình một người lựa chọn danh mục tốt nhất hoặc sự phân bổ tài sản cho một tình huống cụ thể giữa một loạt danh mục hiện tại.

Bài toán lên lịch điều độ sản xuất, nói cách khác, xuất hiện trong những trường hợp một loạt công việc hoặc nhiệm vụ phải được thực hiện và có giới hạn các nguồn lực/công cụ để thực hiện nó. Trong các trường hợp này, người ta phải hỏi để tìm ra một lịch trình tối ưu sử dụng những công cụ hiện có để thực hiện nhiệm vụ trong thời gian ngắn nhất có thể.

Vì công nghệ lượng tử vẫn còn ở giai đoạn phát triển ban đầu nên các nhà nghiên cứu đang cố gắng phát triển các công cụ tối ưu mà không hoàn toàn phụ thuộc vào máy tính lượng tử, ít nhất cho đến khi các máy tính đó sẵn sàng về mặt thương mại. Trong công trình của mình, Schuetz và cộng sự đã đưa vào một kỹ thuật tối ưu dựa trên GNNs được lấy cảm hứng từ vật lý.

“Với khả năng có thể mở rộng của chúng, các GNN từ vật lý có thể hữu dụng cho giải xấp xỉ (quy mô lớn) các bài toán tối ưu tổ hợp với mô hình gốc lượng tử, trong khi vẫn hỗ trợ được khách hàng của chúng tôi để họ có được sự sẵn sàng lượng tử qua sự trình diễn toán học mà các thiết bị lượng tử có thể hiểu”, Brubaker nói.

Cách tiếp cận do Schuetz và cộng sự phát triển lần đầu nhận diện là bài toán Hamilton (hàm chi phí) mã hóa các bài toán tối ưu hóa cụ thể mà người ta đang cố gắng giải quyết. Nó liên quan đến các biến quyết định phản hồi với các nút bên trong một biểu đồ.

“Ý tưởng chính của chúng tôi là sau đó định khung các bài toán tối ưu tổ hợp dưới dạng nhiệm vụ phân loại nút không giám sát mà GNN học hỏi về màu sắc (nói cách khác, spin hoặc biến) cho mọi nút”, Schuetz giải thích. “Đến điểm cuối, GNN được huấn luyện qua một hàm mất khách hàng được mã hóa bài toán tối ưu cụ thể mà bạn quan tâm, trong một phản hồi một đối một với bài toán Hamilton ban đầu, đem lại một lựa chọn nguyên tắc cho hàm mất của GNN”.

Sau khi huấn luyện GNN, nhóm gnhieen cứu dự tính giá trị cuối cùng của bài tập phép gán nút mềm cho các phép gán lớp cứng. Kết quả cuối cùng cho phép họ tính xấp xỉ bài toán tối ưu tổ hợp quan tâm.

Các tiếp cận này có rất nhiều điểm tiên tiến so với những phương pháp khác vẫn dùng để giải các bài toán tối ưu tổ hợp. Nổi tiếng nhất, phương pháp của họ ở quy mô lớn, có nghĩa là hữu dụng trong giải quyết về mặt tính toán các bài toán phức tối ưu với hàng trăm triệu nút.

“GNN được tối ưu của chúng tôi đặt trên cơ sở liên quan toán học tổng quát và trực tiếp giữa các Ising spin Hamiltonians kiểu mẫu và hàm mất khác biệt. Chúng tôi huấn luyện GNN trên cơ sở đó, qua đó đem đến một khung độc đáo cho một phạm vi lớp các bài toán tối ưu tổ hợp và mở ra một công cụ hiệu quả của vật lý cho các cách tiếp cận học máy hiện đại”, Brubaker nói. “Các ý tưởng từ vật lý kết hợp với công cụ học máy hiện đại giúp chúng tôi đề xuất một cách giải quyết đơn giản, tổng quát và mạnh mẽ không hề phụ thuộc vào hàm mất mát”.

Đáng chú ý, cách tiếp cận này có thể giải xấp xỉ các bài toán tối ưu mà không cần huấn luyện dán nhãn, vốn là một đòi hỏi chính của mọi phương pháp học có giám sát. Vì kỹ thuật này đóng vai trò trong các bài toán tối ưu như các đồ thị Ising Hamilton, nó có thể chạy trên phần cứng lượng tử.

“Chúng tôi đã đem đến một khung liên ngành độc đáo cho các bài toán tối ưu kết hợp những cái nhìn từ vật lý và công cụ từ học sâu hiện đại”, Schuetz giải thích. “Với cái khung này, chúng tôi đã có một công cụ có thể áp dụng rộng rãi cho các bài toán NP-khó chính tắc; các ví dụ chính bao gồm cắt tối đa, độ phủ tối thiểu, các bài toán độc lập tối đa cũng như bài toán thủy tinh spin  Ising”.

Trong tương lai, phương pháp dựa trên GNN mới do nhóm nghiên cứu này giới thiệu có thể hữu dụng để giải quyết các bài toán tối ưu phức tạp của thế giới thực. Vì đây là phương pháp có thể mở rộng quy mô nên Phòng thí nghiệm Giải pháp lượng tử của Amazon và AWS có kế hoạch cung cấp nó cho khách hàng như một công cụ để tạo điều kiện thuận lợi cho quá trình chuyển đổi của họ sang công nghệ lượng tử. Trên thực tế thì kỹ thuật của họ có thể cho phép khách hàng tiếp cận cả hai vấn đề liên quan đến các trường hợp sử dụng cụ thể trong khuôn khổ mô hình gốc lượng tử, cả trên quy mô nhỏ và quy mô phù hợp với ngành.

“Trong tương lai, chúng tôi sẽ tiếp tục nghiên cứu về khái niệm, lý thuyết cũng như cả các câu hỏi ứng dụng. Nói cách khác chúng tôi có vô số ý tưởng cải thiện các năng lực mà GNN đề xuất và như thế có nhiều ứng dụng cho các trường hợp mà chúng tôi có thể cố gắng giải quyết được bằng công cụ mới. Chúng tôi sẽ tiếp tục sử dụng các phản hồi của khách hàng để giúp hướng dẫn mình và tối ưu chương trình nghiên cứu của mình”, Katzgraber nói.

Thanh Hương tổng hợp

Nguồn: https://combonews.online/graph-neural-networks-influenced-by-physics-to-handle-combinatorial-optimization-problems/

https://techxplore.com/news/2022-05-physics-inspired-graph-neural-networks-combinatorial.html