How to Solve It: Modern Heuristics

This is not a book about algorithms. Certainly, it is full of algorithms, but that’s not what this book is about. This book is about possibilities. Its purpose is to present you not only with the prerequisite mandatory knowledge of the available problem-solving techniques, but more importantly to expand your ability to frame new problems and to think creatively — in essence, to solve the problem of how to solve problems, a talent that has become a lost art. Instead of devoting the necessary time and critical thinking required to frame a problem, to adjust our representation of the pieces of the puzzle, we have become complacent and simply reach for the most convenient subroutine, a magic pill to cure our ills. The trouble with magic is that, empirically, it has a very low success rate, and often relies on external devices such as mirrors and smoke. As with magic, most of the seemingly successful applications of problem solving in the real world are illusory, mere specters of what could have been achieved.

At the risk of starting with a tautology, real-world problems are difficult to solve, and they are difficult for several reasons:

Three basic concepts are common to every algorithmic approach to problem solving. Regardless of the technique that you employ, you’ll need to specify: (1) the representation, (2) the objective, and (3) the evaluation function. The representation encodes alternative candidate solutions for manipulation, the objective describes the purpose to be fulfilled, and the evaluation function returns a specific value that indicates the quality of any particular solution given the representation (or minimally, it allows for a comparison of the quality of two alternative solutions). Let’s consider each of these aspects of problem solving in turn.

There are many classic algorithms that are designed to search spaces for an optimum solution. In fact, there are so many algorithms that it’s natural to wonder why there’s such a plethora of choices. The sad answer is that none of these traditional methods is robust. Every time the problem changes you have to change the algorithm. This is one of the primary shortcomings of the well-established optimization techniques. There’s a method for every problem — the problem is that most people only know one method, or maybe a few. So they often get stuck using the wrong tool to attack their problems and consequently generate poor results.

We’ve seen a slew of techniques that manipulate complete solutions. Let’s now consider some of the algorithms that work with partial or incomplete solutions and solve problems by constructing solutions one piece at a time. We begin with the best-known category: greedy algorithms.

We’ve discussed a few traditional problem-solving strategies. Some of them guarantee finding the global solution, others don’t, but they all share a common pattern. Either they guarantee discovering the global solution, but are too expensive (i.e., too time consuming) for solving typical real-world problems, or else they have a tendency of “getting stuck” in local optima. Since there is almost no chance to speed up algorithms that guarantee finding the global solution, i.e., there is almost no chance of finding polynomial-time algorithms for most real problems (as they tend to be NP-hard), the other remaining option aims at designing algorithms that are capable of escaping local optima.

In the previous three chapters we discussed various classic problem-solving methods, including dynamic programming, branch and bound, and local search algorithms, as well as some modern heuristic methods like simulated annealing and tabu search. Some of these techniques were seen to be deterministic. Essentially you “turn the crank” and out pops the answer. For these methods, given a search space and an evaluation function, some would always return the same solution (e.g., dynamic programming), while others could generate different solutions based on the initial configuration or starting point (e.g., a greedy algorithm or the hill-climbing technique). Still other methods were probabilistic, incorporating random variation into the search for optimal solutions. These methods (e.g., simulated annealing) could return different final solutions even when given the same initial configuration. No two trials with these algorithms could be expected to take exactly the same course. Each trial is much like a person’s fingerprint: although there are broad similarities across fingerprints, no two are exactly alike.

The essential idea of evolutionary problem solving is quite simple. A population of candidate solutions to the task at hand is evolved over successive iterations of random variation and selection. Random variation provides the mechanism for discovering new solutions. Selection determines which solutions to maintain as a basis for further exploration. Metaphorically, the search is conducted on a landscape of hills and valleys (see figure 7.1), which is also called a “response surface” in that it indicates the response of the evaluation function to every possible trial solution. The goal of the exploration is most often to locate a solution, or set of solutions, that possesses sufficient quality as measured by the evaluation function. It’s not enough to simply find these solutions, however, we need to find them quickly. After all, enumeration will find such solutions too, but for real problems we’d grow old waiting for the answers. The speed with which suitable solutions can be discovered is in part dependent on the choices we make in determining the representation of trial solutions, the evaluation function, the specific variation and selection operators, and the size and initialization of the population, among other facets. The key to designing successful evolutionary algorithms lies in making the appropriate choices for these concerns in light of the problem at hand.

