search

schrum2 / MM-NEAT

Modular Multiobjective (Hyper) Neuro-Evolution of Augmenting Topologies + MAP-Elites: Java code for evolving intelligent agents in Ms. Pac-Man, Tetris, and more, as well as code for Procedural Content Generation in Mario, Zelda, Minecraft, and more!
http://people.southwestern.edu/~schrum2/re/mm-neat.php
Other
50 stars 20 forks source link

Some parallelism for SteadyStateExperiment #774

Closed schrum2 closed 2 years ago

schrum2 commented 2 years ago

A Steady State Evolutionary Algorithm is one where a single individual is evaluated at a time and then the population/archive/whatever gets updated based on that one individual. MAP Elites falls into this category, and the problem with this approach is the inefficiency. You could evaluate multiple individuals simultaneously.

In principle, it is possible to simply have the archive treated like an external resource and have several separate algorithms sample members of the archive, mutate them to create offspring, evaluate them, and then add the results back to the archive. However, this wide open approach would be a bit difficult to implement given the way the code is currently structured. However, there is something we can do that gives us a bit of an improvement.

In SteadyStateExperiment there is a line of code where ea.newIndividual() is executed. Add a command line parameter "steadyStateBatchSize" that allows this command to be executed "steadyStateBatchSize" number of times in parallel per iteration of the loop. Executing in parallel will be especially helpful for fitness functions that have to wait and see if the shape is moving.

However, this also means that MinecraftLonerShapeTask can't be allowed to simply place all shapes at the same location for evaluation ... this will actually be a fairly complicated issue. Should talk about it first.

schrum2 commented 2 years ago

I've decided to go in a different direction on this. I've introduced the steadyStateArchetypeSaving parameter to simply prevent archetype saving. I've also synchronized the clean-up step. I think that I want to have several parallel loops instead of parallel batches, but some more changes in archetype cleanup are needed first.

schrum2 commented 2 years ago

Stage is set for more work here. First, replace the parallelMinecraftSlots parameter with a new steadyStateThreads parameter (this will generalize beyond Minecraft. The parameter will still be used for initialization and determining the number of available corners, but now will be used in SteadyStateExperiment too.

In the run method, spawn steadyStateThreads number of threads that contain the while loop as their run() method. Launch each one and then join each one so they keep running.

schrum2 commented 2 years ago

This will be challenging. Work together, but don't start until we've discussed it a bit

schrum2 commented 2 years ago

I also don't want you working on this until we figure out what is up with issue #787 since these changes will not be worth the effort if parallelism is not giving us a benefit. It is possible that the Minecraft server itself is serving as a bottleneck that prevents us from getting a benefit from parallelism.

schrum2 commented 2 years ago

Running the test in SteadyStateExperiment with a single thread took 21.153916666666664 minutes. How about in parallel?

schrum2 commented 2 years ago

Running the same test with 10 parallel threads took only 7.492233333333333 minutes! So, a big savings.

However, there was a crash right at the end. Maybe one thread shut things down before the others were finished? Need to fix that still, but this seems to work.

schrum2 commented 2 years ago

Actually, the crash was related to interacting with the world via the diamond and emerald blocks, but is fixed now (I believe ... testing now).

schrum2 commented 2 years ago

@alejmedinajr @MuellMark @richeyme I just closed this task. The timing is a bit inconvenient ... it would have been nice to run experiments using this code over the 3-day weekend, but it's not a big deal. In any case, this code does seem to run faster, and should be used in additional experiments that you conduct throughout next week.

One final note before closing: The number of individuals generated may slightly overshoot the intended maximum as each thread has to close independently. This is a minor issue ... probably not even worth fixing, but worth mentioning.