Now Reading
Beginner’s Guide To Genetic Algorithms


Beginner’s Guide To Genetic Algorithms


Source: DeepMind

Everything in this universe is governed by one principle- to achieve equilibrium. Things appear and disappear in this process. Life appeared out of chemical imbalances or thermal and electrical gradients in the primordial soup.

The design of life is often very simple; it's the scientific tools that humans make it difficult to decipher. The trick of nature is to find the most optimal solution to every problem. There is no other way around. Unless the right strategy for survival is identified, it keeps on mutating towards a single effective solution.



This aspect can be seen across various building blocks of life on earth.

The frugality of their movements can be replicated in everyday networking problems faced by humans. For instance, the travelling salesman problem is one such idea, which deals with finding the shortest distance between two or more distinct points.

Choosing a better move correctly and quickly is a fundamental skill of living organisms that corresponds to solving a computationally demanding problem.

For instance, a unicellular plasmodium of Physarum polycephalum searches for a solution to the travelling salesman problem (TSP) by changing its shape to minimise the risk of being exposed to aversive light stimuli.

Genetic algorithms have already demonstrated the ability to made breakthroughs in the design of such complex systems as jet engines.

The theme of genetics can be applied to computer algorithms. If something doesn’t work it should terminate. Over the years many algorithms have been built to weed out the interruptions.

How Do Genetic Algorithms Work

Genetic algorithms were introduced in the 1960s by John H Holland which were later improvised by Goldberg in the late eighties.

Initial attempts to integrate computer science with evolution didn’t go as expected because the techniques employed, relied on mutation rather than mating to generate new gene combinations.

Holland worked on creating a genetic code that could represent the structure of any computer program. This resulted in a classifier system with conditions are represented by a string of bits. The presence of a characteristic is taken as ‘1’ the absence of which is considered as ‘0’

For example, a classifier rule that recognised flowers might be encoded as a string containing 1’s for the bits corresponding to “petals”, “leaves”, “pollination” or “aroma”. And, 0’s for the bits corresponding to “tails”, “barking” or “stock prices”.

A population of random strings 1’s and 0’s can be rated according to the quality of the result. The measure of fitness could be profits from stock market prices or image classification(1’s or 0’s).

High-quality strings mate while the low-quality ones perish. With every generation, these mutations result in predomination of improved solutions.

The search for a good solution in a genetic algorithm context is the search for particular binary strings.

Biological chromosomes cross over one another when two gametes meet to form a zygote similar to the process of crossover in genetic algorithms. The resulting offspring does not replace the parent strings; instead they replace low-fitness strings, which are discarded at each generation so that the total population remains the same size.

Source: John H. Holland

The most important aspect of these mutations is that not only advance the search for solution, but they provide a strategy to keep on evolving by terminating the uniformity in population which leads to termination of evolution itself.

The regions of solution space, mapped by genetic algorithms would be searched for target regions. So those strings which are in target regions but are not the fittest, are more prone to be selected in the offspring for the next generation.

A statistician would need to evaluate dozens of samples from thousands or millions of regions to estimate the average fitness of each region. The genetic algorithm manages to achieve the same result with far fewer strings and virtually no computation.

A string with 1101 is a member of both 11 and also 11. Here ‘’ represents unspecified bit’s value.

The regions that contain many unspecified bits will be sampled by a large fraction of strings in a population. This nature of implicit parallelism gives genetic algorithm a certain advantage over other processes.

The implicit parallelism of genetic algorithms comes in handy while solving nonlinear problems; problems where the fitness of two binary strings is relatively closer. This leads to an explosion of possibilities. But, many compact building blocks repeat themselves and can be considered good enough to exploit to attain above average performance and use the results automatically into the next generation.

Applications Of Genetic Programming

The design of a turbine involves at least 100 variables, each of which can take on a different range of values. The resulting search space contains more than 10387 points.

See Also

The testing of a turbine considers constraints like the shape of the walls, pressure, flow at various points in the cylinder; turbulent or not and other such factors.

Simulating the jet engine for every constraint and then searching for solution is a tedious job for the engineers.

A group of researchers at General Electric put a genetic algorithm to use in the design of high-bypass jet engine turbine such as those that power commercial airliners. These turbines, which consist of multiple stages of stationary and rotating blade rows enclosed in a roughly cylindrical duct, are at the centre of engine-development projects that last five years or more and consume up to $2 billion.

Engineers equipped with such expert systems are able to design the engine with twice the improvements in less than a day which otherwise would have taken eight weeks.

In the context of machine learning, the use of genetic algorithms looks even more obvious with its rule-based characteristics and measuring the fitness of the solutions.

The goal of any machine learning model is to come up with optimal solutions irrespective large, less or no prior data.

Getting to the target solution in a swarm of data points requires devouring on historical results while stating close to the reality in order to avoid overfitting. Converging on the approximate solution is done by various methods of which stochastic optimisation method is one. Probabilistic model-building genetic algorithms are a part of stochastic optimisation methods.

These algorithms generate new solutions using an implicit distribution defined by one or more variables. These evolutionary algorithms use an explicit probability distribution encoded by a Bayesian network.

Hyperparameter selection is a key task in improving neural networks and the implicit characteristic of genetic algorithms to implicitly search for best-fit strings makes it a suitable contender for machine learning and AI applications as well along with other optimisation problems.

“As massively parallel computers become more common, it will be feasible to evolve software populations whose size more closely approaches those of natural species. Each processor can be devoted to a single string because the algorithm's operations focus on single strings or, at most, a pair of strings during the crossover. As a result, the entire population can be processed in parallel.,” explains John H. Holland about genetic algorithms.

Know how to implement genetic algorithms in Python here.



Register for our upcoming events:


Enjoyed this story? Join our Telegram group. And be part of an engaging community.


Our annual ranking of Artificial Intelligence Programs in India for 2019 is out. Check here.

Provide your comments below

comments

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
Scroll To Top