zig-NEAT (NeuroEvolution of Augmenting Topologies)

[limpid wing]

https://github.com/cryptodeal/zig-NEAT

Really find NEAT fascinating and have wanted to get my hands dirty implementing an out of the box Machine Learning architecture, so pet-project the last month or two has been to port goNEAT (Golang implementation of NEAT) to Zig for fun/practice. Link to goNEAT implementation: https://github.com/yaricom/goNEAT

Haven't written too much in lower level languages previously (excluding Go, have written a bit of C++), so probably a solid amount of room for further optimizations (and likely not following some Zig best-practices); will be focusing on optimizing/fixing those issues as I clean up code and rewrite the Structs using comptime type parameters to make the library more generic/generally useful.

Works to solve XOR and basic CartPole; planning to add further examples going forward.

zig-NEAT (NeuroEvolution of Augmenting Topologies; WIP)

[wary cloud]

👀

[limpid wing]

Benchmarking the goNEAT XOR example against zig-NEAT XOR example with build flag -Doptimize=ReleaseFast (same starting genome/options/evaluation function used in both), zig-NEAT implementation is substantially faster (Zig requires ~66.96% less time per epoch):
goNEAT Avg Time Per Epoch: 259658 nanoseconds
zig-NEAT Avg Time Per Epoch: 85788.49 nanoseconds

[limpid wing]

Moved examples to their own folders in the root dir so they demonstrate how to use zig-NEAT as a library in other projects.

[limpid wing]

zig-NEAT also implements/exposes generally useful Graph Theory functionality (used internally); based on zigraph (https://github.com/thebsv/zigraph), but updated to run on latest Zig (nightly) and implements additional algorithms such as Bellman-Ford, Moore Bellman-Ford, Floyd Warshall, & Johnson's Algorithm. The implementation of the path finding algorithms is based on gonum/graph.

[limpid wing]

Added Novelty Search optimization and accompanying demo where an Agent controlled by an Artificial Neural Network learns to navigate a maze. Novelty Search proves effective in escaping the problem of local optimum that can be encountered with Objective based Optimization.

E.g. solving the hard maze demo with a population of 250 organisms and 2000 generations, the Agents trained using Objective based optimization fail to find the exit within 2000 generations; Novelty Search optimization under the same conditions learns to navigate the maze/find the exit typically in <150 generations.

[limpid wing]

zig-NEAT (NeuroEvolution of Augmenting Topologies)

[limpid wing]

Implemented ES-HyperNEAT and HyperNEAT algorithms; pending debugging of the Retina demo (which uses ES-HyperNEAT) as, thus far, I've been unable to replicate the results detailed in the paper (unclear whether it's an issue w library's current implementation of ES-HyperNEAT or the experiment setup itself, including, but not limited to the start genome/parameters): https://www.mitpressjournals.org/doi/pdfplus/10.1162/ARTL_a_00071

[limpid wing]

Most functionality now has docs: https://cryptodeal.github.io/zig-NEAT/

[wary cloud]

actually really neat (I'm sorry)

[limpid wing]

Tangentially related since it's another ML library I've just started working on written in Zig (will get it's own post eventually, but need to have more of the basics working), but I've started writing zigTensor: https://github.com/cryptodeal/zigTensor

It's strongly based on Flashlight, which is a C++ Tensor library that allows devs to implement custom backends from Meta's AI Research Team: https://github.com/flashlight/flashlight

I've had the pleasure of working closely with 2 of Flashlight's contributors in building shumai (Javascript ML Library for Bun runtime backed by Shumai), so have gotten a solid look under the hood of Flashlight and really appreciate the thought that went into making the library so versatile; hope to bring the same flexibility to zigTensor: https://github.com/facebookresearch/shumai

Initial bindings are going to be for ArrayFire CPU, but ultimately hope to get up to feature parity with Flashlight in the default backends included with the library (ArrayFire CPU, ArrayFire OpenCL, ArrayFire CUDA, OneDNN, & Stub) .

[weak rover]

How do you calculate out put of neat network while everything is all over place
Just storing each node output in memory?

[limpid wing]

Each network node NNode has field activation, which tracks the latest activation value of the node. Here's where the XOR example loads inputs into the network/reads outputs: https://github.com/cryptodeal/zig-NEAT/blob/main/examples/xor/src/main.zig#L78C9-L94C10

If you're curious for more info on how the output values are calculated, check out Network.forwardSteps: https://github.com/cryptodeal/zig-NEAT/blob/main/src/network/network.zig#L386C5-L398C1

[weak rover]

Then how big network going to be?
You storing all activation
I was thinking about finding better way

Like some how dropping activation value if you don't need it anymore

[limpid wing]

Yea, NEAT tends to start with small networks and evolve complexity, so this works well for problems like XOR, CartPole, etc where a relatively simple ANN can be evolved to solve the problem at hand.

For larger networks (as would be encountered when using ES-HyperNEAT algo), there's FastNetworkSolver, which tracks state in way that is more efficient for larger networks) https://github.com/cryptodeal/zig-NEAT/blob/main/src/network/fast_network.zig#L73C12-L73C12

[weak rover]

It is same tbh it holds everything until last second
Or i am wrong?

[limpid wing]

Mostly the same, but there's not actually a Node type (albeit MIMOControlNode) for the FastNetworkSolver, state of nodes such as: activation value, NodeActivationType, etc are kept in slices where each element in the slice holds a value for a specific node in the Network (e.g. neuron_signals: []f64 holds the current actiation values for each node). adjacent_matrix: [][]f64 holds the cxn weights from node to node in network.

[weak rover]

Yeah it is more efficient then normal neat
Normal neat is kinda brute force

Btw how you remove unused network?
I using struct to hold them but don't know how delete them

[limpid wing]

Call .deinit() on pretty much any allocated struct in the library to free all associated resources ^^

Typically, the Network is held as part of the Organism struct when running an experiment, so calling org.deinit() frees the underlying network as well as any genetic structs that comprise the Organism

[weak rover]

I was thinking about putting them in a array and just pop them x)

And fill it wit new generation
Keeping top organisms there until extinction event happens

[limpid wing]

Yep, that's effectively the use case of the Population struct; see Population: https://github.com/cryptodeal/zig-NEAT/blob/main/src/genetics/population.zig#L18 and also PopulationEpochExecutor, which runs the reproduction cycle at each epoch: https://github.com/cryptodeal/zig-NEAT/blob/main/src/genetics/population_epoch.zig. Config options such as dropoff_age (and a few others) help weed out older Organisms that haven't improved their fitness over a specified number of runs, which makes room for new Organisms/Species in the Population.

[weak rover]

I see i see

I still need to learn zig to actually coding

I come from python

Didn't give me edge here really
Memory problem to grow big networks
As you need lots of them

[limpid wing]

I actually had only really worked with JS until about a year or so ago, so I get that feeling; best thing for me was to just start writing Zig and things started to click

[weak rover]

Js is nice