Parameter tuning of a choice-function based hyperheuristic using Particle Swarm Optimization
MetadataShow full item record
A Constraint Satisfaction Problem is defined by a set of variables and a set of constraints, each variable has a nonempty domain of possible values. Each constraint involves some subset of the variables and specifies the allowable combinations of values for that subset. A solution of the problem is defined by an assignment of values to some or all of the variables that does not violate any constraints. To solve an instance, a search tree is created and each node in the tree represents a variable of the instance. The order in which the variables are selected for instantiation changes the form of the search tree and affects the cost of finding a solution. In this paper we explore the use of a Choice Function to dynamically select from a set of variable ordering heuristics the one that best matches the current problem state in order to show an acceptable performance over a wide range of instances. The Choice Function is defined as a weighted sum of process indicators expressing the recent improvement produced by the heuristic recently used. The weights are determined by a Particle Swarm Optimization algorithm in a multilevel approach. We report results where our combination of strategies outperforms the use of individual strategies. © 2012 Elsevier Ltd. All rights reserved.
Showing items related by title, author, creator and subject.
Choice functions for autonomous search in constraint programming: GA vs. PSO [Funkcije izbora za samostalno pretraživanje u ograničenom programiranju: Genetski algoritam nasuprot optimizaciji roja čestica] (2020) Soto R.; Crawford B.; Misra S.; Palma W.; Monfroy E.; Castro C.; Paredes F. (2013)
ArticleSoto R.; Crawford B.; Palma W.; Galleguillos K.; Castro C.; Monfroy E.; Johnson F.; Paredes F. (Elsevier Inc., 2015)
Autonomous search in constraint satisfaction via black hole: A performance evaluation using different choice functions (2020) Soto R.; Crawford B.; Olivares R.; Niklander S.; Olguín E. (Springer Verlag, 2016)