March 31, 2017

Unlocking Genetic Algorithms

When it comes to creating artificial intelligence, we can attempt to mimic the same process that nature uses to push species forward through the process of evolution. After all, why reinvent all of life when the answers already exist? By taking the simple approach of the 'survival of the fittest', we can create simulations that start off with a seemingly random population of organisms, and through the process of selection and cross-breeding, cultivate a type of organism that is really good at solving a given problem.

To do this we can employ the use of a Genetic Algorithm (GA) that is inspired by the very process of natural evolutionary selection. Although there are many machine learning algorithms that we can utilise, we’re going to start with a GA for the simple reason that this is nature’s algorithm of choice. There are, however, a few downsides to this approach, as I will highlight further on.

Nature’s algorithm

Everything that exists in nature exists in a vast, highly complex system. Every element has the possibility to interact with every other element and affect it in some way. It is impossible to isolate any one parameter as everything is so intrinsically linked. If progress is to occur in a given species, it must happen in tandem with every other species around it. Even if you live under a rock, you cannot escape the interconnectedness of the universe. In nature, the simple rule is that if a species continues to adapt to its ever-changing environment, the future of its kind will live on, albeit ungratefully. When you look at a problem over a long timescale, it is easy to see why the organisms that adapted to their environment the best are the ones that are left standing at the end.

Nature doesn’t provide any special help to any of its inhabitants, but rather rewards them for being able to play by its rules. This puts the responsibility solely on the individual without the need of any external help. Through this continuous process of natural selection, nature has managed to created a massively diverse range of life that is specially suited to its region on Earth. The human mind is arguably the most complex thing to emerge from this process, which highlights the power of such a relatively simple algorithm. But nature has also had 4 billion years to achieve this. Whilst it is a massively powerful algorithm, it is rather slow. It is also important to note that - as far as we know - nature is not using this algorithm to achieve a certain goal. Instead anything goes, and whatever emerges is a success / a piece of art / magical / what it is.

This is great news for creating emergent characteristics as this algorithm is perfectly suited to generative outputs. However, if we’re trying to recreate an artificial mind that shares similarities with a biological one, we’re going to have to be a bit more precise. This will come later however. For now, we’ve only just started exploring, and the promise of GAs is of great interest.

Why Genetic Algorithms?

What advantages then does a GA have over other machine learning algorithms? As mentioned previously, GAs are highly suited to incredibly complex environments where it is impossible to know and control all the different parameters. If our artificial mind ever comes into being, it will be expected to operate within such a complex environment and as such would need to be highly adaptable and capable of making sense of all the data it would be receiving. This is an impossible task to plan and build for, so some element of trial and error would be necessary, allowing the algorithm to choose the most suitable parameters to solve the given problems. Whilst a GA is not the most efficient at achieving a solution when the problem is well understood, it shines when deployed on problems that contain many unknowns. If we’re looking for a general all-purpose algorithm, this is a good place to start.

The Basic Structure

There are some important terms to know when talking about GAs.

Every living organism has a set of instructions that not only determine how it is composed of the smallest building blocks of life, but also how it behaves within its environment. These instructions are encoded into the genes of the organism and are connected together to form sets of chromosomes.

In a GA, the genes are represented by the settings or attributes that are encoded for each organism. We can use the term genotype when talking about the collection of genes or settings for each organism and the phenotype as the physical expression of the genes, or the organism itself. Although this isn't so relevant to this post it's useful to make this distinction now.

The beauty of a GA lies in just how simple it is. There is no need for complex math since a GA just uses brute computational force to try every possible scenario, picking the best solution each time and repeating the process. Dumb, but very powerful.

A typical GA generally has the following components;

Initialisation

A population of randomly assigned agents is generated. Each agent is a potential solution to the problem we’re trying to solve.

Fitness Function Calculation

Each agent is then evaluated to see how well it solves the problem we want it to solve. Some agents may do very well, whilst others may do poorly. The whole spectrum is usually present within a GA sample.

Crossover

The agents that scored the highest get to influence those that didn’t do so well in an attempt to give them the abilities to better solve the problem. This is achieved by ‘breeding’ agents together and sharing parts of their internals to create a ‘healthier’ overall population.

Mutation

As shown previously, mutation is key to diversity and is vital in the realm of GAs to push an agent into a every random possibility so that all possibilities are effectively considered.

Termination

Evolution can and will continue forever, but we don’t have the luxury of time to wait for this. Once the pool of agents achieves an acceptable level of competency, we can end the simulation leaving us with the solutions that best solve the problem.

Can I get that in Pink?

The following is a simple demo of how a GA goes through all of its steps to find a specific colour. This cycle continues to run until a threshold of 95% is achieved. If you turn autorun off, you can call any part of the algorithm in any order. What you will find when you try this however, is that the algorithm doesn't always function as expected. For example, if you never use the mutation button, the GA will generally fail to get close enough to the colour it's looking for.

Autorun

Set Goal

Initialise Population

Fitness Function Calculation

Crossover

Mutation

Check / Termination

Although this is a very simple program, it outlines the basic process of a GA. This particular algorithm can be assigned to many different problems but generally keeps the same structure.

If it still isn't clear what's going on above, here is the psuedo code for a generic GA. If you want to build one yourself, chances are the structure will follow this.

GA( ) {

 initialize a random population

 find the fitness of the population

 while (termination criteria is reached) do the following {

  select parents

  breed/crossover all individuals with probability, Pc

  mutate all individuals with probability, Pm

  check fitness of population

  select survivors for next round

  run next round

 }

}

That's pretty much the basics - now go forth and solve all the impossible problems of the world! Or better yet, find all the solutions to problems that don't exist #innovation.

next

Minimum Viable Brain

To tackle the mammoth task of emulating brain functions, we better start by making it easier for ourselves. The approach here will be to whittle it down into the most basic form and then work our way up.