Tiết lộ các giới hạn của phương pháp phỏng đoán tìm kiếm địa phương đã học: Bạn có phải là người mạnh mẽ nhất trong số những người nhu mì không?

Bảng liên kết

Tóm tắt & Giới thiệu

Công việc có liên quan

Đánh giá cho Max-Cut

Đánh giá SAT

Tóm tắt và Triển vọng, Tài liệu tham khảo

Nguyên liệu bổ sung

trừu tượng

Trong những năm gần đây, việc kết hợp mạng lưới thần kinh với phương pháp phỏng đoán tìm kiếm cục bộ đã trở nên phổ biến trong lĩnh vực tối ưu hóa tổ hợp. Bất chấp nhu cầu tính toán đáng kể, phương pháp này đã cho thấy những kết quả đầy hứa hẹn với kỹ thuật thủ công tối thiểu. Tuy nhiên, chúng tôi đã xác định được ba hạn chế quan trọng trong việc đánh giá thực nghiệm những nỗ lực tích hợp này. Thứ nhất, các trường hợp có độ phức tạp vừa phải và cơ sở yếu đặt ra thách thức trong việc đánh giá chính xác tính hiệu quả của các phương pháp tiếp cận dựa trên học tập. Thứ hai, việc không có nghiên cứu cắt bỏ gây khó khăn cho việc định lượng và phân bổ các cải tiến một cách chính xác cho kiến trúc học sâu. Cuối cùng, việc khái quát hóa các phương pháp phỏng đoán đã học qua các phân phối khác nhau vẫn chưa được khám phá. Trong nghiên cứu này, chúng tôi tiến hành điều tra toàn diện về những hạn chế đã được xác định này. Đáng ngạc nhiên là chúng tôi chứng minh rằng phương pháp phỏng đoán đã học đơn giản dựa trên Tìm kiếm Tabu vượt trội so với phương pháp phỏng đoán đã học hiện đại (SOTA) về mặt hiệu suất và khả năng khái quát. Những phát hiện của chúng tôi thách thức các giả định phổ biến và mở ra những con đường thú vị cho nghiên cứu và đổi mới trong tương lai về tối ưu hóa tổ hợp.

1. GIỚI THIỆU

