C code for Partition Crossover and NK landscapes

C code aiming to reproduce parts of Renato Tintos, Darrell Whitley, and Francisco Chicano. 2015. Partition Crossover for Pseudo-Boolean Optimization. In Foundations of Genetic Algorithms XIII (FOGA 2015). ACM, Aberystwyth, 137-149. DOI


See px_nk.c or px_nk.tar


gcc -O2 px_nk.c -lm


px_nk.c takes all its inputs via the command line (see main() in px_nk.c). Defaults are provided for all ten arguments. Defaults can be invoked either by omitting the argument or providing a null string for that argument. (In Unix, how you specify an empty argument depends in detail on the shell you are using. In tcsh you can use "".)
  1. K
  2. K
  3. Adjacent 0 or Random 1
  4. Type of crossover, 0 two point 1 uniform 2 partition crossover
  5. crossover rate
  6. point mutation rate (per locus)
  7. tournament size
  8. pseudo random number seed used for NK landscape fitness values
  9. pseudo random number seed used, if random (argument 3), for NK landscape connectivity
  10. pseudo random number seed used by genetic algorithm
The code is set up to reproduce experiments from Darrell Whitley PPSN 2016 tutorial on Stuart Kauffman's NK landscapes.

Example using Partition Crossover on NK 500,3 adjacent connectivity

./a.out 500 3 0 2

Example investigating fraction of local optima produced by Partition Crossover on NK 500,3 random connectivity

By setting the crossover rate at 1, we trigger GA2, the second set of experiments (population size 20 and 20 generations).
./a.out 500 3 1 2 1


PPSN 2016 tutorial slide 34 Optimal Solutions: Adjacent NK Model

See also FOGA 2015 Table 1.

2-pointUniformPartition Crossover
500 1 0050
500 3 0037

50 runs Adjacent NK Landscape run_NK.bat

PPSN 2016 tutorial slide 34 Percent of Offspring that are Local Optima

See also FOGA 2015 Table 5.

Model2-pointUniformPartition Crossover
500 1Adjacent    80.5    0100    
500 3Adjacent 34.7    0  93.3
500 1Random   0.0220  91.8
500 3Random   0      0  58.9

Mean percentage of 50 runs on NK Landscapes run_GA.bat

A few unix linux tcsh scripts are available. These may need adapting for other unix command line shells or non-unix systems.


Francisco's Java code.


My thanks to Darrell Whitley and Francisco Chicano
23 April 2018 (Last update 6th August 2018)