Skip to Main content Skip to Navigation
Conference papers

Raffiner l'heuristique CHS à l'aide de bandits

Mohamed Sami Cherif 1 Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Résumé : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03270911
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Friday, June 25, 2021 - 11:12:03 AM
Last modification on : Tuesday, October 19, 2021 - 10:50:58 PM
Long-term archiving on: : Sunday, September 26, 2021 - 9:07:07 PM

File

jfpc2021c.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03270911, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

65

Files downloads

19