Optimierungsalgorithmen haben sich in den letzten Jahrzehnten zu einem Standardwerkzeug in vielen Anwendungsgebieten entwickelt. Prominente Beispiele sind Management, Logistik, Maschinenbau, Design, Chemie und Medizin. Nach kurzer Rechenzeit können sie näherungsweise optimale Lösungen für komplexe Probleme liefern. Die Forschung auf dem Gebiet der Optimierung hat die widersprüchlichen Ziele, sowohl die Geschwindigkeit als auch die Lösungsqualität der Algorithmen zu erhöhen. Damit solche Forschung erfolgreich sein und einen echten Einfluss auf die Praxis haben kann, müssen wir in der Lage sein
- die Performanz eines Algorithmus zu analysieren,
- den Einfluss der verschiedenen Eigenschaften eines Optimierungsproblems auf seine Schwere zu verstehen, und
- die Performanz von verschiedenen Algorithmen auf eine Faire und statistisch vernünftige Weise zu vergleichen.
Dies ist schwieriger, als man erwarten würde. Sehr viele Optimierungsverfahren sind sogenannte "Anytime Algorithms"/"Jederzeit Algorithmen"), die mit einer groben ersten Schätzung der Lösung eines Problems beginnen und diese in jedem Schritt zu verbessern suchen. Alle Evolutionären Algorithmen, alle lokalen Suchen (wie z.B. Simulated Annealing/Simulierte Abkühlung und Tabu-Suche), alle Schwarmintelligenz-Methoden wie der Ameisenalgorithmus und Partikelschwarmoptimierung, CMA-ES, und Memetische Algorithmen sind Jederzeit Algorithmen, aber auch viele exakte Lösungsverfahren wie Branch-and-Bound fallen in diese Kategorie, nur um ein paar zu nennen.
Der Vergleich von Jederzeit Algorithmen muss das gesamte Laufzeitverhalten der Verfahren beinhalten und kann sich nicht auf "Endergebnisse" reduzieren, da solche im eigentlichen Sinne nicht existieren und da sonst falsche Schlussfolgerungen nicht unwahrscheinlich sind. Dazu muss man berücksichtigen, dass die meisten oben genannten Algorithmen zufallsbasiert sind, d.h., nach jeder Ausführung bei gleicher Eingabe andere Lösungen generieren könnten. Darum müssen Performanzdaten über mehrere unabhängige Ausführungen hinweg gesammelt werden. Durch all diese Faktoren wird eine gründliche Analyse dieser Algorithmen erschwert.
Wir stellen eine Open Source Software vor, die Ihnen diese Arbeit erleichtern kann. Sie müssen nun lediglich die Performanzdaten Ihrer Algorithmen auf Ihren Problemen messen und unsere Software unterstützt Sie bei der Analyse. Die Software erfordert keinerlei Programmierkenntnisse und hat nahezu keine Anforderungen an die Art der zu analysierenden Algorithmen und Probleme. Sie erstellt Berichte sowohl in LaTeX als auch XHTML. Verschiedene Arten von Diagrammen und Datengruppierungen können frei konfiguriert werden, um ein besseres Verständnis der Algorithmenverhaltens zu ermöglichen. Grafiken und Texte können für die direkte Wiederverwendung in Publikationen wie IEEE Transactions und Springer LNCS generiert werden. Die Software steht auch als Docker-Image zur Verfügung, so dass sie sofort mit sehr geringem Installationsaufwand unter Linux, Windows, und MacOS verwendet werden kann.
Wir demonstrieren die Funktionsweise der Software anhand eines Beispielexperiments, in dem sechs primitive Heuristiken für ein Erfüllbarkeitsproblem, das Maximum Satisfiability Problem (MAX-SAT) untersucht werden. Weitere Beispiele für numerische Optimierung und das Problem des Handlungsreisenden stehen zum Download bereit.
Mehr Informationen können auf http://optimizationbenchmarking.github.io/ gefunden werden.
- Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui, Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine (CIM), 9(3):40-52, August 2014. Featured article and selected paper at the website of the IEEE Computational Intelligence Society (http://cis.ieee.org/).
details / doi:10.1109/MCI.2014.2326101 / pdf - Thomas Weise, Yuezhong Wu, Raymond Chiong, Ke Tang, and Jörg Lässig. Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. Journal of Global Optimization. accepted 12 February, 2016, published first online: 23 February, 2016.
details / doi:10.1007/s10898-016-0417-5 / pdf