Feasibility and Availability based Heuristics for ACO algorithms solving Binary CSP - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année :

Feasibility and Availability based Heuristics for ACO algorithms solving Binary CSP

(1) , ,
1
María-Cristina Riff
  • Fonction : Auteur
  • PersonId : 1036328
Bertrand Neveu
  • Fonction : Auteur

Résumé

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.
Fichier principal
Vignette du fichier
PID5328385.pdf (264.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01872433 , version 1 (12-09-2018)

Identifiants

  • HAL Id : hal-01872433 , version 1

Citer

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⟩

Collections

ENPC PARISTECH
30 Consultations
162 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More