Emergent Behaviour, Population-based Search and Low-pass Filtering

Riccardo Poli, Alden Wright, Nic McPhee W. B. Langdon
Computer Science
University of Essex Logo

Paper presented at CEC-2006 Pages 395-402


Frequency Response for GA

Crossover Smoothes Landscape

Use Schema Theorem

Average Slope in next generation

= ½|ní(11)-ní(10)|+½|ní(01)-ní(00)|
= ½|n(1*)n(*1)-n(*1)n(*0)|+½|n(0*)n(*1)-n(0*)n(*0)|
= ½n(1*)|n(*1)-n(*0)|+½n(0*)|n(*1)-n(*0)|
= ½(n(1*)+n(0*))|n(*1)-n(*0)|
= ½|n(*1)-n(*0)|
= ½|n(11)+n(01)- n(10)-n(00)|
= ½|n(11)-n(10) +n(01)- n(00)|
≤ ½|n(11)-n(10)|+½|n(01)- n(00)|

Steps in Prove

Crossover reduces slope


Demonstration: OneMix

Average superimposed on OneMix benchmark


GA and OneMix

Infinite Population Unitation Model

OneMix Infinite Pop g=1 Crossover

Initial population is Gaussian.

Selection responds to all frequencies.

Crossover responds to low frequencies.

Impact of crossover in first generation

OneMix Infinite Pop g=1 Mutation

Selection responds to all frequencies.

Mutation responds to higher frequencies

Impact of mutation in first generation


W.B.Langdon 25 July 2006