Titulo Estágio
The Traveling Thief
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
CISUC
Enquadramento
Many real world problems comprise a non-linear combination of several sub-problems. The existing interactions between partial solutions impact the quality of the global solution, thus complicating the task of optimisation algorithms.
Unfortunately, many benchmarks adopted by the Evolutionary Computation community tend to ignore this question and the impact of non-linear interactions between problem components is usually outside the discussion of algorithmic effectiveness.
The Traveling Thief Problem (TTP) is a recent benchmark [1] that considers the interdependence between two well known problems: the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP). The underlying idea behind the TTP is to maximize the profit of a thief that is traveling through a certain number cities stealing items. The thief uses a knapsack with a limited capacity and pays a rent for it, that depends on the time needed to visit all the cities. The interdependence of the TTP emerges from the fact that the speed of the thief depends (non-linearly) on the weight of the items picked so far.
In a recent work [2] we proposed an Evolutionary Algorithm (EA) to solve the TTP by tackling both sub-problems at the same time. The experimental study conducted showed that solving the problem as a whole creates conditions for discovering solutions with enhanced quality. Moreover, we conducted an additional experimental analysis that showed that fixing one of the sub-problems, might compromise the quality of the overall results.
Objetivo
Building upon the work the is being conducted at our Group, the goal is to propose, develop and access the effectiveness of a bio-inspired heuristic to tackle the TTP problem. In concrete we aim at develop a constructive heuristic to tackle both TTP sub-problems at the same time.
Plano de Trabalhos - Semestre 1
- Review of the state of the art
- Analysis of the existing heuristics for the TTP
- Proposal of a constructive heuristic for the TTP
- Documentation
Plano de Trabalhos - Semestre 2
- Implementation and Validation of the constructive heuristic
- Experimental analysis of the new heuristic
- Documentation
Condições
The ECOS Laboratory and its computing resources are available for performing experiments. The research group has a computer cluster available for the experimental analysis.
Observações
The student will work within a research group with high national and international visibility. During the work the student will acquire a set of skills that are important for someone who wants to pursue an academic/researching career.
The candidate curriculum is required.
Students with strong skills in programming (Python/C) are highly preferred.
Orientador
Nuno Lourenço & Francisco B. Pereira & Ernesto Costa
naml@dei.uc.pt 📩