Bachelorprojekt - Softwareteknologi
Project No. 0251:  Visualizing and Evaluating the Working Principles of Nature-inspired Optimization Metaheuristics

Aktuelle

Tidligere

Description:

Visualizing and evaluating the working principles of nature-inspired optimization metaheuristics

Nature-inspired metaheuristics such as evolutionary algorithms, simulated annealing and ant colony optimization are often applied to hard optimization problems. The aim of this project is to develop a framework that implements and visualizes the working principles of nature-inspired metaheuristics for the solution of combinatorial optimization problems, most notably the traveling salesperson problem (TSP).

As a minimum, the framework should allow for the following:

• Search spaces: bit strings and permutations (corresponding to TSP tours)
• Nature-inspired algorihms: simulated annealing, an evolutionary algorithm, an ant colony optimization algorithm
• Problems:
• benchmark functions OneMax and LeadingOnes
• selected TSP instances from the TSPlib library (comopt.ifi.uni-heidelberg.de/software/TSPLIB95/)
• Visualize the constructed solutions for two-dimensional TSP instances
• Extract key figures from a run of a metaheuristic such as best-so-far fitness, running time, number of function evaluations etc.

The framework should be flexible, modular and extensible so that other problem classes, metaheuristics and visualizations can be added. Different metaheuristics should be evaluated w.r.t. their appropriateness for given optimization problems as part of the project.

Prerequisites:

Some prior knowledge of nature-inspired metaheuristics is beneficial

Restrictions: Max. 3 projects in spring 2022

Supervisor(s) Carsten Witt

Sidst opdateret: Nov 19, 2021 af Carsten Witt