Titulo Estágio
Developing Partition Crossovers for Combinatorial Optimisation Problems
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI
Enquadramento
Combinatorial optimisation algorithms can be broadly divided into two classes: local search approaches and constructive search approaches. Local search approaches work by iteratively trying to improve a current solution by modifying it in some way. The rules that govern such modifications define a neighbourhood structure on the search space, and a solution that is at least as good as any other solution in its neighbourhood is called a local optimum. Thus, local search approaches solve a local formulation of a global optimisation problem. The absolute quality of the locally optimal solutions thus obtained depends critically on the choice of neighbourhood, even if also on the details of the local search algorithm itself. Although neighbourhoods are usually defined based on the internal structure of the solutions and on how solution components contribute to overall solution quality, the search algorithms themselves can only access the external neighbourhood structure and an a measure of the overall quality of each solution.
In contrast, constructive approaches depend on and directly exploit knowledge of the internal structure of solutions, often in combination with how solution components affect overall solution quality. For this reason, constructive approaches are potentially more powerful than pure local search approaches on problems where the relation between internal solution structure and overall solution quality is well understood.
So-called partition crossovers are search operators that use knowledge of the internal solution structure to tunnel between local optima in the context of local search. They have been shown to be very powerful on certain optimisation problems, namely the travelling salesman problem and pseudo-boolean optimisation, but it remains unclear how the operation of these crossovers can be related to the neighbourhood structure used to define the local optima on which they operate. Establishing such a relation based on the fact that both the neighbourhood structure and partition crossover exploit the same internal solution structure, even if in different ways, is the main challenge of this project.
Objetivo
The main objective of this work is the development of an abstract interpretation of partition crossover in terms of an underlying search neighbourhood and related concepts, such as distance, segments/intervals, and geometric recombination. Such an abstraction should then enable the definition of a programming interface for the implementation partition crossovers and, in turn, the development of partition crossovers for other combinatorial problems with suitable structural properties.
Plano de Trabalhos - Semestre 1
1. Study of local search operators and related concepts, including geometric recombination
2. Review of partition crossovers for the Travelling Salesman Problem, pseudo-boolean optimisation, and possibly other problems
3. Implementation of partition crossovers for the Travelling Salesman Problem
4. Preliminary proposal of an API for partition crossover implementation
5. Intermediate report writing
Plano de Trabalhos - Semestre 2
1. Design of partition crossovers for other combinatorial optimisation problems
2. Implementation of problems and solvers, including the proposed partition crossover operators, under the proposed API
3. Experimental study
4. Evaluation and discussion of the methodology adopted and of the results achieved
5. Dissertation writing
Condições
Good background in algorithms, data structures and evolutionary computation. The work will be carried out in the CISUC AC laboratories.
Orientador
Carlos Manuel Mira da Fonseca
cmfonsec@dei.uc.pt 📩