|
Optimizing is finding the best solution for a specific problem. For practical problems, size of the solution space may be limited or widespread. When there are limited number of possibilities to solve a problem, all of them can be checked to find the best solution. However, there are hundreds, thousands, millions or trillions of solution candidates for some problems. Out of them, there may be several good solutions. However, there is only one best solution and it is called the optimized solution. When there are numerous possibilities in the solution space, it is impractical to check all of them in order to find the best solution. In such situations, optimization techniques can be used to find the best solution. One simple application is the "travelling salesman problem". The objective of it is to find the shortest path which connects number of cities. When there are only few cities, the shortest path can be found manually. However, when there are hundreds or thousands of cities, an optimization technique can be used to find the shortest path.
Among the optimization techniques, there are several nature-inspired methods developed by researchers after observing and analyzing many natural processes. Genetic Algorithm Optimization (GAO), Ant-Colony Optimization (ACO), Particle Swarm Optimization (PSO), Monkey Search Optimization (MSO) and Wind Driven Optimization (WDO) are some of the famous nature-inspired optimization techniques.
GAO is developed based on Darwin’s principle of evolution. The fundamental principle of natural selection is the main evolutionary principle that has been formulated by Charles Darwin, without any knowledge about genetic mechanism. The animals (or plants) best suited to their environment are more likely to survive and reproduce, passing on the characteristics which helped them survive to their offspring. i.e., the "survival of the fittest". GAO in particular became popular through John Holland's work in the early 1970s. He demonstrated the model's universality by applying GAO to economics, psychology, game theory, etc. GAO operates on a group of trial solutions in parallel. The individuals in the group compete to reproduce and pass on their characteristics to the next generation. At each generation, each individual solution is checked how well or bad it is and the least fit individuals are removed. Therefore, GAO assures the continuous improvement of the suitability.
Some nature-inspired methods rely on how certain animals optimize their path to find food. For an example, in an ant colony, ants optimize their route from the nest to the food. ACO technique is based on this phenomenon. At first, the ants wander randomly. When an ant finds a source of food, it walks back to the colony leaving "markers" (pheromones) that show the path has food. When other ants come across the markers, they are likely to follow the path with a certain probability. They populate the path with their own markers as they bring the food back. As more ants find the path, it gets stronger until there are a couple streams of ants traveling to various food sources near the colony. Because the ants drop pheromones every time they bring food, shorter paths are more likely to be stronger, hence optimizing the solution. Once the food source is depleted, the route is no longer populated with pheromones and slowly decays. James McCaffrey introduced the ACO algorithm.
PSO is another nature-inspired evolutionary optimization technique based on the movement and intelligence of swarms. Imagine a swarm of bees in a field with the goal of finding the location with the highest density of flowers in the field. The bees begin in random locations with random velocities looking for flowers. Occasionally, one bee may fly over a place with more flowers than had been encountered by any bee in the swarm. The whole swarm would then be drawn toward that location in additional to their own personal discovery. Eventually, the bees’ flight leads them to the one place in the field with the highest concentration of flowers. Soon, all the bees swarm around this point. PSO was developed in 1995 by J. Kennedy and R. Eberhart in attempting to model this behavior.
MSO is derived from the mountain climbing process of monkeys. When there are many mountains in a given field, monkeys climb up from their respective positions. When they reach a mountain top they search whether there are mountains around it higher than the present position. If so, the monkeys jump to the higher mountain and climb it. Ultimately, the monkeys reach the highest mountain.
The WDO technique is a new type of nature-inspired global optimization methodology and it is based on atmospheric motion. This technique is introduced by Dr. Bayraktar with his initial idea of the wind moving from high pressure points to low pressure points. It is mapped to the optimization where we want to move from low performing combinations to high performing combinations within a search space. At its core, a population of infinitesimally small air parcels navigates over an N-dimensional search space following Newton's second law of motion, which is also used to describe the motion of air parcels within the earth's atmosphere. Compared to similar particle based algorithms, WDO employs additional terms in the velocity update equation, providing robustness and extra degrees of freedom to fine tune the optimization.
In addition to these techniques, many more nature-inspired optimization methods are used in various fields such as Engineering, Medicine, Biology, Management, Business and Operations Research.
Dr. (Mrs.) J. M. J. W. Jayasinghe
Senior Lecturer - Department of Electronics
Wayamba University of Sri Lanka
|
