Optimization By Learning

Abstract

Optimização combinatória é uma área que é objecto de estudo há vários anos, onde existem inúmeros algoritmos diferentes que se especializam em resolver problemas dentro do domínio desta. Um problema de optimização combinatória típico consiste em encontrar uma solução óptima entre um grupo de soluções candidatas com o intuito de maximizar/minimizar um dado objectivo. O campo de Machine Learning observou recentemente um grande crescimento, de particular relevância para este trabalho pela sua utilidade na automatização do processo de criação, adaptação e seleção de algorítmos de optimização aplicados a optimização combinatória. Nesta tese, é explorada a proposta de utilização de métricas de análise de fitness landscape, em exploração local, estocástica e iterativa do Travelling Salesman Problem. Treinamos um classificador de Machine Learning que tenta selecionar o melhor operador possivel numa dada instância, observando as propriedades da fitness landscape do local onde se encontra. Primeiro criamos um dataset para treinar o nosso classificador, e analisamos as instâncias generadas e os padrões de comportamento das métricas retiradas. Depois testamos diferentes configurações de classificadores, explorando os resultados obtidos, e finalmente testamos a nossa solução em conjunto com um algoritmo trepa colinas.Os resultados mostram que a escolha de operadores promissores utilizando um modelo de Machine Learning treinado com métricas relativas à análise da fitness landscape não é uma tarefa trivial, devido a dificuldades em distinguir padrões no comportamento dos operadores e nas propriedades das landscapes dos Travelling Salesman Problems abordados aqui.

Combinatorial optimization (CO) is a field that has been an object of study for many years, and there are a multitude of different algorithms specialized in solving a plethora of problems in the area. A typical CO problem consists of finding an optimal solution among a set of candidates that maximizes/minimizes the given objective. The field of Machine Learning has experienced a large growth in recent years for a multitude of purposes, but of particular interest here is its usefulness in the automation of the process of creating, adapting, and selecting optimization algorithms. In this dissertation, we explore the usage of fitness landscape analysis metrics in a local, stochastic, iterative exploration of the Travelling Salesman Problem, to train a Machine Learning classifier that attempts to select the best possible operator given the proprieties of the local landscape of a given solution. We create a dataset to train our model on, then process to analyse the generated instances and the behavior of the extracted metrics. We then test several different classifier configurations, explore the obtained results, and finally test our solution against an hill climbing algorithm.The results show the choice of promising operators utilizing a Machine Learning model trained using fitness landscape analysis metrics is not a trivial task, due to difficulty in discerning patterns both on operator behavior and on the landscape proprieties of the studied Travelling Salesman Problem instances.