Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 11
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A neural network based guidance for a BRKGA: an application to the longest common square subsequence problem

  • Reixach, Jaume
  • Blum, Christian
  • Đukanović, Marko
  • Raidl, Günther R.
24th European Conference, EvoCOP 2024 Held as Part of EvoStar 2024 Aberystwyth, UK, April 3–5, 2024, Proceedings, Thomas Stützle, Markus Wagner, editors, In this work we apply machine learning to better guide a biased random key genetic algorithm (Brkga) for the longest common square subsequence (LCSqS) problem. The problem is a variant of the well-known longest common subsequence (LCS) problem in which valid solutions are square strings. A string is square if it can be expressed as the concatenation of a string with itself. The original Brkga is based on a reduction of the LCSqS problem to the LCS problem by cutting each input string into two parts. Our work consists in enhancing the search process of Brkga for good cut points by using a machine learning approach, which is trained to produce promising cut points for the input strings of a problem instance. In this study, we show the benefits of this approach by comparing the enhanced Brkga with the original Brkga, using two benchmark sets from the literature. We show that the results of the enhanced Brkga significantly improve over the original results, especially when tackling instances with non-uniformly generated input strings., Jaume Reixach and Christian Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. G¨unter R. Raidl is supported by the Vienna Graduate School on Computational Optimization (VGSCO), Austrian Science Foundation, project no. W1260-N35. Marko Djukanovi´c is supported by the project entitled “Development of artificial intelligence models and algorithms for solving difficult combinatorial optimization problems” funded by the Ministry of Scientific and Technological Development and the Higher Education of the Republic of Srpska., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Efficient Search Algorithms for the Restricted Longest Common Subsequence Problem

  • Djukanović, Marko
  • Kartelj, Aleksandar
  • Eftimov, Tome
  • Reixach, Jaume
  • Blum, Christian
En Computational Science – ICCS 2024, 24th International Conference, Malaga, Spain, July 2–4, 2024, Proceedings, Part V.- Conference proceedings., This paper deals with the restricted longest common subsequence (RLCS) problem, an extension of the well-studied longest common subsequence problem involving two sets of strings: the input strings and the restricted strings. This problem has applications in bioinformatics, particularly in identifying similarities and discovering mutual patterns and motifs among DNA, RNA, and protein molecules. We introduce a general search framework to tackle the RLCS problem. Based on this, we present an exact best-first search algorithm and a meta-heuristic Beam Search algorithm. To evaluate the effectiveness of these algorithms, we compare them with two exact algorithms and two approximate algorithms from the literature along with a greedy approach. Our experimental results show the superior performance of our proposed approaches. In particular, our exact approach outperforms the other exact methods in terms of significantly shorter computation times, often reaching an order of magnitude compared to the second-best approach. Moreover, it successfully solves all problem instances, which was not the case with the other approaches. In addition, Beam Search provides close-to-optimal solutions with remarkably short computation times., The research of M. Djukanović is partially supported by the Ministry for Scientific and Technological Development and Higher Education of the Republic of Srpska, B &H in the course of the bilateral research project between B &H and Slovenia entitled “Theoretical and computational aspects of some graph problems with the application to graph network information spreading” and the COST Action ROAR-NET under no. CA22137. A. Kartelj was supported by grant 451-03-47/2023-01/200104 funded by the Ministry of Science Technological Development and Innovations of the Republic of Serbia. J. Reixach and C. Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Extending CMSA with Reinforcement Learning: Application to Minimum Dominating Set

  • Reixach, Jaume
  • Blum, Christian
