Treffer: Recombination vs stochasticity : a comparative study on the maximum clique problem

Title:
Recombination vs stochasticity : a comparative study on the maximum clique problem
Authors:
Vella, Michael, Abela, John, Guillaumier, Kristian
Publication Year:
2024
Collection:
University of Malta: OAR@UM / L-Università ta' Malta
Subject Terms:
Graph theory -- Data processing, Computational complexity, Monte Carlo method, Stochastic processes, Heuristic algorithms, Cluster analysis -- Computer programs
Document Type:
Fachzeitschrift article in journal/newspaper
Language:
English
Relation:
Vella, M., Abela, J., & Guillaumier, K. (2024). Recombination vs Stochasticity : A Comparative Study on the Maximum Clique Problem. arXiv preprint arXiv:2409.18157.; https://www.um.edu.mt/library/oar/handle/123456789/133255
DOI:
10.48550/arXiv.2409.18157
Availability:
https://www.um.edu.mt/library/oar/handle/123456789/133255
https://doi.org/10.48550/arXiv.2409.18157
Rights:
info:eu-repo/semantics/openAccess ; The copyright of this work belongs to the author(s)/publisher. The rights of this work are as defined by the appropriate Copyright Legislation or as modified by any successive legislation. Users may access this work and can make use of the information contained in accordance with the Copyright Legislation provided that the author must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the prior permission of the copyright holder.
Accession Number:
edsbas.622F4BCA
Database:
BASE

Weitere Informationen

The maximum clique problem (MCP) is a fundamental problem in graph theory and in computational complexity. Given a graph 𝐺, the problem is that of finding the largest clique (complete subgraph) in 𝐺. The MCP has many important applications in different domains and has been much studied. The problem has been shown to be NP-Hard and the corresponding decision problem to be NP-Complete. All exact (optimal) algorithms discovered so far run in exponential time. Various meta-heuristics have been used to approximate the MCP. These include genetic and memetic algorithms, ant colony optimization, greedy algorithms, Tabu algorithms, and simulated annealing. This study presents a critical examination of the effectiveness of applying genetic algorithms (GAs) to the MCP compared to a purely stochastic approach. Our results indicate that Monte Carlo algorithms, which employ random searches to generate and then refine sub-graphs into cliques, often surpass genetic algorithms in both speed and capability, particularly in less dense graphs. This observation challenges the conventional reliance on genetic algorithms, suggesting a reevaluation of crossover and mutation operators’ roles in exploring the solution space. We observe that, in some of the denser graphs, the recombination strategy of genetic algorithms shows unexpected efficacy, hinting at the untapped potential of genetic methods under specific conditions. This work not only questions established paradigms but also opens avenues for exploring algorithmic efficiency in solving the MCP and other NP-Hard problems, inviting further research into the conditions that favor purely stochastic methods over genetic recombination and vice versa. ; peer-reviewed