Examinando por Autor "Duarte, Abraham"

Mostrando 1 - 20 de 35

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.
A variable neighborhood search approach for the adaptive multi round influence maximization problem
(Springer, 2024-08-20) Lozano-Osorio, Isaac; Sánchez-Oro, Jesús; Duarte, Abraham
Social Networks have been in continuous growing during the last decades. The huge amount of information and applications has led to an increase in the interest of scientists and practitioners in the study of problems related to the influence in Social Networks. Some of the wide variety of real-world applications in this area are viral marketing, disease analysis, rumor detection, public opinion, among others. In this paper, the Adaptive Multi Round Influence Maximization problem is studied, in which the influence of a set of selected users (seed set) is propagated in multiple rounds independently, with the possibility of selecting different seed sets in each round. Therefore, seed sets can be adaptively selected based on the propagation results in the previous rounds. Since each node is activated with a certain probability, the total number of activated nodes must be calculated through an Influence Diffusion Model (IDM), which results in a rather computationally demanding method. In this research, the Independent Cascade Model is considered, which is one of the most extended IDMs, and also the one used in the best previous method. Practitioners highlight the relevance of designing an algorithm capable of efficiently solving the problem. In this research, the problem is addressed by considering the Variable Neighborhood Search methodology, proposing a novel constructive method that relies on independent probability based on events, and an intelligent local search method. Our best algorithm is compared with the state-of-the-art method, named AdaIMM, to analyze the performance of the proposal. The obtained results show the superiority of the proposal in both quality (influence spread) and computing time, obtaining the best solution in all the 40 instances considered requiring half of the computing time than the best previous approach (28 s vs. 53 s). Additionally, the best previous method presents an average deviation of 24.23%. These results are further confirmed by conducting non-parametric statistic tests.
An efficient and effective GRASP algorithm for the Budget Influence Maximization Problem
(Springer, 2023-09-21) Lozano-Osorio, Isaac; Sánchez-Oro, Jesús; Duarte, Abraham
Social networks are in continuous evolution, and its spreading has attracted the interest of both practitioners and the scientific community. In the last decades, several new interesting problems have aroused in the context of social networks, mainly due to an overabundance of information, usually named as infodemic. This problem emerges in several areas, such as viral marketing, disease prediction and prevention, and misinformation, among others. Then, it is interesting to identify the most influential users in a network to analyze the information transmitted, resulting in Social Influence Maximization (SIM) problems. In this research, the Budget Influence Maximization Problem (BIMP) is tackled. BIMP proposes a realistic scenario where the cost of selecting each node is different. This is modeled by having a budget that can be spent to select the users of a network, where each user has an associated cost. Since BIMP is a hard optimization problem, a metaheuristic algorithm based on Greedy Randomized Adaptive Search (GRASP) framework is proposed.
An Efficient Fixed Set Search for the Covering Location with Interconnected Facilities Problem
(Springer, 2023-02-23) Lozano-Osorio, Isaac; Sánchez-Oro, Jesús; Martínez-Gavara, Anna; López-Sánchez, Ana D.; Duarte, Abraham
This paper studies the Coverage Location Problem with Interconnected Facilities (CPIF). It belongs to the family of Facility Location Problems, but being more realistic to nowadays situations as surveillance, or natural disaster control. This problem aims at locating a set of interconnected facilities to minimize the number of demand points that are not covered by the selected facilities. Two facilities are considered as interconnected if the distance between them is smaller than or equal to a predefined distance, while a facility covers a demand point if the distance to it is smaller than a certain threshold. The wide variety of real-world applications that fit into this model makes them attractive for designing an algorithm able to solve the problem efficiently. To this end, a metaheuristic algorithm based on the Fixed Set Search framework is implemented. The proposed algorithm will be able to provide high-quality solutions in short computational times, being competitive with the state-of-the-art.
An efficient heuristic algorithm for software module clustering optimization
(Elsevier, 2022-08) Yuste, Javier; Duarte, Abraham; Pardo, Eduardo G.
In the lifecycle of software projects, maintenance tasks usually entail 75% of the total costs, where most efforts are spent in understanding the program. To improve the maintainability of software projects, the code is often divided into components, which are then grouped in different modules following good design principles, lowering coupling and increasing cohesion. The Software Module Clustering Problem (SMCP) is an optimization problem that looks for maximizing the modularity of software projects in the context of Search-Based Software Engineering. In the SMCP, projects are often modeled as graphs. Therefore, the SMCP can be interpreted as a graph partitioning problem, which is proved to be NP-hard. In this work, we propose a new heuristic algorithm for software modularization, based on a Greedy Randomized Adaptive Search Procedure with Variable Neighborhood Descent. We present a three-fold categorization of neighborhoods for the SMCP and leverage domain-specific information to filter unpromising solutions. Our proposal has been successfully tested over a dataset of real software projects, outperforming the previous state-of-the-art approach in terms of Modularization Quality in very short computing times. Therefore, it could be integrated in software development tools to improve the quality of software projects in real time.
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.
An improved GRASP method for the Multiple Row Equal Facility Layout Problem
(Elsevier, 2021-11-15) R. Uribe, Nicolás; Herrán, Alberto; Colmenar, J. Manuel; Duarte, Abraham
As it is well documented in the literature, an effective facility layout design of a company significantly increases throughput, overall productivity, and efficiency. Symmetrically, a poor facility layout results in increased work-in process and manufacturing lead time. In this paper we focus on the Multiple Row Equal Facility Layout Problem (MREFLP) which consists in locating a given set of facilities in a layout where a maximum number of rows is fixed. We propose a Greedy Randomized Adaptive Search Procedure (GRASP), with an improved local search that relies on an efficient calculation of the objective function, and a probabilistic strategy to select those solutions that will be improved. We conduct a through preliminary experimentation to investigate the influence of the proposed strategies and to tune the corresponding search parameters. Finally, we compare our best variant with current state-of-the-art algorithms over a set of 552 diverse instances. Experimental results show that the proposed GRASP finds better results spending much less execution time.
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.