Global Optimization Strategies: Analogies to Human Behavior

CIplus Band 2/2018 Global Optimization Strategies: Analogies to Human Behavior Jörg Stork and Thomas Bartz-Beielstein Global Optimization Strategies: Analogies to Human Behavior Jörg Stork Thomas Bartz-Beielstein June 25, 2018 Optimization algorithms [9] are present everywhere in our daily live. Without even noticing them, they ensure that our orders arrive on time, our phones have the best connection and products have a certain quality. If we walked through a modern company, we would notice that nearly every production process was optimized and every machine was developed with help of mathematical optimization. During the last decades, several new design schemes for optimization algorithms were developed and new algorithms are proposed every day. Particular two groups of algorithms are in the focus of current research. First, the so-called metaheuristics, which are capable of solving a large variety of optimization problems with stochastic strategies without much knowledge about the problem to solve [2]. Second, model-based and especially surrogate-assisted optimization algorithms, which dominate the field of costly real-world applications and have become the state-of-the-art for this task in efficient algorithm design [1]. Similar to many modern technical developments, many of these algorithms are nature-inspired [6]. For example, these search strategies have analogies with the behavior of animals. To give an overview of the different available optimization methods, we want to use a similar approach and classify them based on the natural human behavior in path finding. To establish such a comprehensive taxonomy, we focus on identifying key elements of algorithm design and utilize these to define a clear separation between a small number of algorithm classes. In contrast to other work, by these means we will keep the level of detail on an abstract, but still valuable level. This abstraction level allows us to present simply comprehensible ideas on how the individual classes differ and moreover, how the respective algorithms perform their searches. For this purpose, we divide optimization algorithms into intuitive classes: Wanderer, Guide, Cartographer. The Wanderer The intuitive description of a wanderer is a single (human) individual who wanders through the landscape to find the most attractive place in the neighborhood. By these means he only utilizes local information about his 1 current position to find the best direction. So if the goal of this individual is to find the highest mountain, he will likely follow the ascending way, because he directly satisfies the current objective. Furthermore, he does not utilize gathered information, so that there is a chance that he will revisit the same place. This class resembles classical stochastic and gradient-based hill climbing strategies [8, 5], which vary a single candidate solution until a better or the best possible solution (the global optimum) is found. The selection of a classical hill climber is greedy, which means that only improving steps are accepted. The search strategy is able to solve convex problems with a single optimum very fast and efficient, but is not suitable for problems with many optima. The Guide To give an intuitive idea, a human hiker looking for an interesting place would try to memorize her own path, follow travel signs about interesting or forbidden search regions or ask other people to share their knowledge and give directions. Furthermore she will pass on her own gained knowledge about the landscape to other people if asked. Algorithms from the guide class use several simultaneous candidate solutions spread over the search space and thus have good exploration abilities. Evolutionary algorithms [3, 7] are the outstanding example for this class. They further combine the information of gathered solutions to create new candidates. These search strategies are able to solve complex, multi-modal problems. The Cartographer The intuitive idea is a human-like specialist who systematically measures a landscape by taking samples of the height to create a topological map, which resembles the real landscape. This map will be exact at the sampled locations and approximates the remaining landscapes by regression. It can then be examined and utilized by any other individual to find a desired location. One could think of a guide or wanderer using a paper map or digital navigation system to find the highest mountain. This algorithm class uses data-driven models of all gathered solutions. They are used to intelligently search the space by putting candidate solutions in very promising areas or those where no information is gathered yet [4, 1]. Because of the complexity of the models and their larger computation time, these algorithms are best for very complex and expensive optimization problems, where solutions have to be found in a couple of iterations. Benefits of this taxonomy can be described as follows: No up to date taxonomy is dealing with surrogate-assisted optimization in the larger scope of continuous 2 global optimization [10, 9]. This new taxonomy for optimization algorithms based on the visual idea of moving individuals fills this gap. It is based on selected design aspects of a continuous optimization algorithm. They are the use of information,candidate evaluation, the type of individual,search space and additionally the characteristics of the manageable problems. Utilizing these features, we derive a set of comprehensible algorithm classes. In general, it is beneficial for each user to identify if an optimization algorithm is suitable for their problem before applying them. This approach supports users in their selection of an adequate algorithm. References [1] Bartz-Beielstein, T., Lasarczyk, C.W., Preuß, M.: Sequential parameter optimization. In: Evolutionary Computation, 2005. The 2005 IEEE Congress on, vol. 1, pp. 773–780. IEEE (2005) [2] Boussaïd, I., Lepagnot, J., Siarry, P.: A survey on optimization metaheuristics. Information Sciences 237, 82–117 (2013) [3] Eiben, A.E., Smith, J.E.: Introduction to evolutionary computing, vol. 53. Springer (2003) [4] Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. Journal of Global optimization 13(4), 455– 492 (1998) [5] Michalewicz, Z., Fogel, D.B.: How to solve it: modern heuristics. Springer Science & Business Media (2013) [6] Rozenberg, G., Bck, T., Kok, J.N.: Handbook of natural computing. Springer Publishing Company, Incorporated (2011) [7] Schwefel, H.P.P.: Evolution and optimum seeking: the sixth generation. John Wiley & Sons, Inc. (1993) [8] Shanno, D.F.: Conditioning of quasi-newton methods for function minimization. Mathematics of computation 24(111), 647–656 (1970) [9] Törn, A., Zilinskas, A.: Global Optimization. Springer (1989) [10] Zlochin, M., Birattari, M., Meuleau, N., Dorigo, M.: Model-based search for combinatorial optimization: A critical survey. Annals of Operations Research 131(1-4), 373–395 (2004) 3 Kontakt/Impressum Diese Veröffentlichungen erscheinen im Rahmen der Schriftenreihe "CIplus". Alle Veröffentlichungen dieser Reihe können unter https://cos.bibl.th-koeln.de/home abgerufen werden. Die Verantwortung für den Inhalt dieser Veröffentlichung liegt beim Autor. Datum der Veröffentlichung: 02.07.2018 Herausgeber / Editorship Prof. Dr. Thomas Bartz-Beielstein, Prof. Dr. Wolfgang Konen, Prof. Dr. Boris Naujoks, Prof. Dr. Horst Stenzel Institute of Computer Science, Faculty of Computer Science and Engineering Science, TH Köln, Steinmüllerallee 1, 51643 Gummersbach url: www.ciplus-research.de Schriftleitung und Ansprechpartner/ Contact editor’s office Prof. Dr. Thomas Bartz-Beielstein, Institute of Computer Science, Faculty of Computer Science and Engineering Science, TH Köln, Steinmüllerallee 1, 51643 Gummersbach phone: +49 2261 8196 6391 url: http://www.spotseven.de eMail: [email protected] ISSN (online) 2194-2870