Nahezu enge Laufzeitgarantien für viele-objektive evolutionäre Algorithmen

Trotz erheblicher Fortschritte im Bereich der mathematischen Laufzeitanalyse von multi-objektiven evolutionären Algorithmen (MOEAs) ist die Leistung von MOEAs bei diskreten viele-objektiven Problemen wenig verstanden. Insbesondere sind die wenigen bestehenden Grenzen für die SEMO-, globale SEMO- und SMS-EMOA-Algorithmen bei klassischen Benchmarks alle ungefähr quadratisch in der Größe der Pareto-Front. In dieser Arbeit beweisen wir nahezu enge Laufzeitgarantien für diese drei Algorithmen bei den vier häufigsten Benchmark-Problemen OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros und OneJumpZeroJump, und das für beliebige Anzahl von Zielen. Unsere Grenzen hängen nur linear von der Größe der Pareto-Front ab, was zeigt, dass diese MOEAs bei diesen Benchmarks viel besser mit vielen Zielen umgehen als frühere Arbeiten angedeutet haben. Unsere Grenzen sind eng, abgesehen von kleinen polynomialen Faktoren in der Anzahl der Ziele und der Länge der Bitfolgen. Dies ist das erste Mal, dass solche engen Grenzen für viele-objektive Anwendungen dieser MOEAs bewiesen werden. Während bekannt ist, dass solche Ergebnisse für den NSGA-II nicht gelten können, zeigen wir, dass unsere Grenzen, durch ein aktuelles strukturelles Ergebnis, auf den NSGA-III-Algorithmus übertragbar sind.