An interactive introduction to Simulated Annealing!

Simulated Annealing (SA) is a very basic, yet very useful optimization technique. In principle, it’s a modification of what’s sometimes called a “hill climbing” algorithm.

Let’s look at a practical example to explain what hill climbing is, and what SA addresses. Imagine you’re in a 1-dimensional landscape and you want to get to the highest possible point. Further, a crazed optimization expert has blindfolded you so you can’t see anything; all you can do is randomly try to go either left or right, by tapping your foot to feel if a step in that direction is higher than where you’re currently standing. If it is, you take that step, and repeat. read more

Descending into modular neuroevolution for logic circuits

A while ago, I did a post on beating OpenAI games using neuroevolution (NE). Go read that if you’re interested, but here’s the gist: a typical strategy for training an agent to beat those games is to have a neural network (NN) play the games a bunch, and then improve the weights of the NN using a reinforcement learning algorithm that uses gradient descent (GD), and it of course works pretty well.

However, an alternative to those methods is to use a gradient free method (which I’ll call “GD-free”), like I did in that post: you try a bunch of random changes to the NN’s weights, and only keep the resulting NNs that play the game well. That’s the “evolutionary” aspect of it, and using methods like that to create NNs is often called “neuroevolution” (NE). read more

In case hexapods weren’t creepy enough: the centipede robot!

Similar to…most of? my ideas, I don’t remember why I thought of this. I think after I made the reinforcement learning robot, I was on a robot kick, and came up with this. Hexapods are of course a robot classic, but I don’t think I had ever seen a centipede robot.

Why a centipede? Well… I can make up a few “practical” reasons: because of its length, it could potentially bridge gaps, or bend “upwards” to have height, or possibly even climb. But the real reason is because they haven’t been done that much and I thought it would be cool, funny, and creepy. read more

Training a real robot to play Puckworld with reinforcement learning

After I trained an agent to play “puckworld” using Q-learning, I thought “hey, maybe I should make a real robot that learns this. It can’t be that hard, right?”

Hooooooooo boy. I did not appreciate how much harder problems in the physical world can be. Examples of amateurs doing Reinforcement Learning (RL) projects are all over the place on the internet, and robotics are certainly touted as one of the main applications for RL, but in my experience, I’ve only found a few examples of someone actually using RL to train a robot. Here’s a (very abridged!) overview of my adventure getting a robot to learn to play a game called puckworld. read more

Beating OpenAI games with neuroevolution agents: pretty NEAT!

Let’s start with a fun gif!

Something I’ve been thinking about recently is neuroevolution (NE). NE is changing aspects of a neural network (NN) using principles from evolutionary algorithms (EA), in which you try to find the best NN for a given problem by trying different solutions (“individuals”) and changing them slightly (and sometimes combining them), and taking the ones that have better scores. read more

Genetic Algorithms, part 2

Last time, in case you missed it, I left off with a laundry list of things I wanted to expand on with Genetic Algorithms (GA). Let’s see which of those I can do this time!

This is pretty wordy and kind of dry, since I was just messing around and figuring stuff out, but I promise the next one will have some cool visuals.

Some mathy tesselating stamp art!

I was recently at the art store for some reason, just browsing. I found the linoleum stamp section at the back and immediately wanted to make some! We had made them in 5th grade art class or something, and I remember liking it a lot, but had never since then. They’re kind of the perfect type of art for me, since I seem to like 3D things with more of a “crafts” element. I like carving/whittling anyway, so this was perfect.

I grabbed a few (pretty cheap), and on the way home thought of what I’d do: make a square stamp with weaving paths, asymmetric, such that it could be stamped out in a grid to either create cool repeating patterns, or random ones. read more

Skyscraper fun with OR-Tools!

My friend Mike recently showed me a puzzle game called Skyscrapers, which you can play here. It’s a neat idea, in the general theme of “fill in the numbers with these constraints” puzzles like Sudoku or Verbal Arithmetic.

The rules are like so. You’re given a board like this, representing a group of city blocks (one building per square), with numbers around the sides: read more