Metaheuristics
Metaheuristics are general optimization procedures that can be applied to a wide variety of problems. They are not problem-specific and often have a rather simple structure, a loop of sampling and selection as given in Algorithm 1. At each iteration $i$, they maintain a collection $S_i$ of interesting candidate solutions $x\in S_i$ from the solution space $\mathbb{X}$. They use these selected solutions in one way or another to sample a collection $N_i$ of new solutions. This may happen via a unary search operator, a binary operator, by updating some statistical model and then sampling the model, or by using any other imaginable method. Either way, we get a collection of new solutions $N_i$. Then, $S_i$ and $N_i$ are combined into a collection $P_i=S_i\cup N_i$ and the collection $S_{i+1}\subseteq P_i$ for the next iteration is chosen from it. Normally, the better a solution $x\in P_i$ relative to the other members of $P_i$, meaning the smaller its corresponding objective value $f(x)$, the higher its chance to be selected into $S_{i+1}$. This is how trial-and-error works:
Sample collection $S_1$ of initial solutions from the solution space $\mathbb{X}$.
For $i$ from 1 to$\dots$
Create collection $N_i$ of new solutions based on $S_i$.
$P_i\gets S_i\cup N_i$.
Select collection $S_{i+1}$ from $P_i$ according to some policy.
Many different algorithms follow this pattern. The most common sub-fields are
- local search (including, e.g., RLS, SA, and Tabu Search)
- evolutionary computation methods (such as EAs, GAs, and MAs) and
- swarm intelligence methods (most prominently, ACO and PSO).
Posts
Guest Talk ‘Applied Operations Research in Driving Sustainability’ by Dr. Sina Abdipoor
On August 24th, our team welcomed Dr. Mr. Sina Abdipoor (سینا عبدیپور) to give the talk “Applied Operations Research in Driving Sustainability.” Dr. Abdipoor is a young and outstanding colleague from Sunway University, Malaysia who has a rich experience in Operations Research (OR), optimization, and local search for scheduling and other practical optimization tasks.
Space Optimization Competition of the European Space Agency
Recently, the fourth Space Optimization Competition (SpOC) organized by the Advanced Concepts Team of the European Space Agency (ESA) ended. It was held at the Genetic and Evolutionary Computation Conference (GECCO’2026) taking place from July 13 to 17, 2026 in San José, Costa Rica. The competition was about applying optimization algorithms to problems from space logistics and space Operations Research. It had three challenges,
Paper Accepted at GECCO: When Frequency Fitness Assignment Fails: Trapped States in Frequency-Guided Local Search
Our paper When Frequency Fitness Assignment Fails: Trapped States in Frequency-Guided Local Search has been accepted at the Genetic and Evolutionary Computation Conference (GECCO’2026) taking place from July 13 to 17, 2026 in San José, Costa Rica.
Frequency Fitness Assignment and Invariance Properties
Frequency Fitness Assignment (FFA, 频率适应度分配) is an “algorithm plugin” that fundamentally changes how the selection step in metaheuristics works. Recently, we discussed how FFA can be plugged into the simple local search algorithm RLS, yielding the FRLS. According to my claim above, the FRLS should work fundamentally different from the RLS. That’s a pretty bold claim. Let me substantiate it a bit.
Plugging Frequency Fitness Assignment into Metaheuristics
Frequency Fitness Assignment (FFA, 频率适应度分配) is a technique that fundamentally changes how (metaheuristic) optimization algorithms work. The goal of this post is to explore how this technique can be plugged into an existing algorithm. We first discuss optimization and the general pattern of metaheuristics in general. We then discuss the simplest local search algorithm – randomized local search, or RLS for short. We plug FFA into this algorithm and obtain the FRLS. We finally list some properties of FRLS as well as some related works.
Why you should use Evolutionary Algorithms to solve your optimization problems (and why not).
Some time ago, I discussed why global optimization with an Evolutionary Algorithm (EA) is not necessarily better than local search. Actually, I was asked “Why should I use an EA?” quite a few times. Thus, today, it is time to write down a few ideas about why and why not you may benefit from using an EA. I tried to be objective, which is not entirely easy since I work in that domain.
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).
What is optimization?
The center of my research is optimization. But what is optimization? Basically, optimization is the art of making good decisions. It provides us with a set of tools, mostly from the areas of computer science and mathematics, which are applicable in virtually all fields ranging from business, industry, biology, physics, medicine, data mining, engineering, to even art.
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
- Wei SHI (施玮) and Thomas Weise (汤卫思): An Initialized ACO for the VRPTW. 14th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'2013), October 20-23, 2013, Hefei, Anhui, China, Lecture Notes in Computer Science (LNCS), volume 8206/2013, pages 93–100. Berlin, Germany: Springer-Verlag GmbH.
- Thomas Weise (汤卫思), Alexandre Devert, and Ke TANG (唐珂): A Developmental Solution to (Dynamic) Capacitated Arc Routing Problems using Genetic Programming. 14th Genetic and Evolutionary Computation Conference (GECCO'2012), July 7-11, 2012, Philadelphia, PA, USA, pages 831–838. New York, NY, USA: ACM.
- Yu WANG, Bin LI (李斌), Thomas Weise (汤卫思), Jianyu WANG, Bo YUAN (袁博), and Qiongjie TIAN: Self-Adaptive Learning Based Particle Swarm Optimization. Information Sciences 181(20):4515-4538. October 2011.
- Thomas Weise (汤卫思), Stefan Niemczyk, Raymond Chiong, and Mingxu WAN (万明绪): A Framework for Multi-Model EDAs with Model Recombination. 4th European Event on Bio-Inspired Algorithms for Continuous Parameter Optimisation (EvoNUM'2011), part of Applications of Evolutionary Computation — Proceedings of EvoAPPLICATIONS 2011: EvoCOMPLEX, EvoGAMES, EvoIASP, EvoINTELLIGENCE, EvoNUM, and EvoSTOC, April 27-29, 2011, Torino, Italy, Part 1, Lecture Notes in Computer Science (LNCS), volume 6624, pages 304–313. Berlin, Germany: Springer-Verlag GmbH.
- Mingxu WAN (万明绪), Thomas Weise (汤卫思), and Ke TANG (唐珂): Novel Loop Structures and the Evolution of Mathematical Algorithms. 14th European Conference on Genetic Programming (EuroGP'2011), April 27-29, 2011, Torino, Italy, Lecture Notes in Computer Science (LNCS), volume 6621/2011, pages 49–60. Berlin, Germany: Springer-Verlag GmbH.
- Pu WANG, Thomas Weise (汤卫思), and Raymond Chiong: Novel Evolutionary Algorithms for Supervised Classification Problems: An Experimental Study. Evolutionary Intelligence 4(1):3–16. March 2011.
- Wenxiang CHEN (陈文祥), Thomas Weise (汤卫思), Zhenyu YANG (杨振宇), and Ke TANG (唐珂): Large-Scale Global Optimization Using Cooperative Coevolution with Variable Interaction Learning. 11th International Conference on Parallel Problem Solving from Nature (PPSN'2010), Part II, September 11-15, 2010, Kraków, Poland, Lecture Notes in Computer Science (LNCS), volume 6239, pages 300–309. Berlin, Germany: Springer-Verlag GmbH.
- Raymond Chiong, Thomas Weise (汤卫思), and Bee Theng Lau: Template Design using Extremal Optimization with Multiple Search Operators. International Conference on Soft Computing and Pattern Recognition (SoCPaR'2009), December 4-7, 2009, Malacca, Malaysia, pages 202–207. Piscataway, NJ, USA: IEEE.
- 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 (汤卫思) and Michael Zapf: Evolving Distributed Algorithms with Genetic Programming: Election. 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation (GEC'2009), June 12-14, 2009, Shanghai, China, pages 577–584. New York, NY, USA ACM Press.
- 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 (汤卫思): Evolving Distributed Algorithms with Genetic Programming. PhD Thesis published in May 2009 at the Department of Electrical Engineering and Computer Science (FB16) of the University of Kassel in Kassel, Germany.
- 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.
- Thomas Weise (汤卫思), Michael Zapf, Mohammad Ullah Khan, and Kurt Geihs: Combining Genetic Programming and Model-Driven Development. International Journal of Computational Intelligence and Applications (IJCIA), 8(1):37–52. March 2009.
- 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.
- Thomas Weise (汤卫思): Global Optimization Algorithms — Theory and Application. self-published, free e-book. 2009.
- Michael Zapf and Thomas Weise (汤卫思): Can Solutions Emerge? 3rd International Workshop on Self-Organizing Systems (IWSOS'2008), December 10-12, 2008, Vienna, Austria. Lecture Notes in Computer Science (LNCS), volume 5343/2008, pages 299–304. Berlin, Germany: Springer-Verlag GmbH.
- Michael Zapf and Thomas Weise (汤卫思): Applicability of Emergence Engineering to Distributed Systems Scenarios. 6th European Workshop on Multi-Agent Systems (EUMAS'2008), December 18-19, 2008, Bath, UK.
- Thomas Weise (汤卫思), Michael Zapf, and Kurt Geihs: Evolving Proactive Aggregation Protocols. 11th European Conference on Genetic Programming (EuroGP'2008), March 26-28, 2008, Naples, Italy, Lecture Notes in Computer Science (LNCS) volume 4971/2008, pages 254–265. Berlin, Germany: Springer-Verlag GmbH.
- Michael Zapf and Thomas Weise (汤卫思): Offline Emergence Engineering For Agent Societies. 5th European Workshop on Multi-Agent Systems (EUMAS'2007), December 14, 2007, Hammamet, Tunesia.
- Thomas Weise (汤卫思), Michael Zapf, and Kurt Geihs: Rule-based Genetic Programming. 2nd International Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS'2007), December 10-12, 2007, Budapest, Hungary, pages 8–15. Piscataway, NJ, USA: IEEE Computer Society.
- Thomas Weise (汤卫思), Michael Zapf, Mohammad Ullah Khan, and Kurt Geihs: Genetic Programming meets Model-Driven Development. 7th International Conference on Hybrid Intelligent Systems (HIS'2007), September 17-19, 2007, Kaiserslautern, Germany, pages 332–335. Piscataway, NJ, USA: IEEE Computer Society.
- Thomas Weise (汤卫思), Kurt Geihs, and Philipp Andreas Baer: Genetic Programming for Proactive Aggregation Protocols. 8th International Conference on Adaptive and Natural Computing Algorithms (ICANNGA'2007), April 11-17, 2007, Warsaw, Poland, Part I, Lecture Notes in Computer Science (LNCS), volume 4431/2007, pages 167–173. Berlin, Germany: Springer-Verlag GmbH.
- Thomas Weise (汤卫思) and Kurt Geihs: DGPF — An Adaptable Framework for Distributed Multi-Objective Search Algorithms Applied to the Genetic Programming of Sensor Networks. 2nd International Conference on Bioinspired Optimization Methods and their Applications (BIOMA'2006), October 9-10, 2006, Ljubljana, Slovenia, pages 157–166.
- Thomas Weise (汤卫思) and Kurt Geihs: Genetic Programming Techniques for Sensor Networks. Tagungsband: 5. GI/ITG KuVS Fachgesprächs “Drahtlose Sensornetze”, July 17-18, 2006, Stuttgart, Germany, pages 21–25.