Abstract
This article describes the Distance Minimisation Problem (DMP) from a metaheuristic optimisation point of view. The problem is motivated by real applications and can be used to test the performance of optimisation methods like Evolutionary Algorithms. After formally describing the problem and its extensions using different metrics or dynamics, we perform experiments with well-known metaheuristic methods to demonstrate the performance on various DMP instances. The results show that modern algorithms like NSGA-II and SMPSO can struggle with this kind of problem under certain conditions, especially when Manhattan distances are used. On the other hand, specialised methods like GRA lack diversity of solutions in some cases. This indicates that even modern and powerful metaheuristic algorithms need to be chosen with care and with the respective optimisation task in mind.
Zusammenfassung
Dieser Artikel beschreibt das Distanzminimierungsproblem (DMP) aus der Perspektive der metaheuristischen Optimierung. Das Problem ist von realen Anwendungen inspiriert und kann genutzt werden um die Leistung von Optimierungsmethoden wie Evolutionären Algorithmen zu untersuchen. Nach einer formalen Beschreibung des Problems und der möglichen Erweiterungen mit verschiedenen Metriken oder Dynamiken führen wir Experimente mit bekannten Metaheuristiken durch, um die Performanz auf verschiedenen DMP Instanzen zu untersuchen. Die Ergebnisse zeigen, dass selbst moderne Algorithmen wie NSGA-II und SMPSO unter bestimmten Bedingungen Schwierigkeiten mit dieser Art von Problem haben, insbesondere wenn die Manhattan Metrik benutzt wird. Auf der anderen Seite erreichen spezialisierte Methoden wie der GRA in einigen Fällen nur eine geringe Diversität der Lösungen. Dies zeigt dass bei der Auswahl selbst moderner und etablierter metaheuristischer Algorithmen das zugrundeliegende Problem berücksichtigt werden sollte.
About the authors
Sanaz Mostaghim is a full professor of computer science at the Otto-von-Guericke University Magdeburg, Germany. She holds a PhD degree in electrical engineering and computer science from the University of Paderborn, Germany. She worked as a postdoctoral fellow at ETH Zurich in Switzerland and as a lecturer at Karlsruhe Institute of technology (KIT), Germany. Her research interests are in the area of evolutionary multi-objective optimisation, swarm intelligence, and their applications in robotics, science and industry. She serves as an associate editor for IEEE Trans. on Evolutionary Computation, IEEE Trans. on Cybernetics, IEEE Trans. on System, Man and Cybernetics: Systems and IEEE Trans. on Emerging Topics in Computational Intelligence.
Christoph Steup is a Post-Doc and project manager at the Otto-von- Guericke University in Magdeburg. He studied computer science with an emphasis on electrical engineering in Magdeburg and at the KTH in Sweden. After receiving his diploma, he started working on wireless sensor networks and distributed robotics in 2011 and published papers in the field of distributed sensing, time synchronization in WSN and efficient programming of embedded devices. Apart from his research, he supervises student teams entering competitions in the RoboCup and the Carolo Cup. He finished is PhD in 2018 and is now handling the theoretical and practical swarm robotics research in the “SwarmLab” of the Otto-von-Guericke University. In the lab he works on locomotion, self-organization, distributed sensing and distributed behaviour of swarms of air and ground robots.
Heiner Zille studied Information Engineering and Management at the Karlruhe Institute of Technology (KIT), Germany and the Doshisha University, Japan. He received his B.Sc. and M.Sc. degrees in 2011 and 2014 respectively. Currently, he is working as a research assistant and pursuing his PhD degree in the areas of evolutionary computation and swarm intelligence. From August 2015 to July 2016, he worked as a guest PhD student at Osaka Prefecture University in Sakai, Japan. His research focuses on multi-objective optimisation, in particular on problems with large numbers of decision variables.
References
1. Mohaned Al-Obaidy, Aladdin Ayesh and Alaa F. Sheta. Optimizing the communication distance of an ad hoc wireless sensor networks by genetic algorithms. Artificial Intelligence Review, 29(3):183, Nov 2009.10.1007/s10462-009-9148-zSearch in Google Scholar
2. K. Deb, A. Pratap, S. Agarwal and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.10.1109/4235.996017Search in Google Scholar
3. Kalyanmoy Deb. Multi-objective optimization using evolutionary algorithms. Wiley. Wiley, 2001.Search in Google Scholar
4. Joost R. Duflou, John W. Sutherland, David Dornfeld, Christoph Herrmann, Jack Jeswiet, Sami Kara, Michael Hauschild and Karel Kellens. Towards energy and resource efficient manufacturing: A processes and systems approach. CIRP Annals, 61(2):587–609, 2012.10.1016/j.cirp.2012.05.002Search in Google Scholar
5. H. Ishibuchi, M. Yamane, N. Akedo and Y. Nojima. Many-objective and many-variable test problems for visual examination of multiobjective search. In IEEE Congress on Evolutionary Computation, pages 1491–1498, 2013.10.1109/CEC.2013.6557739Search in Google Scholar
6. Hisao Ishibuchi, Naoya Akedo and Yusuke Nojima. A many-objective test problem for visually examining diversity maintenance behavior in a decision space. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 649–656. ACM, 2011.10.1145/2001576.2001666Search in Google Scholar
7. Hisao Ishibuchi, Yasuhiro Hitotsuyanagi, Noritaka Tsukamoto and Yusuke Nojima. Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space. In Parallel Problem Solving from Nature, PPSN XI, pages 91–100. Springer, 2010.10.1007/978-3-642-15871-1_10Search in Google Scholar
8. Mario Köppen and Kaori Yoshida. Many-objective particle swarm optimization by gradual leader selection. In Adaptive and Natural Computing Algorithms, pages 323–331. Springer, 2007.10.1007/978-3-540-71618-1_36Search in Google Scholar
9. Mario Köppen and Kaori Yoshida. Substitute distance assignments in nsga-ii for handling many-objective optimization problems. In Evolutionary Multi-Criterion Optimization, pages 727–741. Springer, 2007.10.1007/978-3-540-70928-2_55Search in Google Scholar
10. André Kottenhahn. Dynamische distanzminimierungsprobleme mit variablem schwierigkeitsgrad für multikriterielle optimierung. Master’s thesis, Otto von Guericke University, 2017.Search in Google Scholar
11. H. Masuda, Y. Nojima and H. Ishibuchi. Visual examination of the behavior of emo algorithms for many-objective optimization with many decision variables. In IEEE Congress on Evolutionary Computation, pages 2633–2640, 2014.10.1109/CEC.2014.6900642Search in Google Scholar
12. Antonio J Nebro, JJ Durillo, Jose Garcia-Nieto, CA Coello Coello, Francisco Luna and Enrique Alba. SMPSO: A new PSO-based metaheuristic for multi-objective optimization. In IEEE symposium on Computational intelligence in multi-criteria decision-making, pages 66–73, 2009.10.1109/MCDM.2009.4938830Search in Google Scholar
13. J.I.U. Rubrico, J. Ota, T. Higashi and H. Tamura. Metaheuristic scheduling of multiple picking agents for warehouse management. Industrial Robot: the international journal of robotics research and application, 35(1):58–68, 2008.10.1108/01439910810843298Search in Google Scholar
14. Oliver Schütze, Adriana Lara and Carlos A Coello Coello. On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Trans. on Evolutionary Computation, 15(4):444–455, 2011.10.1109/TEVC.2010.2064321Search in Google Scholar
15. Qingfu Zhang and Hui Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712–731, 2007.10.1109/TEVC.2007.892759Search in Google Scholar
16. H. Zille, A. Kottenhahn and S. Mostaghim. Dynamic distance minimization problems for dynamic multi-objective optimization. In IEEE Congress on Evolutionary Computation, pages 952–959, 2017.10.1109/CEC.2017.7969411Search in Google Scholar
17. H. Zille and S. Mostaghim. Properties of scalable distance minimization problems using the manhattan metric. In IEEE Congress on Evolutionary Computation, pages 2875–2882, 2015.10.1109/CEC.2015.7257246Search in Google Scholar
18. H. Zille and S. Mostaghim. Using ϵ-dominance for hidden and degenerated pareto-fronts. In IEEE Symposium Series on Computational Intelligence, pages 845–852, 2015.10.1109/SSCI.2015.125Search in Google Scholar
© 2018 Walter de Gruyter GmbH, Berlin/Boston