On the Preservation of Input/Output Directed Graph Informativeness Under Crossover

There exists a broad class of networks that connect inputs to outputs. These networks include chemical transformation networks, electrical circuits, municipal water systems, and neural networks. The goals of this paper are to provide a theoretical foundation for evolutionary crossover on this class of graphs and connect crossover to informativeness, a measure of the connectedness of inputs to outputs. Informativeness is defined as a partially informative graph has at least one path from an input to some output, a very informative graph has a path from every input to some output, and a fully informative graph has a path from every input to every output. A neural network with nonzero weights and any number of layers is fully informative. As links are removed (assigned zero weight), it may become very, partially, or not informative (the complement of informativeness is actionability, which is a measure of how connected outputs are from inputs). We define a crossover operation on Input/Output Directed Graphs (IOD Graphs) in which we find subgraphs with matching sets of forward and backward directed links to “swap.” With this operation, IOD Graphs can be subject to evolutionary computation methods. We show that fully informative parents may yield a noninformative child. We also show that under certain conditions, crossover compatible, partially informative parents yield partially informative children and very informative input parents with partially informative output parents yield very informative children. However, even under these conditions, full informativeness may not be retained. Similar results hold for actionability.