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.

Movie Review: Wall-E

Rating: G

Degree to which what sins there are in the movie (as defined biblically) are condemned (0 = sin is always winked at, 10 = sin is always condemned): 7

Degree to which the story has redemptive value (0 = no one saves anyone, 10 = practically the story of Christ's redemption of His people): 5

Artistry of movie (0 = completely inartistic, 10 = stunning work of art): 5

Originality (0 = copies everything from somewhere else, 10 = unique): 3

Synopsis: The people of Earth have been so neglectful of their environment that it can no longer sustain photosynthesis, and therefore life. A single robot (named Wall-E) roams the Earth, and it is his sole business to sort through trash and organize it into square bundles. The movie opens with views of whole skyscrapers built of these small squares of trash. We see him going about his daily business, when he is interrupted by a spaceship landing, and another robot getting out and starting to investigate Earth. Wall-E is immediately "smitten" by the supposedly female robot, who he finds out is named Eva. Just before Eva arrives, Wall-E finds one little plant growing, which he immediately transplants into his little hoard of treasures. When Wall-E shows the plant to Eva, she immediately goes unconscious and has a little green plant sign on her that is pulsating. She also, incidentally, pockets the plant. Wall-E starts doing romantic things for the unconscious Eva, imagining that she's actually responding to him, and in general making a fool of himself. Eventually, the spaceship returns and takes Eva with it, but not before Wall-E manages to hook himself onto the exterior of the spaceship. The spaceship takes off, and Wall-E somehow manages to survive atmospheric exit. The spaceship docks with a gigantic spaceship on which we find out the rest of the human race dwells. The rest of the story shows how Wall-E and Eva interact with each other and the humans.

Critical Review: I'm someone who believes we should be caring for animals and the environment, but why? Because man, however fallen he may be, is still the crown of creation. We are stewards of God's creation. Moreover, there are other moral principles that are, to my mind, far more important than saving the environment. For example, it is more important for men to be free to worship God than it is to take care of the environment. It is more important to save baby humans not yet born than to save the whales.

For these reasons, the movie came across as exceptionally "preachy" - in the bad sense of the word. Hollywood came across as the typical we-are-environmentalists-and-the-worst-crime-you-can-commit-is-to-degrade-the-environment-in-any-way.

There were too many references to past movies and themes. 2001, A Space Odyssey, came to mind, with the battle between the ship's captain and the auto-pilot (who even looked like the computer in 2001). There were distinct themes of Brave New World.

There were a few genuinely funny moments - I enjoyed in particular the scene where Wall-E is showing Eva his treasure collection and hands her a unsolved Rubic's Cube. The camera excludes her for a second or two, and then re-includes her holding a solved Rubic's Cube. Very geeky, that.

I didn't appreciate the typical feminist gender reversal in this movie. Wall-E is supposedly masculine, and Eva supposedly feminine. But Eva has all the firepower, does all the dragon-slaying, and has the take-charge attitude, whereas Wall-E is the lovable, caring, nurturing sort.

Overall: a mediocre movie. It might be worth watching, but it's not nearly as good as The Incredibles.

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