I’m starting to mull ways to use generic algorithms on a decentralised network. Thoughts?
A couple of intriguing threads:
executable genotype of immutable function() (in JSON, RDF?) = automata
parallelism via client with subpopulation (eg web app). Social/viral app?
This post is just to see if anyone else is interested in the area and have ideas or know of relevant work we can gather together.
So far all I’ve done is a few searches to gauge the state of the area in the open source community and collected links to projects and demos mainly in JavaScript, some in Rust. (There is quite a lot in Python if any pythonheads are interested but I haven’t collected those).
One guy (also a world YoYo champion) has created a couple of web based demos which are great to watch, and you can tweak them a bit too. The first attempts to evolve a ‘walker’ (two dimensional humanoid), but I find the second even more interesting to watch, racing cars against each other to evolve a better car! These are only two of the projects I found, posting here because they are fun :
I just found a freeware program I wrote back in the 80’s on the internet archive and you can run it in the DOS emulator! It’s called the Genetic Algorithm Workbench and has a graphical (WIMP) UI (see/run/download it here!). I used it to help market services to apply GAs to engineering problems and wrote it, including the whole WIMP/multitasking bit to learn C++ (anyone remember Zortech C++?). We got some work with oil companies using and customising various tools for their applications. I haven’t played with GAs since then but they never left my interest. My original interest was looking for ways to evolve code rather than write it, so I’m still curious about that - hence the bit in the above bullets about functions/automata.
Please reply if you are interested and fancy investigating GAs and thinking about ways to implement them on the network and post anything you think might be helpful. For now I’m thinking only of client side apps that could be implemented with the existing APIs.
Updates:
musing about a Decentralised Open Ended Evolutionary Search App (here)
I’ve been digging and learning from the Uber Labs presentation Recent Advances in Population-Based Search for Deep Neural Networks: Quality Diversity, Indirect Encodings, and Open-Ended Algorithms posted below by David which is fantastic. For anyone whose interest is piqued I recommend it, and have located the slides (pdf) and their code at Uber Research on github. Their research seems to have culminated in the Go-Explore algorithm which has solved previously unsolved problems and performs ahead of humans and other algorithms on a platform game. At the end of the presentation they highlight the ‘three pillars’ underlying the kind of “Open Ended Evolution” algorithm that this represents, which they explore with the techniques of Novelty Search • Quality Diversity • Open-Ended Search • Indirect Encoding. These are each fascinating in their own right, and the presentation does a fantastic job of explaining how and why they work, and how they come together to advance the effort to create powerful general computational AI.
Unison language is interesting for distributed computation / GAs on SAFE. See: unisonweb.org and github
Would like to discuss with you soon an existing algorithmic application and if/how we might be able to apply a practical safe GA based software algorithm solution & the benefits of the safenetwork to enhance the already significant therapeutic benefits provided.
One of the features of genetic algorithms is that they are both compute intensive and that it is relatively easy to distribute that computation. So the new distributed language Unison (via @oetyng) looks like an interesting possibility for GAs on SAFE. See: unisonweb.org and github
I imagine a marketplace that would facilitate the sharing of code and data between clients and workers, but it would also verify the results and manage payments without requiring trust between the parties. It could be used for genetic algorithms, reinforcement learning, or other similar things where the same code needs to run with different sets of parameters in potentially many different environments, but it could also be used for less parallelized code.
Clients post binary code, a number of data sets, the payment offered (for CPU cycles, IO requests, and so on) and put some money in escrow.
Worker receives the code and one or more sets, distributed by the marketplace. When done, it posts the results together with the bill for the resource use.
The marketplace distributes the same jobs to multiple workers and it compares both the results and the reported resource use to avoid cheating. If everything checks out, it pays the workers and returns the results to the client.
It’s the client’s job to make sure the code they post doesn’t give away any secrets. The binary code is for a specific version of a virtual machine (web assembly?) that the workers need to use to execute it, and the virtual machine must monitor resource use so it can report it to the marketplace.
Things can get more complicated if we want to exploit hardware for floating point math due to implementation differences. GPUs would add even more complexity since subsequent runs of the same code may return different results (warps execute in a random order) unless much care is taken.
Thanks very much for posting this presentation David, I had a ball watching and learned a lot but wish I could have asked a question!
It occurred to me early on that there is a symmetry between diversity in the solution-agent, and diversity in the environment. So for example, generating diverse mazes would have a similar effect to generating diverse maze solvers, and when Ken Stanley began this seemed to be an important element of open endedness in artificial life (which he used as an example), but was subsequently discarded!
They went on, with Jeff Clune’s walker, to generate the test environments which was good, but done independently from the agents themselves. They never connected the change in environment directly to the change in the solutions. Even though this was present in many of the examples, such as giraffes growing long necks causing trees to grow taller and vice versa. Or where we now recognise wolves can cause a valley to thrive, or die when they are not present.
So in the real world or a-life simulated world, the interactions of individuals change the environment.
This is a key element of the open ended evolution on earth, and perhaps a general property of open ended systems.
Another example: example, plants changed our atmosphere to one which could support animals (oxygen rich), and animals evolved to both take advantage of that and create a balance which meant plants did not die from a lack of CO2.
This aspect of co-evolution wasn’t present in any of their research and only alluded to at the end when talking about communication between agents.
So I was curious as to why they have not done/published any work using simulated environments in which the agents evolve and directly affect the environment in which they are tested, rather than what appeared to be separate evolution / generation of agents and environment.
I agree, I think that would be very interesting. Something I would like to do, if I had time (oh please please one day) is to use actors and the lib @oetyng posted is a great example of that along with diversity search based cppn’s/hyperneat and for groups or network of actors to work together, but in the physical world.
What I mean is give them hints, like read wikipedia, you will find it here, listed for source, here is the mic and so on. Then have each actor network for all the different senses (if you like) search around their space but also communicate shared inputs, so be able to say this sound input is similar to this camera input and so on. Then let these evolve and see what happens.
I would also like my robots that I started building years back to be able to evolve, but again start by cheating, show them how to find an electric socket for recharge and so one, then let them learn better ways.
In terms of a cheat to start mechanism I am intrigued by teaching it (by cheating) Who What Why Where When as questions it should ask whenever possible, i.e. when there is discernible inputs via the mic (somebody speaking). Anyhow it is truly fascinating to be able to perhaps evolve at 4Ghz
Algorithms that evolve over time. Well that’s an interesting concept. I’m not a high level programmer but here are my thoughts on the possible applications.
You could have a series of applications working in tandem. 1. A personal search engine that refined it’s search results every time you searched based on past experience. Unlike say Google which uses a massive database of multiple user data and harvests data from all over the net this one would instead use only your data and instead “procreate” and have “children” that would in turn mutate and return possible results for you to choose from. So say you searched for “cats” do you mean “cats the musical” “jungle cats in Africa” “housecats” “lolcats” “cats the slang expression” or any number of the different permutations of the word. Each child would return as an iteration of that word. Then as you showed interest it would gain fitness. Results would crossbreed with one another based on fitness. So if you liked “lolcats” and “housecats” it would show you more common housecats doing stupid and ridiculous stuff. If you choose Lolcats + musical it would return stupid videos of cats. The engine could also draw on a definitions database which would be formed in a similar way by those attempting to define terms. Type in a word and the engine returns a definition. Type in a definition and the engine attempts to return the defining word. But of course people don’t always define words the same way so the engine has to learn and present the user with multiple options much the same way the search engine would present the user with multiple search results. And as languages evolve over time so would the definitions language engine. A third engine could be a rating system to work with the search engine but independent from it. What offends or is considered inappropriate to people. Again this varies and is very subjective but there might be some consensus as to “Oh you might want some warning before you click this.” So essentially it would be like the search engine but more like the site rot.com and essentially the engine would be seeking to find out what offends the user and why? So content would be given and they would be asked how it made them feel along with a series of adjectives. Fitness would be gained the more offended the user got until they left the engine. Yes that sounds rather toxic but it would also give info on what was considered offensive to people and that’s also why it’s separate from the search engine. Keep in mind people that actively sought out such content would develop a tolerance for it. Might want to pair it with one’s personal filters, again what does this make you feel and why? No reason to leak data in any of this since it’s all driven by local algorithms.
I had Michael stay here for a week as I was looking at that very thing while the guys were getting Fleming ready. Of course changes in house meant I had to drop all of this and step in again to manage Fleming. In any case it’s incredibly powerful and SAFE will benefit from that work. When I can get back to it then brilliant, I was mega excited, so let’s see.
Their research seems to have culminated in the Go-Explore algorithm which has solved previously unsolved problems and performs ahead of humans and other algorithms on a platform game. At the end of the presentation they highlight the ‘three pillars’ underlying the kind of “Open Ended Evolution” algorithm that this represents, which they explore with the techniques of Novelty Search • Quality Diversity • Open-Ended Search • Indirect Encoding. These are each fascinating in their own right, and the presentation does a fantastic job of explaining how and why they work, and how they come together to advance the effort to create powerful general computational AI.
:
