Deep learning algorithms are very popular and used in many machine learning and artificial applications, from forecasting to autonomous cars. However, one of the downsides of deep learning architecture is that these structures have a lot of differentiable parameters that require a lot of training data, often a lot of compute resources, often multiple machines, and need dense sampling to map input space to output space to model even simple functions reliably. Genetic algorithms are among the more popular, more straightforward alternative sets of algorithms. These are inspired by the evolutionary process of natural selection and are built on operations mimicking nature, such as biologically chromosome-based mutation, crossover, and selection. The genetic algorithm can learn abstract simple discriminative functions with fewer examples that describe the data and require much less sampling of input space to produce a solution. The reason for the lack of adaptation of these algorithms, just like symbolic AI , is the difficulting of building large scalable solutions, which is one of the significant advantages of deep nets.
This article will look at the basic intuition behind these algorithms using a set of essential python functions and building from scratch.
The basic algorithm will involve selecting parents from the population, crossover(mating) of best parents, mutation of child chromosome, and then repeating the process until we converge on a solution.
The basic unit of analysis will be a chromosome, a more fancy word for any data structure that encodes a possible solution to the problem at hand. A chromosome can be a string, an array, a list, etc. An individual also has a "fitness" score; this is a number that represents how good a solution to the problem this individual is.
The biological equivalent may be how much an organism suits its given habitat. Based on evolutionary theory, evolution will guide the slow iteration process in the organism gene pool for maximizing fitness related to the environment.
In this example, a gene will be represented by a bit. Each individual will have a collection of genes, which will be integer values.
The population is a collection of individuals. We will consider the population a list of data structures used to run crossover and mutation operations.
Crossover, or the mating of two parents to produce a child, will be an operation to pick genes from both parents randomly.
A mutation operation is a random change in a child's chromosome, which will simply be inverting one of the bits or genes randomly.
The overall genetic algorithm is more straightforward than backpropagation based on gradient descent as used in deep neural nets.
It will involve performing the above operations and repeating the process till a solution is reached.
Let's start a factory scenario where a set of sensors is installed on the manufacturing line. The value of one by all nine sensors will indicate the optimum working of the factory. Hence, in this case, we will use the genetic algorithm to find all one's space from all viable populations.
Let's start by creating two chromosomes and writing out the crossover function. Fitness function is highest for all ones. The mutation operation will randomly invert genes or bits based on the mutation rate provided.
Now that we have set up our two primary operations for mutation and crossover let's create a training function for 50 tries to see if we can find the optimum solution for all ones. Hence will loop over for 50 shots, run crossover and mutation operations on each successive child, and store results for plotting.
The output hovers between values and never converges to 1 due to random selection. However, we are still one crucial ingredient of parent selection to make the randomness work to connect to a final solution.
Let's write a function to sort fitness in a population and select a parent for crossover. I will just select the two fittest parents from the population during each cycle or iteration and add the child to the current population.
Now, run the training loop for 50 iterations, and this time the algorithm will converge to the best solution within the population.
Overall the above example may feel a little contrived however it simply illustrates the learning process of genetic algorithms. The chromosome described in the example can be extended to more complex data structures and applications and the fitness function. For more advanced use cases, genetic computation frameworks such as DEAP for python can be used.
