Neuroevolution of Augmenting Topologies (NEAT)

This video explains the NEAT algorithm! This algorithm (published in 2001) lays the groundwork for the evolution of neural network architectures/topologies. This groundwork includes the encoding of neural network topologies, modifications to enable crossover, and the importance of minimal initialization!
Thanks for watching! Please Subscribe!
Paper Link: citeseerx.ist.psu.edu/viewdoc/...

[@IBMboy]

I learned about NEAT watching SethBling video on MarI/O AI, it was mind blowing watching NN and evolution working together, and i didnt know it was all the way back from 2001! really old comparing to other techniques. This video is a very clear summary.

[@connorshorten6311]

Thank you so much!! I think this is a great example of an old algorithm that responds really well to scaling up computational resources! I'm not sure NEAT directly is very useful for things other than toy control problems like cart-pole balancing, but I think the extension in CoDeepNEAT really expands the potential of this framework!

[@darkerbit]

This is the best explanation of NEAT I've ever seen!

[@connorshorten6311]

Thank you so much!!

[@xeozim]

Really good intro to NEAT, I'm about to give it a go with Python and this is excellent for a short background to it

[@MTEXX]

Great presentation. Like the NN itself, you presented many new terms for me to explore.

[@rigbyb]

This is a great explanation, thanks a lot :)

[@98Destructo]

Hello, Great video man! What kind of fitness functions were they using for giving the fitness score to each genome?

[@markusflicke7749]

Awesome as always. Thanks

[@connorshorten6311]

Thank you so much!!

[@prafulsrivastava8942]

Nice sum up!

[@sudeepkuchara5287]

ngl i have a talk tomorrow and this is an excellent revision material

[@SiOnCaa]

Thanks for this excellent explanation! I am experimenting with NEAT for a while now, but I stumbled across this detail. You talked about the innovation numbers for connections and its importance for crossover. Do you handle innovation numbers for the nodes too? And if so, how do you keep track of them? My initial consideration was to remember for each node-mutation between which nodes it was created to be able to reuse the specific innovation number if another genome was about to mutate the same way. This seemed to be a good solution but if other node-mutations are about to occur, the node won’t be located between the initial nodes it was created for. My current setup is to handle innovation numbers of nodes locally within each genome increasing it whenever this genome created a new node. I would be very happy to hear your thoughts on this! And again, thanks for your content!

[@connorshorten6311]

Thank you for sharing your experience with this! Your analysis is very interesting, would you mind providing an example of how you would locally track the innovation numbers? My understanding of innovation numbers is that it facilitates the crossover operation. The construction of intermediate nodes is definitely tricky to visualize in your mind, but I think it helps to remember that a lot of neural architecture search designs will just discount a node if it's output doesn't end up connecting in the future, so say you have a sequential path from say node 1 --> node 4 --> node 7 and you have a crossover where node 1 goes to node 5 but node 5 doesn't connect to the output, you would just drop node 5 after compiling the architecture.

[@SiOnCaa]

