Saturday, November 22, 2008

Book Review: How to Solve It: Modern Heuristics, by Zbigniew Michalewicz and David B. Fogel



This was a fun book to read, if you're into geeky books, that is. One of the central points the authors were trying to make throughout the whole book is that one problem is different from another, and that therefore the methods of solution will likely have to differ. Indeed, if you incorporate zero knowledge of the problem into your solution, then your solution must essentially be a random search.

Three problems provided a common thread for the many methods the authors reviewed. The first problem was the Traveling Salesman Problem (TSP). This is a famous unsolved problem in computer science. The idea is that a salesman must visit a given number of cities once only, and do so using the shortest possible path. The solution space is of size (n-1)!/2, where n is the number of cities. Applications of this problem could be drilling holes in a printed circuit board quickly. The second problem was the Boolean satisfiability problem (SAT). Here you have an expression involving a certain number of Boolean variables (they're like switches: they can be either on or off, 0 or 1, True or False), and you want to find a collection of values for which the expression comes out True. The size of the solution space is 2^n. Applications of the SAT problem include scheduling problems. Finally, there was a particular non-linear optimzation problem (NLP): maximize a complicated function involving the sums of fourth powers of cosines, the products of squares of cosines, and several complicated constraints involving sums and products. The solution space of this problem is technically uncountable infinite, but on a computer you have restrictions. Supposing a particular representation for numbers on a computer, say, with n variables each of which is m bits long, you have a solution space of order n * 2^m. Applications of this particular optimization problem might be limited, but the kind of problem is ubiquitous.

I really liked the way the authors kept hammering away at the same three problems throughout the entire book. It provided a good element of continuity. I also liked their assertion that human nature is to have a hammer and assume everything is a nail. The authors approach problem-solving differently, better: find the right tool for the job at hand. Contrary to many collections of numerical recipes (as valuable as those can be), the authors are more trying to examine the wisdom of when to use a particular technique on a particular problem.

Another theme of the book was a profound point. Suppose you teach a particular technique in a chapter of a textbook, and then you have the students do the end-of-chapter problems. Naturally, those end-of-chapter problems require applying the technique the kids just learned. After all, they're at the end of THAT chapter! However, such an approach does nothing to teach kids when to use a particular technique and when not to. An interesting and fascinating illustration of this point came when the authors proposed two relatively simple problems, not requiring any math beyond high school geometry and trigonometry, outside of the context of a particular technique. The problems were, therefore, much harder to solve. Indeed, the authors gave these two problems to math and engineering undergrads, graduate students, and even professors. Fewer than 5% could solve the problems in anything less than an hour, even though the solutions, if you know the trick, take less than five minutes each to write! Apparently, we are not taught truly to solve problems, the hard problems, the problems we've never seen before. That is the point the authors were making, and I think it's valid.

The authors propose using evolutionary computing to solve the TSP, SAT, and NLP problems mentioned above. While they don't claim it's a panacea, they do urge this family of solutions because of its flexibility in light of changing conditions, competitive conditions, etc. You still have to tune the solution to the problem, or evolutionary computing will not do any better than a random search in the search space.

The method of evolutionary computing takes its cue from the theory of evolution. And here we have to be careful as Christians. I don't believe in Darwinian evolution, not a bit of it. First of all, and most importantly, it doesn't square with Scripture. Second of all, although you do seem to see micro-evolution within species, there is no evidence whatsoever for macro-evolution. Moreover, it is rather evident that many proponents (certainly not all) of the theory of evolution take that position precisely so they can rule out the existence of God. I reject the theory of evolution, therefore, on both theological and scientific grounds. The theory of evolution, in fact, is not science but a faith. By the same token, Creation "Science" is not science either, but faith. Both are dealing with highly non-repeatable events (the origin of the universe), and thus, ultimately, no experiments are available which will provide evidence one way or the other.

However, just because I reject the theory of evolution doesn't mean that, in theory, a method of computation based on those ideas is necessarily immoral or somehow anti-Christian. The authors, as is usual with evolutionists, are unfortunately a bit preachy (in the bad sense of the word) on the point of evolution.

The evolutionary methods of computation have achieved some remarkable results in obtaining approximate solutions to problems (which is often the best you can hope for!). In addition to evolutionary computing, the authors delve into neural networks, fuzzy logic, coevolutionary systems, and multicriterial decision-making. All of these things are fascinating because they are so real. It's so easy to see real-world applications of these concepts!

Overall, I'd highly recommend this book to anyone whose business in life is to solve problems, especially of the numeric kind.


 
Visit Math Help Boards for friendly, free and expert math help.

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home