Algorithms and Heuristics, Some things you should know
Algorithm: Word used by programmers when… They do not want to explain what they did.
You might find the joke above of poor taste but I have come to realize that there is a disconcerting truth to it. I will tell you the story of a problem. One very much like a problem you might face on a Monday morning, as you come into your office ready for the week.
It goes like this: Your boss calls you into his office, and tells you of this problem that your company(and you) have in your production facility. You (and your company) would like to optimize throughput across the factory, by reducing the amount of time your “next-gen” automated soldering arms spend… well soldering. The idea:
Given a set of points the soldering arm has to visit, write a program that will come up with a path that minimizes the amount of time spent traveling between these points.
What is an algorithm?
It is a recipe to solve a problem. It is a set of instructions describing what to perform to come up with the solution to the problem.
That program your boss wants you to write? It implements the algorithm. An algorithm can be written and expressed in many different languages. Beyond the syntax of your programming language of choice, the ideas and instructions that make up the algorithm are still there. The algorithm is language agnostic.
As a good engineer, you sit with a piece of paper, prompting yourself to come up with a possible recipe. This algorithm… what could it be? One idea would be to start at some point, solder it then visit the nearest point and solder there. Then find the nearest point from that new position, solder it, and so on…
Not bad! It seems you have things under control… or so it appears.
What makes a good algorithm?
So far, what you have is an algorithm, and it is also based on a heuristic, which, in this case, might not even be a good one.
Before we look at the definition of a heuristic: There are usually many ways (or algorithms) to solve a problem. A good algorithm, however, is a little bit of a different beast.
A good algorithm must be correct, efficient, and easy to implement.
Correct
If there is one thing to remember from this post, let it be this: You might very well be able to come up with an algorithm. One that solves the problem for the current input, or possible inputs you might think of. It doesn’t make it correct.
Correctness must be shown. It must be proved and demonstrated. We will come back to this in a bit. It can be scary to realize that usually, in the industry, a program that is right in most cases and does not slow down the application is regarded as acceptable. Even if a better solution for the same problem exists. It is only after it causes major issues (legal, performance,…), that the qualities listed above are revisited and enforced.
“Obviousness” is your enemy when it comes to “correctness”. Be wary of an algorithm that you want to say is obviously correct.
Back to our not-so-hypothetical problem. The image above shows a case where the algorithm is on-point! But… what if the first point was not the most left?
As can be seen, in the examples above, our algorithm doesn’t do a very good job all the time. You might interject and say: “Wait, all our problems come from the fact that the starting point is random. Let’s put a constraint that it always starts on the most left point.” Good point (pun intended), I had a similar thought. But then…
So that’s it. This “nearest-neighbor” algorithm doesn’t cut it. Here again, you might say: “Except in very particular cases, the algorithm does a pretty good job… overall”. And I tend to agree. In the industry, this approach would be acceptable. It would be refined and made a little bit more robust, then pushed to production…
Until someone decides to make a product out of your code and state: “Guaranteed to always find the best path”. But that’s another story and another problem.
In summary, what we have here is an algorithm, albeit an incorrect one. It follows a heuristic.
A heuristic usually does a good job at coming up with a solution. A good heuristic for the problem at hand, will get you as close as possible to the best solution.
It does not offer any guarantees that its solution is the best or how far from this best solution it is. It will be content with making an informed, educated guess about what that best solution could be.
In short, it is not a correct algorithm, but it is one that in practice will give good enough results.
Efficient
Efficiency refers to the time and space complexity of an algorithm
This problem is actually famous. One for which there is no efficient, correct solution. It is known as the “Traveling Salesman Problem”.
As a matter of fact, to solve this correctly, you need to explore all possible paths and compute their lengths, then pick the shortest path, i.e the best solution. For a problem with 10 points, there are 10! possibilities. And problems with O(N!) time complexity are some of the worst to brute-force your way to a solution.
So, in practice, everybody would be happy to settle for a good heuristic. Yes, not all heuristics are created equal.
Easy to Implement
Good algorithms are correct, efficient, and easy to implement.
If, by some miracle, another algorithm of your creation could solve correctly and efficiently this well-known intractable problem but required tons of lines of code, hundreds of files… Let’s just say, it might not be worth it… depending on the case at hand.
Heuristics. What are they?
Let’s say, for some obscure reason, you were placed in unknown territory and asked to find the highest point of the land. Let’s also say that, for even more obscure reasons, you had to do it… blindfolded!
If you had all the time in the world, you could devise a way to map the land, exhaustively exploring each of its square meters. In the end, the map would tell you where that highest point would be.
If you didn’t have all that time, you would be content with finding a good enough solution as fast as possible. That could entail, identifying the direction with the highest slope from where you are initially, then moving in that direction. You would rinse and repeat until you got to a maximum.
Now, nothing tells you that you are at the highest point. But this solution is definitely better than where you started. You could even make the argument that given the resources at your disposal and constraints you were subjected to, this is good enough.
That is a heuristic and a prime example of why they are important. It’s these shortcut we find to problems when finding the best, correct solution seems too difficult.
The literature identifies 5 main instances where using heuristics appears to make sense to humans:
- When one is faced with too much information: Here exhaustively searching for the best solution is just not practical.
- When one is faced with very little information to make a decision: You are required to make a decision but you know nothing of the problem space or the consequences of your decision. One is forced to rely on previous experiences, rule of thumbs,… and hope for the best
- When the time allowed before making a decision is limited: Here also, exhaustively searching for the best solution is just not practical.
- When finding a good enough solution is… good enough: Maybe your application does not need to solve the equation and get to “π” as the answer. Your heuristic leads you to “3.14” and you are happy.
- When the appropriate heuristic happens to come to mind as one is looking for a solution.
More formally, computer scientists use heuristics when trying to solve hard problems. Those are problems whose solutions run in super-polynomial time. In essence, it takes a long time to find the solution for those problems.
The “Traveling Salesman Problem” is one of these problems. Finding the best solution for 4 points is near-instantaneous, finding the solution for 11 points can take 5 seconds, for 50 points it will take… forever — Well, not actually forever, but an insane amount of time. It’s bigger than anything we can conceive. In such cases, a good enough answer now within a few seconds is better than none for millenniums while the algorithm is bravely “wrestling” with this.
A Heuristic is a problem solving framework rather than an algorithm to find a solution.
The Heuristic guides an algorithm in finding good choices. So, it does not need to exhaustively search the problem space for the best solution. It is a sacrifice of correctness and accuracy for efficiency.
Some heuristic can be quite advanced and integrate past experiences, learning from them or using them to predict policies for “better moves”. They are generally opinionated about where to go next in order to converge toward better solutions. They might use deterministic and stochastic components. Many of them are cleverly constructed to use landscape information and history for better selections.
It is important to stress the fact that heuristics make assumptions. Therefore, the quality of solutions obtained with a heuristic will considerably depend on how much the problem you are trying to solve matches these assumptions. For example, there are instances where greedy algorithms will actually give you the exact, correct solution to a problem. For others ones, they can lead to bad, suboptimal solutions (Typically, it’s the problem of local vs global optimums)
Some heuristics in the wild
One way to come up with a heuristic is to consider how a human would tackle that problem. Humans do not always research all possible solutions before coming up with the best one. They do not like to waste unnecessary efforts and are pretty good at coming up with shortcuts that give good enough solutions.
Some heuristics in real life include:
- Working Backward: When trying to derive a solution from the input is too difficult, one can try constructing a solution by starting from what the output should be and working backward.
- Solve a bigger problem, by solving its smaller parts: Combining the solution of the smaller problems is believed to bring a solution to the bigger one.
Some heuristics in computer science:
- Greedy Algorithms: These algorithms believe that making the best decisions now, to maximize some immediate reward, will lead to an overall solution that shadows the best solution.
- Local Search Methods: The algorithm will choose a somewhat arbitrary initial solution. It will then iteratively make some tweaks to it, thereby incrementally increasing the quality of the resulting solution.
- Genetic Algorithms: These are quite fascinating. They believe that principles from the Darwinian Theory of Evolution can be adopted by an algorithm. These will enable it to converge toward an approximation of the best solution. An initial generation of possible candidate solutions is generated and evaluated. The finest candidates are “reproduced” with small stochastic variations to mimic the “survival of the fittest”. This new generation is once again evaluated, and its best candidates reproduced. The process is repeated until the resulting solutions satisfy some criteria.
- Tabu Search Algorithms: As the algorithm works, it will dynamically partition the problem space into areas that are marked as “tabu”. These are areas that have already been processed or are believed to lead to bad solutions. The algorithm is then incentivized to look for solutions away from these “tabu” regions. These “tabu” regions will expand while the area that is believed to contain the solution shrinks around it.
- Simulated Annealing Algorithms: Here the algorithm will mimic the annealing process in metallurgy. It consists of cycles of controlled heating and cooling on a material to increase the size of its crystals and reduce their defects. In essence, a solution is chosen, then modified with a non-deterministic component (i.e “heating up” the system). This non-deterministic component causes lesser and lesser effects as the “temperature” goes down. This modification scheme generates multiple possible solutions. The first one that meets some criterion is chosen for the next cycle. The “temperature” of the system is then decreased. This, therefore, constrains future solutions to smaller and smaller regions around current solutions. And the cycle is repeated.
That’s it for me. I hope you enjoyed it. Leave a comment if you feel like it. I’m always happy to engage with the community.
From a fellow problem solver.