This volume constitutes the refereed proceedings of Metaheuristics on 15th International Conference, MIC 2024, held in Lorient, France, during June 4–7, 2024.- The 36 full papers presented together with 34 short papers were carefully reviewed and selected from 127 submissions. The conference focuses on artificial intelligence, combinatorial optimization, computer science, graph theory, evolutionary algorithms, genetic algorithms, simulated annealing, optimization, optimization problems., This work leverages reinforcement learning for designing a new variant of Construct, Merge, Solve and Adapt (CMSA), a rather new hybrid metaheuristic for combinatorial optimization. We demonstrate a twofold improvement over the standard CMSA. Firstly, the new variant simplifies CMSA by eliminating the need for a greedy function to probabilistically generate solutions. Additionally, it performs better, as we demonstrate in the context of the Minimum Dominating Set (MDS) problem., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Large Language Models for the Automated Analysis of Optimization Algorithms

  • Chacón Sartori, Camilo
  • Blum, Christian
  • Ochoa, Gabriela
GECCO '24: Genetic and Evolutionary Computation Conference, July 14 - 18, 2024, VIC, Melbourne, Australia., The ability of Large Language Models (LLMs) to generate high-quality text and code has fuelled their rise in popularity. In this paper, we aim to demonstrate the potential of LLMs within the realm of optimization algorithms by integrating them into STNWeb. This is a web-based tool for the generation of Search Trajectory Networks (STNs), which are visualizations of optimization algorithm behavior. Although visualizations produced by STNWeb can be very informative for algorithm designers, they often require a certain level of prior knowledge to be interpreted. In an attempt to bridge this knowledge gap, we have incorporated LLMs, specifically GPT-4, into STNWeb to produce extensive written reports, complemented by automatically generated plots, thereby enhancing the user experience and reducing the barriers to the adoption of this tool by the research community. Moreover, our approach can be expanded to other tools from the optimization community, showcasing the versatility and potential of LLMs in this field., C. Chacón and C. Blum were supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/ 501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

STNWeb for the analysis of optimization algorithms: a short introduction

  • Chacón Sartori, Camilo
  • Blum, Christian
This volume constitutes the refereed proceedings of Metaheuristics on 15th International Conference, MIC 2024, held in Lorient, France, during June 4–7, 2024., Ponencia de conferencia., In the realm of optimization, where intricate landscapes conceal possibly hidden pathways to high-quality solutions, STNWeb serves as a beacon of clarity. This novel web-based visualization platform empowers researchers to delve into the intricate interplay between algorithms and optimization problems, uncovering the factors that influence algorithm performance across diverse problem domains, be they discrete/combinatorial or continuous. By leveraging the inherent power of visual data representation, STNWeb transcends traditional analytical methods, providing a robust foundation for dissecting algorithm behavior and pinpointing the mechanisms that elevate one algorithm above another. This visually-driven approach fosters a deeper understanding of algorithmic strengths and weaknesses, ultimately strengthening the discourse surrounding algorithm selection and refinement for complex optimization tasks., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Two Examples for the Usefulness of STNWeb for Analyzing Optimization Algorithm Behavior

  • Akbay, Mehmet Anıl
  • Blum, Christian
15th International Conference, MIC 2024, Lorient, France, June 4–7, 2024, Proceedings, Part II., Search Trajectory Networks (STNs) are visualizations of directed graphs designed to analyze the behavior of stochastic optimization algorithms such as metaheuristics. Their purpose is to provide researchers with a tool that allows them to gain a deeper understanding of the behavior exhibited by multiple algorithms when applied to a specific instance of an optimization problem. In this short paper, we present two examples of our work in which STN graphics have helped us to discover interesting and useful algorithm/problem characteristics., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Advocating CMSA as a Baseline Algorithm for Algorithm Comparison in Combinatorial Optimziation

  • Blum, Christian
Included in the following conference series: International Conference on Information Technology, Adaptive Intelligence: Select Proceedings of InCITe 2024, Volume 1, Conference proceedings., In the field of approximate algorithms for combinatorial optimization, researchers frequently assess their optimization algorithms by comparing them to integer linear programming solvers like CPLEX and Gurobi, whenever feasible. Predictably, the general trend indicates that soft computing techniques such as evolutionary algorithms and tabu search tend to surpass integer linear programming solvers once the difficulty of the considered problem instances exceeds a certain threshold. In this paper, we advocate for adopting (or additionally using) a recent hybrid technique known as CMSA for evaluating newly developed optimization algorithms. CMSA employs an iterative approach, applying integer linear programming solvers to opportunely defined sub-instances of the addressed problem instances. Remarkably, this technique tends to outperform black-box integer linear programming solvers, especially in the context of larger and more challenging problem instances. We substantiate our argument by presenting results related to the bin packing problem with conflicts., The author was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Application of Adapt-CMSA to the Electric Vehicle Routing Problem with Simultaneous Pickup and Deliveries

  • Akbay, Mehmet Anıl
  • Blum, Christian
  • Kalayci, Can Berk
