Titulo Estágio
Compression Techniques for Optimization Algorithms
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
ECOS/CISUC
Enquadramento
Many algorithms for optimization
have to maintain a large pool of potential solutions to a given problem, such as
evolutionary algorithms, or algorithms for multicriteria optimization. In order
to run these algorithms in devices with few memory available, special
algorithms and data structures are needed to compress and uncompress solutions
in an efficient manner, without bringing too much computational cost (see .
G. R. Raidl and B. Hu., Enhancing genetic algorithms by a
trie-based complete solution
archive., In P. Cowling and P. Merz, editors, Evolutionary
Computation in
Combinatorial Optimisation - EvoCOP 2010, volume 6022 of LNCS,
pages 239-251. Springer, 2010). Several compression
techniques are available but they have been used quite rarely in the context of algorithms
for optimization.
Objetivo
The goal is to design and analyse algorithms and data structures that compress and uncompress solutions for a given set of real-life optimization problems, such as the knapsack problem, the shortest path problem and sequence alignment problem. The solutions to these problems are usually represented as a sequence of strings or integers as well as permutations and graphs. The student will consider compression techniques at run-lenght enconding level (e.g., Lempel-Ziv technique) and at data-structure level (e.g. tries and directed acyclic word graphs). The final goal is to perform an in-depth experimental analysis that allows to understand the trade-off memory vs. time of compression techniques in optimization algorithms.
Plano de Trabalhos - Semestre 1
1
Month: Problem identification
2 Months: Literature review on
compression techniques and optimization algorithms
1 Month: Writing of the preliminary
report (includes a description of the main compression techniques and their application to optimization algorithms).
Plano de Trabalhos - Semestre 2
2 Months: Algorithm implementation
1 Month: Experimental analysis
1 Month: Thesis writing.
Condições
The ECOSLab and its computing resources are available for performing
experiments. The research group owns a computer cluster for the
experimental analysis.
Observações
The student will work in a very motivated research group with wide
international visibility. He/she will
strengthen his abilities on the design and analysis of algorithms and
data structures for problem solving and will develop advanced
programming skills. This type of work is appropriate to students that
want to follow an academic career in design and analysis of algorithms.
Students
with excellent record on
Algorithms and Data Structures, Advanced Programming Lab and Evolutionary Computation are highly
preferable. Good experience in C,
C++, or Java is also necessary.
Orientador
Luis Paquete
paquete@dei.uc.pt 📩