TY - JOUR

T1 - Parameter tuning of a choice-function based hyperheuristic using Particle Swarm Optimization

AU - CRAWFORD LABRIN, BRODERICK

AU - SOTO DE GIORGIS, RICARDO JAVIER

AU - Monfroy, Eric

AU - PALMA MUÑOZ, WENCESLAO ENRIQUE

AU - Castro, Carlos

AU - Paredes, Fernando

PY - 2013/4/1

Y1 - 2013/4/1

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - Constraints satisfaction

KW - Hyperheuristics

KW - Particle Swarm

UR - http://www.scopus.com/inward/record.url?scp=84872015521&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2012.09.013

DO - 10.1016/j.eswa.2012.09.013

M3 - Article

AN - SCOPUS:84872015521

VL - 40

SP - 1690

EP - 1695

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

IS - 5

ER -