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.