학습된 지역 검색 휴리스틱의 한계 공개: 당신은 가장 온유한 사람입니까?

링크 표

개요 및 소개

관련된 일

Max-Cut 평가

SAT 평가

요약 및 전망, 참고자료

보충 자료

추상적인

최근에는 조합 최적화 분야에서 신경망과 지역 검색 휴리스틱을 결합하는 것이 인기를 얻고 있습니다. 상당한 계산 요구에도 불구하고 이 접근 방식은 최소한의 수동 엔지니어링으로 유망한 결과를 보여주었습니다. 그러나 우리는 이러한 통합 시도에 대한 실증적 평가에서 세 가지 중요한 한계를 확인했습니다. 첫째, 중간 정도의 복잡성과 약한 기준선을 가진 사례는 학습 기반 접근 방식의 효과를 정확하게 평가하는 데 어려움을 겪습니다. 둘째, 절제 연구가 없기 때문에 딥 러닝 아키텍처의 개선 사항을 정확하게 정량화하고 그 원인을 파악하기가 어렵습니다. 마지막으로, 다양한 분포에 걸쳐 학습된 휴리스틱의 일반화는 아직 충분히 탐구되지 않았습니다. 본 연구에서는 이러한 확인된 한계에 대해 포괄적인 조사를 수행합니다. 놀랍게도 우리는 Tabu Search를 기반으로 한 단순 학습 휴리스틱이 성능 및 일반화 가능성 측면에서 최첨단(SOTA) 학습 휴리스틱을 능가한다는 것을 보여줍니다. 우리의 연구 결과는 일반적인 가정에 도전하고 조합 최적화에 대한 미래 연구와 혁신을 위한 흥미로운 길을 열어줍니다.

1. 소개

NP-하드 조합 최적화(CO) 문제에 대한 효과적인 휴리스틱 또는 근사 알고리즘을 설계하는 것은 도메인 지식과 광범위한 시행착오가 필요한 어려운 작업입니다. 따라서 문제의 고유 구조를 활용하는 알고리즘을 학습하기 위해 기계 학습을 통해 이러한 까다롭고 지루한 설계 프로세스를 자동화한다는 아이디어는 연구자들 사이에서 상당한 관심을 얻었습니다(Bello et al., 2016; Khalil et al., 2017; Bengio et al. ., 2021; Dong et al., 2021). 특히 이러한 연구(Khalil et al., 2017; Barrett et al., 2020; Yolcu and P'oczos, 2019)의 상당 부분은 CO 문제에 대해 그래프 신경망(GNN)을 사용하는 데 집중했습니다. 컴퓨팅 요구에도 불구하고 이러한 GNN 기반 접근 방식은 특정 문제에 맞춰진 SOTA 휴리스틱에 비해 경쟁력 있는 성능을 보여주었습니다.

이러한 잠재적인 발전은 큰 가능성을 제시하지만 몇 가지 우려 사항은 여전히 남아 있습니다. 학습된 휴리스틱의 뛰어난 성능은 특정 인스턴스와 기준선의 선택에 기인할 수 있습니다. 특히, 기준선이 약한 경우 학습된 휴리스틱이 기준선을 쉽게 능가할 수 있습니다. 하드 인스턴스와 적절한 기준선 선택이 없으면 학습된 휴리스틱은 SOTA 휴리스틱과 비슷한 성능을 쉽게 보여줄 수 있으며 이는 학습된 휴리스틱의 실제 기능을 과대평가할 수 있습니다. 더욱이, 딥 러닝 아키텍처의 확장성 문제로 인해 SOTA 휴리스틱과의 비교가 종종 생략되기도 합니다.

학습 기반 접근 방식의 하위 집합(Khalil et al., 2017; Yolcu and P'oczos, 2019; Barrett et al., 2020, 2022)은 기존 휴리스틱의 기능이나 동작을 통합하여 잠재적으로 휴리스틱을 통합하여 향상된 성능을 제공합니다. 기계 학습 구성요소를 사용한 원리. 딥러닝 아키텍처에 대한 통합 휴리스틱 및 절제 연구와의 포괄적인 비교가 부족하면 딥러닝 아키텍처의 구체적인 기여를 결정하는 것이 어려워집니다. 결과적으로 통합 휴리스틱이 강력하다면 학습된 휴리스틱은 기본 휴리스틱보다 원활하게 성능을 발휘할 수 있지만 딥 러닝 아키텍처는 약간의 역할을 합니다.

학습된 휴리스틱의 또 다른 위대한 성과(Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019)는 초기에 특정 배포판의 더 작고 특정 인스턴스에 대해 교육을 받았지만 다음의 더 큰 인스턴스에서 테스트할 때 인상적인 성능을 보여줍니다. 다른 분포. 이 성과는 학습 기반 접근 방식을 사용하는 핵심 목표, 즉 휴리스틱에서 흔히 요구되는 광범위한 사용자 정의 및 도메인별 지식의 필요성을 완화하는 것과 일치하는 중요한 성과입니다. 하이퍼파라미터를 사용하는 고전적인 휴리스틱은 특정 분포에 맞게 미세 조정된 경우 문제에 직면할 수도 있지만 다양한 분포에 걸쳐 일반화될 수도 있습니다. 기본 탐구는 학습된 휴리스틱이 실제로 고전적 휴리스틱에 비해 우수한 일반화 가능성을 보여주는지 여부를 중심으로 이루어집니다. 학습된 휴리스틱과 고전적 휴리스틱의 철저하고 통찰력 있는 비교는 학습된 휴리스틱의 일반화 가능성에 대한 귀중한 통찰력을 제공합니다.

학습된 휴리스틱은 이론적 보장이 부족한 경우가 많으므로 경험적 평가가 제안된 방법론의 강점과 한계를 이해하는 유일한 방법입니다. 우리는 이들 연구에 대한 실증적 평가에서 몇 가지 근본적이면서도 중추적인 질문이 아직 탐구되지 않은 상태로 남아 있다고 믿습니다. 이러한 질문은 모든 유형의 학습된 휴리스틱과 관련이 있지만, 우리는 지역 검색 휴리스틱 학습에 중점을 두고 많이 인용되고 최근 동료 검토를 거친 출판물을 분석하여 질문하고 대답합니다. 우리의 목표는 우리 작업에서 논의된 CO 문제에 대한 철저한 벤치마크를 제공하는 것이 아니라 미래의 연구자들이 연구를 평가할 수 있도록 지원하는 것입니다.

구체적으로 다음과 같은 질문과 답변을 드립니다.

1. 학습된 휴리스틱이 과도하게 매개변수화될 수 있습니까? 전적으로. ECO-DQN의 GNN을 선형 회귀로 대체하고 Tabu Search(Glover, 1990)에 연결되는 ECO-DQN(Barrett et al., 2020)의 기능 하위 집합을 활용하여 SoftTabu라는 정리된 ECO-DQN 버전을 소개합니다. . 우리의 연구는 SoftTabu가 NPhard Maximum-Cut(Max-Cut) 문제에 대해 ECO-DQN에 비해 우수한 성능과 일반화 가능성을 보여준다는 것을 보여줍니다.

2. 기본 편향이 학습된 휴리스틱의 우수한 성능에 기인할 수 있습니까? 예, 우리는 바닐라 학습 휴리스틱인 SoftTabu가 Max-Cut 문제에 대해서는 S2V-DQN(Khalil et al., 2017), SAT(Boolean Satisfiability)에 대해서는 GNNSAT(Yolcu and P'oczos, 2019)보다 성능이 뛰어날 수 있음을 보여줍니다.

*삼. 학습된 휴리스틱은 인스턴스 선택 편향으로 인해 우수한 일반화 가능성을 보여줄 수 있습니까?*예, ECO-DQN은 더 어려운 인스턴스에서 일반화가 좋지 않고 검색 공간에 쉽게 갇히게 된다는 것을 보여줍니다.