How nature inspires us to solve problems? An introduction to metaheuristics

In this blog post, I’d like you to present computational problem-solving techniques, called metaheuristics. We use some of them at LogicAI, but I’d like to focus on a general overview. My aim is to keep things as concise and non-technical as possible and focus on concepts and business applications. If you are interested in use-cases and high-level ideas of such techniques, you’re in the right place
Blog
Machine learning

Table of Contents

Did you ever hear about heuristics? It probably rings a bell, but what exactly are they? To put it in simple terms, a heuristic is some form of shortcut – a technique designed to solve an optimization problem in a quick yet effective way. It aims to find “good enough solution” to such a problem, especially when finding the exact solution is too hard or time-consuming, by trading accuracy, completeness, optimality for speed.

Note that I’m using the definition of heuristic coming from computer science – different fields (e.g. cognitive science or psychology) may define it slightly differently, although the high-level concept of a heuristic as some form of “shortcut” in general remains the same, nevertheless the discipline.

But this post is about metaheuristics, right? They’re higher-level heuristics (or procedures in general) designed to find the “right” heuristic – the one which provides the sufficiently good solution I already mentioned.

Many metaheuristics use some form of stochastic optimization, hence that the solution found is dependent on the set of generated random variables. They search over a large set of feasible solutions, so they can often find sufficient solutions with less computational effort than traditional optimization algorithms, iterative methods, or simple heuristics. Because of this, they are useful approaches for optimization problems. They have a major downside, though – compared to “regular” optimization algorithms and iterative methods, metaheuristics may not find a globally optimal solution on some classes of problems.

There are plenty of metaheuristics and many ways to classify them. For example, we can group them due to the type of optimum that is searched for:

  • local search metaheuristics –  focus on improvement on simple local search algorithms.
  • global search metaheuristics –  try to overcome the limitations of local search and utilization of population-based methods.

We can also classify metaheuristics by a number of solutions they’re trying to improve:

  • single-solution approach –  focuses on modifying and improving a single candidate solution.
  • population-based approaches – aims to improve multiple candidate solutions, usually utilizing population characteristics to do so.

Having said that, there are many classes of problems where metaheuristics can be useful. I’d like to present some of them to you – I aim to give you some examples of such heuristics, a good intuition about how they work and last but not least, what class of business problems they can help you solve. Metaheuristics are a vast topic – to keep things concise I will focus on three of them – particle swarm optimization, ant colony optimization, and simulated annealing.

Particle swarm optimization

Remember the distinction between single-solution and population-based metaheuristics? Particle swarm optimization, or PSO in short, is one that focuses on populations. It aims to solve an optimization problem by moving the population of candidate solutions, in this scenario called “particles”, around in the search space. It’s performed according to predefined mathematical formulae over the particle’s position and velocity. Like many metaheuristics, it’s inspired by natural phenomena – in this case, bird flocking or fish schooling (birds and fish are our “particles”). It’s a population-based algorithm, which tries to implement some form of “swarm intelligence” to find the solution. To give you a little more insight, imagine that a group of birds is randomly searching for food in an area.

  • There is only one piece of food in the area being searched.
  • All the birds do not know where the food is.
  • But they know how far the food is in each iteration.

To ensure the survival of the flock, the birds have to find food. So what strategy should they choose? The effective one is to follow the bird which is nearest to the food. Particle swarm optimization tries to implement such a mechanism using math. It has some convenient mathematical properties which make this method a good choice for optimization problems where “classic” optimization algorithms can’t be used (PSO does not require that the optimization problem be differentiable in contrast to the family of gradient descent methods).

 

Having this high-level overview of PSO, let’s go through some examples of business applications:

  • Energy/power industry – optimization of generators’ output in a grid, to minimize fuel costs,
  • Heating – minimization of the cost of heating system in a given life cycle time,
  • Water supply – optimization of the water distribution network to avoid water shortage and minimize the cost of the supply.

Ant colony optimization

Many computational problems rely on finding the shortest (or at least “good”) path. You may have heard about some of them, like traveling salesman problem: given a list of locations and the distances between each pair of them, what is the shortest possible route that visits each location and returns to the place of the start? Ant colony optimization is a family of algorithms designed to solve this kind of problem. Like in our former example, it’s inspired by nature – in this case, pheromone-based communication between ants, seeking the best route between their colony and a source of food. Real ants lay down pheromones directing each other to resources while exploring their environment. The algorithm model optimization problem as the actions of such an ant colony.

