Question

How does the serach space in the context of evolutionary computation relate to the search spaces in normal search?

Answer 1

In order to answer this question, we first need to understand what are search spaces in evolutionary computation, and the search spaces in normal searches.

Search space in evolutionary computation:

The search space of an evolutionary computation is the set of all possible genomes. The problems you see with this definition rely on some misconceptions:

• Genomes may not be variable in length: not all genetic algorithms have mutation rules that allow insertions and deletions, but if they vary in length, there is no problem with a search space containing all the possible genomes of arbitrary length.
• Consider the representations of possible shapes of a screw propeller. The function that maps a genome to a particular shape of screw propeller may always halt, in which case the halting problem does not even apply. The genomes may not necessarily be representations of all possible programs either. Depending on the application they may,
• In this case, the "halting problem" states that some of these computer programs do not halt and you don't know which these are. However, that does not change the definition of the search space, which is still the set of all possible genomes. Moreover, the fact that some programs do not halt does not necessarily matter if the environment kills off such programs with positive probability, as happened in Tierra. All the halting problem tells you is that you will never be sure when you've found the optimal solution in that case. In short, the halting problem is a red herring. You can try and equate a genome with a computer program.

The set of all possible genomes is your search space. There is no problem with this definition, even if the genomes happen to grow and shrink.

Hence, the genome represents a potential solution to your search problem.

Search Space in a Normal Search:

The definition of a search space is the set or domain through which an algorithm searches. In computer science, the space may be a well-defined and finite data structure. Or, as in decision theory, it may be a vast and possibly infinite set whose elements need to be individually generated during the search.

For example, In chess, the search space is complicated. The search space is the set of all possible valid moves. For a given turn the space is finite, but the set of all possible games is infinite. Since the player is trying to maximize the probability of winning, they must search through many turns. These possibilities must be generated during the search.

As per the explanation of search spaces, in each of the above mentioned topics, we see that the search space of evolutionary computation relate to search spaces in normal searches, in the following ways:

• Search spaces in evolutionary computation, as well as normal search, is the set of all possible genomes and set of all possible valid moves respectively.
• In evolutionary computation, search space contains all the possible genomes of arbitrary length, whereas even in normal search, the search space the possibility of each and every move is generated.
• Irrespective of growth or shrinkage with respect to genomes in evolutionary computation, there is no change in the search space. Similarly in normal searches, no matter which move is generated, the set of moves in the search space won't change.