Computer Aided Systems Theory – EUROCAST 2024 19th International Conference, Las Palmas de Gran Canaria, Spain, February 25 – March 1, 2024, Revised Selected Papers, Part I, Conference paper., The Vehicle Routing Problem (VRP) has long been a cornerstone in combinatorial optimization, aiming to optimize the fleet of vehicles delivering goods in a transportation network. With the global shift towards sustainability, Electric Vehicles (EVs) have emerged as a green logistics alternative, leading to the Electric Vehicle Routing Problem with Simultaneous Pickup and Delivery (EVRP-SPD). This problem variant introduces the complexities of EV constraints, such as battery limitations and recharging necessities, coupled with handling delivery and pickup demands simultaneously during a single customer visit. This paper presents the application of the recent hybrid metaheuristic Construct, Merge, Solve & Adapt (CMSA) to the EVRP-SPD. Our self-adaptive version of CMSA, combined with a set covering-based mathematical formulation, offers a promising approach to efficiently tackle larger instances of the problem, aiming to provide high-quality solutions., This paper was supported by grants TED2021-129319B-I00 and PID2019-104156GB-I00 funded by MCIN/AEI/10.13039/501100011033. Moreover, M.A. Akbay and C.B. Kalayci received support from the Technological Research Council of Turkey (TUBITAK) under grant number 119M236. The corresponding author was funded by the Ministry of National Education, Turkey (Scholarship Prog.: YLYS-2019)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A Short Bibliometric Review of Metaheuristics

  • Akbay, Mehmet Anıl
  • Reixach, Jaume
  • Rodríguez-Corominas, Guillem
  • Chacón Sartori, Camilo
  • Blum, Christian
This paper presents a concise bibliometric review of metaheuristics, a class of high-level, problem-independent algorithmic frameworks designed for heuristic optimization. Since their rise in the late twentieth century, driven largely by advances in computational power, metaheuristics have become increasingly popular in solving complex optimization problems. In this review, we examine the evolution of the metaheuristics literature, highlighting key trends, developments, and the growing impact of this field over time., The research presented in this paper was supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/ AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

The Hybrid Metaheuristic CMSA

  • Blum, Christian
  • Reixach, Jaume
In this chapter, we describe the Construct, Merge, Solve & Adapt (CMSA) algorithm, a metaheuristic framework designed to address hard combinatorial optimization problems. CMSA combines the probabilistic construction of solutions within an adaptive, iterative process with solution merging and exact optimization techniques. The algorithm probabilistically constructs solutions through heuristic methods, which are then merged into a reduced subproblem. This subproblem is solved using exact optimization approaches, mostly integer programming. Based on the feedback from this solving phase, the algorithm adapts its construction and merging strategies in subsequent iterations, progressively finding solutions of improving quality over time. CMSA’s hybrid nature allows it to balance between the speed of heuristic construction and the accuracy of exact methods, making it particularly effective for large-scale problems. After a general description of standard CMSA, we outline a recent self-adaptive variant and a variant that uses reinforcement learning to improve the search process. All three algorithm variants are applied to the classical maximum independent set problem. Moreover, an experimental evaluation is provided to show their comparative behavior., The authors were supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Tight Bounds for an Accelerated k-means++ Algorithm

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús
  • Blum, Christian
21st IFIP WG 12.5 International Conference, AIAI 2025, Limassol, Cyprus, June 26–29, 2025, Proceedings, Part I, Conference proceedings. IFIP (International Federation for Information Processing)., In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the -means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer reviewed