Examinando por Autor "Duarte, Abraham"

Mostrando 1 - 20 de 26

A fast variable neighborhood search approach for multi-objective community detection
(Applied Soft Computing (Elsevier), 2021-11) Perez-Pelo, Sergio; Sanchez-Oro, Jesús; Gonzalez-Pardo, Antonio; Duarte, Abraham
Community detection in social networks is becoming one of the key tasks in social network analysis, since it helps analyzing groups of users with similar interests. This task is also useful in different areas, such as biology (interactions of genes and proteins), psychology (diagnostic criteria), or criminology (fraud detection). This paper presents a metaheuristic approach based on Variable Neighborhood Search (VNS) which leverages the combination of quality and diversity of a constructive procedure inspired in Greedy Randomized Adaptative Search Procedure (GRASP) for detecting communities in social networks. In this work, the community detection problem is modeled as a bi-objective optimization problem, where the two objective functions to be optimized are the Negative Ratio Association (NRA) and Ratio Cut (RC), two objectives that have already been proven to be in conflict. To evaluate the quality of the obtained solutions, we use the Normalized Mutual Information (NMI) metric for the instances under evaluation whose optimal solution is known, and modularity for those in which the optimal solution is unknown. Furthermore, we use metrics widely used in multiobjective optimization community to evaluate solutions, such as coverage, ϵ-indicator, hypervolume, and inverted generational distance. The obtained results outperform the state-of-the-art method for community detection over a set of real-life instances in both, quality and computing time.
A general variable neighborhood search for the cyclic antibandwidth problem
(Computational Optimization and Applications (Springer), 2022-01-17) Cavero, Sergio; Pardo, Eduardo G.; Duarte, Abraham
Graph Layout Problems refer to a family of optimization problems where the aim is to assign the vertices of an input graph to the vertices of a structured host graph, optimizing a certain objective function. In this paper, we tackle one of these problems, named Cyclic Antibandwidth Problem, where the objective is to maximize the minimum distance of all adjacent vertices, computed in a cycle host graph. Specifically, we propose a General Variable Neighborhood Search which combines an efficient Variable Neighborhood Descent with a novel destruction–reconstruction shaking procedure. Additionally, our proposal takes advantage of two new exploration strategies for this problem: a criterion for breaking the tie of solutions with the same objective function and an efficient evaluation of neighboring solutions. Furthermore, two new neighborhood reduction strategies are proposed. We conduct a thorough computational experience by comparing the algorithm proposed with the current state-of-the-art methods over a set of previously reported instances. The associated results show the merit of the introduced algorithm, emerging as the best performance method in those instances where the optima are unknown. These results are further confirmed with nonparametric statistical tests.
A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem
(Springer, 2022) Casado, Alejandra; Pérez-Peló, Sergio; Sánchez-Oro, Jesús; Duarte, Abraham
The selection of individuals with similar characteristics from a given population have always been a matter of interest in several scientific areas: data privacy, genetics, art, among others. This work is focused on the maximum intersection of k-subsets problem (kMIS). This problem tries to find a subset of k individuals with the maximum number of features in common from a given population and a set of relevant features. The research presents a Greedy Randomized Adaptive Search Procedure (GRASP) where the local improvement is replaced by a complete Tabu Search metaheuristic with the aim of further improving the quality of the obtained solutions. Additionally, a novel representation of the solution is considered to reduce the computational effort. The experimental comparison carefully analyzes the contribution of each part of the algorithm to the final results as well as performs a thorough comparison with the state-of-the-art method. Results, supported by non-parametric statistical tests, confirms the superiority of the proposal.
A heuristic approach for the online order batching problem with multiple pickers
(Elsevier, 2021) Gil-Borrás, Sergio; G.Pardo, Eduardo; Alonso-Ayuso, Antonio; Duarte, Abraham
The Online Order Batching Problem with Multiple Pickers (OOBPMP) consists of optimizing the operations related to the picking process of orders in a warehouse, when the picking policy follows an order batching strategy. In this case, this variant of the well-known Order Batching Problem considers the existence of multiple workers in the warehouse and an online arrival of the orders. We study three different objective functions for the problem: minimizing the completion time, minimizing the picking time, and minimizing the differences in the workload among the pickers. We have identified and classified all previous works in the literature for the OOBPMP. Finally, we propose a multistart procedure hybridized with a Variable Neighborhood Descent metaheuristic to handle the problem. We test our proposal over well-known instances previously reported in the literature by empirically comparing the performance of our proposal with previous methods in the state of the art. The statistical tests corroborated the significance of the results obtained.
A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem
(MIT Press Direct, 2023) Martin-Santamaria, Raul; Cavero, Sergio; Herran, Alberto; Duarte, Abraham; Colmenar, Jose Manuel
Reproducibility of experiments is a complex task in stochastic methods such as evolu- tionary algorithms or metaheuristics in general. Many works from the literature give general guidelines to favor reproducibility. However, none of them provide both a practical set of steps and also software tools to help on this process. In this paper, we propose a practical methodology to favor reproducibility in optimization prob- lems tackled with stochastic methods. This methodology is divided into three main steps, where the researcher is assisted by software tools which implement state-of-the- art techniques related to this process. The methodology has been applied to study the Double Row Facility Layout Problem, where we propose a new algorithm able to obtain better results than the state-of-the-art methods. To this aim, we have also repli- cated the previous methods in order to complete the study with a new set of larger instances. All the produced artifacts related to the methodology and the study of the target problem are available in Zenodo.
A reactive path relinking algorithm for solving the bi-objective p-Median and p-Dispersion problem
(Springer, 2023) Lozano Osorio, Isaac; Sánchez-Oro, Jesús; López Sánchez, Ana Dolores; Duarte, Abraham
This paper deals with an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities. The problem is addressed with a novel path relinking approach, called reactive path relinking, which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. Additionally, the proposal is adapted to a multi-objective perspective for finding a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature.
An experimental comparison of Variable Neighborhood Search variants for the minimization of the vertex-cut in layout problems
(Elsevier, 2012) Sánchez-Oro, Jesús; Duarte, Abraham
Variable Neighborhood Search (VNS) is a metaheuristic for solving optimization problems based on a systematic change of neighborhoods. In recent years, a large variety of VNS strategies have been proposed. However, we have only found limited experimental comparisons among different VNS variants. This paper reviews three VNS strategies for finding near-optimal solutions for vertex-cut minimization problems. Specifically, we consider the min-max variant (Vertex Separation Problem) and the min-sum variant (SumCut Minimization Problem). We also present an preliminary computational comparison of the methods on previously reported instances.
Apuntes de la asignatura Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pérez, Sergio; Pantrigo, Juan José; Duarte, Abraham
Diapositivas de Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio
Efficient Iterated Greedy for the Two-Dimensional Bandwidth Minimization Problem
(Elsevier, 2022) Cavero, Sergio; G. Pardo, Eduardo; Duarte, Abraham
Graph layout problems are a family of combinatorial optimization problems that consist of finding an embedding of the vertices of an input graph into a host graph such that an objective function is optimized. Within this family of problems falls the so-called Two-Dimensional Bandwidth Minimization Problem (2DBMP). The 2DBMP aims to minimize the maximum distance between each pair of adjacent vertices of the input graph when it is embedded into a grid host graph. In this paper, we present an efficient heuristic algorithm based on the Iterated Greedy (IG) framework hybridized with a new local search strategy to tackle the 2DBMP. Particularly, we propose different designs for the main IG procedures (i.e., construction, destruction, and reconstruction) based on the trade-off between intensification and diversification. Additionally, the improvement method incorporates three advanced strategies: an efficient way to evaluate the objective function of neighbor solutions, a tiebreak criterion to deal with “flat landscapes”, and a neighborhood reduction technique. Extensive experimentation was carried out to assess the IG performance over state-of-the-art methods, emerging our approach as the most competitive algorithm. Specifically, IG finds the best solutions for all instances considered in considerably less execution time. Statistical tests corroborate the merit of our proposal.
Ejercicios de la asignatura Algortimos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio
Finding weaknesses in networks using Greedy Randomized Adaptive Search Procedure
(Wiley, 2020-02-17) Pérez-Peló, Sergio; Sánchez-Oro, Jesús; Duarte, Abraham
En los últimos años, la relevancia de la ciberseguridad ha sido cada vez más evidente para las empresas e instituciones, así como para los usuarios finales. Por ello, es importante garantizar la robustez de una red. Con el objetivo de mejorar la seguridad de la red, es conveniente averiguar cuáles son los nodos críticos de la infraestructura, para protegerlos de atacantes externos. Este trabajo aborda este problema, denominado problema α-separador, desde una perspectiva heurística, proponiendo un algoritmo basado en el Procedimiento de Búsqueda Adaptativa Aleatoria Greedy (GRASP). En particular, se propone un enfoque novedoso para el procedimiento constructivo, en el que se utilizan métricas de centralidad derivadas del análisis de redes sociales como criterio voraz. Además, se mejora la calidad de las soluciones proporcionadas mediante un método de combinación basado en Path Relinking (PR). Este trabajo explora diferentes variantes de PR, adaptando también la más reciente, Exterior PR, para el problema considerado. La combinación de GRASP + PR permite al algoritmo obtener soluciones de alta calidad en un tiempo de computación razonable. La propuesta se apoya en un conjunto de experimentos computacionales intensivos que muestran la calidad de la propuesta, comparándola con el algoritmo más competitivo encontrado en el estado del arte.
General Variable Neighborhood Search for the optimization of software quality
(Elsevier, 2024-05) Yuste, Javier; Pardo, Eduardo G.; Duarte, Abraham
In the area of Search-Based Software Engineering, software engineering issues are formulated and tackled as optimization problems. Among the problems within this area, the Software Module Clustering Problem (SMCP) consists of finding an organization of a software project that minimizes coupling and maximizes cohesion. Since modular code is easier to understand, the objective of this problem is to increase the quality of software projects, thus increasing their maintainability and reducing the associated costs. In this work we study a recently proposed objective function named Function of Complexity Balance (FCB). Since this problem has been demonstrated to be -hard, we propose a new heuristic algorithm based on the General Variable Neighborhood Search (GVNS) schema to tackle the problem. For the GVNS, we propose six different neighborhood structures and categorize them into three different groups. Then, we analyze their contribution to the results obtained by the algorithm. In order to improve the efficiency of the proposed approach, we leverage domain-specific information to perform incremental evaluations of the objective function and to explore only areas of interest in the search space. The proposed algorithm has been tested over a set of real world software repositories, achieving better results than the previous state-of-the-art method, a Hybrid Genetic Algorithm, in terms of both quality and computing times. Furthermore, the relevance of the improvement produced by our proposal has been corroborated by non-parametric statistical tests
GRASP con Path Relinking para el problema del SumCut
(MAEB, 2012) Sánchez-Oro, Jesús; Duarte, Abraham
En este artículo se propone un algoritmo GRASP combinado con Path Relinking para resolver el problema de minimización del SumCut. En el problema del SumCut, a partir de un grafo de n nodos es necesario etiquetar todos los nodos de forma que ca- da uno de ellos reciba una etiqueta única del conjunto f1; 2;
GRASP with strategic oscillation for the α-neighbor p-center problem
(Elsevier, 2022) Sánchez-Oro Calvo, Jesús; López Sánchez, Ana Dolores; García Hernández-Díaz, Alfredo; Duarte, Abraham
This paper presents a competitive algorithm that combines the Greedy Randomized Adaptive Search Procedure including a Tabu Search instead of a traditional Local Search framework, with a Strategic Oscillation post-processing, to provide high-quality solutions for the α-neighbor p-center problem (α − pCP). This problem seeks to locate p facilities to service or cover a set of n demand points with the objective of minimizing the maximum distance between each demand point and its αth nearest facility. The algorithm is compared to the best method found in the state of the art, which is an extremely efficient exact procedure for the continuous variant of the problem. An extensive comparison shows the relevance of the proposal, being able to provide competitive results independently of the α value.
Multi-objective general variable neighborhood search for software maintainability optimization
(Elsevier, 2024-07) Yuste, Javier; Pardo, Eduardo G.; Duarte, Abraham; Hao, Jin-Kao
The quality of software projects is measured by different attributes such as efficiency, security, robustness, or understandability, among others. In this paper, we focus on maintainability by studying the optimization of software modularity, which is one of the most important aspects in this regard. Specifically, we study two well-known and closely related multi-objective optimization problems: the Equal-size Cluster Approach Problem (ECA) and the Maximizing Cluster Approach Problem (MCA). Each of these two problems looks for the optimization of several conflicting and desirable objectives in terms of modularity. To this end, we propose a method based on the Multi-Objective Variable Neighborhood Search (MO-VNS) methodology in combination with a constructive procedure based on Path-Relinking. As far as we know, this is the first time that a method based on MO-VNS is proposed for the MCA and ECA problems. To enhance the performance of the proposed algorithm, we present three advanced strategies: an incremental evaluation of the objective functions, an efficient exploration of promising areas in the search space, and an analysis of the objectives that better serve as guiding functions during the search phase. Our proposal has been validated by experimentally comparing the performance of our algorithm with the best previous state-of-the-art method for the problem and three reference methods for multi-objective optimization. The experiments have been performed on a set of 124 real software instances previously reported in the literature
Multistart Search for the Cyclic Cutwidth Minimization Problem
(Computers & Operations Research (Elsevier), 2021) Cavero, Sergio; Pardo, Eduardo G.; Laguna, Manuel; Duarte, Abraham
English: The Cyclic Cutwidth Minimization Problem (CCMP) is a Graph Layout Problem that consists of finding an embedding of the vertices of a candidate graph in a host graph, in order to minimize the maximum cut of a host edge. In this case, the host graph is restricted to be a cycle. In this paper, we identify a new lower bound for the problem, and also a property which allows search procedures to drastically reduce the neighborhood size during the search. Additionally, we propose the use of an alternative objective function for min–max optimization problems, never used before in the context of the CCMP. These strategies have been combined within a multistart search procedure for this problem. The obtained method is compared with the state of the art for the CCMP using sets of problem instances previously published. Statistical tests indicate the merit of our proposal. Español: El problema de minimización del ancho de corte cíclico (CCMP) es un problema de grados que consiste en encontrar un embebido de los vértices de un grafo candidato en un grafo huésped, con el fin de minimizar el máximo corte de una arista del grafo huésped. En este caso, el grafo huésped se restringe a ser un ciclo. En este artículo, identificamos una nueva cota inferior para el problema, y también una propiedad que permite a los procedimientos de búsqueda reducir drásticamente el tamaño del vecindario durante la búsqueda. Además, proponemos el uso de una función objetivo alternativa para los problemas de optimización min-max, nunca utilizada antes en el contexto del CCMP. Estas estrategias se han combinado dentro de un procedimiento de búsqueda multistart para este problema. El método obtenido se compara con el estado del arte para el CCMP utilizando conjuntos de instancias de problemas publicados anteriormente. Las pruebas estadísticas indican el mérito de nuestra propuesta.
On the analysis of the influence of the evaluation metric in community detection over social networks
(MDPI, 2019) Perez-Pelo, Sergio; Sanchez-Oro, Jesus; Martin-Santamaria, Raul; Duarte, Abraham
Community detection in social networks is becoming one of the key tasks in social network analysis, since it helps with analyzing groups of users with similar interests. As a consequence, it is possible to detect radicalism or even reduce the size of the data to be analyzed, among other applications. This paper presents a metaheuristic approach based on Greedy Randomized Adaptive Search Procedure (GRASP) methodology for detecting communities in social networks. The community detection problem is modeled as an optimization problem, where the objective function to be optimized is the modularity of the network, a well-known metric in this scientific field. The results obtained outperform classical methods of community detection over a set of real-life instances with respect to the quality of the communities detected.
Order batching problems: Taxonomy and literature review
(Elsevier, 2023) G. Pardo, Eduardo; Gil-Borrás, Sergio; Alonso-Ayuso, Antonio; Duarte, Abraham
Order Batching is a family of optimization problems related to the process of picking items in a warehouse as part of supply chain management. Problems classified into this category are those whose picking policy consists of grouping the orders received in a warehouse into batches, prior to starting the picking process. Once the batches have been formed, all items within the same batch are picked together on a single picking route. In this survey we review the optimization problems known in this family, focusing on manual picking systems and rectangular-shaped warehouses with only parallel and cross aisles, which is the most common warehouse configuration in the literature. First, we identify the decisions within the strategic, tactical, and operational levels that influence the picking task. Then, we characterize the optimization problems belonging to this family, whose objective function might differ. The identified problems are classified into a taxonomy proposed in this paper, which is designed to host future problems within this family. We also review the most outstanding papers by category and the strategies and algorithms proposed for the most relevant activities: batching, routing, sequencing, waiting, and assigning. To conclude, we outline the open issues and future paths of the topic under study.
Pruebas de evaluación de la asignatura Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio