Examinando por Autor "Johnson, F."
Mostrando 1 - 20 de 24
Resultados por página
Opciones de ordenación
Ítem Acceso Abierto A binary fruit fly optimization algorithm to solve the set covering problem(Springer Verlag, 2015) Crawford, B.; Soto, R.; Torres-Rojas, C.; Peña, C.; Riquelme-Leiva, M.; Misra, S.; Johnson, F.; Paredes, F.The Set Covering Problem (SCP) is a well known NP-hard problem with many practical applications. In this work binary fruit fly optimization algorithms (bFFOA) were used to solve this problem using different binarization methods. The bFFOA is based on the food finding behavior of the fruit flies using osphresis and vision. The experimental results show the effectiveness of our algorithms producing competitive results when solve the benchmarks of SCP from the OR-Library. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto A comparison of three recent nature-inspired metaheuristics for the set covering problem(Springer Verlag, 2015) Crawford, B.; Soto, R.; Peña, C.; Riquelme-Leiva, M.; Torres-Rojas, C.; Misra, S.; Johnson, F.; Paredes, F.The Set Covering Problem (SCP) is a classic problem in combinatorial optimization. SCP has many applications in engineering, including problems involving routing, scheduling, stock cutting, electoral redistricting and others important real life situations. Because of its importance, SCP has attracted attention of many researchers. However, SCP instances are known as complex and generally NP-hard problems. Due to the combinatorial nature of this problem, during the last decades, several metaheuristics have been applied to obtain efficient solutions. This paper presents a metaheuristics comparison for the SCP. Three recent nature-inspired metaheuristics are considered: Shuffled Frog Leaping, Firefly and Fruit Fly algorithms. The results show that they can obtainn optimal or close to optimal solutions at low computational cost. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto A matheuristic approach combining local search and mathematical programming(Hindawi Publishing Corporation, 2016) Lagos, C.; Guerrero, G.; Cabrera, E.; Niklander, S.; Johnson, F.; Paredes, F.; Vega, J.A novel matheuristic approach is presented and tested on a well-known optimisation problem, namely, capacitated facility location problem (CFLP). The algorithm combines local search and mathematical programming. While the local search algorithm is used to select a subset of promising facilities, mathematical programming strategies are used to solve the subproblem to optimality. Proposed local search is influenced by instance-specific information such as installation cost and the distance between customers and facilities. The algorithm is tested on large instances of the CFLP, where neither local search nor mathematical programming is able to find good quality solutions within acceptable computational times. Our approach is shown to be a very competitive alternative to solve large-scale instances for the CFLP. © 2016 Carolina Lagos et al.Ítem Acceso Abierto A software project management problem solved by firefly algorithm(Springer Verlag, 2016) Crawford, B.; Soto, R.; Johnson, F.; Misra, S.; Olguín, E.In software project management there are several problems to deal, one of those is the Software Project Scheduling Problem (SPSP). This problem requires to assign a set of resources to tasks for a given project, trying to decrease the duration and cost of the whole project. The workers and their skills are the main resources in the project. In this paper we present the SPSP as a combinatorial optimization problem and a novel approach to solve SPSP by a Firefly algorithm. Firefly algorithm is a new metaheuristic based on the behaviour of the firefly. We present the design of the resolution model to solve the SPSP using an algorithm of fireflies and we illustrate some experimental results in order to demonstrate the viability and soundness of our approach. © Springer International Publishing Switzerland 2016.Ítem Acceso Abierto A teaching-learning-based optimization algorithm for solving set covering problems(Springer Verlag, 2015) Crawford, B.; Soto, R.; Aballay, F.; Misra, S.; Johnson, F.; Paredes, F.The Set Covering Problem (SCP) is a representation of a kind of combinatorial optimization problem which has been applied in several problems in the real world. In this work we used a binary version of Teaching-Learning-Based Optimization (TLBO) algorithm to solve SCP, works with two phases known: teacher and learner; emulating the behavior into a classroom. The proposed algorithm has been tested on 65 benchmark instances. The results show that it has the ability to produce solutions competitively. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto A XOR-based ABC algorithm for solving set covering problems(Springer Verlag, 2016) Soto, R.; Crawford, B.; Lizama, S.; Johnson, F.; Paredes, F.The set covering problem is a classical problem in the subject of combinatorial optimization that consists in finding a set of solutions that cover a range of needs at the lowest possible cost. The literature reports various techniques to solve this problem, ranging from exact algorithms to approximate methods. In this paper, we present a new XOR-based artificial bee colony algorithm for solving set covering problems. We integrate a XOR operator to binarize the solution construction in order to cope with the binary nature of set covering problems. We also incorporate pre-processing phases and dynamic ABC parameters so as to improve solving time. We report interesting and competitive experimental results on a set of 65 benchmarks from the Beasley’s OR-Library. © Springer International Publishing Switzerland 2016.Ítem Acceso Abierto Algoritmos Murciélago Binarios para el problema de cobertura de conjuntos [Binary bat algorithms for the set covering problem](Institute of Electrical and Electronics Engineers Inc., 2015) Crawford, B.; Soto, R.; Olea C.; Johnson, F.; Paredes, F.In the present paper, we resolve the Set Covering Problem using the recently presented meta-heuristic named Binary Bat Algorithm. We use two variations of this algorithm. The Binary Bat Algorithm algorithm was created observing how the bats evade obstacles and find preys to eat, the use of echo-localization is how they do it. We made some changes using two different transfer and two discretization techniques to solve the problem. © 2015 AISTI.Ítem Acceso Abierto An artificial bee colony algorithm for the resource contrained project scheduling problem(Springer Verlag, 2015) Crawford, B.; Soto, R.; Johnson, F.; Norero E.; Olguín, E.We present an approach to solve the Resource Constrained Project Scheduling Problem. This problem consists on executing a group of activities limited by constraints. Precedence relationships force to some activities to begin after the finalization of others. In addition, processing every activity requires a predefined amount of limited resources. The target of this problem is to minimize the duration of whole project. In this paper, an approach based on Artificial Bee Colony algorithm for the Resource Constrained Project Scheduling Problem is presented. That algorithm is one of the most recent algorithms in the domain of the collective intelligence who was motivated by the intelligent behavior observed in the domestic bees to take the process of forage. Thus, ABC combines methods of local search and global search, trying to balance the process of the exploration and exploitation of the space of search. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto Automated, adaptive, and optimized search for CSPs via cuckoo search(Springer Verlag, 2015) Soto, R.; Crawford, B.; Flores J.; Mella F.; Galleguillos, C.; Johnson, F.; Paredes, F.Constraint Programing is a programming paradigm devoted to the efficient solving of constraint satisfaction problems (CSPs). A CSP is a formal problem representation mainly composed of variables and constraints defining relations among those variables. The resolution process of CSPs is commonly carried out by building and exploring a search tree that holds the possibles solutions. Such a tree is dynamically created by interleaving two different phases: enumeration and propagation. During enumeration, the variables and values are chosen to build the possible solution, while propagation intend to delete the values having no chance to reach a feasible result. Autonomous Search is a new technique that gives the ability to the resolution process to be adaptive by re-configuring its enumeration strategy when poor performances are detected. This technique has exhibited impressive results during the last years. However, such a re-configuration is hard to achieve as parameters are problem-dependent and their best configuration is not stable along the search. In this paper, we introduce an Autonomous Search framework that incorporates a new optimizer based on Cuckoo Search able to efficiently support the re-configuration phase. Our goal is to provide an automated, adaptive, and optimized search system for CSPs. We report encouraging results where our approach clearly improves the performance of previously reported Autonomous Search approaches for CSPs. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto Autonomous tuning for constraint programming via artificial bee colony optimization(Springer Verlag, 2015) Soto, R.; Crawford, B.; Mella F.; Flores J.; Galleguillos, C.; Misra, S.; Johnson, F.; Paredes, F.Constraint Programming allows the resolution of complex problems, mainly combinatorial ones. These problems are defined by a set of variables that are subject to a domain of possible values and a set of constraints. 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. Autonomous Search provides the ability to the solver to self-tune its enumeration strategy in order to select the most appropriate one for each part of the search tree. This self-tuning process is commonly supported by an optimizer which attempts to maximize the quality of the search process, that is, to accelerate the resolution. In this work, we present a new optimizer for self-tuning in constraint programming based on artificial bee colonies. We report encouraging results where our autonomous tuning approach clearly improves the performance of the resolution process. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto Estrategias de enumeración para resolver problemas de satisfacción de restricciones: evaluación de desempeño [Enumeration strategies to solve constraint satisfaction problems: performance evaluation](Institute of Electrical and Electronics Engineers Inc., 2015) Soto, R.; Crawford, B.; Olivares R.; Herrera R.; Johnson, F.; Paredes, F.In constraint programming, efficiency in the resolution process can be affected by the order in which the variables of the problem and the domain values are selected. This activity is known as enumeration. At the beginning, it is difficult to determine the best choice variable-value pair that can generate potential solutions for constraint satisfaction problems. In this paper, we present an evaluation of different enumeration strategies, based on performance exhibited in a set indicators. These strategies solve different instances of constraint problems satisfactions. The results show that it is feasible to solve constraint satisfaction with at least one strategy enumeration. © 2015 AISTI.Ítem Acceso Abierto Experiential solving: Towards a unified autonomous search constraint solving approach(Springer Verlag, 2015) Crawford, B.; Soto, R.; Crawford, K.; Johnson, F.; de la Barra, C.L.; Galdames, S.To solve many problems modeled as Constraint Satisfaction Problems there are no known efficient algorithms. The specialized literature offers a variety of solvers, which have shown good performance. Nevertheless, despite the efforts of the scientific community in developing new strategies, there is no algorithm that is the best for all possible situations. This paper analyses recent developments of Autonomous Search Constraint Solving Systems. Showing that the design of the most efficient and recent solvers is very close to the Experiential Learning Cycle from organizational psychology. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto Firefly algorithm to solve a project scheduling problem(Springer Verlag, 2016) Crawford, B.; Soto, R.; Johnson, F.; Valencia, C.; Paredes, F.This paper describes the Software Project Scheduling Problem (SPSP) as a combinatorial optimization problem. In this problem raises the need for a process to assign a set of resources to tasks for a project in a given time, trying to decrease the duration and cost. The workers are the main resource in the project. We present the design of the resolution model to solve the SPSP using an algorithm of fireflies (Firefly Algorithm, FA). We illustrate the experimental results in order to demonstrate the viability and soundness of our approach. © Springer International Publishing Switzerland 2016.Ítem Acceso Abierto Improving Tabu search performance by means of automatic parameter tuning(IEEE Canada, 2016) Lagos, C.; Crawford, B.; Soto, R.; Cabrera, E.; Vega, J.; Johnson, F.; Paredes, F.A common problem when performing (meta)heuristic techniques over complex combinatorial optimization problems is parameter tuning. Finding the right parameter values can lead to significant improvements in terms of the best solution objective value found by the heuristic, heuristic reliability, and heuristic convergence, among others. Unfortunately, this is usually a tedious and complicated task if done manually. Furthermore, parameter values usually depend on the problem that is going to be solved. In this paper, we propose a framework that is based on the genetic programming (GP) technique to fine tune a key parameter of the well-known tabu search (TS) algorithm. Several experiments are performed over a set of small instances of the well-known capacitated facility location problem. The results have shown that adjusting the probability of acceptance of the best neighbor ρ in the TS algorithm using GP leads to an average value of the obtained solution that is closer to the optimal solution than the average value obtained by the simple TS algorithm with an a priori selected value for ρ. More importantly, standard deviation of the algorithm is greatly improved by our approach, which makes it much more reliable if time limitations are present. Finally, we confirm that the value of the parameter ρ largely depends on the problem that is attempted to solve. © 2016 IEEE.Ítem Acceso Abierto Optimización por colonia de gatos del problema de cobertura de conjuntos [Binary cat swarm optimization for the set covering problem](Institute of Electrical and Electronics Engineers Inc., 2015) Crawford, B.; Soto, R.; Berrios, N.; Johnson, F.; Paredes, F.The set covering problem belongs to the combinatorial optimization problems, whose complexity is exponential theoretically established as NP-complex problems. Consists in finding a subset of columns in a matrix of zeros and ones such that cover all rows of the matrix at minimal cost. The solution to this problem is presented using, for first time, the binary cat swarm optimization algorithm. This metaheuristic is based on the cat's behavior, where cats have curiosity by objects in motion and have a great hunting ability. Cats have two modes of behavior: seeking mode and tracing mode. The algorithm is tested on 65 instances, which are compared in a result table including a column with the relative percentage deviation. © 2015 AISTI.Ítem Acceso Abierto Problema del conjunto de cobertura resuelto mediante el algoritmo Binario de Optimización basado en Enseñanza-Aprendizaje [The set covering problem solved by the Binary Teaching-Learning-based Optimization algorithm](Institute of Electrical and Electronics Engineers Inc., 2015) Crawford, B.; Soto, R.; Leiva, F.A.; Johnson, F.; Paredes, F.The Set Covering Problem (SCP) is a representation of a kind of combinatorial optimization problem which has been applied in several problems in the real world. In this work is used the binary version of Teaching-Learning-Based Optimization algorithm (TLBO), which works with two phases known as teacher and learner phases in this way emulates the behaviour into a classroom, besides this problem is solved with eight different transfer functions and five discretization methods all of them altogether to solve The Set Covering Problem from the OR-Library. © 2015 AISTI.Ítem Acceso Abierto Recent harmony search algorithms for 0–1 optimization problems(Springer Verlag, 2015) Crawford, B.; Soto, R.; Guzmán N.; Johnson, F.; Paredes, F.The Set Covering Problem (SCP) has long been concentrating the interest of many researchers in the field of Combinatorial Optimization. SCP is a 0–1 integer programming problem that consists in finding a set of solutions which allow to cover a set of needs at the lowest cost possible. There are many applications of these kind of problems, the main ones are: location of services, files selection in a data bank, simplification of boolean expressions, balancing production lines, among others. Different metaheuristics have been proposed to solve it. Here, we present the possibilities to solve Set Covering Problems with Harmony Search. © Springer International Publishing Switzerland 2015.Ítem Acceso Abierto Software project scheduling using the Hyper-Cube ant colony optimization algorithm [Programiranje računarskog projekta primjenom Hyper-Cube algoritma za optimizaciju kolonije mrava](Strojarski Facultet, 2015) Crawford, B.; Soto, R.; Johnson, F.; Misra, S.; Paredes, F.; Olguín, E.This paper introduces a proposal of design of Ant Colony Optimization algorithm paradigm using Hyper-Cube framework to solve the Software Project Scheduling Problem. This NP-hard problem consists in assigning tasks to employees in order to minimize the project duration and its overall cost. This assignment must satisfy the problem constraints and precedence between tasks. The approach presented here employs the Hyper-Cube framework in order to establish an explicitly multidimensional space to control the ant behaviour. This allows us to autonomously handle the exploration of the search space with the aim of reaching encouraging solutions. © 2015, Strojarski Facultet. All rights reserved.Ítem Acceso Abierto Solving a distribution network design problem by means of evolutionary algorithms(National Institute for R and D in Informatics, 2016) Cabrera, G.; Niklander, S.; Cabrera, E.; Johnson, F.In this paper a simple and efficient evolutionary algorithm is implemented to solve a Distribution Network Design problem (DND). The DND problem that we address here integrates inventory policies with location/allocation decision making. This problem, also known as Inventory Location Modeling problem, is a complex combinatorial optimization problem that cannot be solved by exact methods as the number of decision variables increases. We compare our algorithm to previously implemented algorithms. Our evolutionary approach is shown to be very competitive in terms of both objective function value and execution time. © 2017, All Rights Reserved.Ítem Acceso Abierto Solving manufacturing cell design problems using a shuffled frog leaping algorithm(Springer Verlag, 2016) Soto, R.; Crawford, B.; Vega, E.; Johnson, F.; Paredes, F.The manufacturing Cell Design Problem (MCDP) is a well-known problem for lines of manufacture where the main goal is to minimize the inter-cell moves. To solve the MCDP we employ the Shuffled Frog Leaping Algorithm (SFLA), which is a metaheuristic inspired on the natural memetic features of frogs. The frog tries to leap all over the search space for a better result until the stopping criteria is met. The obtained results are compared with previous approaches of the algorithm to test the real efficiency of our proposed SFLA. The results show that the proposed algorithm produces optimal solutions for all the 50 studied instances. © Springer International Publishing Switzerland 2016.