Titulo Estágio
Evolutionary algorithms for the Google Hash Code problems
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
ECOS - CISUC
Enquadramento
The Google Hash Code is a programming competition where teams are asked to solve a challenging engineering problem using their computers and programming languages and tools of their choice. A collection of 11 problem statements from past competitions is publicly available from the Hash Code website. Hash Code challenges are typically modelled after problems arising in real-world situations, such as scheduling drone deliveries or self-driving cars, city planning and Wi-Fi router placement, for example, and are posed as “open” problems for which there are many valid solutions, some of which are better than others. In fact, most if not all Hash Code problems are essentially combinatorial optimization problems. The competition scoring rules define how to compute the quality of solutions.
Meanwhile, there is growing interest in the scientific community in the development of a suite of combinatorial optimisation benchmark problems that are relevant in practice and approachable from a theoretical perspective. It can be argued that the Hash Code problems have some potential in this context. On the one hand, they must be sufficiently simple to describe and implement for teams to be able to solve them (to some extent) in a few hours. On the other hand, they are illustrative of the problems that arise in industry by design. Since all of those problems have already been solved by many teams (thousands of teams for the qualification rounds, and tens of the best teams in the case of the final rounds) from around the world, there is also plenty of empirical data on the best solutions that have been achieved, even if under severe time constraints.
Finally, there is also great interest in how to make evolutionary algorithms more easily available to industry. One important aspect is the perception that combinatorial optimisation problems can be structurally very different from one another, which makes it difficult to write general-purpose heuristic solver software without incurring into the modelling effort required by integer linear programming (ILP) solvers, for example. In this work, an approach based on so-called geometric search operators will be adopted to allow evolutionary algorithms to be implemented in such a general way.
Objetivo
The main objective of this work is the development, implementation and evaluation of evolutionary algorithms (EAs) for the Hash Code problems. However, rather than developing a custom EA for each problem, a clear separation between the problems and the EA solvers will be established to the extent that exactly the same solver implementation can be applied to several different problems, not only in a technical sense, but also concerning the quality of the results.
Another very important objective is a critical discussion of the merits and shortcomings of the proposed approach to solver development for all parties potentially involved: EA researchers, software developers, and practitioners. Performance dimensions to be considered will include problem and solver development effort, computational performance of the implemented software, and the quality of the solutions achieved.
Plano de Trabalhos - Semestre 1
1. Familiarisation with the Hash Code competition challenges, and selection of a small number of different problems for further consideration.
2. Study of geometric search operators in evolutionary algorithms and related concepts.
3. Formulation of the chosen Hash Code problems as combinatorial local optimisation problems (search space, search neighbourhood, objective function).
4. Proof-of-concept implementation of search operators and objective functions for the chosen problems, as well as of a simple local search algorithm.
5. Intermediate report writing.
Plano de Trabalhos - Semestre 2
1. Implementation of state-of-the-art evolutionary algorithms based on geometric search operators.
2. Implementation of additional Hash Code problems to extend the benchmark suite.
3. Experimental study.
4. Evaluation and discussion of the methodology adopted and of the results achieved.
5. Dissertation writing.
Condições
Very good background in evolutionary computation, algorithms and data structures. The work will be carried out in the CISUC ECOS laboratories. A computer cluster is available to support the development and evaluation of the algorithms developed.
Observações
This project is NOT supported by Google or the Google Hash Code Team in any way, and will be carried out independently. Use of the Hash Code problems for practising and discussion is permitted by Google.
Orientador
Carlos M. Fonseca
cmfonsec@dei.uc.pt 📩