Bat algorithm

Last updated

The Bat algorithm is a metaheuristic algorithm for global optimization. It was inspired by the echolocation behaviour of microbats, with varying pulse rates of emission and loudness. [1] [2] The Bat algorithm was developed by Xin-She Yang in 2010. [3]

Contents

Metaphor

The idealization of the echolocation of microbats can be summarized as follows: Each virtual bat flies randomly with a velocity at position (solution) with a varying frequency or wavelength and loudness . As it searches and finds its prey, it changes frequency, loudness and pulse emission rate . Search is intensified by a local random walk. Selection of the best continues until certain stop criteria are met. This essentially uses a frequency-tuning technique to control the dynamic behaviour of a swarm of bats, and the balance between exploration and exploitation can be controlled by tuning algorithm-dependent parameters in bat algorithm.

A detailed introduction of metaheuristic algorithms including the bat algorithm is given by Yang [4] where a demo program in MATLAB/GNU Octave is available, while a comprehensive review is carried out by Parpinelli and Lopes. [5] A further improvement is the development of an evolving bat algorithm (EBA) with better efficiency. [6]

See also

Related Research Articles

<span class="mw-page-title-main">Microbat</span> Suborder of mammals

Microbats constitute the suborder Microchiroptera within the order Chiroptera (bats). Bats have long been differentiated into Megachiroptera (megabats) and Microchiroptera, based on their size, the use of echolocation by the Microchiroptera and other features; molecular evidence suggests a somewhat different subdivision, as the microbats have been shown to be a paraphyletic group.

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Particle swarm optimization</span> Iterative simulation method

In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formula over the particle's position and velocity. Each particle's movement is influenced by its local best known position, but is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

Swarm intelligence (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems.

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems.

In computer science and operations research, the artificial bee colony algorithm (ABC) is an optimization algorithm based on the intelligent foraging behaviour of honey bee swarm, proposed by Derviş Karaboğa in 2005.

<span class="mw-page-title-main">Bat</span> Order of flying mammals

Bats are mammals of the order Chiroptera. With their forelimbs adapted as wings, they are the only mammals capable of true and sustained flight. Bats are more agile in flight than most birds, flying with their very long spread-out digits covered with a thin membrane or patagium. The smallest bat, and arguably the smallest extant mammal, is Kitti's hog-nosed bat, which is 29–34 millimetres in length, 150 mm (6 in) across the wings and 2–2.6 g in mass. The largest bats are the flying foxes, with the giant golden-crowned flying fox, reaching a weight of 1.6 kg and having a wingspan of 1.7 m.

In mathematical optimization, the firefly algorithm is a metaheuristic proposed by Xin-She Yang and inspired by the flashing behavior of fireflies.

In operations research, cuckoo search is an optimization algorithm developed by Xin-She Yang and Suash Deb in 2009. It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of host birds of other species. Some host birds can engage direct conflict with the intruding cuckoos. For example, if a host bird discovers the eggs are not their own, it will either throw these alien eggs away or simply abandon its nest and build a new nest elsewhere. Some cuckoo species such as the New World brood-parasitic Tapera have evolved in such a way that female parasitic cuckoos are often very specialized in the mimicry in colors and pattern of the eggs of a few chosen host species. Cuckoo search idealized such breeding behavior, and thus can be applied for various optimization problems. It has been shown that cuckoo search is a special case of the well-known -evolution strategy.

<span class="mw-page-title-main">Meta-optimization</span>

In numerical optimization, meta-optimization is the use of one optimization method to tune another optimization method. Meta-optimization is reported to have been used as early as in the late 1970s by Mercer and Sampson for finding optimal parameter settings of a genetic algorithm.

Xin-She Yang is a Senior Research Scientist at National Physical Laboratory, best known as a developer of various heuristic algorithms for engineering optimization. He obtained a DPhil in applied mathematics from Oxford University. He has given invited keynote talks at SEA2011, SCET2012, BIOMA2012 and Mendel Conference on Soft Computing. He has been elected as a Fellow of the Institute of Mathematics and its Application in 2021. He has been on the prestigious list of Highly Cited Researchers since 2016 by Clarivate Analyatics/Web of Science.

In computer science, imperialist competitive algorithms are a type of computational method used to solve optimization problems of different types. Like most of the methods in the area of evolutionary computation, ICA does not need the gradient of the function in its optimization process. From a specific point of view, ICA can be thought of as the social counterpart of genetic algorithms (GAs). ICA is the mathematical model and the computer simulation of human social evolution, while GAs are based on the biological evolution of species.

<span class="mw-page-title-main">Enrique Alba</span> Spanish computer science professor (born 1968)

Enrique Alba is a professor of computer science at the University of Málaga, Spain.

Social cognitive optimization (SCO) is a population-based metaheuristic optimization algorithm which was developed in 2002. This algorithm is based on the social cognitive theory, and the key point of the ergodicity is the process of individual learning of a set of agents with their own memory and their social learning with the knowledge points in the social sharing library. It has been used for solving continuous optimization, integer programming, and combinatorial optimization problems. It has been incorporated into the NLPSolver extension of Calc in Apache OpenOffice.

Fish School Search (FSS), proposed by Bastos Filho and Lima Neto in 2008 is, in its basic version, an unimodal optimization algorithm inspired on the collective behavior of fish schools. The mechanisms of feeding and coordinated movement were used as inspiration to create the search operators. The core idea is to make the fishes “swim” toward the positive gradient in order to “eat” and “gain weight”. Collectively, the heavier fishes have more influence on the search process as a whole, what makes the barycenter of the fish school moves toward better places in the search space over the iterations.

In evolutionary computation, Minimum Population Search (MPS) is a computational method that optimizes a problem by iteratively trying to improve a set of candidate solutions with regard to a given measure of quality. It solves a problem by evolving a small population of candidate solutions by means of relatively simple arithmetical operations.

<span class="mw-page-title-main">Spiral optimization algorithm</span> Optimization algorithm

In mathematics, the spiral optimization (SPO) algorithm is a metaheuristic inspired by spiral phenomena in nature.

This is a chronological table of metaheuristic algorithms that only contains fundamental algorithms. Hybrid algorithms and multi-objective algorithms are not listed in the table below.

References

  1. J. D. Altringham, Bats: Biology and Behaviour, Oxford University Press, (1996).
  2. P. Richardson, Bats. Natural History Museum, London, (2008)
  3. Yang, X. S. (2010). "A New Metaheuristic Bat-Inspired Algorithm, in: Nature Inspired Cooperative Strategies for Optimization (NISCO 2010)". Studies in Computational Intelligence. 284: 65–74. arXiv: 1004.4170 . Bibcode:2010arXiv1004.4170Y.
  4. Yang, X. S., Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010).
  5. Parpinelli, R. S.; Lopes, H. S. (2011). "New inspirations in swarm intelligence: A survey". International Journal of Bio-Inspired Computation. 3: 1–16. doi:10.1504/ijbic.2011.038700. S2CID   16866891.
  6. Tsai, P. W.; Pan, J. S.; Liao, B. Y.; Tsai, M. J.; Istanda, V. (2012). "Bat algorithm inspired algorithm for solving numerical optimization problems". Applied Mechanics and Materials. 148–149: 134–137. Bibcode:2011AMM...148..134T. doi:10.4028/www.scientific.net/amm.148-149.134.

Further reading