In my last post, I introduced the notion of deep contingency and contrasted it with deep hierarchy—the hypothesized property of fitness functions that genetic algorithms purportedly exploit. Here I provide evidence that recombinative evolution can optimize multiple deeply contingent components in parallel. Specifically, I generalize the contingent parities function presented in the previous post (which you should read first) and examine the performance of a simple genetic algorithm on an instance of the generalized problem. For the sake of comparison, the behavior of simulated annealing is also presented.

The pseudocode for a Contingent Parities Function with multiple components is given below:

The following figure shows the missteps of component 1 (in blue) and component 2 (in green) of a chromosome with maximal fitness in each generation when a simple genetic algorithm was applied to an contingent parities function with two components of order 2 and height 100. The y-coordinate of the green dots (representing the missteps of component 2) were dodged by +0.5 to reduce overlap. The maximal fitness in each generation is shown in red.

To regenerate this figure, clone the branch of this repository as follows:

git clone -b multicomponent-cpf https://github.com/burjorjee/royal-roads.git

Then execute the following python code:

import royalroads as rr
cpf = rr.ContingentParitiesFunction(order=2, height=100, numComponents=2)
rr.evolve(fitnessFunction=cpf,
          popSize=500,
          maxGens=1000,
          probMutation=0.004,
          sigmaScaling=True,
          sigmaScalingCoeff=0.5,
          useClamping=True,
          rngSeed=1,
          visualize=True)

The figure shows that the simple genetic algorithm optimizes both components of the contingent parities function concurrently. The maximal fitness achieved was 199.

A plot showing the behavior of simulated annealing on the same function follows below:

To regenerate this figure execute the following python code:

import royalroads as rr
cpf = rr.ContingentParitiesFunction(order=2, height=100, numComponents=2)
rr.anneal(fitnessFunction=cpf,
          epochsPerPeriod=500,
          numPeriods=1000,
          initFitnessDropOfOneAcceptanceProb=0.6,
          finalFitnessDropOfOneAcceptanceProb=0.01)

The maximal fitness achieved was 168.