Original scientific paper

Choice functions for autonomous search in constraint programming: GA vs. PSO

Ricardo Soto orcid.org/0000-0001-5685-2905 ; Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2950, Valparaíso, Chile and Universidad Autónoma de Chile, Pedro de Valdivia 641, Santiago, Chile
Broderick Crawford orcid.org/0000-0001-5500-0188 ; Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2950, Valparaíso, Chile and Universidad Finis Terrae, Av. Pedro de Valdivia 1509, Santiago, Chile
Sanjay Misra ; Atilim University, Ankara, Turkey
Wenceslao Palma ; Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2950, Valparaíso, Chile
Eric Monfroy ; CNRS, LINA, Université de Nantes, 2 rue de la Houssinière, Nantes, France
Carlos Castro orcid.org/0000-0003-4149-7730 ; Universidad Técnica Federico Santa María, Avenida España 1680, Valparaíso, Chile
Fernando Paredes orcid.org/0000-0003-0223-6052 ; Escuela de Ingeniería Industrial, Universidad Diego Portales, Manuel Rodríguez Sur 415, Santiago, Chile

Abstract

The variable and value ordering heuristics are a key element in Constraint Programming. Known together as the enumeration strategy they may have important consequences on the solving process. However, a suitable selection of heuristics is quite hard as their behaviour is complicated to predict. Autonomous search has been recently proposed to handle this concern. The idea is to dynamically replace strategies that exhibit poor performances by more promising ones during the solving process. This replacement is carried out by a choice function, which evaluates a given strategy in a given amount of time via quality indicators. An important phase of this process is performed by an optimizer, which aims at finely tuning the choice function in order to guarantee a precise evaluation of strategies. In this paper we evaluate the performance of two powerful choice functions: the first one supported by a genetic algorithm and the second one by a particle swarm optimizer. We present interesting results and we demonstrate the feasibility of using those optimization techniques for Autonomous Search in a Constraint Programming context.

Keywords

Artificial Intelligence; Autonomous Search; Constraint Programming

Hrčak ID:

106690

URI

https://hrcak.srce.hr/106690

Publication date:

21.8.2013.

Article data in other languages: croatian

Visits: 2.096 *