Bio-Inspired Metaheuristics: A Comprehensive Survey

Bio-Inspired Metaheuristics: A Comprehensive Survey

Rachid Kaleche (Laboratoire d'Informatique Oran (LIO), Université Oran 1, Algeria), Zakaria Bendaoud (GeCoDe Laboratory, Saida University, Algeria) and Karim Bouamrane (Laboratoire d'Informatique Oran (LIO), Université Oran 1, Algeria)
Copyright: © 2020 |Pages: 18
DOI: 10.4018/IJOCI.2020100101
OnDemand PDF Download:
Available
$37.50
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

In real life, problems becoming more complicated, among them NP-Hard problems. To resolve them, two families of methods exist, exact and approximate methods. When exact methods provide the optimal solution in an unacceptable amount of time, the approximate ones provide good solutions in a reasonable amount of time. Approximate methods are two kinds, heuristics and metaheuristics. The first ones are problem specific, while metaheuristics are independent from problems. A broad number of metaheuristics are inspired from nature, specially from biology. These bio-inspired metaheuristics are easy to implement and provide interesting results. This paper aims to provide a comprehensive survey of bio-inspired metaheuristics, their classification, principals, algorithms, their application domains, and a comparison between them.
Article Preview
Top

Introduction

Nowadays, scientific and engineering communities are dealing with more and more complex and difficult/sophisticated problems. One type of these complex problems are the NP-Hard problems. They can be found in different important areas, for instance health, transportation, engineering conception for example, and have different natures: continuous or discrete, constrained or not constrained, mono or multi-objective, mono or multi modal. Their resolutions can be done either by exact methods or by approximate ones. Exact methods provide the optimal solution but after an unacceptable amount of time. However, approximate methods provide good solutions in a reasonable amount of time. There are composed of two types, heuristics which are problem-specific and metaheuristics which are independent from the problem to resolve.

Any metaheuristic explores a space of solutions in order to find the optimal one or at least a good one. It uses two important processes, namely, the diversification and the intensification. In the diversification step the metaheuristic explores the search space in its globality in order to find a promising area. On the other hand, in the intensification process, the metaheuristic exploits a local region to improve a solution. Because of the exponentiality of the search space, the metaheuristics explore it randomly hoping to find a solution of high-level quality in an acceptable amount of time. This trade-off between a reasonable amount of time and the goodness of the solution quality are among the main import advantages of metaheuristics.

In addition, among advantages of metaheuristics are the following list:

  • They are used where exact methods fail;

  • They have in most cases nature as an inspiration source: biology, physical phenomenon, …;

  • Their conception is easy, they liberate us from gradient complexity of objective function (Siarry, 2014);

  • They are generic; therefore, they are relevant to a broad number of problems (Siarry, 2014);

  • The duality intensification, diversification allows for the first to improve quality of a solution by exploring his neighbourhood; and for the second process to explore promising regions of the search space in order to enhance the global solution;

  • They accept a degradation of a current solution hopping to escape a local optimal trap and finding interesting solutions (Siarry, 2014).

Some of their drawbacks can be summarized as follows:

  • The convergence to optimal solution is not a guarantee;

  • They don’t give any information about the proximity of the solution obtained compared to the optimal solution;

  • Their behaviours depend on the tuning of their parameters; consequently, they depend on experiences and feelings of their users;

  • They suffer from a lack of theorical studies;

  • It is difficult to analyse their performance.

The most important number of metaheuristics are inspired from nature. This last, offers several natural methods to tackle complicated daily problems. In nature, insects, animals and other bio-organisms have developed capabilities to deal with complicated real-life problems. The used methods and the obtained results by these “non-intelligent” living beings to resolve daily complicated problems are amazing. Inspired by nature, researchers and engineers developed ingenious solutions to deal with industrial, health, transport and other problems.

Going from the fact that essential information about bio-inspired metaheuristics are dispatched within an important number of studies, consequently leading to make the research task more complicated. In addition, there is a lack of studies detailing and regrouping important information about bio-inspired metaheuristics. The aim is to offer to researchers and engineers a study within which they can find:

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 12: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 11: 4 Issues (2021)
Volume 10: 4 Issues (2020)
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing