Dévoiler les limites des heuristiques de recherche locale apprises : êtes-vous le plus puissant des doux ?

Tableau des liens

Résumé et introduction

Travaux connexes

Évaluation pour Max-Cut

Évaluation pour SAT

Résumé et perspectives, références

Matériel supplémentaire

Abstrait

Ces dernières années, la combinaison de réseaux de neurones avec des heuristiques de recherche locale est devenue populaire dans le domaine de l'optimisation combinatoire. Malgré ses exigences informatiques considérables, cette approche a donné des résultats prometteurs avec un minimum d’ingénierie manuelle. Cependant, nous avons identifié trois limites critiques dans l'évaluation empirique de ces tentatives d'intégration. Premièrement, les instances de complexité modérée et de bases de référence faibles posent un défi pour évaluer avec précision l’efficacité des approches basées sur l’apprentissage. Deuxièmement, l’absence d’étude sur l’ablation rend difficile la quantification et l’attribution précise des améliorations à l’architecture d’apprentissage profond. Enfin, la généralisation des heuristiques apprises à travers diverses distributions reste sous-explorée. Dans cette étude, nous menons une enquête approfondie sur ces limites identifiées. Étonnamment, nous démontrons qu’une simple heuristique apprise basée sur la recherche taboue surpasse les heuristiques apprises de l’état de l’art (SOTA) en termes de performances et de généralisabilité. Nos résultats remettent en question les hypothèses dominantes et ouvrent des voies passionnantes pour la recherche et l’innovation futures en optimisation combinatoire.

1. INTRODUCTION

Concevoir des heuristiques ou des algorithmes d'approximation efficaces pour des problèmes d'optimisation combinatoire (CO) NP-difficiles est une tâche difficile, nécessitant souvent une connaissance du domaine et de nombreux essais et erreurs. Ainsi, l’idée d’automatiser ce processus de conception exigeant et fastidieux grâce à l’apprentissage automatique pour apprendre des algorithmes qui exploitent la structure inhérente d’un problème a suscité un intérêt considérable parmi les chercheurs (Bello et al., 2016 ; Khalil et al., 2017 ; Bengio et al. ., 2021 ; Dong et al., 2021). En particulier, une partie considérable de ces travaux (Khalil et al., 2017 ; Barrett et al., 2020 ; Yolcu et P´oczos, 2019) se sont concentrés sur l'utilisation de réseaux de neurones graphes (GNN) pour les problèmes de CO. Malgré les exigences informatiques, ces approches basées sur GNN ont démontré des performances compétitives par rapport aux heuristiques SOTA adaptées à des problèmes spécifiques.

Même si ces avancées potentielles sont très prometteuses, certaines préoccupations demeurent. Les performances supérieures des heuristiques apprises peuvent être attribuées à la sélection d’instances spécifiques et de lignes de base. Plus précisément, si les lignes de base sont faibles, les heuristiques apprises peuvent facilement les surpasser. Sans instances difficiles et sans sélection de base appropriée, les heuristiques apprises peuvent facilement montrer des performances comparables à celles des heuristiques SOTA, ce qui peut conduire à une surestimation des capacités réelles des heuristiques apprises. De plus, les comparaisons avec les heuristiques SOTA sont parfois laissées de côté en raison des problèmes d’évolutivité des architectures d’apprentissage profond.

Un sous-ensemble d'approches basées sur l'apprentissage (Khalil et al., 2017 ; Yolcu et P´oczos, 2019 ; Barrett et al., 2020, 2022) intègrent la fonctionnalité ou le comportement des heuristiques traditionnelles, offrant potentiellement des performances améliorées ou améliorées en intégrant des heuristiques. principes avec des composants d’apprentissage automatique. En l’absence d’une comparaison complète avec l’heuristique intégrée et d’une étude d’ablation de l’architecture d’apprentissage profond, il devient difficile de déterminer la contribution spécifique de l’architecture d’apprentissage profond. Par conséquent, si les heuristiques intégrées sont robustes, les heuristiques apprises peuvent facilement surpasser les heuristiques de base, tandis que l’architecture d’apprentissage profond joue un petit rôle.

Une autre grande réussite des heuristiques apprises (Khalil et al., 2017 ; Barrett et al., 2020 ; Toenshof et al., 2019), initialement formées sur des instances plus petites et spécifiques d'une distribution particulière, présente des performances impressionnantes lorsqu'elles sont testées sur des instances plus grandes d'une distribution particulière. répartitions différentes. Cette réalisation constitue une réalisation importante, conforme à l'objectif principal de l'utilisation d'approches basées sur l'apprentissage : atténuer la nécessité d'une personnalisation approfondie et de connaissances spécifiques à un domaine souvent requises par l'heuristique. Bien que les heuristiques classiques avec hyperparamètres puissent également rencontrer des défis si elles sont affinées pour une distribution spécifique, elles peuvent également se généraliser à différentes distributions. La question principale consiste à déterminer si les heuristiques apprises démontrent effectivement une généralisabilité supérieure à celle des heuristiques classiques. Une comparaison approfondie et perspicace des heuristiques apprises avec les heuristiques classiques fournit des informations précieuses sur la généralisabilité des heuristiques apprises.

Les heuristiques apprises manquent souvent de garanties théoriques, ce qui fait de l'évaluation empirique la seule méthode permettant de comprendre les forces et les limites des méthodologies proposées. Nous pensons que plusieurs questions fondamentales, mais cruciales, restent inexplorées dans l’évaluation empirique de ces travaux. Bien que ces questions soient pertinentes pour tous les types d’heuristiques apprises, nous les posons et y répondons en analysant des publications récentes et très citées, évaluées par des pairs, axées sur l’apprentissage des heuristiques de recherche locale. Notre objectif n'est pas de fournir des références exhaustives pour les problèmes de CO abordés dans nos travaux mais plutôt d'aider les futurs chercheurs à évaluer leurs recherches.

Concrètement, nous posons et répondons aux questions suivantes :

1. Les heuristiques apprises peuvent-elles être surparamétrées ? Absolument. En remplaçant le GNN dans ECO-DQN par une régression linéaire et en utilisant un sous-ensemble de fonctionnalités d'ECO-DQN (Barrett et al., 2020) lié à Tabu Search (Glover, 1990), nous introduisons une version élaguée d'ECO-DQN appelée SoftTabu. . Notre étude démontre que SoftTabu présente des performances et une généralisabilité supérieures par rapport à ECO-DQN pour le problème NPhard Maximum-Cut (Max-Cut).

2. Le biais de base peut-il être attribué à la performance supérieure des heuristiques apprises ? Oui, nous démontrons que SoftTabu, une heuristique apprise vanille, peut surpasser S2V-DQN (Khalil et al., 2017) pour le problème Max-Cut et GNNSAT (Yolcu et P´oczos, 2019) pour la satisfaisabilité booléenne (SAT).

*3. Les heuristiques apprises peuvent-elles démontrer une généralisabilité supérieure en raison du biais de sélection des instances ?*Oui, nous démontrons que ECO-DQN présente une mauvaise généralisation sur des instances plus difficiles et se retrouve facilement piégé dans l'espace de recherche.