I'm wondering if evolution-like (or genetic) algorithms are competitive for combinatorial optimization (CO) problems, such as knapsack, maximum independent set, travelling salesman etc. problems in comparison? I mean, as I know evolution algorithms are used when we know little about the structure of the optimizing function (for example for Black Box Optimization), so it means that Evolution should not be particularly strong for CO. Does anybody know any practical evidence/benefits of Evolution for CO?
1
-
$\begingroup$ Random key (and biased random key) genetic algorithms are designed specifically for discrete optimization problems. $\endgroup$– prubin ♦Commented Oct 20, 2023 at 22:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
While pure Evolutionary algorithms might have some drawbacks, when combined with local search methods, which can make further use of the problem structure, Genetic algorithms can perform very well. The combination of an evolution strategy, with a local solver is also called memetic or hybrid. Examples for this are the HGS-CVRP solver which is currently State-of-the-art for CVRP problems:
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624. https://doi.org/10.1287/opre.1120.1048 (Available HERE in technical report form).
Another example is the HG-means solver for minimum sum-of-squares clustering:
HG-means: A scalable hybrid genetic algorithm for minimum sum-of-squares clustering. D. Gribel and T. Vidal, 2019. Pattern Recognition, https://doi.org/10.1016/j.patcog.2018.12.022
-
$\begingroup$ 1) Thank you for your answer and the examples, after a bit searching I found out that KaMIS (the SOTA for Maximum independent set problem) also uses Evolution inside. So it is worth to try. 2) To clarify your answer about combination with local search, am I right that generally Evolution is rough method that can found promising regions, where one must use other methods to improve the solution via more accurate methods? $\endgroup$ Commented Oct 17, 2023 at 10:28
-
$\begingroup$ Yes exactly, for many problems and Evolutionary strategies that seems to be the case. Exploration by Evolution and Exploitation by Local Search. $\endgroup$– PeterDCommented Oct 18, 2023 at 20:20