​@@connorshorten6311 Thanks for the quick reply! I will try to be more specific, but since english is not my native language I will probably need to write more than necessary to make my self clear here. So bear with me ;-) As you corrrectly stated, storing the innovation numbers of *connections* in a central place is critical for NEATs crossover functionality to work. Each client (or genome) requests this central state for getting or creating the desired connection by passing the from- and to-node to it. Each connection maps a number (innovationnumber) to two nodes (from & to). Whenever a requested connection does not yet exists, it will be created with an incremented innovation number. But for the distinction whether a connection was already created, there must be any kind of identification to the nodes itself. In your reply the nodes 1, 4, 7 and 5. Do you centralize the identification number of nodes too, or do you keep track of them locally within each client eg via an always increasing integer member? I think this question comes down to this: Does NEAT require same identification of nodes within the heredity (same node-ids withing the crossover history) or globally within each genome regardless of any crossover? For visualization a small visualization: Lets use the alphabet for node identification to be able to distinguish between node-ids and connection-innovation-ids. Each genome starts with an inital neuronal network of just the input and the output layer defined (No connections at the moment). For the sake of simplicity lets use one input node and one output node. _______ G1: i h o A B G2: i h o A B Central storage: empty _______ Now a link mutation occurs within G1 and a connection between two randomly selected nodes will be requested. Since the are no connections defined, it will be created with an innvoation-number of 1 and passed down to the genome. _______ G1: i h o A -> B 1 G2: i h o A B Central storage: 1: A->B _______ Next up G2 will also create a link mutation. It requests it by passing A and B to the central storage and receives the connection with the same innovation number. _______ G1: i h o A -> B 1 G2: i h o A -> B 1 Central storage: 1: A->B _______ Now the interesting part. On my initial setup I kept track of each new node that was created and mapped its id to the from- and to-nodes it has splitted. Like this: Lets say in G1 occures a node mutation. G1 asks the central storage about the identification of a node splitting the connection of A->B. It does not exist so increment the node-innovation and pass it to the requesting genome. _______ G1: i h o A -> C -> B 2 3 G2: i h o A -> B 1 Central storage: Connections Nodes 1: A->B C: A->B 2: A->C 3: C->B _______ G2 could now also develop a node mutation and receives the same node-id by passing the splitting nodes to the central storage. This is all fun and games till there is another node-mutation splitting conneciton 2 or 3. Than the node C no longer splits the nodes A and B but D and B or A and D. My current setup, with increasing node-identification, will handle the same situation like this: G1 creates a new (third) node. It increases its own node-identifier to C and asks the central storage for the two accruing connections. _______ G1: (last node-id: C) i h o A -> C -> B 2 3 G2: i h o A -> B 1 Central storage: Connections 1: A->B 2: A->C 3: C->B _______ At this moment the resulting situation is the same. If G2 develops a node-mutation itself, it would also give it the id C. But lets asume you got a slightly different initial network. I hope with this i will be able to make myself clear here as to why I struggle with this :-) _______ G1: (last node-id: C) i h o A \ 1 C / 2 B G2: i h o A \ 1 C / 2 B Central storage: Connections 1: A->C 2: B->C _______ Setup global node-identification: If now a mutation in G1 occurs, splitting connection 1. The central storage will keep track of the newly created node-id D and that it slitted A and C. It is irrelevant whether G2evelops a node-mutation between B and C first. Because it would receive a increased id of E. Whenever G2 is about to split A and C, it will receive the same node-id from the central storage (D). Setup local node-identification: Same situation as described above: Now the node-ids will depend on the creation-order. When G1 creates a node between A and C first, it would get the id C. When G2 then creates a node between B and C first, it would get the id C too. Both setups got their advantages/disadvantages. I read the paper of Kenneth Stanley and all sort of explanations but never found any discussion about that. As before I would be glad to hear your thoughts on this!

[@jacobhall8267]

Where do you go to download it?

[@ryandoesstuffapparently1540]

I am fascinated by NEAT. I’m still a total beginner, but I’m aiming to use NEAT in Unity to build a rag doll that learns how to stand up and walk and keep itself balanced.

[@tristantendson]

You know, that’s really neat

[@palee630]

What does sh mean at the fitness computation?

[@karstenhannes9628]

What I don't get in the cross-over figure at 9:00 is that the excess and disjoint genes of the fittest parent are inherited. As you mentioned, in case Parent 2 is the fittest genes 3, 7 and 8 should be kept but 5 should be discarded. But in the offspring gene 5 exists! So it looks like all disjoint and excess genes are kept in the figure...

[@bjarke7886]

confused me aswell

[@strohkoenig]

This is because the video does not explain the example correct at this point. In the paper where this image is from it is explained that both parents in this example have the same fitness. Then all genes are inherited. If they don't (which is usually the case), only the genes of the more fit parent are inherited.

[@karstenhannes9628]

@@strohkoenig I see! Read the paper as well and did not get that the parents had the same fitness in the example... Pretty special case though :P . But thanks for the clarification :-)

[@strohkoenig]

@@karstenhannes9628 It is only mentioned in the caption of the image. One can easily miss it. ;-)

[@VG-hf2sg]

Great Video. But please let me know: How do you solve the problem that basically with each generation, you get children with more and more neurons? If recombination is done that way, amount of neurons will increase parabolic. Given a limit as the maximum amount of neurons a network is allowed to have, how to adapt the recombination? Thank you!

[@hck1bloodday]

I recreated a version in which the possible mutations include removing a node and removing a connection. that way if your network, behaves better with less nodes than with more, it will get a better fitness score and habe a better chance to reproduce

[@JuliusFreiny]

Am I missing something? At 9:15 you're saying Parent 2 has performed better, so we keep 3, 7 and 8 and discard 5. But why is 5 shown in the offspring then? Also: Why is 2 blue and not white?

[@mlwithaarvy]

What kind of explanation is this....???? What is the crossover? 9:13 No mention of how parent 2 has better performance without showing any reference. also you said 5 is discarded but its there in the offspring. If there is a global table and you have to use it one at a time, how it could be asynchronous? at 8:25 how do you say the crossover is given value..? which operation is being performed here? also which information is missing?

[@laserbean00001]

The sharing function isn't 0 or 1. It's 0 or 1 - (δ/σ_share)^α

[@NikopolAU]

9:15 > "and discard 5". Proceeds to not discard 5.

[@DrN007]

9:15 You're wrong.

[@papercolor8259]

talk is cheap.