Examinando por Autor "Paredes F."

Mostrando 1 - 3 de 3
  • Miniatura
    ÍtemAcceso Abierto
    A binary cat swarm optimization algorithm for the Non-Unicost set covering problem
    (Hindawi Publishing Corporation, 2015) Crawford B.; Berríos N.; Johnson F.; Paredes F.; Castro C.; Soto R.; Norero E.
    The Set Covering Problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. To solve the Set Covering Problem we use a metaheuristic called Binary Cat Swarm Optimization. This metaheuristic is a recent swarm metaheuristic technique based on the cat behavior. Domestic cats show the ability to hunt and are curious about moving objects. Based on this, the cats have two modes of behavior: seeking mode and tracing mode. We are the first ones to use this metaheuristic to solve this problem; our algorithm solves a set of 65 Set Covering Problem instances from OR-Library. © 2015 Broderick Crawford et al.
  • Miniatura
    ÍtemAcceso Abierto
    A hybrid alldifferent-tabu search algorithm for solving sudoku puzzles
    (Hindawi Publishing Corporation, 2015) Soto, R.; Crawford, B.; Galleguillos C.; Paredes F.; Norero E.
    The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement. It consists in filling a n2 × n2 grid, composed of n columns, n rows, and n subgrids, each one containing distinct integers from 1 to n2. Such a puzzle belongs to the NP-complete collection of problems, to which there exist diverse exact and approximate methods able to solve it. In this paper, we propose a new hybrid algorithm that smartly combines a classic tabu search procedure with the alldifferent global constraint from the constraint programming world. The alldifferent constraint is known to be efficient for domain filtering in the presence of constraints that must be pairwise different, which are exactly the kind of constraints that Sudokus own. This ability clearly alleviates the work of the tabu search, resulting in a faster and more robust approach for solving Sudokus. We illustrate interesting experimental results where our proposed algorithm outperforms the best results previously reported by hybrids and approximate methods. © 2015 Ricardo Soto et al.
  • Miniatura
    ÍtemAcceso Abierto
    Efficient Parallel Sorting for Migrating Birds Optimization When Solving Machine-Part Cell Formation Problems
    (Hindawi Publishing Corporation, 2016) Soto, R.; Crawford, B.; Almonacid, B.; Paredes F.
    The Machine-Part Cell Formation Problem (MPCFP) is a NP-Hard optimization problem that consists in grouping machines and parts in a set of cells, so that each cell can operate independently and the intercell movements are minimized. This problem has largely been tackled in the literature by using different techniques ranging from classic methods such as linear programming to more modern nature-inspired metaheuristics. In this paper, we present an efficient parallel version of the Migrating Birds Optimization metaheuristic for solving the MPCFP. Migrating Birds Optimization is a population metaheuristic based on the V-Flight formation of the migrating birds, which is proven to be an effective formation in energy saving. This approach is enhanced by the smart incorporation of parallel procedures that notably improve performance of the several sorting processes performed by the metaheuristic. We perform computational experiments on 1080 benchmarks resulting from the combination of 90 well-known MPCFP instances with 12 sorting configurations with and without threads. We illustrate promising results where the proposal is able to reach the global optimum in all instances, while the solving time with respect to a nonparallel approach is notably reduced. © 2016 Ricardo Soto et al.