Examinando por Autor "Olivares, R."
Mostrando 1 - 7 de 7
Resultados por página
Opciones de ordenación
Ítem Acceso Abierto A choice functions portfolio for solving constraint satisfaction problems: A performance evaluation(IEEE Computer Society, 2016) Soto, R.; Crawford, B.; Olivares, R.Constraint Programming (CP) allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a variable and then a value from the given problem, phase known as enumeration. In this context, Autonomous Search (AS) that is a particular case of adaptive systems, enables the problem solver to control and adapt its internal configuration during solving time, based on performance metrics in order to be more efficient. The goal is to provide a mechanism for CP solvers, integrating a component able to evaluate the solving performance process. In particular, we employ a classic decision making method called Choice Function (CF). In this paper, we present an evaluation of different choice functions, based on performance exhibited in a indicators set. The results are promising and show that it is feasible to solve constraint satisfaction problems with this new technique. © 2015 IEEE.Ítem Acceso Abierto Autonomous search in constraint satisfaction via black hole: a performance evaluation using different choice functions(Springer Verlag, 2016) Soto, R.; Crawford, B.; Olivares, R.; Niklander, S.; Olguín, E.Autonomous Search is a modern technique aimed at introducing self-adjusting features to problem-solvers. In the context of constraint satisfaction, the idea is to let the solver engine to autonomously replace its solving strategies by more promising ones when poor performances are identified. The replacement is controlled by a choice function, which takes decisions based on information collected during solving time. However, the design of choice functions can be done in very different ways, leading of course to very different resolution processes. In this paper, we present a performance evaluation of 16 rigorously designed choice functions. Our goal is to provide new and interesting knowledge about the behavior of such functions in autonomous search architectures. To this end, we employ a set of well-known benchmarks that share general features that may be present on most constraint satisfaction and optimization problems. We believe this information will be useful in order to design better autonomous search systems for constraint satisfaction. © Springer International Publishing Switzerland 2016.Ítem Acceso Abierto Evaluando la eficiencia de utilizar funciones de selección en búsqueda autónoma para resolver problemas de satisfacción de restricciones [Evaluating the efficient of using choice functions to solve CSPs via autonomous Search](IEEE Computer Society, 2016) Soto, R.; Crawford, B.; Olivares, R.; Olguin, E.Constraint programming is a powerful paradigm that allows for solving optimization and constraint satisfaction problems (CSPs). In this context, a main concern of this technology is that the efficient problem resolution usually relies on the employed solving strategy. Unfortunately, selecting the proper one is known to be complex as the behavior of strategies is commonly unpredictable. Recently, Autonomous Search appeared as a new technique to tackle this concern. The idea is to let the solver adapt its strategy during solving time in order to improve performance. This task is controlled by a choice function which decides, based on performance information, how the strategy must be updated. In this paper, we evaluate the impact on the solving phase of 16 different choice functions. We employ as test bed a set of well-known benchmarks that collect general features present on most CSPs. Interesting experimental results are obtained in order to provide the best-performing choice functions for solving CSPs. © 2016 AISTI.Ítem Acceso Abierto El problema de cobertura de conjuntos solucionado por el algoritmo del Agujero Negro [The set covering problem solved by the Black Hole algorithm](IEEE Computer Society, 2016) Soto, R.; Crawford, B.; Figueroa, I.; Olivares, R.; Olguin, E.The Set Covering Problem is a classical problem in combinatorial optimization that belongs to the Karp's 21 NP-hard problems, with many practical applications. In this paper, an approach based on Black Hole Algorithm is proposed to solve this problem. The black hole algorithm is a metaheuristic that is inspired by nature, especially by the black hole phenomenon in space. To improve the performance of metaheuristics are used repairing operator, which those solutions that violate the constraints, preprocessing accelerate the resolution of the problem, and transfer function and discretization function to adapts the solutions to a binary domains. We report interesting and competitive experimental results on a set of 45 instances preprocessed the Set Covering Problem. © 2016 AISTI.Ítem Acceso Abierto The complexity of designing and implementing metaheuristics(Springer Verlag, 2015) Soto, R.; Crawford, B.; Olivares, R.; Galleguillos, C.; Crawford, K.; Johnson, F.; Paredes, F.Optimization problems can be found in several real application domains such as engineering, medicine, mathematics, mechanics, physics, mining, games, design, and biology, among others. There exist several techniques to the efficient solving of these problems, which can be organized in two groups: exact and approximate methods. Metaheuristics are one of the most famous and widely used approximate methods for solving optimization problems. Most of them are known for being inspired on interesting behaviors that can be found on the nature, such as the way in which ants, bees and fishes found food, or the way in which fireflies and bats move on the environment. However, solving optimization problems via metaheuristics is not always a simple trip. In this paper, we analyze and discuss from an usability standpoint how the effort needed to design and implement efficient and robust metaheuristics can be conveniently managed and reduced. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto The impact of using different choice functions when solving CSPs with autonomous search(Springer Verlag, 2016) Soto, R.; Crawford, B.; Olivares, R.; Niklander, S.; Olguín, E.Constraint programming is a powerful technology for the efficient solving of optimization and constraint satisfaction problems (CSPs). A main concern of this technology is that the efficient problem resolution usually relies on the employed solving strategy. Unfortunately, selecting the proper one is known to be complex as the behavior of strategies is commonly unpredictable. Recently, Autonomous Search appeared as a new technique to tackle this concern. The idea is to let the solver adapt its strategy during solving time in order to improve performance. This task is controlled by a choice function which decides, based on performance information, how the strategy must be updated. However, choice functions can be constructed in several manners variating the information used to take decisions. Such variations may certainly conduct to very different resolution processes. In this paper, we study the impact on the solving phase of 16 different carefully constructed choice functions. We employ as test bed a set of well-known benchmarks that collect general features present on most CSPs. Interesting experimental results are obtained in order to provide the best-performing choice functions for solving CSPs. © Springer International Publishing Switzerland 2016.Ítem Acceso Abierto Using autonomous search for solving constraint satisfaction problems via new modern approaches(Elsevier, 2016) Soto, R.; Crawford, B.; Olivares, R.; Galleguillos, C.; Castro, C.; Johnson, F.; Paredes, F.; Norero, E.Constraint Programming is a powerful paradigm which allows the resolution of many complex problems, such as scheduling, planning, and configuration. These problems are defined by a set of variables and a set of constraints. Each variable has non-empty domain of possible value and each constraint involves some subset of the variables and specifies the allowable combinations of values for that subset. The resolution of these problems is carried out by a constraint satisfaction solver which explores a search tree of potential solutions. This exploration is controlled by the enumeration strategy, which is responsible for choosing the order in which variables and values are selected to generate the potential solution. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. Autonomous search is a particular case of adaptive systems that aims at improving its solving performance by adapting itself to the problem at hand without manual configuration of an expert user. The goal is to improve their solving performance by modifying and adjusting themselves, either by self-adaptation or by supervised adaptation. This approach has been effectively applied to different optimization and satisfaction techniques such as constraint programming, metaheuristics, and SAT. In this paper, we present a new Autonomous Search approach for constraint programming based on four modern bio-inspired metaheuristics. The goal of those metaheuristics is to optimize the self-tuning phase of the constraint programming search process. We illustrate promising results, where the proposed approach is able to efficiently solve several well-known constraint satisfaction problems. © 2016 Elsevier B.V.