Raffiner l'heuristique CHS à l'aide de bandits

Mohamed Sami Cherif (1) , Djamal Habet (1) , Cyril Terrioux (1)

1 COALA - COntraintes, ALgorithmes et Applications

Récemment, une heuristique efficace, appelée Conflict History Search (CHS), a été introduite pour la résolution du problème de satisfaction de contraintes (CSP). Elle repose sur une technique d'apprentissage par renforcement appelée Exponential Recency Weighted Average (ERWA) pour estimer la dureté des contraintes. CHS favorise les variables qui apparaissent souvent dans les échecs récents. Le paramètre de pas utilisé dans CHS est important car il contrôle l'estimation de la dureté des contraintes. Dans cet article, nous envisageons un raffinement de ce paramètre à l'aide d'un bandit manchot. Le bandit sélectionne une valeur appropriée de ce paramètre lors des redémarrages effectués par l'algorithme de recherche. Chaque bras correspond à l'heuristique CHS avec une valeur donnée pour le paramètre de pas et est récompensé selon sa capacité à mener une recherche efficace. Une phase d'entraînement est introduite en amont de la recherche pour aider le bandit à choisir un bras pertinent. L'évaluation expérimentale montre que cette approche conduit à des améliorations significatives.

Domains: Artificial Intelligence [cs.AI]

Mohamed Sami Cherif, Djamal Habet, Cyril Terrioux. Raffiner l'heuristique CHS à l'aide de bandits. Actes des 16èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2021, Nice, France. ⟨hal-03270911⟩