Complexity, Heuristics, and Artificial Intelligence

Artificial Intelligence has truly come of age. From being confined in the labs for several decades, it has now emerged as the most sought-after field within the current computing and technology landscape. Over the years, several powerful models and algorithms have been introduced that have been inspired by a variety of natural and physical phenomena. However, despite their success overall, these AI-based algorithms have a limitation of not being able to guarantee an optimal solution to even marginally-complex problems. As optimality is not guaranteed, both natural as well as artificially-intelligent systems are constrained to work with sub-optimal outcomes. For us human, this is indeed a humbling observation since advanced research in AI has also highlighted the limits to our own natural intelligence in dealing with complexity.

Complexity is a topic which is introduced at an early stage in a typical computer science curriculum. An example of a relatively complex problem often discussed in the classrooms is the much-celebrated travelling salesman problem. For example, consider 5 cities numbered from 1 to 5 with known distances between each of them, the task is to start from city 1 and find the shortest tour of all the cities. For example, both 1->3->5->4->2 as well as 1->4->3->2->5 are considered valid tours that start from city 1 and go through all the cities.

It turns out that finding the optimal tour is not so trivial. The complexity of solving the travelling salesman problems is estimated by the number of tours and sub-tours that are required to be analysed before conclusively determining the optimal solution. The key challenge is that the number of tours that need to be analysed grow sharply as we increase the number of cities in the problem. As an example, for a 100-city problem, the approximate number of tours that are required to be evaluated comes to a mammoth 10³⁴.

For a complex problem such as a 100-city travelling salesman problem, one is tempted to deploy the latest and greatest hardware to achieve an optimal outcome. Hypothetically speaking, we could deploy the fastest supercomputer in the world today called the IBM Summit based in Oak Ridge National Laboratory in Tennessee, USA. This is a very impressive machine which takes up 5,600 square feet of floor space and achieves a performance of more than 100 petaflops, which could be estimated as 10¹⁷ floating-point operations per second.

If we simplistically assume that a floating-point operation is required to generate one (partial or complete) tour, then it would take Summit 10¹⁷ seconds to generate all paths to enable us to compute the optimum. Given that a year consists of approximately 10⁸ seconds, that implies it will take the Summit 10⁹ years to generate the optimal solution. In short, if we were to have deployed Summit to solve this problem about a billion years ago, by now, it would be about time for it to complete its calculations!

It is apparent that even the fastest of computers will be overwhelmed by complex problems such as the 100-city travelling salesman problem. Yet, it might come as a surprise to readers that problems of much higher magnitude are being routinely dealt by current AI algorithms which are deployed on machines which are much less powerful than the Summit. This seems so remarkable that we must wonder how do AI algorithms manage to achieve this impressive feat? The answer lies in the application of heuristics.

Heuristic is any information or knowledge that helps the algorithm explore areas that are most promising to find good solutions. For example, in the case of travelling salesman problem, we could use what is known as the nearest-neighbour heuristic. This simply means that we could formulate a short path by going to the distance-wise closest unvisited city from any given city. Although this could generate a good solution in a fraction of a time, this pruning of potential solutions comes at a cost of not being able to guarantee an optimal solution.

Hence, for complex problems, the application of heuristics offers a stark choice. Either wait till eternity to find the optimum solution despite using the fastest supercomputer, or, use heuristics and find good-enough solution in a reasonable amount of time and move on to do other things.

Since achieving optimality is not an option given the inadequacy of hardware, research on heuristics has become a central tenet of AI. The scope of AI research is increasingly geared to either develop an innovative new heuristic or improvise an existing heuristic to achieve better results. For example, the heuristics within the genetic algorithm are inspired by the natural process of evolution; deep learning is inspired from the human brain and built using a heuristic-based backpropagation algorithm; and the simulated annealing algorithm uses heuristics inspired from the heat treatment process in the field of metallurgy to introduce structural changes within metals.

The various AI algorithms perform differently from the type of problem being solved, however, despite producing good results, none of them guarantee optimality due to their reliance on heuristics.

The research in AI have highlighted the central role of heuristics in both artificial as well as natural intelligence. Up until a few decades ago, the basis of all economic theories and research was the assumption that human beings are rational agents that can make optimal decisions. Herbert Simon, a Nobel prize winning economist as well as one of the founding fathers of AI, turned this assumption over its head by highlighting that human rationality is bounded by several constraints such as time, information and cognitive capabilities. These constraints put a limit on our achieving optimality as we undertake a heuristic decision-making process that simultaneously attempts at resolving all constraints resulting in sub-optimal but good enough (satisficing) decisions.

Therefore, much like artificial intelligence, heuristics also play a central role in human intelligence and thereby puts a limit on our ability to achieve optimum.

If we believe that success in life is akin to achieving best possible outcomes, then we are in the need to seriously rejig our definition of success. AI research shows that no intelligent system can achieve optimality under all conditions. Perfection is a luxury that we can only avail if we have eternal time on our hands along with limitless resources. Since these are unrealistic prerequisites, it’s prudent for both artificial and naturally intelligent systems to rely on heuristics and live by the principle: the best is enemy of the good.

Published in The Express Tribune, May 16^th, 2019.

Like Opinion & Editorial on Facebook, follow @ETOpEd on Twitter to receive all updates on all our daily pieces.