Nature does not hurry yet everything is accomplished.

There is no better teacher than nature herself , she never rushes but everything is established. Have you ever wondered how our human brain is able to distinguish thousands of dog breeds from cats' even if we had never seen few of the breeds before too? How do ants find their way to the food? Let's learn about algorithms inspired from mother nature and know their applications in varied fields !

Contents

• Optimisation Algorithm
  • Important terms
  • Deterministic algorithms
  • Stochastic algorithms
    • Heuristic
    • Metaheuristic
      • population based
      • trajectory based
• Nature inspired algorithm
  • Physics inspired
  • Chemical inspired
  • Biological Inspired
    • Evolutionary algorithms
    • Bio inspired Algorithms
    • Swarm Intelligence optimisation
• Conclusion

Point	Nature Inspired Algorithms
What is it?	Algorithms replicating the core principle of an natural process
Examples	Harmony Search Algorithm (HSA), Black hole search Algorithm (BHS), Swarm Intelligence-based Algorithms like Bat Algorithm (BatA) and more.
Applications	Finding the Shortest Path, Solving difficult Optimization Problems

Optimisation Algorithms

Optimisation algorithms are algorithms that tend to find the best solution possible for a problem. It can be classified into two types :- deterministic and stochastic.

Some important terms -

Global , local optima :
Local optima - Most optimal solution in the local space i.e within a certain domain.
Global optima - General optimal solution in global space i.e. for overall problem and is not defined for a set.

Objective function :
Function in the form f = ax+by to solve optimization problems in linear programming.An objective function attempts to maximize profits or minimize losses based on a set of constraints and the relationship between one or more decision variables.
Fitness function :
Fitness Function (also known as the Evaluation Function) evaluates how close a given solution is to the optimum solution of the desired problem.It is also a type of objective problem.

Deterministic

A set of rules are followed to reach the most optimised solution.Common programming methods like dynamic programing , linear and non-linear programming are few examples.Deterministic algorithms always give the same output for a given input and donot change from time to time.

Stochastic

Stochastic algorithms or non deterministic algorithms are random in nature and tend to provide different solutions .Stochastic algorithms tend to explore several regions of search space at same time and they have the capability to escape from local optima to global optima i.e. from case specific solution to a more generalised solution. Thus they can be helpful in solving NP-Hard problems whose polynomial time complexity solution is not yet found through deterministic methods.

There are two types of stochastic algorithms - Heuristic and Meta Heuristic

Heuristic

Heuristic algorithm is where the optimal solution is found through hit and trial method.All the possible solutions are explored and seen which one is the optimal one and returned.Can have a heavy toll with respect to time and may never give optimal solution.

Metaheuristic

Metaheuristic algorithms explore the optimal solution through both randomness factors and a set of pre-defined rules.They utilise the best of both heuristic and deterministic features. Metaheuristic algorithms can be furthur classified to two types - Population based and Trajectory based.

Population based approach -
An algorithm that maintains an entire set of candidate solutions, each solution corresponding to a unique point in the search space of the problem.
They use multiple agents to search for an optimal or near-optimal solution.In population-based optimization methods, proper control of exploration (global search) and exploitation (local search) is important in finding the optimum solution efficiently in search space.

Trajectory based approach -
A single agent or solution which moves through the design space or search space in a piecewise style. A better move or solution is always accepted, while a not-so-good move can be accepted with certain probability.The steps or moves trace a trajectory in the search space, with a non-zero probability that this trajectory can reach the global optimum.

Nature inspired computing paradigm

Every object in Universe wants to achieve stability , a state of equilibrium.Universal entities have their own unique ways to achieve a state of stability, an optimal solution .

Nature inspired algorithms are a domain of metaheuristic algorithms that mimic natural phenomena by combining randomness and defined rules.

Nature inspired algorithms come in handy when -

• Conventional approaches are not able to solve the problem.
• The problem is highly complex and involves many parameters , objectives , when it possesses a great deal of nonlinearity.

For Example , take travelling salesman problem with constraints like minimum cost by traversing each town atmost once . It cannot be solved in polynomial time using deterministic algorithms. In such cases , metaheurisitc algorithms especially nature inspired algorithms can give much needed
answers!

Nature Inspired algorithms are of three types based on inspiration modes - Physics , Biology , Chemistry. We will go through selected and interesting algorithms in brief to get a gist of how nature inspired algorithms work , how the algorithms are formulated by natural inspiration.

Physics Based Algorithms

