Genetic Algorithm: How Evolutionary Search Finds Better Solutions

There are certain problems which are straightforward to optimise because the path to the solution is flat and mathematically well behaved.

Others are messy.

A delivery company might have hundreds of stops to assign to vehicles. A manufacturer may desire the optimum production schedule for several machines. A data scientist can potentially need to explore thousands of potential combinations of features.

When problems are of this type, it is often not feasible to check all possible solutions.

A genetic algorithm (GA) works in a different way. Rather than taking a single path to an answer, it operates on a set of potential solutions and continually refines those solutions with the help of ideas borrowed from the process of evolution in biology.

Start With a Population

The algorithm starts with a number of candidate solutions.

Suppose a logistics company in India wants to make an efficient route for their delivery vehicle to go to several locations.

Each of the possible orderings of those stops may be considered a candidate solution.

The algorithm doesn't begin with just a single route, but with multiple routes in a population. Some will be poor. Some may already be fairly efficient.

Now the algorithm has to be able to compare them.

Measure Fitness

Each candidate gets a fitness score.

In a route-planning problem, fitness may be based on distance or on fuel cost/delivery time.

The score may also penalize idle machines, missed deadlines and overtime for a manufacturing schedule.

The fitness function is important because it specifies what it means to be “better”.

An algorithm may well optimize the wrong goal if the goal itself is poorly designed.

Select Better Candidates

Selection is the next step.

Solutions with higher fitness scores have a higher probability of becoming parents to the next generation.

This is not necessarily the case where only one superior solution remains. There should be some diversity in the population since when searching for only a few similar candidates, the search can become stagnant and settle on a mediocre candidate.

The objective is to improve the quality of the candidates while not compromising diversity.

Mix Them Up: Crossover

The algorithm generates new solutions from parents using crossover.

Crossover is a blend of two parent solutions.

Let's say one route is good at serving the northern section of a city and another route is good at serving the southern section.

A child solution could benefit from parts of both solutions to form a crossover operation.

The actual crossover method is dependent on representation of the problem. A route can't be combined like a numerical parameter list.

Add Variation Through Mutation

If the algorithm would only recombine the solutions found, the population might quickly become too alike.

A small random change is brought by mutation.

Within a route, mutation could involve exchanging two stops. It could make very small changes to one of the parameters in a numerical optimisation problem.

Mutation presents an opportunity for the search to look at some things it couldn't see in the current population.

This random variation is why genetic algorithms can search a complex space much more widely than methods that take steps from one solution to the next.

Repeat Across Generations

After selection, crossover and mutation, the new candidates form the next generation.

They are assessed once again for fitness.

The process repeats:

Population → Fitness → Selection → Crossover → Mutation → New Population

Strong solutions are more prevalent in the long term.

The algorithm stops when it reaches a chosen number of generations, achieves a satisfactory fitness level or stops making meaningful improvements.

Why Do This?

Genetic algorithms are employed in situations where traditional optimization techniques are hard.

According to MathWorks, they are population-based optimisation methods that can solve well problems that are discontinuous, highly nonlinear, stochastic or poorly suited to standard optimisation methods.

They can be used in the application areas of scheduling, engineering design, routing, feature selection and parameter optimization.

The good thing about them is that they're flexible.

The algorithm doesn't need a smooth mathematical terrain, nor derivatives. It is primarily required to have a representation for candidate solutions and a fitness function to assess them.

What Are the Restrictions?

Just because a genetic algorithm is a type of optimisation, does not mean it is the optimal optimiser.

It could involve many assessments of the fitness function and may be more computing intensive than an appropriate classical optimisation method. It also cannot ensure that the optimum that it yields is the really optimum solution.

The results will vary depending on the number of individuals, the mutation rate, the type of cross-over and the stopping criteria.

Insufficient mutation can cause a loss of diversity. The search can become close to a random exploration if there is too much.

Extra care should be taken in designing the fitness function.

The Bigger Lesson

The best way to grasp a genetic algorithm is not to learn all the biological jargon.

It is to recognise the search strategy.

Rather than pruning one candidate solution until it becomes progressively more successful, the algorithm keeps track of numerous alternatives; it praises better candidate solutions; it populates them with useful features and continually varies them.

This is a significant instance of the fact that optimisation can transcend simple formulas, especially for beginners of data science and AI in India.

Sometimes the way to a good answer is not to calculate the answer directly.

It is to allow a set of possible solutions to compete, blend and evolve.