Name and Classification: Hypercube Diagram (Classification: State Space Visualization)

Intent: When you want to visualise an N-dimensional space defined over binary spaces, this pattern provides a 2D representation of an N-dimensional hypercube. It shows the complete set of values defined at the corners of the hypercube. The values can be categories or numbers (natural or rational).

Also known as: Hyperspace Graph Paper

Motivation: Exploiting the human visual system’s ability to infer structure from repeated patterns, texture or grouping is a powerful way to

  • visualize fitness landscape of the complete set of real or binary fitness values defined over a hypercube.
  • visualize attractors of a continuous space: given the corners of the hypercube as an initial set of conditions, illustrate the final set of attractors of the system.

Applicability: Use the Hypercube Diagram when

  • Your underlying variables are defined over binary strings and the dependent measure can be Boolean, categorical or real-valued.
  • Visual inspection of the binary strings does not give an indication of the structure and possibly grouping of the space.

Structure:

Participants:

Collaborations:

Example Visualization:

Figure 1. Eight-dimensional hierarchical-if-and-only-if function. Shown are (a) the basin of attraction for the global optimum, 00000000 and (b) the basin of attraction for the local optimum 00111111 (the bottom right point in the upper left quadrant). Points in the basin have been highlighted by drawing a triangle across the upper left half of the area. Figure and caption taken from Wiles & Tonkes (2002)

Consequences: The Hypercube Diagram has the following consequences and inherent limitations:

  • To interpret the maps correctly requires training.
  • It is most useful for visualizing small to medium sized spaces depending on the size of the display. For example, N = 20 gives a hypercube of 220 =~ one million points and gives a map of size 1024 x 1024.
  • The 2D visualisation shows recursive structure as repeated patterns in the 2D map.

Implementation: The Hypercube Diagram has the following implementation variations:

  • Shading / colour based on category, or real valued states. Shading can be used for a real value such as in fitness functions, distinct colours can be used for categories.
  • To look at larger spaces, variables can be grouped or omitted.
  • Alternative layouts include:
    • Recursive symmetry (rather than translational symmetry)
    • Karnaugh Maps used to design electrical circuits.

Known Uses:

  • Fitness functions (Wiles & Tonkes, 2002)
  • Lyapunov measurements (Nicholas Geard)
  • Karnaugh maps (Hill & Peterson, 1974)

Related Patterns: Use with State Space Stability Measure to characterise the basins of attraction of a dynamic system.

Sample Code: Coming Soon

References:

F.J. Hill and G. R. Peterson.  Introduction to switching theory and logical design, Section 6.4: “Karnaugh Map Representation of Boolean Functions”.  1974.  John Wiley and Sons, Sydney.

Wiles, J. & Tonkes, B. (2002). Visualisation of hierarchical cost surfaces for evolutionary computation. In Proceedings of the 2002 Congress on Evolutionary Computation, 157–162.