Boolean Functions Fitness Spaces
W. B. Langdon and R. Poli
School of Computer Science
The University of Birmingham,
Birmingham B15 2TT, UK
http://www.cs.bham.ac.uk/wbl, 126 rmp
Tel: +44 (0) 121 414 4791 Fax: +44 (0) 121 414 4281
Technical Report: CSRP-98-16
16 June 1997
We investigate the distribution of performance of the Boolean functions of 3 Boolean
(particularly that of the parity functions),
the always-on-6 and even-6 parity functions.
We use enumeration,
uniform Monte-Carlo random sampling and sampling random full trees.
As expected XOR dramatically changes the fitness distributions.
In all cases once some minimum size threshold has been exceeded,
the distribution of performance is approximately independent of program
However the distribution of the performance of full trees is
different from that of asymmetric trees and varies with tree depth.
We consider but reject testing the No Free Lunch (NFL) theorems on these functions.
William B Langdon
Tue Jun 16 15:05:48 BST 1998