Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Feasibility and Availability based Heuristics for ACO algorithms solving Binary CSP

Abstract : A Constraint Satisfaction Problem is composed by a set of variables, their related domains and a set of constraints among the variables that must be satisfied. These are known as hard problems to be solved. Many algorithms have been proposed to solve these problems. Metaheuristics and in particular ant-based algorithms have been used to solve difficult instances. In this paper, we propose new heuristics to be included in an ant-based algorithm in order to improve its performance when tackling hard constraint satisfaction problems. These heuristics are focused on the availability of consistent variable values and to restrict the ants collaborative information to the feasibility. To evaluate these heuristics we used the well-known Ant Solver algorithm and tested with problem instances from the transition phase. Results show that using our heuristics the Ants algorithm increases the number of problems that it is able to solve. Finally, a statistical analysis is presented to compare these approaches.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-enpc.archives-ouvertes.fr/hal-01872433
Contributeur : Bertrand Neveu <>
Soumis le : mercredi 12 septembre 2018 - 10:15:16
Dernière modification le : samedi 22 septembre 2018 - 01:11:03
Archivage à long terme le : : jeudi 13 décembre 2018 - 12:56:19

Fichier

PID5328385.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01872433, version 1

Collections

Citation

Nicolás Rojas-Morales, María-Cristina Riff, Bertrand Neveu. Feasibility and Availability based Heuristics for ACO algorithms solving Binary CSP. IEEE Congress on Evolutionary Computation, Jul 2018, Rio de Janeiro, Brazil. ⟨hal-01872433⟩

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

195