Session:

LBP - Late Breaking Papers

Title:

Exhaustive Directed Search

Authors:

Sanza Kazadi
Daniel Johnson
Jhanisus Melendez
Brian Goo

Abstract:

We explore the development of an exhaustive directed search of state space based on concepts from evolutionary computation. A brief investigation of the evolvability of an evolutionary algorithm illustrates that evolutionary algorithms are capable of reaching optimal solutions when the diversification operator (which may be a \emph{pseudo-operator} which acts over many different diversification steps) is capable of reaching, at every improvement point, another, more improved population element. Moreover, we demonstrate that the upper limit on the time to the optimal point is identical to that of an \emph{exhaustive directed search}. This search is exhaustive, but borrows the diversification operator from the evolutionary algorithm and proceeds in such a way that, if left alone, it would exhaustively search the space. However, we demonstrate that this type of search can perform comparably with the evolutionary algorithm, avoiding deceptive search tracks that might trap an evolutionary algorithm.