next up previous
Next: Introduction

Boolean Functions Fitness Spaces

W. B. Langdon and R. Poli
School of Computer Science
The University of Birmingham,
Birmingham B15 2TT, UK
{W.B.Langdon,R.Poli}, 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 inputs (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 length. 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