A Simple Genetic Algorithm Written in Ruby

I recently started making my way through An Introduction to Genetic Algorithms by Melanie Mitchell. I’m not too far into it yet but I’ve been pleasantly surprised by how clearly the author explains each concept.

In the first chapter she outlines a simple algorithm that is the basis for most applications of genetic algorithms. There isn’t any code in the book so I decided to implement it on my own in Ruby to understand it better:

The algorithm as described in the book is quoted below with my comments following each section.

1. Start with a randomly generated population of n l-bit chromosomes (candidate solutions to a problem).

In this code, n is represented by the POPULATION_SIZE constant and l by NUM_BITS. The initial randomly generated population is created using the Population’s seed! method.

2. Calculate the fitness f(x) of each chromosome x in the population.

The fitness of a Chromosome can be calculated by its fitness method. In this example, the fitness is simply the number of 1’s that the chromosome contains.

3. Repeat the following steps until n offspring have been created:

a. Select a pair of parent chromosomes from the current population, the probability of selection being an increasing function of fitness. Selection is done “with replacement,” meaning that the same chromosome can be selected more than once to become a parent.

A chromosome is chosen from the population using the Population’s select method. This method implements fitness-proportionate selection using roulette-wheel sampling which is conceptually equivalent to giving each individual a slice of a circular roulette wheel equal in area to the individual’s fitness. The roulette wheel is spun, the ball comes to resent on one wedge-shaped slice, and the corresponding individual is selected.

b. With probability Pc (the “crossover probability” or “crossover rate”), cross over the pair at a randomly chosen point (chosen with uniform probability) to form two offspring. If no crossover takes place, form two offspring that are exact copies of their respective parents.

The crossover probability is defined by CROSSOVER_RATE. The crossover is performed by the Chromosome’s bitwise AND (&) operator which I overloaded for this class.

c. Mutate the two offspring at each locus with probability Pm (the mutation probability or mutation rate), and place the resulting chromosomes in the new population. If n is odd, one new population member can be discarded at random.

The mutation rate is defined by the MUTATION_RATE constant. The mutation is performed by the Chromosome’s mutate! method.

4. Replace the current population with the new population.

5. Go to step 2.

Here are the results for 1,000 generations where the population is 24, the number of bits per chromosome is 64, the mutation rate is 0.001, and the crossover rate is 0.7. Pay attention to the average value over time:

Generation 1 - Average: 32 - Max: 40
Generation 2 - Average: 33 - Max: 38
Generation 3 - Average: 34 - Max: 41
Generation 4 - Average: 34 - Max: 37
Generation 5 - Average: 34 - Max: 41
Generation 6 - Average: 35 - Max: 39
Generation 7 - Average: 34 - Max: 43
Generation 8 - Average: 35 - Max: 45
Generation 9 - Average: 36 - Max: 44
Generation 10 - Average: 37 - Max: 44
...
Generation 990 - Average: 49 - Max: 50
Generation 991 - Average: 49 - Max: 50
Generation 992 - Average: 49 - Max: 51
Generation 993 - Average: 49 - Max: 51
Generation 994 - Average: 49 - Max: 51
Generation 995 - Average: 49 - Max: 50
Generation 996 - Average: 49 - Max: 50
Generation 997 - Average: 48 - Max: 50
Generation 998 - Average: 48 - Max: 50
Generation 999 - Average: 48 - Max: 50
Generation 1000 - Average: 48 - Max: 50

The average fitness of the population increases from 32 initially to 48 by the 1,000th generation, just as you’d expect for a population slowly becoming more fit over time.

If this interests you, I encourage you to try it yourself and experiment with different values for MUTATION_RATE, POPULATION_SIZE, and NUM_BITS.

For example, increasing the mutation rate from 0.001 (1 in 1,000) to 0.01 (1 in 100) has the following effect on the average fitness over time:

Given the impact that the mutation rate has on long term fitness of the population, how can we determine what the optimal mutation rate is? Can the chromosome’s mutation rate change over time? Can different sections of the chromosome evolve to have different mutation rates? What about the number of bits or the population size? These are a few of the things I hope to find out :)

How Workflowy Has Changed the Way I Work

workflowyI’ve been using this amazing web and iOS app called Workflowy for more than a year and a half and it has completely changed the way I work. I am such a big fan of Workflowy that it is the only web app that I’ve paid for that I didn’t have to simply because I want to support their company and see them thrive (their free plan allows you to create 500 items per month, their pro plan costs $4.99/month or $49/year).

In this post I’ll share in detail how I use Workflowy in the hope that you might try it and benefit from it as much as I have. If you already use it, maybe you will pick up a few ideas for your own workflow.

Workflowy Introduction

Below is Workflowy’s official two minute introduction video. If you’ve never used Workflowy, I highly recommend watching it before continuing because it will give you a quick overview of Workflowy’s core features which I’ll be referring to in this post.

