Hypergraphs provide a mechanism through which properties of high-dimensional surfaces can be explored with relative ease. Visualisation provides direct insight into landscape structure negating the need for mathematical expertise. Early unpublished experiments on the usability of hypergraphs showed that for six-dimensional hypercubes, people either mastered the display and learned to navigate very quickly -- usually in time linearly proportional to the Hamming distance between points -- or failed to understand the structure at all. One subject, a computer science graduate student, not only had the fastest times of any of the people tested, but also appeared to navigate between points in constant time.
The hypergraph visualisation technique is not without its shortcomings. Primary amongst its limitations is its lack of scalability. Because the hypergraph attempts to represent the entire surface (a worthy goal), the size and complexity of the display scales exponentially in the dimensionality of the cost function. It is not expected that the approach be used in exploring real-world problems, since if the cost surface can be enumerated, the function poses little practical difficulty. Even on some artificially constructed test functions, the cost surfaces for problems of `interesting' size are too large to represent. For example, Holland's [10] hyperplane defined functions (hdf) are defined over spaces of hundreds of dimensions.
Nevertheless, some simplifications can be made that allow these larger, and more complex cost functions to be reduced to manageable sizes: much of the space in hdfs is a flat plateau of uniform (maximal) cost which can be removed by the deletion of `uninteresting' dimensions. On these simplified versions of hierarchically defined test functions, the hypergraph display provides useful intuitions of the high-dimensional structure.
A further issue with applying the hypergraph approach to hierarchical, modular functions is the mismatch between the topology of the graph and the manner in which GAs search. The unfolding of the space into the hypergraph structure is done so that neighbouring points are laid out in a recursive fashion. That is, the layout of the hypergraph is designed to visually enhance the Hamming distance between points: translational adjacency in the hypergraph topology represents single-point mutation. The layout of the hypergraph is thus tuned to display how the space would be searched by a hill-climbing approach. Crossover works by combining subsequences from potentially disparate points. The hypergraph does not make it clear how a population of solutions would adapt when crossover is used. A possible solution to this dilemma might be to animate the adaptation of a population, but the dimension limitations, discussed above, may limit the viability of this approach.
As mentioned in the introduction, the hypergraph visualisation technique is aimed at exploring cost surfaces that have a hierarchical, modular structure defined over a binary space. To this end, the technique is successful (modulo the reservations above) in that it uses the human perceptual system's ability to perceive symmetry as a way to enhance the salient features of recursive high-dimensional structure. We have also successfully used hypergraphs for investigating non-hierarchical surfaces, particular NK functions [4]. For these surfaces, the hypergraph is not unfolded recursively, rather, neighbouring dimensions are grouped together along an axis (i.e., low-order dimensions are along the x-axis and high-order dimensions are along the y-axis).
