Browsing by Author "Palma, Wenceslao"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    A binary monkey search algorithm variation for solving the set covering problem
    (2020) Crawford, Broderick; Soto, Ricardo; Olivares, Rodrigo; Embry, Gabriel; Flores, Diego; Palma, Wenceslao; Castro, Carlos; Paredes, Fernando; Rubio, Jose-Miguel
    In complexity theory, there is a widely studied grouping of optimization problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set covering problem, known as one of Karp's 21-complete problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set covering problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains.We propose a new climbing process with a better exploratory capability and a newcooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the easley's OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
  • No Thumbnail Available
    Item
    A Novel Learning-Based Binarization Scheme Selector for Swarm Algorithms Solving Combinatorial Problems
    (2021) Lemus-Romani, Jose; Becerra-Rozas, Marcelo; Crawford, Broderick; Soto, Ricardo; Cisternas-Caneo, Felipe; Vega, Emanuel; Castillo, Mauricio; Tapia, Diego; Astorga, Gino; Palma, Wenceslao; Castro, Carlos; Garcia, Jose
    Currently, industry is undergoing an exponential increase in binary-based combinatorial problems. In this regard, metaheuristics have been a common trend in the field in order to design approaches to successfully solve them. Thus, a well-known strategy includes the employment of continuous swarm-based algorithms transformed to perform in binary environments. In this work, we propose a hybrid approach that contains discrete smartly adapted population-based strategies to efficiently tackle binary-based problems. The proposed approach employs a reinforcement learning technique, known as SARSA (State-Action-Reward-State-Action), in order to utilize knowledge based on the run time. In order to test the viability and competitiveness of our proposal, we compare discrete state-of-the-art algorithms smartly assisted by SARSA. Finally, we illustrate interesting results where the proposed hybrid outperforms other approaches, thus, providing a novel option to tackle these types of problems in industry.