Does evolutionary computation ring a bell? In computer science, it’s the family of algorithms for global optimization inspired by biological evolution. Instead of following explicit mathematical gradients, these special models generate variants, test them, and retain the top performers. They’ve shown promise in early work by OpenAI, Google, and others, but they’re somewhat tough to prototype — there’s a dearth of tools targeting evolutionary algorithms and natural evolution strategies (NES).
Luckily, the folks at Uber’s engineering department are on the case. The company today open-sourced EvoGrad, a Python library designed to help researchers differentiate through expectations — long-run average values of repetitions of the same experiment they represent — of random variables, which is a key step in estimating NES gradients. Additionally, the company announced evolvability ES, a new NES-based meta-learning algorithm developed by Uber researchers that precipitated the creation of EvoGrad.
“The idea is to enable more rapid exploration of variants of NES, similar to how [Google’s TensorFlow machine learning framework] enables deep learning research,” wrote project contributors Alex Gajewski, Jeff Clune, Kenneth O. Stanley, and Joel Lehman in a blog post. “We believe there are many interesting algorithms yet to be discovered in this vein, and we hope this library will help to catalyze progress in the machine learning community.”
As the team explains, traditional evolutionary algorithms subject a parallelly evolving collection of potential solutions to a sort of survival-of-the-fittest competition. Those that rank highest are granted more “offspring” — modified copies of themselves or combinations of themselves with others — in the next generation. On the other hand, those that score poorly are removed from the population.
NES then abstracts the population as a probability distribution, enabling the solutions to be sampled and evaluated. Basically, an objective function — one that can be differentiated by evaluating population samples, yielding a mathematical formula for an explicit gradient of improvement — iteratively updates the population distribution such that the average fitness of solutions drawn from it is maximized.
The symbolic form of the gradient estimation must be separately derived for choices representing population distribution and optimization metrics, which tends to be tedious and which requires specific mathematical knowledge. But EvoGrad handles the bulk of this — it provides probability distributions which may be used in the expectation function. Developers can maximize for things like mean fitness or variance of behaviors, producing populations that can easily be adapted to solve a wide range of tasks.
Alongside EvoGrad, the researchers detailed evolvability ES, a technique they proposed in a recent paper accepted at the Genetic and Evolutionary Computation Conference earlier this month in Prague. It’s a new, efficient, and scalable algorithm for directly optimizing evolvability that applies modified versions of NES that maximize the diversity of behaviors in a single evolved population.
In one experiment, evolvability ES managed to evolve a population of AI controllers for a digital four-legged robot that encoded diverse walking behaviors (i.e., behaviors that efficiently walked in all different directions). Moreover, the population’s behaviors became better adapted to walking over time.
“A longstanding goal in evolutionary computation (the study of algorithms inspired by biological evolution) is to create algorithms that generate evolvable solutions (in other words, solutions able to rapidly adapt to new challenges),” wrote the team. “We believe this is an exciting (and unexpected) result, and future work on evolvability ES through EvoGrad and other libraries could further explore more complex multi-modal population distributions and combinations with more expressive genetic encodings.”
Uber’s been on an open source tear lately. Just earlier this month, it released the Plato Research Dialog System, a toolkit for developing and testing conversational AI, which followed hot on the heels of its Ludwig framework. And in February, it made freely available Autonomous Visualization System, a web-based platform for vehicle data.