Thiết kế các thuật toán phỏng đoán hoặc xấp xỉ hiệu quả cho các bài toán tối ưu hóa tổ hợp NP-hard (CO) là một nhiệm vụ đầy thách thức, thường đòi hỏi kiến thức về miền và thử và sai sâu rộng. Do đó, ý tưởng tự động hóa quy trình thiết kế đòi hỏi khắt khe và tẻ nhạt này thông qua học máy để học các thuật toán khai thác cấu trúc vốn có của một vấn đề đã thu hút được sự quan tâm đáng kể của các nhà nghiên cứu (Bello và cộng sự, 2016; Khalil và cộng sự, 2017; Bengio và cộng sự ., 2021; Đồng và cộng sự, 2021). Đặc biệt, một phần đáng kể trong số các công trình này (Khalil và cộng sự, 2017; Barrett và cộng sự, 2020; Yolcu và P'oczos, 2019) đã tập trung vào việc sử dụng Mạng thần kinh đồ thị (GNN) cho các vấn đề về CO. Bất chấp nhu cầu tính toán, các phương pháp tiếp cận dựa trên GNN này đã chứng tỏ hiệu suất cạnh tranh so với các phương pháp chẩn đoán SOTA được thiết kế riêng cho các vấn đề cụ thể.

Mặc dù những tiến bộ tiềm năng này mang lại nhiều hứa hẹn nhưng vẫn còn một số lo ngại. Hiệu suất vượt trội của các phương pháp phỏng đoán đã học có thể là do việc lựa chọn các trường hợp và đường cơ sở cụ thể. Cụ thể, nếu đường cơ sở yếu thì các phương pháp phỏng đoán đã học có thể dễ dàng hoạt động tốt hơn chúng. Nếu không có các trường hợp cứng và lựa chọn đường cơ sở thích hợp, các phương pháp phỏng đoán đã học có thể dễ dàng cho thấy hiệu suất tương đương với các phương pháp phỏng đoán SOTA và điều này có thể dẫn đến việc đánh giá quá cao khả năng thực tế của các phương pháp phỏng đoán đã học. Hơn nữa, việc so sánh với phương pháp chẩn đoán SOTA đôi khi bị bỏ qua do những thách thức về khả năng mở rộng với kiến trúc học sâu.

Một tập hợp con các phương pháp tiếp cận dựa trên học tập (Khalil và cộng sự, 2017; Yolcu và P'oczos, 2019; Barrett và cộng sự, 2020, 2022) kết hợp chức năng hoặc hành vi của phương pháp phỏng đoán truyền thống, có khả năng mang lại hiệu suất được cải thiện hoặc nâng cao bằng cách tích hợp phương pháp phỏng đoán nguyên tắc với các thành phần học máy. Nếu thiếu sự so sánh toàn diện với phương pháp phỏng đoán tích hợp và nghiên cứu cắt bỏ về kiến trúc học sâu thì việc xác định đóng góp cụ thể của kiến trúc học sâu sẽ trở nên khó khăn. Do đó, nếu các phương pháp phỏng đoán tích hợp mạnh mẽ thì các phương pháp phỏng đoán đã học có thể hoạt động tốt hơn các phương pháp phỏng đoán cơ bản một cách liền mạch, trong khi kiến trúc học sâu chỉ đóng một vai trò nhỏ.

Một thành tựu to lớn khác của phương pháp phỏng đoán đã học (Khalil và cộng sự, 2017; Barrett và cộng sự, 2020; Toenshof và cộng sự, 2019), ban đầu được đào tạo về các phiên bản nhỏ hơn và cụ thể từ một phân phối cụ thể, cho thấy hiệu suất ấn tượng khi thử nghiệm trên các phiên bản lớn hơn từ phân bố khác nhau. Thành tựu này được coi là một thành tựu quan trọng, phù hợp với mục tiêu cốt lõi của việc sử dụng các phương pháp tiếp cận dựa trên học tập: giảm thiểu nhu cầu tùy chỉnh sâu rộng và kiến thức về miền cụ thể thường được yêu cầu bởi phương pháp phỏng đoán. Mặc dù các phương pháp phỏng đoán cổ điển với siêu tham số cũng có thể gặp phải thách thức nếu chúng được tinh chỉnh cho một phân bố cụ thể, nhưng chúng cũng có thể khái quát hóa trên các phân bố khác nhau. Câu hỏi chính xoay quanh việc liệu các phương pháp phỏng đoán đã học có thực sự chứng minh được khả năng khái quát hóa vượt trội so với các phương pháp phỏng đoán cổ điển hay không. Sự so sánh kỹ lưỡng và sâu sắc giữa các phương pháp phỏng đoán đã học với các phương pháp phỏng đoán cổ điển sẽ cung cấp những hiểu biết sâu sắc có giá trị về tính khái quát của các phương pháp phỏng đoán đã học.

Các phương pháp phỏng đoán đã học thường thiếu sự đảm bảo về mặt lý thuyết, khiến việc đánh giá thực nghiệm trở thành phương pháp duy nhất để hiểu được điểm mạnh và hạn chế của các phương pháp được đề xuất. Chúng tôi tin rằng một số câu hỏi cơ bản nhưng then chốt vẫn chưa được khám phá trong quá trình đánh giá thực nghiệm các tác phẩm này. Mặc dù những câu hỏi này phù hợp với tất cả các loại chẩn đoán đã học, nhưng chúng tôi hỏi và trả lời chúng bằng cách phân tích các ấn phẩm được bình duyệt gần đây và được trích dẫn nhiều, tập trung vào việc tìm hiểu các phương pháp phỏng đoán tìm kiếm địa phương. Mục tiêu của chúng tôi không phải là cung cấp các tiêu chuẩn đầy đủ cho các vấn đề về CO được thảo luận trong công việc của chúng tôi mà là hỗ trợ các nhà nghiên cứu trong tương lai đánh giá nghiên cứu của họ.

Cụ thể, chúng tôi hỏi và trả lời các câu hỏi sau:

1. Liệu phương pháp phỏng đoán đã học có thể bị tham số hóa quá mức không? Tuyệt đối. Thay thế GNN trong ECO-DQN bằng hồi quy tuyến tính và sử dụng một tập hợp con các tính năng từ ECO-DQN (Barrett và cộng sự, 2020) liên kết đến Tabu Search (Glover, 1990), chúng tôi giới thiệu một phiên bản rút gọn của ECO-DQN có tên là SoftTabu . Nghiên cứu của chúng tôi chứng minh rằng SoftTabu thể hiện hiệu suất vượt trội và khả năng tổng quát so với ECO-DQN đối với bài toán NPhard Maximum-Cut (Max-Cut).

2. Liệu sai lệch cơ bản có thể được cho là do hiệu quả vượt trội của các phương pháp phỏng đoán đã học được không? Có, chúng tôi chứng minh rằng SoftTabu, một phương pháp phỏng đoán đã học theo vanilla, có thể hoạt động tốt hơn S2V-DQN (Khalil và cộng sự, 2017) đối với bài toán Max-Cut và GNNSAT (Yolcu và P'oczos, 2019) về Khả năng thỏa mãn Boolean (SAT).

*3. Liệu phương pháp phỏng đoán đã học có thể chứng minh khả năng khái quát hóa vượt trội do sai lệch lựa chọn phiên bản không?*Có, chúng tôi chứng minh rằng ECO-DQN thể hiện khả năng khái quát hóa kém trên các trường hợp khó hơn và dễ bị mắc kẹt trong không gian tìm kiếm.