Evolutionary Optimization of Independent Deeply Contingent Components Happens in Parallel

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 parallelSpecifically, 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:

mcpf-algo

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.

mcpf-ga

To regenerate this figure, clone the \texttt{multicomponent-cpf} 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:

mcpf-sa

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.

Evolutionary Optimization of Independent Deeply Contingent Components Happens in Parallel

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s