Browsing by Author "Soto, Ricardo"

Now showing 1 - 10 of 10
  • 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 New Learnheuristic: Binary SARSA - Sine Cosine Algorithm (BS-SCA)
    (Springer Science and Business Media Deutschland GmbH, 2022) Becerra-Rozas, Marcelo; Lemus Romani, José Isaac; Crawford, Broderick; Soto, Ricardo; Cisternas Caneo, Felipe; Trujillo Embry, Andrés; Arnao Molina, Máximo; Tapia, Diego; Castillo, Mauricio; Rubio, José Miguel
    This paper proposes a novel learnheuristic called Binary SARSA - Sine Cosine Algorithm (BS-SCA) for solving combinatorial problems. The BS-SCA is a binary version of Sine Cosine Algorithm (SCA) using SARSA to select a binarization operator. This operator is required due SCA was created to work in continuous domains. The performance of BS-SCA is benchmarked with a Q-learning version of the learnheuristic. The problem tested was the Set Covering Problem and the results show the superiority of our proposal.
  • 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.
  • Thumbnail Image
    Item
    Continuous Metaheuristics for Binary Optimization Problems: An Updated Systematic Literature Review
    (2023) Becerra-Rozas, Marcelo; Lemus Romani, José Isaac; Cisternas Caneo, Felipe; Crawford, Broderick; Soto, Ricardo; Astorga, Gino; Castro, Carlos; García, José
    For years, extensive research has been in the binarization of continuous metaheuristics for solving binary-domain combinatorial problems. This paper is a continuation of a previous review and seeks to draw a comprehensive picture of the various ways to binarize this type of metaheuristics; the study uses a standard systematic review consisting of the analysis of 512 publications from 2017 to January 2022 (5 years). The work will provide a theoretical foundation for novice researchers tackling combinatorial optimization using metaheuristic algorithms and for expert researchers analyzing the binarization mechanism’s impact on the metaheuristic algorithms’ performance. Structuring this information allows for improving the results of metaheuristics and broadening the spectrum of binary problems to be solved. We can conclude from this study that there is no single general technique capable of efficient binarization; instead, there are multiple forms with different performances.
  • 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
    Reinforcement Learning Based Whale Optimizer
    (Springer International, 2021) Becerra Rozas, Marcelo; Lemus Romani, José Isaac; Crawford, Broderick; Soto, Ricardo; Cisternas Caneo, Felipe; Embry, Andres Trujillo; Molina, Maximo Arnao; Tapia, Diego; Castillo, Mauricio; Misra, Sanjay; Rubio, Jose Miguel
    This work proposes a Reinforcement Learning based optimizer integrating SARSA and Whale Optimization Algorithm. SARSA determines the binarization operator required during the metaheuristic process. The hybrid instance is applied to solve benchmarks of the Set Covering Problem and it is compared with a Q-learning version, showing good results in terms of fitness, specifically, SARSA beats its Q-Learning version in 44 out of 45 instances evaluated. It is worth mentioning that the only instance where it does not win is a tie. Finally, thanks to graphs presented in our results analysis we can observe that not only does it obtain good results, it also obtains a correct exploration and exploitation balance as presented in the referenced literature.
  • 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.