The first problem discussed in section VIII has only a slight connection with the traveling salesman problem (TSP) in that it also requires finding a minimum-distance solution. This is where the similarities end, however, because there aren’t any tricks for finding perfect solutions to the TSP. The problem is NP-hard [135]: there are no known algorithms for finding perfect solutions that have a complexity that grows as only a polynomial function of the number of cities. As a consequence, we must rely on generating solutions that are less than perfect, but as close as possible within a reasonable amount of time. This is a significant challenge, and for this reason we will devote this entire chapter to the TSP. Furthermore, the TSP is related to other problems in scheduling and partitioning, and its broad generality makes it an important keystone in combinatorial optimization. Some ideas that might be useful for addressing the TSP might also be useful in a variety of other applications. The TSP also serves to illustrate many of the central concepts of this book: the flexibility of an evolutionary approach to problem solving, the ease of incorporating problem-specific knowledge, and the ease of hybridization.

Every real-world problem poses constraints. You can’t get away from them. It’s only the textbooks that allow you solve problems in the absence of constraints. Dhar and Ranganathan [80] wrote:

Virtually all decision making situations involve constraints. What distinguishes various types of problems is the form of these constraints. Depending on how the problem is visualized, they can arise as rules, data dependencies, algebraic expressions, or other forms.

Almost every practical heuristic search algorithm is controlled by some set of parameters. In simulated annealing, for example, there’s a temperature parameter, and what’s more, you have to decide the schedule for reducing the temperature over time. In hill-climbing, there’s a parameter that controls the size of the local neighborhood in which you’ll look for improvements. In tabu search, you must determine how to implement the rules for the memory structure. None of these algorithms comes neatly wrapped in a gift box where all you have to do is open the box and receive your nice surprise!

As we have seen, real-world problems are usually associated with large sample spaces and nonlinear, multimodal evaluation functions. In many cases, there are no closed-form mathematical procedures for generating solutions, and even when these techniques exist, they are often too computationally intensive to be practical. Their computational complexity increases at such a rapid rate that when we try to apply them to anything but trivial problems they are practically useless. In order to make them more useful, we accept simplified assumptions about the real world, perhaps mandating the application of a linear evaluation function, with linear constraints, integer values, or other common mathematical devices. We sacrifice the right answer just to get any answer at all.

If you spend any significant amount of time trying to solve problems, “racking your brain,” you will inevitably contemplate the prospects of automating your thinking process. The dream is to make a computer simulation that simulates the way your brain functions so that it can solve problems the same way you do. But brains don’t function with the same mechanisms as serial digital computers. Biological processing is inherently and massively parallel in character, whereas traditional computing is sequential. Each step in an algorithm is conducted in turn until a final halting condition is reached. Further, although there are conceptual similarities between neurons in living brains and logic gates in computers, the firing rates of biological neurons are much slower than computer logic gates (on the order of milliseconds for neurons versus nanoseconds for computers). These and other differences in design lead to an intuition that these alternative input-output devices should each be able to tackle different problems with efficiency.

Prior to the advent of the digital computer, calculations were often performed on slide rules. By necessity, answers were almost always “good enough” rather than precise because our eyesight and manual dexterity weren’t sufficient to manipulate a slide rule to yield an arbitrary number of significant digits. To multiply, say, π by e you would line up the slide rule at about 3.14, give or take, and then read off the answer next to 2.72 on the upper index. With a little practice, you could generate answers that were within the degree of precision offered in the original problem (here, two decimal places). No one could expect finer tuning than that. Perhaps this is where the common saying “close enough for government work” originated. Today, in contrast, the precision of the modern digital computer is a great asset.

We know that no single algorithm can be the best approach to solve every problem. We have to incorporate knowledge about the problem at hand into our algorithm in some useful manner; otherwise, it may not be any better than a random search. One way to approach this issue is to hybridize an evolutionary algorithm with more standard procedures, such as hill-climbing or greedy methods. Individual solutions can be improved using local techniques and then placed back in competition with other members of the population. The initial population can be seeded with solutions that are found with classic methods. There are many ways to form hybrid approaches that marry evolutionary algorithms with other procedures.

We’ve covered a great deal of material in this text, and as we approach the end, let’s take the opportunity to review what we’ve discussed. The primary question to ask when facing a problem is “what’s my objective?” If you don’t have your goal well focused and plainly in mind, your hope of attaining the goal is minimal, and even if you do attain it, you might not even know that you did! Keep your eye on the objective whenever you’re solving a problem. It’s all too easy to simply march off in the quest for a solution and forget what you were trying to solve in the first place. It’s also easy to be diverted or side-tracked into addressing some other concern that may or may not be of comparable importance.