title: Diseño de Algoritmos Heurísticos y  Metaheurísticos eficientes para el problema SBPR
title: Optimización Eficiente del Problema SBPR mediante Algoritmos Heurísticos y Metaheurísticos
titleType: AlternativeTitle
title: Propuestas Metaheurísticas para Abordar el Problema SBPR
titleType: AlternativeTitle
title: Implementación y Análisis de Algoritmos Heurísticos para el Problema SBPR
titleType: AlternativeTitle
title: Efficient Algorithms for Sorting Permutations Using Prefix Reversals
titleType: AlternativeTitle
title: Metaheuristic Optimization for Permutation Sorting with Prefix Reversals
titleType: AlternativeTitle
title: Sorting by Prefix Reversals: Algorithms, Complexity, and Applications
titleType: AlternativeTitle
Creators: name: Palacios, Wilmer
name: Hernández Gómez, Fernando José
Publisher: name: Zenodo
Year: 2024
Subjects: Algoritmos heurísticos, Algoritmos metaheurísticos, Optimización combinatoria, Ordenamiento de permutaciones,
Sorting permutations, Heuristics algorithms, Metaheuristics algorithms, Combinatorial optimization

description: Sorting Permutations by Prefix Reversals (SBPR) is a classical combinatorial optimization problem that involves transforming a given permutation of $n$ elements into the identity permutation $\text{id}$ using a series of prefix reversals—operations that reverse the order of the leftmost elements of the permutation. This problem is often illustrated using the metaphor of a stack of pancakes that must be sorted using a spatula: at each step, the spatula is inserted under a prefix of the stack, which is then flipped to move elements closer to their sorted positions.

Since 2012, SBPR has been formally proven to belong to the NP-Hard class of computational problems. This classification implies that finding an optimal solution in polynomial time is unlikely, especially as the size of the problem grows. Consequently, recent research has focused on the use of heuristic and metaheuristic algorithms as practical alternatives that can deliver high-quality approximate solutions within a reasonable timeframe.

In this research, several heuristic and metaheuristic algorithms were designed and implemented, guided by methodologies and criteria established in the relevant literature. Notably, a family of life-inspired metaheuristics—algorithms inspired by biological and ecological systems—was proposed and demonstrated strong performance in navigating large and complex search spaces.

The implementation was carried out using the Python programming language within the Google Colab environment. In addition to algorithmic development, this work involved a review of modern permutation theory and fundamental ordering strategies.

The performance of the proposed algorithms was evaluated against benchmark instances and results reported in the scientific literature over the past decade. A comparative analysis highlighted the strengths and weaknesses of each method and identified the most suitable approaches for different problem contexts.

Ultimately, this thesis contributes to the advancement of research in combinatorial optimization by offering new algorithmic solutions, empirical evaluations, and insights into the practical applicability of prefix reversal sorting strategies.