Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Software Engineering

Taras Iks verteidigt seine Diplomarbeit zum Thema "Empirische Studie verschiedener Algorithmen für das Multi-Objective Release Planning".

Abstract:
In dieser Arbeit wird das Next-Release-Problem (NRP), basierend auf klassischen sowie realistischen Datensätzen, bearbeitet. Das NRP wird von fünf Algorithmen in Pareto- und Nicht-Pareto-Varianten gelöst und ausgewertet. Als Algorithmen werden NSGA-II (evolutionärer Algorithmus), Ant Colony Optimization (hybrider Algorithmus), Tabu Search und Simulated Annealing (beide lokale Suchalgorithmen) sowie Random Search verwendet. Das NRP sowie Algorithmen werden in jMetal-Framework implementiert. Weiterhin werden fünf Forschungsfragen zur Qualität der Nicht-Pareto- und Pareto-Algorithmen sowie zur Diversität, Zeit und Skalierung der Pareto-Algorithmen formuliert und anhand statistischer Daten beantwortet. Die empirische Studie hat einige interessante Entdeckungen gemacht: Obwohl Simulated Annealing die zweit schlechteste Metaheuristik für Pareto-Probleme darstellt, liefert sie für Nicht-Pareto-Probleme Lösungen auf dem Niveau vom Genetic Algorithm sowie Tabu Search und gehört somit zu den besten Metaheuristiken im Nicht-Pareto-Fall. Des Weiteren wurde festgestellt, dass Ant Colony Optimization und Random Search bei Nicht-Pareto-Problemen mit höherem Kostenfaktor bessere Lösungen im Vergleich zu anderen Metaheuristiken liefern, als wenn der Kostenfaktor geringer ist. Diese Tendenz wurde bei anderen Metaheuristiken nicht beobachtet. Bei Pareto-Problemen wurde allerdings deutlich, dass es starke Leistungsunterschiede zwischen den einzelnen Algorithmen gibt, so liefert Tabu Search in 90 % der Fälle Lösungen von besserer Qualität als alle anderen Algorithmen. Außerdem hat die Korrelationsanalyse gezeigt, dass Tabu Search gut in Bezug auf die Qualität der Lösungen skaliert.