Browsing by Author "Soto, Ricardo"

Now showing 1 - 7 of 7
  • No Thumbnail Available
    Item
    A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem
    (2021) Garcia, Jose; Lemus-Romani, Jose; Altimiras, Francisco; Crawford, Broderick; Soto, Ricardo; Becerra-Rozas, Marcelo; Moraga, Paola; Paz Becerra, Alex; Pena Fritz, Alvaro; Rubio, Jose-Miguel; Astorga, Gino
    Optimization techniques, specially metaheuristics, are constantly refined in order to decrease execution times, increase the quality of solutions, and address larger target cases. Hybridizing techniques are one of these strategies that are particularly noteworthy due to the breadth of applications. In this article, a hybrid algorithm is proposed that integrates the k-means algorithm to generate a binary version of the cuckoo search technique, and this is strengthened by a local search operator. The binary cuckoo search algorithm is applied to the NP-hard Set-Union Knapsack Problem. This problem has recently attracted great attention from the operational research community due to the breadth of its applications and the difficulty it presents in solving medium and large instances. Numerical experiments were conducted to gain insight into the contribution of the final results of the k-means technique and the local search operator. Furthermore, a comparison to state-of-the-art algorithms is made. The results demonstrate that the hybrid algorithm consistently produces superior results in the majority of the analyzed medium instances, and its performance is competitive, but degrades in large instances.
  • 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.
  • Thumbnail Image
    Item
    Autonomous Parameter Balance in Population-Based Approaches: A Self-Adaptive Learning-Based Strategy
    (2024) Vega, Emanuel; Lemus-Romani, Jose; Soto, Ricardo; Crawford, Broderick; Loffler, Christoffer; Pena, Javier; Talbi, El-Gazhali
    Population-based metaheuristics can be seen as a set of agents that smartly explore the space of solutions of a given optimization problem. These agents are commonly governed by movement operators that decide how the exploration is driven. Although metaheuristics have successfully been used for more than 20 years, performing rapid and high-quality parameter control is still a main concern. For instance, deciding the proper population size yielding a good balance between quality of results and computing time is constantly a hard task, even more so in the presence of an unexplored optimization problem. In this paper, we propose a self-adaptive strategy based on the on-line population balance, which aims for improvements in the performance and search process on population-based algorithms. The design behind the proposed approach relies on three different components. Firstly, an optimization-based component which defines all metaheuristic tasks related to carry out the resolution of the optimization problems. Secondly, a learning-based component focused on transforming dynamic data into knowledge in order to influence the search in the solution space. Thirdly, a probabilistic-based selector component is designed to dynamically adjust the population. We illustrate an extensive experimental process on large instance sets from three well-known discrete optimization problems: Manufacturing Cell Design Problem, Set covering Problem, and Multidimensional Knapsack Problem. The proposed approach is able to compete against classic, autonomous, as well as IRace-tuned metaheuristics, yielding interesting results and potential future work regarding dynamically adjusting the number of solutions interacting on different times within the search process.
  • No Thumbnail Available
    Item
    Binarization of Metaheuristics: Is the Transfer Function Really Important?
    (2023) Lemus-Romani, Jose; Crawford, Broderick; Cisternas-Caneo, Felipe; Soto, Ricardo; Becerra-Rozas, Marcelo
    In this work, an approach is proposed to solve binary combinatorial problems using continuous metaheuristics. It focuses on the importance of binarization in the optimization process, as it can have a significant impact on the performance of the algorithm. Different binarization schemes are presented and a set of actions, which combine different transfer functions and binarization rules, under a selector based on reinforcement learning is proposed. The experimental results show that the binarization rules have a greater impact than transfer functions on the performance of the algorithms and that some sets of actions are statistically better than others. In particular, it was found that sets that incorporate the elite or elite roulette binarization rule are the best. Furthermore, exploration and exploitation were analyzed through percentage graphs and a statistical test was performed to determine the best set of actions. Overall, this work provides a practical approach for the selection of binarization schemes in binary combinatorial problems and offers guidance for future research in this field.
  • No Thumbnail Available
    Item
    Intelligent decision-making for binary coverage: Unveiling the potential of the multi-armed bandit selector
    (2024) Becerra-Rozas, Marcelo; Lemus-Romani, Jose; Crawford, Broderick; Soto, Ricardo; Talbi, El-Ghazali
    In this article, we propose the integration of a novel reinforcement learning technique into our generic and unified framework. This framework enables any continuous metaheuristic to operate in binary optimization, with the technique in question known as the Multi -Armed Bandit. Population -based metaheuristics comprise multiple individuals that cooperatively and globally explore the search space using their limited individual capabilities. Our framework allows these population -based metaheuristics to continue leveraging their original movements, designed for continuous optimization, once they are binary encoded. The generality of the framework has facilitated the instantiation of popular algorithms from the optimization, machine learning, and evolutionary computing communities. Furthermore, it permits the design of new and innovative optimization instances using various component strategies, reflecting the framework's modularity. The results comparing two statistical techniques and three hybridizations coming from Machine Learning, have shown to obtain a better performance with the metahuristics in Grey Wolf Optimizer and Whale Optimization Algorithm.
  • No Thumbnail Available
    Item
    Swarm-Inspired Computing to Solve Binary Optimization Problems: A Backward Q-Learning Binarization Scheme Selector
    (2022) Becerra-Rozas, Marcelo; Lemus-Romani, Jose; Cisternas-Caneo, Felipe; Crawford, Broderick; Soto, Ricardo; Garcia, Jose
    In recent years, continuous metaheuristics have been a trend in solving binary-based combinatorial problems due to their good results. However, to use this type of metaheuristics, it is necessary to adapt them to work in binary environments, and in general, this adaptation is not trivial. The method proposed in this work evaluates the use of reinforcement learning techniques in the binarization process. Specifically, the backward Q-learning technique is explored to choose binarization schemes intelligently. This allows any continuous metaheuristic to be adapted to binary environments. The illustrated results are competitive, thus providing a novel option to address different complex problems in the industry.