Understanding Compositional Pattern Producing Networks (Part One)

Such lack of uniformity between network topologies makes evolution of CPPNs somewhat unique and difficult, so I thought it would be worthwhile to explain some of the details of how CPPNs are typically evolved and how such lack of structural uniformity is handled.Historical MarkingsEach time a new connection is added into a CPPN’s topology, it is given a “historical marking” or “innovation number”, which is simply an integer unique to that specific connection..Each connection added to every CPPN within the population is given a unique historical marking..As connections are added throughout evolution, a global counter is maintained and incremented so that every historical marking assigned is unique..Such historical markings allow one to understand the history and lineage of each connection within the population..Additionally, as structures are crossed over with each other throughout evolution, one can observe which connections are of similar evolutionary descent using historical markings..By performing such simple book-keeping on added connections, several aspects of evolving CPPNs are greatly simplified..In the figure below, you can observe a list of connections and their corresponding innovation numbers (innovation numbers and historical markings are the same thing!).List of Connections [2]Notice that each connection in the image above is assigned an innovation number and the innovation number of every connection is unique..This allows you determine which networks within a population share common connections and, in turn, are descended from the same structures.Crossover of CPPNsAs mentioned previously, part of evolving neural networks with GA involves crossover — the swapping of weight values between networks to create new networks..For the typical evolution of neural networks with GA, crossover is quite simple..Here is a figure to visualize common types of crossover between same-topology networks:Different Types of CrossoverFor the evolution of augmenting topology CPPNs, crossover becomes slightly more complicated due to the fact that the number of weights between two networks may not be the same..However, the process is greatly simplified with the use of innovation numbers..Instead of trying to find a special way to decide which weights to crossover with each other, only weights with the same innovation numbers are crossed over.. More details

Leave a Reply