Interactive metaheuristics for optimization-based decision support systems
Final Report Abstract
Fortgeschrittene Optimierungsmethoden wie beispielsweise moderne Metaheuristiken werden in Entscheidungsunterstützungswerkzeugen noch nicht vollständig ausgeschöpft. Es gibt drei Haupthindernisse für die Integration dieser Methoden in Entscheidungsunterstützungswerkzeuge. Erstens ist es schwierig, ein Modell des Optimierungsproblems zu finden, welches die Aspekte des tatsächlichen Problems allumfassend widerspiegelt. Zweitens gibt es eine Diskrepanz zwischen der Leistung der Optimierungsmethode und den echten Anforderungen eines Nutzers. Und drittens besteht seitens der Nutzer haufig Misstrauen oder Ablehnung gegenüber automatisch generierten Lösungen, was eine effektive Nutzung fortgeschrittener Optimierungsmethoden behindert. Um diese Kernpunkte anzugehen und Optimierungsmethoden in echte Anwendungen einzubinden, wurde in dem durchgeführten Projekt die Interaktion eines Entscheiders mit einem Entscheidungsunterstützungssystem in den Vordergrund gestellt. Die Projekthypothese war, dass durch die Interaktion zwischen einem Nutzer und dem System das Modell des Optimierungsproblems verbessert, der Suchprozess gelenkt und das Verständnis sowie die Akzeptanz der gefundenen Lösung beim Nutzer gefördert werden kann. Das durchgeführte Projekt untersuchte insbesondere eine interaktive Reoptimierungsmethode sowie eine innovative Erweiterung, welche darin besteht, Nutzerfeedbacks zu generalisieren. Diese Erweiterung erlaubt die Verwertung des Nutzerfeedbacks, um für nachfolgende Fälle des gleichen Problemtyps bessere Lösungen zu finden. Der untersuchte Anwendungskontext war die Personaleinsatzplanung, bei welcher Anpassung und Flexibilität Schlüsselaspekte darstellen. Es sei jedoch angemerkt, dass die Methode in weiteren Anwendungskontexten genutzt werden kann, z.B. Produktionsplanung, Transportsystemoptimierung oder allgemeiner bei komplexer Planung und Ablaufkoordination. Im Laufe des Projektes wurde der interaktive Reoptimierungsansatz in zwei Phasen evaluiert. In der ersten Phase wurde eine umfangreiche computerbasierte Studie umgesetzt, die dazu diente, die Optimierungsprozedur zu validieren bevor ein Experiment mit echten Anwendern durchgeführt werden konnte. Die Ergebnisse zeigen, dass die implementierte Methode effizient in der Lage ist, Lösungen unter Bedingungen zu reoptimieren, die bezogen auf den Zeitaufwand und die Lösungsqualität für eine interaktive Nutzung angemessen sind. Während der zweiten Phase des Projektes wurde ein Experiment mit dem Ziel konzipiert, die vorgeschlagene interaktive Reoptimierung mit echten Anwendern zu evaluieren. Für dieses Experiment haben wir einen voll funktionstüchtigen Prototypen eines Entscheidungsunterstützungssystems entwickelt. Dieses beinhaltet eine grafische Benutzerschnittstelle, die dem Anwender ermöglicht, Lösungskandidaten zu modifizieren. Mit Hilfe dieses Systems haben wir zwei Interaktionssettings getestet und miteinander verglichen. Im ersten Fall, der „manuellen Anpassung“, liefert das System eine initiale Lösung und der Anwender editiert die visuell aufbereitete Darstellung der Lösung mittels einer Drag-and-Drop Funktion. Diese Interaktion wird durch das System unterstützt, indem es dem Anwender den Einfluss der getätigten Aktionen auf die Lösung dynamisch rückmeldet. Im zweiten Fall, der „interaktiven Reoptimierung“, war die grafische Oberfläche dieselbe, aber die Lösungskandidaten wurden auf andere Weise angepasst. Hier spezifiziert der Anwender, welche Änderungen an der Lösung gewünscht werden. Durch einen Knopfdruck integriert das System die Änderungen und reoptimiert die Lösung automatisch innerhalb von wenigen Sekunden. Dieser interaktive Prozess kann mit weiteren gewünschten Änderungen iteriert werden bis eine zufriedenstellende Lösung erreicht ist. Jeder Experimentteilnehmer bearbeitete 10 Problemszenarien pro Setting. Die Ergebnisse zeigen die Effizienz des interaktiven Reoptimierungsansatzes auf und verdeutlichen, dass die Reoptimierungsmethode angemessen ist, um initiale Lösungskandidaten an fallspezifische Anforderungen anzupassen. Außerdem hat dieses Experiment gezeigt, dass der Einsatz von interaktiver Reoptimierung und weitere experimentell basierte Untersuchungen von interaktiven Optimierungsmethoden sinnvoll sind. Schließlich wurde über das gesamte Projekt hinweg eine tiefgehende und umfangreiche Literaturrecherche über existierende interaktive Optimierungsmethoden durchgeführt, aus der ein Übersichtsartikel entstanden ist, in dem die Methoden verglichen, klassifiziert und bewertet wurden. Eine Klassifikation von interaktiven Optimierungsmethoden gibt es unseres Wissens nach bisher nicht und stellt damit einen wertvollen Beitrag für die Forschung in diesem Bereich dar, denn sie bildet das konzeptuelle Fundament eines Frameworks für das Design interaktiver Optimierungsmethoden. Es führt in die übliche Terminologie zur Beschreibung und Analyse interaktiver Optimierungsmethoden ein, es unterstützt die Entwicklung von neuen interaktiven Optimierungsmethoden durch das Aufzeigen der wesentlichen Designentscheidungen und es kann dabei helfen, erfolgsversprechende und noch unerforschte Interaktionsmechanismen zu identifizieren.
Publications
- (2013): “Interactive Optimization with Long-Term Preferences Inference on a Shift Scheduling Problem”, In Proceedings of the 14th EU/ME Workshop, pp. 1-6, A. Fink and J. Geiger (eds.), Hamburg, Germany, 2013
D. Meignan, S. Knust
- (2014): “A Heuristic Approach to Schedule Reoptimization in the Context of Interactive Optimization”, In Genetic and Evolutionary Computation Conference, ACM, pp. 461-468, 2014
D. Meignan
(See online at https://doi.org/10.1145/2576768.2598213) - (2015): “An Experimental Investigation of Reoptimization for Shift Scheduling”, In Proceedings of the 11th Metaheuristics International Conference (MIC’15), Agadir, Morocco, June 7-10, 2015
D. Meignan
