Dynamische evolutionäre Optimierung von Netzwerkproblemen

• Antragsteller: Professor Dr. Martin Middendorf
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme ; Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 392050753

Da die meisten Netzwerkoptimierungsprobleme (NOPs) NP-schwer sind, benötigen klassische exakte Algorithmen viele Berechnungsressourcen und können große Probleminstanzen nicht in praktisch relevanter Zeit lösen. Deswegen werden in der Praxis meistens (Meta-)heuristiken wie zum Beispiel genetische Algorithmen zur Lösung von NOPs eingesetzt. In der Forschung werden für NOPs bisher meist (quasi-)statische Bedingungen angenommen, wobei sowohl die Netzwerkumgebung als auch das Optimierungsproblem selbst als im Vorhinein bekannt und während des Optimierungsprozesses unveränderlich angenommen werden. In der Praxis befinden sich NOPs jedoch oft in einem dynamischen Umfeld wo sich die Netzwerktopologie, die Verfügbarkeit von Ressourcen, die Nutzeranforderungen und weitere Bedingungen zeitlich ändern können und oft nicht a priori genau bekannt sind. Wenn solche NOPs für die Praxis zufriedenstellend gelöst werden sollen, dürfen Dynamiken nicht vernachlässigt werden. Es ist auch notwendig die sich stetig verändernden Netzwerkumgebungen zu betrachten, d.h. dynamische NOPs (DNOPs) zu modellieren. Ein DNOP ist schwerer als seine statische Variante, da die sich dynamisch verändernde Umgebung und das sich dynamisch verändernde Problem selber jeweils zusätzliche Schwierigkeiten für die Optimierung bringen. Um ein DNOP erfolgreich zu lösen, muss eine Folge von sehr guten Lösungen erzeugen werden anstatt nur einer einzelnen Lösung wie im statischen Fall. In den letzten Jahren gibt es deshalb ein stark steigendes Interesse evolutionäre Methoden (EMs) für dynamische Optimierungsprobleme (DOPs) zu entwickeln bei denen sich Fitnessfunktion, Entscheidungsvariable und Umgebungsparameter über die Zeit verändern können. Es gibt jedoch bisher keine systematischen Forschungen zu EMs für DNOPs in Bezug auf verschiedene Netzwerkumgebungen. Es ist immer noch unbekannt, sowohl theoretisch als auch praktisch algorithmisch, was eine EM effektiv und effizient macht für verschiedene Arten von Dynamiken. Es ist immer noch unklar wie verschiedene Dynamiken geeignet modelliert und charakterisiert werden können um ein besseres Verständnis von DNOPs zu bekommen. Die spezifischen Eigenschaften von DNOPs in der Praxis müssen erst noch aufgedeckt und analysiert werden. In diesem Projekt soll die aufgezeigte Lücke zwischen den praktischen Anforderungen und dem Stand der Forschung geschlossen werden. Des Weiteren sollen EMs entwickelt werden, die zur Lösung von DNOPs geeignet sind, und es soll unser Verständnis erweitert werden warum und wie EMs effektiv und effizient DNOPs lösen können. Das Projekt adressiert somit sowohl theoretische Fragestellungen als auch algorithmisch praktische Entwicklungen und Untersuchungen. Als Schwerpunkt sollen in diesem Projekt DNOPs aus dem Bereich der Logistik betrachtet werden, obwohl die Forschung durchaus generisch ist und damit das Potential hat wichtige Konsequenzen auch für Anwendungen aus sehr unterschiedlichen Netzwerkumgebungen zu haben.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: China
• Partnerorganisation: National Natural Science Foundation of China
• Kooperationspartner: Professor Yuhui Shi