Examinando por Autor "Araya, I."

Mostrando 1 - 4 de 4
  • Miniatura
    ÍtemAcceso Abierto
    A beam-search approach to the set covering problem
    (Springer Verlag, 2016) Reyes, V.; Araya, I.; Crawford, B.; Soto, R.; Olguín, E.
    In this work we present a beam-search approach applied to the Set Covering Problem. The goal of this problem is to choose a subset of columns of minimal cost covering every row. Beam Search constructs a search tree by using a breadthfirst search strategy, however only a fixed number of nodes are kept and the rest are discarded. Even though original beam search has a deterministic nature, our proposal has some elements that makes it stochastic. This approach has been tested with a well-known set of 45 SCP benchmark instances from OR-Library showing promising results. © Springer International Publishing Switzerland 2016.
  • Miniatura
    ÍtemAcceso Abierto
    Adaptive filtering strategy for numerical constraint satisfaction problems
    (Elsevier Ltd, 2015) Araya, I.; Soto, R.; Crawford, B.
    Abstract The reliability and increasing performance of search-tree-based interval solvers for solving numerical systems of constraints make them applicable to various expert system domains. Filtering methods are applied in each node of the search tree to reduce the variable domains without the loss of solutions. Current interval-based solvers generally leave it up to the solver designer to decide which set of filtering methods to apply to solve a particular problem. In this work, we propose an adaptive strategy to dynamically determine the set of filtering methods that will be applied in each node of the search tree. Our goal is twofold: first, we want to simplify the task of the solver designer, and second, we believe that an adaptive strategy may improve the average performance of the current state-of-the-art strategies. The proposed adaptive mechanism attempts to avoid calling costly filtering methods when their probability of filtering domains is low. We assume that fruitful filtering occurs in nearby revisions or clusters. Thus, the decision about whether or not to apply a filtering method is based on a cluster detection mechanism. When a cluster is detected, the associated methods are consecutively applied in order to exploit the cluster. Alternately, in zones without clusters, only a cheap method is applied, thus reducing the filtering effort in large portions of the search. We compare our approach with state-of-the-art strategies, demonstrating its effectiveness. © 2015 Elsevier Ltd.
  • Miniatura
    ÍtemAcceso Abierto
    Solving manufacturing cell design problems by using a bat algorithm approach
    (Springer Verlag, 2016) Soto, R.; Crawford, B.; Alarcón, A.; Zec, C.; Vega, E.; Reyes, V.; Araya, I.; Olguín, E.
    Manufacturing Cell Design is a problem that consist in distributing machines in cells, in such a way productivity is improved. The idea is that a product, build up by using different parts, has the least amount of travel on its manufacturing process. To solve the MCDP we use the Bat Algorithm, a metaheuristic inspired by a feature of the microbats, the echolocation. This feature allows an automatic exploration and exploitation balance, by controlling the rate of volume and emission pulses during the search. Our approach has been tested by using a well-known set of benchmark instances, reaching optimal values for most of them. © Springer International Publishing Switzerland 2016.
  • Miniatura
    ÍtemAcceso Abierto
    Solving manufacturing cell design problems by using a dolphin echolocation algorithm
    (Springer Verlag, 2016) Soto, R.; Crawford, B.; Carrasco, C.; Almonacid, B.; Reyes, V.; Araya, I.; Misra, S.; Olguín, E.
    The Manufacturing Cell Design is a problem that consist in organize machines in cells to increase productivity, i.e., minimize the movement of parts for a given product between machines. In order to solve this problem we use a Dolphin Echolocation algorithm, a recent bio-inspired metaheuristic based on a dolphin feature, the echolocation. This feature is used by the dolphin to search all around the search space for a target, then the dolphin exploits the surround area in order to find promising solutions. Our approach has been tested by using a set of 10 benchmark instances with several configurations, reaching to optimal values for all of them. © Springer International Publishing Switzerland 2016.