2-Colouring of Cartesian Grid

In this example, the objective is to 2-colour a graph that has nodes laid out on a regular Cartesian grid and that has edges between nearest-neighbours along both axes. Such a graph has a chromatic number of 2. The parameters in the net generation panel can be set as follows:

The following images show three stages in a single run of the Conservative Fixed Probability Colourer (activation=0.3). The local nature of the single-node optimizations performed causes regions to grow in which nodes colours are compatible. But at the boundaries of such regions, the colours are incompatible. Over time, the boundaries flatten and may vanish.

Step 0
Step 60
Step 1000

NB: the region-growing effect is prominent in the CFP algorithm because each step adjusts the colours of many nodes, but it is still present in other algorithms. For example, the following image shows the colouring produced by the sequential, Random Order algorithm (which is a greedy algorithm, so it terminates after one assignment to each node).

The performance of CFP with activation 0.3 (CFP0.3), Sequential Hill Climber with tolerance 0.05 (SHC0.05) and Random Order (RO) are compared in the plot below, which shows Gamma versus steps (on a log scale). Since CFP is massively parallel, it is not surprising that it improves the colouring much more quickly than either of the sequential algorithms. Note though that the final quality is about the same as that achieved by CFP. The RO algorithm terminates abruptly because it is a greedy algorithm.

It is informative to compare the performances of the algorithms using the assignment cost rather than the steps, as shown below. Note that the CFP algorithm requires more assignments to achieve the same Gamma as SHC. This seems reasonable: the SHC algorithm has the luxury of evaluating all possible single-node changes before selecting one.