On the Preservation of Input/Output Directed Graph Informativeness under Crossover
23 views
Skip to first unread message
Andreas Duus Pape
Jun 18, 2024, 9:56:28 AMJun 18
to DT Forum
Hello. I’m very pleased to share this new paper:
On the Preservation of Input/Output Directed Graph Informativeness under Crossover
by Andreas Duus Pape, J. David Schaffer, Hiroki Sayama, Christopher Zosh
This paper is a mathematical analysis of the crossover operation on Input/Output Directed Graphs or IOD Graphs, which are directed networks with inputs and outputs. IOD Graphs include chemical transformation networks, electrical circuits, municipal water systems, and neural networks such as GPT. Crossover, a foundational operation of genetic programming with these networks, has been used in all these domains. This paper characterizes the general relationship of crossover to informativeness, a measure of the connectedness of inputs to outputs, and when and what kinds of informativeness are preserved when the crossover operation creates children from two contributing parent input/output directed graphs.
Full abstract below. Link to full paper is here on arXiv: https://arxiv.org/abs/2406.10369 and attached.
We welcome any feedback. Thank you!
ABSTRACT
There is a broad class of networks which connect inputs to outputs. While evolutionary operators have been applied to a wide array of complex problems, methods to apply such operators to these networks remain ill-defined. We aim to remedy this. We define Input/Output Directed Graphs (or IOD Graphs) as graphs with nodes $N$ and directed edges $E$, where $N$ contains (a) a set of ``input nodes'' $I \subset N$, where each $i \in I$ has no incoming edges and any number of outgoing edges, and (b) a set of ``output nodes'' $O \subset N$, where each $o \in O$ has no outgoing edges and any number of incoming edges, and $I\cap O = \emptyset$. We define informativeness, which involves the connections via directed paths from the input nodes to the output nodes: A partially informative IOD Graph has at least one path from an input to an output, a very informative IOD Graph has a path from every input to some output, and a fully informative IOD Graph has a path from every input to every output.
A perceptron is an example of an IOD Graph. If it has non-zero weights and any number of layers, it is fully informative. As links are removed (assigned zero weight), the perceptron might become very, partially, or not informative.
We define a crossover operation on 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 non-informative child. We also show that under conditions of contiguousness and the no dangling nodes condition, 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.
https://arxiv.org/abs/2406.10369
On the Preservation of Input/Output Directed Graph Informativeness under Crossover
by Andreas Duus Pape, J. David Schaffer, Hiroki Sayama, Christopher Zosh
This paper is a mathematical analysis of the crossover operation on Input/Output Directed Graphs or IOD Graphs, which are directed networks with inputs and outputs. IOD Graphs include chemical transformation networks, electrical circuits, municipal water systems, and neural networks such as GPT. Crossover, a foundational operation of genetic programming with these networks, has been used in all these domains. This paper characterizes the general relationship of crossover to informativeness, a measure of the connectedness of inputs to outputs, and when and what kinds of informativeness are preserved when the crossover operation creates children from two contributing parent input/output directed graphs.
Full abstract below. Link to full paper is here on arXiv: https://arxiv.org/abs/2406.10369 and attached.
We welcome any feedback. Thank you!
ABSTRACT
There is a broad class of networks which connect inputs to outputs. While evolutionary operators have been applied to a wide array of complex problems, methods to apply such operators to these networks remain ill-defined. We aim to remedy this. We define Input/Output Directed Graphs (or IOD Graphs) as graphs with nodes $N$ and directed edges $E$, where $N$ contains (a) a set of ``input nodes'' $I \subset N$, where each $i \in I$ has no incoming edges and any number of outgoing edges, and (b) a set of ``output nodes'' $O \subset N$, where each $o \in O$ has no outgoing edges and any number of incoming edges, and $I\cap O = \emptyset$. We define informativeness, which involves the connections via directed paths from the input nodes to the output nodes: A partially informative IOD Graph has at least one path from an input to an output, a very informative IOD Graph has a path from every input to some output, and a fully informative IOD Graph has a path from every input to every output.
A perceptron is an example of an IOD Graph. If it has non-zero weights and any number of layers, it is fully informative. As links are removed (assigned zero weight), the perceptron might become very, partially, or not informative.
We define a crossover operation on 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 non-informative child. We also show that under conditions of contiguousness and the no dangling nodes condition, 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.
https://arxiv.org/abs/2406.10369
Reply all
Reply to author
Forward
0 new messages