Guided Evolutionary Search for Boolean Networks in the Density Classification Problem

Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the convergence to fixed points, a behavior found in the context of the density classification problem, where the aim is the network’s convergence to a fixed point of the prevailing node value in the initial global configuration of the network; in other words, a global decision is targeted, but according to a constrained, non-global action. Here, we rely on evolutionary searches in order to find rules and network topologies with good performance in the task. All nodes’ neighborhoods are assumed to be defined by non-regular and bidirectional links, and the Boolean function of the network initialized by the local majority rule. Two evolutionary searches are carried out: first, in the space of network topologies, guided by a parameter (\(\omega \)) related to the ’small-worldness’ of the networks, and then, in the space of Boolean functions, but constraining the network topologies to the best family identified in the previous experiment. The results clearly make it evident the key and successful role of the \(\omega \) parameter in looking for solutions to the task at issue.