PhD. Subject: Strategies to design life-long learning heuristic based algorithms

Abstract

Nowadays combinatorial optimization problems arise in many circumstances, and we need to be able to solve these problems e ciently. Unfortunately, many of these problems are proven to be NP-hard, but problems can be related in some way. Analysing di erent combinatorial problems we can see some similarities between them. If we work with this similarities, we could improve the search process of an algorithm, because there exists some concurrent knowledge about solving a problem that could be exploited. For example, if an algorithm can solve an instance <i>X</i> for Sudoku puzzle ensuring uniqueness in blocks before rows and colums, this strategy can be useful for another instance Y when the algorithm is in a local optimum. In other words, some heuristics that can nd interesting candidate solutions can be reused in future during the execution of an algorithm. To do this, an algorithm should learn over time to determine how, when and which heuristic apply. The idea of this investigation is to create strategies to design life-long learning heuristic based algorithms. There have been some investigations in this area applied to 1-D Bin Packing problem, for Traveling Sales Problem and the most important thing, is that can be applied in different kinds of problem.

<i>(Párrafo extraído del texto a modo de resumen)</i>