Titulo Estágio
Alternative Fitness Functions for Evolutionary Algorithms
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
CISUC/DEI
Enquadramento
Evolutionary approaches are frequently used to solve hard optimization problems. Based on an initial population representing feasible solutions of a given problem, new solutions are generated based on a recombination and mutation operators. To keep the size of the population in balance inbetween generations, the quality of solutions is evaluated using a fitness function and poor solutions are discarded usually in a probabilistic way. In most cases, the objective function of the given optimization problem is used as the fitness function.
Since in this case the evaluation of the quality of the individuals within a population is purely based on a simple function evaluation, it does not take into account by how much the objective value of a new solution was improved as compared to the solutions it has been generated from. In other words, the "potential for improvement" of a solution is not quantified nor used in the selection of good solutions. It may be conjectured that this leads - depending on the problem at hand - to a concentration of the current population within small regions of the search space.
Objetivo
The main goal of this project is the development and analysis of different possibilities to quantify and to take into account the relative improvement of a solution as compared to its parents (or the potential for future improvement) within a simple evolutionary algorithm. The improvement potential should be considered as an additional criterion for the fitness evaluation. Alternative concepts of how the relative improvement of the objective value could be taken into account should be developed and their performance should be compared to already existing evolutionary approaches.
Plano de Trabalhos - Semestre 1
1 Month: Problem identification
2 Months: Literature review on evolutionary algorithms
1 Month: Writing of the preliminary report (includes a
description of alternative ways of defining fitness functions based on "potential for improvement")
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
There is the possibility of funding a visit to the co-supervisor, Jochen Gorski, at the group "Optimization and Approximation" of Prof. Dr. Kathrin Klamroth at the University of Wuppertal, Germany, during one week, under the project "Connectedness and local search for multi-objective combinatorial
optimization".
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
Evolutionary Computation, Algorithms and Data Structures, Advanced Programming Lab are highly
preferable. Good experience in C,
C++, or Java, as well as proficiency in English, is also necessary.
Orientador
Luis Paquete e Jochen Gorski
paquete@dei.uc.pt 📩