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

code

See px_nk.c or px_nk.tar

compile

gcc -O2 px_nk.c -lm

running

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 "".)

K
K
Adjacent 0 or Random 1
Type of crossover, 0 two point 1 uniform 2 partition crossover
crossover rate
point mutation rate (per locus)
tournament size
pseudo random number seed used for NK landscape fitness values
pseudo random number seed used, if random (argument 3), for NK landscape connectivity
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

run_302.txt

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

ga2_312.txt

Results

PPSN 2016 tutorial slide 34 Optimal Solutions: Adjacent NK Model

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

References

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
Darrell Whitley, Gray Box Optimization: Theory and Practice. PPSN 2016 tutorial
Darrell Whitley, Search Landscapes and Gray Box Optimization: A Tutorial. 51^st CREST Open Workshop . video
L. Darrell Whitley, Francisco Chicano, Brian W. Goldman. Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT). Evolutionary Computation 24(3): 491-519 (2016). DOI
Francisco Chicano, Darrell Whitley, Gabriela Ochoa, and Renato Tinos. 2017. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017). ACM, Berlin, 753-760. DOI

Francisco's Java code.

Acknowledgement

My thanks to Darrell Whitley and Francisco Chicano

W.B.Langdon
23 April 2018 (Last update 6^th August 2018)

	Model	2-point	Uniform	Partition Crossover
500 1	Adjacent	80.5	0	100
500 3	Adjacent	34.7	0	93.3
500 1	Random	0.022	0	91.8
500 3	Random	0	0	58.9