The Pattern On The Stone: The Simple Ideas That Make Computers Work by W. Daniel Hillis

Author:W. Daniel Hillis [Hillis, W. Daniel]
Language: eng
Format: epub, pdf
ISBN: 9780465066872
Publisher: Perseus Books, LLC
Published: 0101-01-01T00:00:00+00:00

FITNESS LANDSCAPES

The use of heuristics to search through a set of possibilities is ubiquitous in computer programming and has applications far more important than game playing. This is often the way computers find “creative” solutions to problems—usually problems whose solutions are known to be among a large but finite set of possibilities called a search space. The search space in chess is the set of all possible lines of play; the search space in the traveling salesman problem consists of all possible routes linking the cities on the salesman’s list. Since these spaces are too large to search exhaustively, heuristics are used to reduce the area to be searched. In the case of small search spaces, such as in the game of tic-tac-toe, the exhaustive search is preferable, because it is guaranteed to find the right answer.

Generally, the reason that a search space is large is because the possibilities are produced by forming combinations of simpler elements—the individual moves in chess, the city-to-city hops in the traveling salesman problem. This combining of elements leads to a combinatorial explosion of possibilities—an explosion that grows exponentially with the number of elements being combined. Since the possibilities are built from combinations of elements, there is a sense of distance in the space; combinations that share common elements are “closer” than the combinations that do not. This is why it is called a “space” and not just a set of possibilities. To extend the analogy, we can imagine the possibilities as lying in a two-dimensional landscape sometimes known as a fitness landscape. The desirability, or score, of each possible solution is represented by the altitude of a point in the landscape. If similar possibilities have similar scores, then nearby points will have similar altitudes, so the landscape will have well-defined hills and valleys. In this analogy, finding the best solution is like finding the top of the highest hill. Taking the traveling salesman problem as an example, we can imagine each point in the landscape as representing a particular travel itinerary for the salesman. The height of each point represents the distance the salesman must travel, with points representing efficient travel itineraries at higher altitudes. The best itinerary will be at the top of the highest hill.

One of the simplest ways of searching such a space is to compare points at random and remember the best one found. The number of points that can be searched this way is generally limited only by the amount of time available, and the procedure can be applied to any type of space. It is the equivalent of parachuting scouts into various locations in the landscape and asking them to report back their altitude. It is not a very efficient way to find the top of a hill. If the space is large, then in any practical amount of time only a tiny portion of the possibilities will be investigated, and therefore the best point found is unlikely to be one of the highest.

In a search space like

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.