Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs

Abstract

This paper reviews the existing literature on the combination of metaheuristics with machine learning methods and then introduces the concept of learnheuristics, a novel type of hybrid algorithms. Learnheuristics can be used to solve combinatorial optimization problems with dynamic inputs (COPDIs). In these COPDIs, the problem inputs (elements either located in the objective function or in the constraints set) are not fixed in advance as usual. On the contrary, they might vary in a predictable (non-random) way as the solution is partially built according to some heuristic-based iterative process. For instance, a consumer's willingness to spend on a specific product might change as the availability of this product decreases and its price rises. Thus, these inputs might take different values depending on the current solution configuration. These variations in the inputs might require from a coordination between the learning mechanism and the metaheuristic algorithm: at each iteration, the learning method updates the inputs model used by the metaheuristic.

Este artículo revisa la literatura existente sobre la combinación de metaheurísticas con métodos de aprendizaje automático y luego introduce el concepto de heurística de aprendizaje, un tipo novedoso de algoritmos híbridos. Las técnicas de aprendizaje se pueden usar para resolver problemas combinatorios de optimización con entradas dinámicas (COPDI). En estos COPDI, las entradas problemáticas (elementos ubicados ya sea en la función objetivo o en el conjunto de restricciones) no se fijan de antemano como de costumbre. Por el contrario, pueden variar de forma predecible (no aleatoria) ya que la solución se construye parcialmente de acuerdo con algún proceso iterativo basado en heurística. Por ejemplo, la disposición de un consumidor a gastar en un producto específico puede cambiar a medida que disminuye la disponibilidad de este producto y aumenta su precio. Por lo tanto, estas entradas pueden tomar diferentes valores dependiendo de la configuración de la solución actual. Estas variaciones en las entradas pueden requerir una coordinación entre el mecanismo de aprendizaje y el algoritmo metaheurístico: en cada iteración, el método de aprendizaje actualiza el modelo de entradas utilizado por la metaheurística.

Aquest article revisa la literatura existent sobre la combinació de metaheurístiques amb mètodes d'aprenentatge automàtic i després introdueix el concepte d'heurística d'aprenentatge, un tipus nou d'algorismes híbrids. Les tècniques d'aprenentatge es poden usar per resoldre problemes combinatoris d'optimització amb entrades dinàmiques (COPDI). En aquests COPDI, les entrades problemàtiques (elements ubicats ja sigui en la funció objectiu o en el conjunt de restriccions) no es fixen per endavant com de costum. Per contra, poden variar de forma predictible (no aleatòria) ja que la solució es construeix parcialment d'acord amb algun procés iteratiu basat en heurística. Per exemple, la disposició d'un consumidor a gastar en un producte específic pot canviar a mesura que disminueix la disponibilitat d'aquest producte i augmenta el preu. Per tant, aquestes entrades poden prendre diferents valors depenent de la configuració de la solució actual. Aquestes variacions en les entrades poden requerir una coordinació entre el mecanisme d'aprenentatge i l'algoritme metaheurístic: en cada iteració, el mètode d'aprenentatge actualitza el model d'entrades utilitzat per la metaheurística.