Artificial ‘ants’ are in such case mathematical abstractions trying to locate the optimal solutions by moving through parameter space, which represents all possible solutions (e.g. locations, like in the traveling salesman problem). Some species of real ants initially wander randomly, but when they encounter a pheromone trail left by other ants from the colony, they modify their path accordingly and leave another pheromone trail for the rest of the ants and the cycle begins again. Ant colony optimization algorithms try to mimic that behavior to iteratively find the best possible route.

So what are the real-world applications of such algorithms? In general – any problem which requires finding optimal paths. Examples include:

  • Scheduling – algorithms from this family were successfully applied to scheduling problems, such as job scheduling in an aluminum foundry or bus driver scheduling,
  • Space planning – planning alleys and shelves organization to ensure optimal routes of shoppers in supermarkets,
  • Market and business intelligence – there are some use cases in real-time fraud detection as a more “straightforward” alternative to traditional classification algorithms.

Simulated annealing

Let’s leave the animal kingdom for a while. Simulated annealing takes its inspiration from something else – annealing process in metallurgy. In the real world, it involves repetitive heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Simulated annealing tries to translate this into a probabilistic algorithm. Slow cooling from “real-world” annealing is interpreted in the algorithm as a slow decrease in the probability of accepting worse solutions as possible solutions are explored. As I mentioned at the beginning this trade-off is an essential property of metaheuristics in general – accepting worse solutions allows for a more extensive search for the global optimal solution. In short, we sacrifice some local fidelity in favor of better global results. The general mechanism goes as follows:

  • At each time step, the algorithm randomly selects a solution close to the current one and measures its quality.
  • Having such information, it decides to move to that selected solution or to stay with the current one, based on the assessed probability that the new solution is better or worse than the current one.
  • As the algorithm is searching through possible solutions, the initial temperature is progressively decreased to zero
  • That affects the two probabilities – the probability of moving to a better candidate solution is either kept to 1 or is changed towards a positive value; in contrast, the probability of moving to a worse new solution is iteratively changed towards zero

That’s simulated annealing in a nutshell. It has a wide range of applications in optimization involving a large number of variables or parameters:

  • Scheduling – especially in cases of schedules depending on a large number of factors and other schedules
  • Route finding – similarly to an ant colony, simulated annealing was successfully applied in finding the optimal path between two locations
  • Industrial production – optimization of work of various devices, to minimize malfunctions, fuel usage, etc.
  • Heat / Energy – optimization of heat and energy flow in residential buildings

 

So this is basically it – now you have some high-level overview of metaheuristics with some examples of algorithms and their applications. In the next post, you’ll find a complete business case, solved with one of them. Stay tuned!

If you are interested in applying metaheuristics to your business problems, let us know – we’re glad to help.

Contact me to get answers to your questions: greg@logicai.io

Topics:

CTO / Data Scientist / Kaggle Grandmaster

CTO / Data Scientist / Kaggle Grandmaster

Other stories in category

BlogKaggle Days
4 – Nature never goes out of style!

4 – Nature never goes out of style!

4 – Nature never goes out of ...

Five continents, twelve events, one grand finale, and a community of more than 10 million - that's Kaggle Days, a nonprofit event for data science enthusiasts and Kagglers. Beginning in November 2021, hundreds of participants attending each meetup face a daunting task to be on the podium and win one of three invitations to the finals in Barcelona and prizes from Kaggle Days and Z by HPZ by HP.

Paras Varshney

16 Aug 2022

BlogKaggle Days
3 – Now you are playing with power

3 – Now you are playing with power

3 – Now you are playing with ...

"It was amazing," commented attendees of the third Kaggle Days X Z by HP World Championship meetup, and we fully agree. The Moscow event brought together as many as 280 data science enthusiasts in one place to take on the challenge and compete for three spots in the grand finale of Kaggle Days in Barcelona. Of course, we already know the winning teams that best handled the contest task. In addition to the excitement of the competition, in Moscow were also inspiring lectures, speeches, and fascinating presentations of modern equipment. As always, at Kaggle Days, a lot was going on.

Paras Varshney

16 Aug 2022

BlogKaggle Days
2 – Water Water everywhere, not a drop to drink

2 – Water Water everywhere, not a drop to drink

2 – Water Water everywhere, n...

"Happy to be part of shaping the future." "It's the Way of The Future." That is how the participants summed up another meetup organized as part of Kaggle Days, a non-profit event for data science enthusiasts who want to grow and compete for prizes under the watchful eye of top Kaggle mentors and grandmasters. The second meetup in New Delhi is behind us. Three hundred participants, more than one hundred teams, and only three invitations to the finals in Barcelona mean that the excitement could not be lacking.

Paras Varshney

16 Aug 2022