Metaheuristics - What and Why?
Assalaamu ‘alaikum and welcome to the year 2024, everyone!
Bismillah.
Today’s topic. Metaheuristics.
If we dissect the word further, there are two independent words that we can find; “meta” and “heuristic”. Okay. Did you guess that it came from either Latin or Greek? Well, you guessed right!
“Meta” in Greek means “among”, “with”, or “after”. According to Merriam-Webster:
Hence, when you take the term “physics” and apply the “meta-” prefix to form “metaphysics”, it simply refers to a discipline beyond those topics covered under physics. Physics, by nature, is empirical and studies everything about the universe through science. Meanwhile, metaphysics is not a scientific branch. Although its realm is also about the universe, the approach is philosophical.
Similarly, if you have the word “human” and prefix it with “meta-”, then it simply means a human with capabilities beyond a normal human being. Metahuman. X-men, Superman, and the likes.
“Heuristic”, on the other hand, means “to discover” in ancient Greek. According to Wikipedia, “heuristic” in its technical sense refers to:
That is, subhaanallah, very powerful - and there is none other who is more powerful than The One Who Created us in the first place.
Often in life, we find circumstances that require our instant resolve. A quick but good enough solution to a problem. For example, if a man was walking along the pedestrian walkway only to come in view of a rogue vehicle that was about to hit him, what would he do as a sane human being? He would have attempted to move away from the vehicle, wouldn’t he? Absolutely! Whether that “move away” was to the right, left, or back, he would have to do something to either prevent or cause more harm to himself. That quick judgment may not have been a perfect one, but at least the goal of saving his life would have been met. It did not cost him any time for deep thinking. If he did, he would have died instantaneously.
Now, that’s heuristic.
A Grab or taxi driver being able to short-path-traverse to a destination using his “gut feeling” despite Waze’s or Google Map’s route suggestions. Heuristic.
Captain Chesley Sullenberger’s attempt to save all the passengers and crews on board his plane; whether to return back to LaGuardia or land into the Hudson river. Heuristic. He landed the plane into the river and all onboard survived.
What then, is Metaheuristic?
It is a discipline that still involves heuristics for sure. Like heuristics, metaheuristics is also concerned about resolving a problem. However, there is a subtle difference between the two. While heuristic is all about solving a problem faster through the use of something as simple as a rule of thumb (or whatever rules or guidelines thereof), metaheuristics attempt to solve a problem by finding, generating, or selecting a heuristic that provides an optimal solution to the problem at hand.
Let us take the example of Captain Sully’s (Chesley Sullenberg) plane landing decision again to make things clear. Using simple heuristic (that is, “if the tower rises in your windshield, you won’t make it”), Captain Sully was able to save all those on board the plane. What if, during that decision making, he had another heuristic, another golden rule that he may have acquired after flying planes for years - something that he got through experiences, for example. Now he would have more than one heuristics. After weighing in the two, the second heuristic could have provided a more optimal solution that could save not just the passengers and crew, but also the integral structure of the plane after landing. Hence, the process of selecting for the optimal solution amongst a number of heuristic approaches is what we call metaheuristic (well, at least it fits one definition of it).
A more formal and perhaps exhaustive definition can be found here - that metaheuristic is simply:
Why Metaheuristics?
The key to understanding why one would be motivated to use metaheuristics is to understand the fact that time and resources are often scarce. Even for computers, no matter how sophisticated and advanced, there is always a limit at which it can compute a problem. If we were given a problem, and all its possible outcomes/solutions are finite - how do we choose which one would provide the best outcome?
Do we go through all of them one by one?
Well, we could go through each one of them. If it was just outcomes/solutions in total of 5 or 10, we could probably go through all of them and evaluate which one provides the best outcome (reaches our problem objectives).
However, if we take the Travelling Salesman Problem (TSP) as an example, we would probably have hundreds and thousands and even millions of outcomes depending on the size of the problem. TSP is a classical problem example where a salesman needs to traverse from one city to all adjacent cities just once until he returns to the one where he started from. Given that he needs to choose the shortest path, how would one maneauver through all of the possible outcomes within a reasonable amount of time?
You got it - metaheuristic, but how?
One example of a metaheuristic algorithm used to solve TSP is the Ant Colony Optimization (ACO) algorithm. This algorithm is inspired by the behavior of ants in the real world, where ants lay down pheromones to communicate with each other and create paths to food sources.
In ACO, a set of artificial ants is placed on the graph representing the TSP. Each ant constructs a solution by selecting the next city to visit based on the pheromone levels of the previous cities. As the ants move through the graph, they lay down pheromones on the edges they traverse. The pheromone trail deposited by successful ants intensifies, making it more likely for subsequent ants to follow the same path.
The ACO algorithm repeats this process many times, and over time, the pheromone trail directs the ants towards an increasingly optimal solution. Eventually, the algorithm converges to the best solution.
Other metaheuristic algorithms, such as Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS), can also be used to solve TSP by iteratively searching the solution space to find the optimal solution.
In summary, metaheuristic algorithms work by iteratively modifying the candidate solution, evaluating the quality of the new solution, and making a decision based on the quality of the new solution to find the optimal solution to a problem such as TSP.
