On the automatic generation of metaheuristic algorithms for combinatorial optimization problems

Résumé

Every day, we are bombarded with decisions: how to travel to a specific destination; which foods will make our meal; how to best organize our closets. Optimization problems are everywhere: engineering, logistics, biology, economy ... and of course, in our day-to-day lives. All optimization problems have something in common: we want to reach a certain set of objectives, according to a set of restrictions. Optimization problems can be commonly solved using two distinct techniques: exact methods, and approximate methods. Exact methods are able to find the best existing solutions, but when applied to most real-life optimization problems, they scale poorly, and require enormous computing resources and large execution time with modest problem sizes. On the other hand, approximate methods, such as heuristic and metaheuristic algorithms, can find good quality solutions using few resources, but they cannot know if there are better solutions to the solutions they find, or if, on the contrary, any generated solution is optimal. While metaheuristic algorithms have become one of the most popular methods for solving optimization problems, some issues have been highlighted in the literature. Specifically, two of the most common issues are lack of both reproducibility and reusability of the approaches; and adhoc decisions, based on the researcher¿s experience, that may be difficult to justify from a purely scientific point of view. To this end, in this doctoral thesis a new methodology for the automated generation of reproducible metaheuristic configurations is presented. The proposal will not only be theoretical, a reference implementation, called Mork (Metaheuristic Optimization framewoRK) will be provided and tested. The benefits of the methodology and its corresponding implementation will be demonstrated against three completely different optimization problems, belonging to unrelated problem families: a facility layout problem, a vehicle routing problem and a clustering problem.