[youtube https://www.youtube.com/watch?v=SOPYrxvojVo]

Note-Taking & Task Tracking

I’ve used a number of note-taking and task tracking tools over the years including pen and paper, Outlook, Notepad, Remember The Milk, Tooledo, and Evernote.

Workflowy is hands-down the best note-taking app I’ve ever used because of how smoothly it lets you create and organize lists. You can have hundreds of notes on dozens of different topics but keep them all tucked away until you need them. There’s also a quick search feature that you can use to locate notes if you forget where you stashed them.

For task tracking, Workflowy works well when you don’t have a lot of hard or recurring deadlines. If you do have a lot of tasks that have to be completed by certain times (you have these 6 meetings today, X is due every Tuesday at 4pm, Y is due every third Friday by noon, etc) having a todo list application that lets you sort by deadline would probably better suit you.

How I Organize Workflowy

Below is a screenshot of a template that mirrors how I use organize my Workflowy lists. You’ll find a description of each list in the next section.

Items in gray are placeholders for example content that would go within the various lists.

workflowy_demo_template

Tasks

My Tasks list contains everything that I have to do including project tasks, miscellaneous tasks, as well as appointments and deadlines.

When I first started using Workflowy I kept project tasks as list items under projects, miscellaneous (non-project) tasks under a separate Misc Tasks list, and didn’t include appointments or deadlines at all. I’ve found that keeping all tasks, appointments, and deadlines grouped near each other works much better because you can quickly reference what’s on your plate without searching through a dozen different lists. If you prefer to keep your project tasks grouped under your projects, you can tag each task using something like #task and then use Workflowy’s search feature to view just those items.

I divide the Task list into three lists based on how soon each task needs to be accomplished. Short Term tasks are things that I need to do within the next week or so, Medium Term tasks are tasks that I need to do within the next few weeks, and Long Term tasks are tasks that I need to do within the next few months.

My GMail inbox also serves as its own todo list where unread emails are things that still require some action on my part. I generally won’t move something from GMail over to Workflowy except in cases where I respond to an email and need to remind myself to follow-up in case I don’t receive a timely response.

The Short Term tasks are further divided by day of the week. I keep today at the top of the list and it contains the tasks, appointments, and deadlines that I have going on today. For example, Tuesday might include “9am: Fence quote” and “Refactor subdomain validation method.” Each task might also contain its own list with notes about the task. For example, I might have the name and phone number of the fence company coming out to give the quote. As I finish things, I mark them as complete (⌘+Enter on my Macbook) so that they disappear from the list. If I don’t wind up getting to a task on the day I intended, I just drag and drop it to the next day’s list.

I also keep track of appointments on my iPhone’s calendar app, but add them to Workflowy at the beginning of each week so that I can plan each day with the appointments in mind.

In addition to a list for each day of the week, I have a list called Overall that contains tasks that I want to do soon but haven’t picked a specific day to do them yet. I drag tasks from the Overall list to specific days as I find time to work on them. Sometimes I also include non-specific tasks here just to keep them on my daily radar. For example, “Drink less coffee”.

I move tasks from the Medium Term and Long Term lists to the Short Term list as they get closer or as I have time to work on them. If I find myself with some unexpected free time or need a break from whatever I’m working on, I’ll sometimes just knock out a medium term or long term task even if there are still short term tasks still left to do.

Projects

My project list contains all of the projects and initiatives that I’m working on. I group similar projects together to make it easier to browse. For example, I have an Automattic group with several different WordPress.com projects that I’m working on (“.CO Integration”, “Domain Name Registration and Mapping Flow”), a Housework group (“Fence Replacement”, “Mulch Removal”), a Software group (“Lean Domain Search”, “Preceden”), a Hobbies group (“Poker”, “Photography”, “Reading”), and several others. I also have a Misc group for projects that can’t be grouped with other projects and a Potential Projects list for projects that I might want to work on one day.

How you organize the the individual project lists will depend on the type of project. For example, for my Lean Domain Search project I have a sublist called A/B tests which lists all of its ongoing and planned A/B tests, a Marketing list for different inbound and outbound marketing initiatives, and an Ideas list for potential development tasks.

I’d recommend for every project you have an Ideas list where you jot down ideas and potential tasks for that project. Tasks that go here are things that you haven’t committed to doing, but you might one day. If you eventually decide that you want to act on one of these ideas, move it to your Tasks list and figure out how soon you want to do it (Short Term, Medium Term, or Long Term).

You should jot down all project ideas you have, good and bad, so that you don’t have to hold them in your head forever. I’ve found that the quickest way to clearing my head is to just write it all down in Workflowy.

Notes

Finally, my Notes list contains miscellaneous notes and lists I’ve taken in the past. This includes “Command Line Reference”, “Gift Ideas”, “Startup Ideas”, “Product Keys”, “Printer Ink” (HP 564XL), “Microconf Notes” (2012 and 2013), “Server Configuration Steps”, “Recipes”, and much more. If it isn’t a task and isn’t related to a project, I throw it in the Notes list.

I’d also recommend having an Archive list within your Notes list where you can move notes and lists that you don’t need to reference often, but that you don’t want to permanently delete.

Wrapping Up

The structure I outlined above began as a much simpler one that I started with when I started using Workflowy. It evolved over time to suit my needs and you may or may not find it practical for you.

If you’re not a big list maker or note taker, I’d recommend starting very, very small and slowly creating a system that suits your needs. Regardless of what tool you use to track your tasks or take notes, the tool serves you, not the other way around. In other words don’t get too caught up in doing it “correctly” — it’s more important that you stick with it and organize it in a way that’s useful and practical for you.

If you have any questions or feedback about any of this, don’t hesitate to leave a comment or drop me an email. Thanks!

Update: See also Workflowy Organization v2.