Algorithms that are inspired from physics phenomena be it thermodynamics , electromagnetism , gravitational forces and so on.
We will be learning about few interesting physics based algorithms amongst many such algorithms!There are more such algorithms like gravitational search algorithm , big bang crunch etc.

• Simulated Annealing

If the heating temperature is sufficiently high to ensure random state and the cooling process is slow enough to ensure thermal equilibrium, then the atoms will place themselves in a pattern that corresponds to the global energy minimum of a perfect crystal.

As we know every entity in the universe is seeking stability , to attain equilibrium. Simulated annealing takes the advantage of this property of universe which is prevalent field of thermodynamics.
Simulated annealing is an algorithm inspired from the heating-cooling process of metals. We know that in solids,particles are closely packed and which could have defects due to fracture or tightness.But when the solid is heated the atoms become active and randomly move due to the new found freedom as they have more energy.The metal molecules are then cooled down so that they reach a certain stability and settle. This method is used when we need to find global optima as most of the particles when they settle , they would do so at most optimum position.

It is a trajectory based algorithm.

• Harmony Search Algorithm (HSA)

During concerts you might have observed that when singers sing spontaneouosly they first sing few notes and see whether the notes are in harmony with music being played , if yes they continue to sing them continously , else they experiment with other notes to accordingly suit the music. This principle is applied in case of harmony search algorithm,where different candidates are experimented to see and generate the solution , if the solution is better than worst ones then it is updated , best amongst is chosen and observed whether is it reaching global optimum.It is a population based algorithm as we are using set of solutions and finding the global optimum.

• Black hole search Algorithm (BHS)

Black hole is a celestial entity with infinite mass concentrated in a very microscopic volume(singularity) that bends the fabric of time-space and the gravity within is so high that even light cannot escape.Event Horizon is space where even light cannot escape and the gravity is very high!

Black Hole: In black hole algorithm, the best candidate among all the candidates at each iteration is selected as a black hole.
Stars: All the other candidates form the normal stars. The creation of the black hole is not random and it is one of the real candidates of the population.
Movement: Then, all the candidates are moved towards the black hole based on their current location and a random number.

1. Black hole algorithm (black hole) starts with an initial population of candidate solutions to an optimization problem and an objective function that is calculated for them.
2. At each iteration of the Black Hole, the best candidate is selected to be the black hole and the rest form the normal stars. After the initialization process, the black hole starts pulling stars around it.
3. If a star gets too close to the black hole it will be swallowed by the black hole and is gone forever. In such a case, a new star (candidate solution) is randomly generated and placed in the search space and starts a new search.
   The Black Hole algorithm converges to global optimum in all the runs while the other heuristic algorithms may get trapped in local optimum solutions like genetic algorithm, Ant colony Optimization algorithm simulated Annealing algorithm.

The black hole algorithm can be applied to solve the clustering problem and can run on different benchmark datasets.

• Water Drop Algorithm

In rivers we can see flowing of water from one place to another through a path. The paths of water flow have been created by a collection of water drops. It’s also observed that the undertaken path by the rivers seems to be an optimal path in terms of distance travelled by the water.
One of the important properties of flowing water is its velocity. Water drops flowing from one place to another will carry some amount of soil along with it. The soil is usually transferred from fast parts of the path to slow parts of the river. The carried soils will be unloaded in the slower beds of the river.
The following properties are assumed for a flowing water drop in a river:

• A water drop with higher velocity removes more soil than a water drop with lower velocity .
• The velocity of a water drop increases more on a path with low soil than a path with high soil.
• Water chooses an easier path with less soil than a harder path with more soil.

Chemistry Based Algorithms

Chemical reaction optimisation (CRO)

CRO algorithm has attracted the attention of machine learning and cognitive computation community over the past few years and has been successfully applied in several real- world optimization problems.CRO is inspired by the nature of chemical reactions . Usually chemical reactions occur to convert unstable compounds with excess energy to stable ones.This property is embedded in CRO to solve optimization problems, CRO has been used to solve a broad range of engineering problems, including the quadratic assignment problem, neural network training, multimodal continuous problems, etc.

Other Chemistry inspired algorithms include artificial chemical process algorithm (ACPA) based on the principles of artificial chemical, processartificial chemical reaction optimization (ACRO) based on a different set of bi-molecular and uni-molecular chemical reactions different from CRO including redox (reduction-oxidation) reactions, chemical reaction algorithm (CRA) based on the principles of artificial chemistry , and Gases Brownian motion optimisation (GBMO) algorithm based on the laws of Brownian motion and turbulent rotation motion of gas molecules

Biology Based Algorithms

