Such that and only the hamming distances

86 FRONTIERS OF EVOLUTIONARY COMPUTATION

operators that can be represented as graphs, where a vertex represents a type, and an edge represents an operator transformation from one type to another, then P naturally corresponds to a normalized adjacency matrix for the graph.

will exhibit rapid first hitting time for for some polynomial

in and will not exhibit rapid first hitting time for

With the proper constraints on W, however, we may find the following:

Conjecture Consider a search space, with Let the fitness values be Consider a binary encoding of the indices, such that if and only if the Hamming distances, H[ , ], between the binary encodings satisfies Let

We may also consider a class of transmission matrices which can never achieve rapid first hitting time for any set of fitnesses, namely, the “long path??

(Horn et al., 1994) matrices:

has rapid first hitting time.

So, while a long path operator and a binary hypercube operator will have the same average performance in locating the global optimum over all permu­tations of fitness, there will be some permutations that we expect will give the binary hypercube a rapid first hitting time, while none that will give the long path operator a rapid first hitting time. In this way, we can make a definite judgement that the binary hypercube is superior to the long path operator for optimization.

At this juncture, I will refrain from pursuing the numerous possibilities that exist for investigating these open questions, and leave them for forthcoming work.