Evolutionary Algorithms (EAs)
Evolutionary Algorithms (EAs) are population-based metaheuristics.
Posts
Measuring the Runtime of (Optimization) Algorithms
My research area is metaheuristic optimization, i.e., algorithms that can find good approximate solutions for computationally hard problems in feasible time. The Traveling Salesperson Problem (TSP) is an example for such an optimization task. In a TSP, $n$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is $\mathcal{NP}$-hard, meaning that any currently known algorithm for finding the exact / globally best solution for all possible TSP instances will need a time which grows exponentially with $n$ on the worst case instances. And this is unlikely to change. In other words, if a TSP instance has $n$ cities, then the worst-case runtime of any exact TSP solver is in ${\mathcal{O}}(2^n)$. Well, today we have algorithms that can exactly solve a wide range of problems with tens of thousands of nodes and approximate the solution of million-node problems with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.
Are Black-Box Global Search Methods, such as Metaheuristics like Evolutionary Algorithms, better than Local Search?
Sometimes, when discussing the benefits of Evolutionary Algorithms (EAs), their special variant Genetic Algorithms (GAs) with bit-string based search spaces, or other metaheuristic global search algorithms in general, statements like the following may be made:“If you use a huge population size with a large computational budget for both global search metaheuristics (with enough diversity) and local search metaheuristics, the global search approach will no doubt outperform the local search.” I cannot not really agree to this statement, in particular if it is applied to black box metaheuristics (those that make no use of the problem knowledge).
Why research in Computational Intelligence should be less nature-inspired.
The inspiration gleaned from observing nature has led to several important advances in the field of optimization. Still, it seems to me that a lot of work is mainly based on such inspiration alone. This might divert attention away from practical and algorithmic concerns. As a result, there is a growing number of specialized terminologies used in the field of Evolutionary Computation (EC) and Swarm Intelligence (SI), which I consider as a problem for clarity in research. With this article, I would like to formulate my thoughts with the hope to contribute to a fruitful debate.
Publications
- Thomas Weise (汤卫思), Yan JIANG (江炎), Qi QI (齐琪), and Weichen LIU (刘伟臣): A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem. International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13(3):1-18. Autumn 2019.
- Thomas Weise (汤卫思), Xiao-Feng WANG (王晓峰), Qi QI (齐琪), Bin LI (李斌), and Ke TANG (唐珂): Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
- 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 (JOGO) 66(3):511-534. November 2016.
- Yan JIANG (江炎), Thomas Weise (汤卫思), Jörg Lässig, Raymond Chiong, and Rukshan Athauda: Comparing a Hybrid Branch and Bound Algorithm with Evolutionary Computation Methods, Local Search and their Hybrids on the TSP. IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS'2014), part of the IEEE Symposium Series on Computational Intelligence (SSCI'2014), December 9-12, 2014, Orlando, FL, USA, pages 148-155. Los Alamitos, CA, USA: IEEE Computer Society Press.
- Thomas Weise (汤卫思), Raymond Chiong, Jörg Lässig, Ke TANG (唐珂), 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.
- Kai ZHANG, Thomas Weise (汤卫思), and Jinlong LI (李金龙): Fitness Level based Adaptive Operator Selection for Cutting Stock Problems with Contiguity. IEEE Congress on Evolutionary Computation (CEC'2014), part of the World Congress on Computational Intelligence (WCCI'2014), pages 2539-2546, July 6-11, 2014, Beijing, China. Los Alamitos, CA, USA: IEEE Computer Society Press.
- Thomas Weise (汤卫思), Mingxu WAN (万明绪), Ke TANG (唐珂), Pu WANG, Alexandre Devert, and Xin YAO (姚新): Frequency Fitness Assignment. IEEE Transactions on Evolutionary Computation (IEEE-TEVC) 18(2):226-243. April 2014.
- Raymond Chiong, Thomas Weise (汤卫思), and Zbigniew Michalewicz, editors, Variants of Evolutionary Algorithms for Real-World Applications. Berlin/Heidelberg, Germany: Springer-Verlag, 2012.
- Christian Blum, Raymond Chiong, Maurice Clerc, Kenneth Alan De Jong, Zbigniew Michalewicz, Ferrante Neri, and Thomas Weise (汤卫思): Evolutionary Optimization. Variants of Evolutionary Algorithms for Real-World Applications, chapter 1, pages 1-29. Berlin/Heidelberg, Germany: Springer-Verlag, 2012.
- Thomas Weise (汤卫思), Alexander Podlich, and Christian Gorldt: Solving Real-World Vehicle Routing Problems with Evolutionary Algorithms. Natural Intelligence for Scheduling, Planning and Packing Problems, chapter 2, pages 29-53, Studies in Computational Intelligence, volume 250. Berlin/Heidelberg: Springer-Verlag, October 2009.
- Thomas Weise (汤卫思) and Raymond Chiong: . Intelligent Systems for Automated Learning and Adaptation: Emerging Trends and Applications, chapter 6, pages 114-149. Hershey, PA, USA: Information Science Reference / IGI Global, September 2009.
- Thomas Weise (汤卫思), Alexander Podlich, Manfred Menze, and Christian Gorldt: Optimierte Güterverkehrsplanung mit Evolutionären Algorithmen. Industrie Management — Zeitschrift für industrielle Geschäftsprozesse 10(3):37-40. June 2009.
- Thomas Weise (汤卫思), Alexander Podlich, Kai Reinhard, Christian Gorldt, and Kurt Geihs: Evolutionary Freight Transportation Planning. Applications of Evolutionary Computing — Proceedings of EvoWorkshops'2009, April 15-17, 2009, Tübingen, Germany: Eberhard-Karls-Universität Tübingen, Lecture Notes in Computer Science (LNCS), volume 5484/2009, pages 768-777. Berlin, Germany: Springer-Verlag GmbH.
- Alexander Podlich, Thomas Weise (汤卫思), Manfred Menze, and Christian Gorldt: Intelligente Wechselbrückensteuerung für die Logistik von Morgen. Workshops der Wissenschaftlichen Konferenz Kommunikation in Verteilten Systemen (WowKiVS'2009), March 6, 2009, Kassel, Hesse, Germany. In Electronic Communications of the EASST (ECEASST), volume 17, Potsdam, Germany: European Association of Software Science and Technology.