Neural networks working can be best described as nature inspired models , which try to mimic brain's neurons to learn the features and further predict or classify .

Biology based algorithms can be classified into three categories

Evolutionary algorithms

A population based metaheuristic biological inspired algorithm which is inturn inspired by biological mechanisms like reproduction , mutation , recombination and selection.

Types of EAs include :

• Genetical Algorithms
• Differential evolution
• Genetic programming
• Evolutionary programming
• Evolution strategy
• Neuroevolution
• Learning classifier system

Bio inspired algorithms

These algorithms are inspired from commonly observed phenomenon in animals like flock of birds,schools of fish and so on.Particle Swarm Optimisation (PSO) simulates social behaviour of swarms such as birds flocking and fish schooling in nature.
One of the Bio inspired Algorithm -

• L-systems

  L-systems(Lindenmayer systems) were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist .Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of plant development.
  
  L-systems are a recursive, string-rewriting framework, commonly used today in computer graphics to visualize and simulate organic growth, with applications in plant development, procedural content generation, and fractal-like art.
  lets take an example : We have starting letter - A , we can convert it into AB i.e. ever A->AB and every B->A.

So A
AB(A->AB)
ABA (A->AB and B->A)
ABAAB(A->AB , B->A and A->AB)
... and so on.

Some other well known algorithms include Artificial Immune systems(AIS) that stipulate the interaction between antibodies mathematically,Biogeography Based Optimisation (BBO).
There are other bio-inspired search and optimisation algorithms which are less known such as atmosphere clouds model, dolphin echolocation, Japanese tree frogs calling, Egyptian vulture, flower pollination algorithm, great sal- mon run, invasive weed optimisation, paddy field algorithm.

Swarm Intelligence-based Algorithms

The SIA are based on the idea of collective behaviours of insects living in colonies such as ants, bees, wasps and termites. Researchers are interested in the new way of achieving a form of collective intelligence called swarm intelligence. SIAs are also advanced as a computational intelligence technique based around the study of collective behaviour in decentralised and self-organised systems.

• Ant Colony Optimisation (ACO)
  Ant Colony Optimization is inspired from the behavior of a real ant colony, which is able to find the shortest path between its nest and a food source (destination).While moving, ants leave a chemical pheromone trail on the ground. When choosing their way, they tend to choose paths marked by strong pheromone concentrations. The pheromone trails will guide other ants to the food source. It has been shown that the indirect communication between the ants via pheromone trails enables them to find the shortest paths between their nest and food sources.
• Bat Algorithm (BatA)
  It is inspired by the echolocation behavior of bats. The capability of the echolocation of bats is fascinating as they can find their prey and recognize different types of insects even in complete darkness
• Bacterial Foraging Optimisation Algorithm (BFOA)

Bacteria search for nutrients in a such a way that the energy obtained per unit time is maximised. Each bacterium communicates with others by sending signals.
Foraging means essentially hunting and gathering and flagella helps in foraging.
Bacteria is equipped with flagella - which helps it in locomotion. So the bacteria can either swim or tumble using this flagella while foraging.
BFO consists mainly of four behaviors: chemotaxis, swarming, reproduction, and elimination-dispersal.

Chemotaxis- The process, in which a bacterium moves by taking small steps while searching for nutrients, is called chemotaxis and key idea of BFOA is to replicate chemotactic movement of virtual bacteria in the problem search space.In areas with more food , bacteria tend to swim and in scarce places they tend to tumble .Why do they tumble? so that they can get more search space for potential food sources.

Swarming- Ability of bacteria to arrange in swarms/groups .

Reproduction - The bacteria that would be weak at finding food will be eliminated and the ones with strong abilities will split to produce an offspring .

Eliminate-dispersal - due to unexpected changes in environment , bacteria can face entire wipe out, if bacteria is arranged in swarms , isolated in group at a particular space.

It has already been applied to many real world problems and proved its effectiveness over many variants of GA(genetic algorithms) and PSO(particle swarm optimization).Future scope could possibly be in the fields of Mathematical modeling, adaptation, and modification of the algorithm.

Other algorithms include Firefly Algorithm (FA), Cuckoo Search (CS),wolf search, cat swarm optimisation,Artificial bee colony optimisation, fish swarm optimisation, eagle strategy, krill herd, monkey search and weightless swarm algorithms.

Conclusion

Thus we have learnt about nature inspired algorithms , their use cases and its types . An active field of research which is very vast and what we have discussed here is just a gist of what is happening. Nature inspired algorithms have been useful in determining positive results for np hard problems like travelling salesman etc.