Entropy–Based Diversification Approach for Bio–Computing Methods

Rodrigo Olivares, Ricardo Soto, Broderick Crawford, Fabián Riquelme, Roberto Munoz, Víctor Ríos, Rodrigo Cabrera, Carlos Castro

Research output: Contribution to journalArticlepeer-review

Abstract

Nature–inspired computing is a promising field of artificial intelligence. This area is mainly devoted to designing computational models based on natural phenomena to address complex problems. Nature provides a rich source of inspiration for designing smart procedures capable of becoming powerful algorithms. Many of these procedures have been successfully developed to treat optimization problems, with impressive results. Nonetheless, for these algorithms to reach their maximum performance, a proper balance between the intensification and the diversification phases is required. The intensification generates a local solution around the best solution by exploiting a promising region. Diversification is responsible for finding new solutions when the main procedure is trapped in a local region. This procedure is usually carryout by non-deterministic fundamentals that do not necessarily provide the expected results. Here, we encounter the stagnation problem, which describes a scenario where the search for the optimum solution stalls before discovering a globally optimal solution. In this work, we propose an efficient technique for detecting and leaving local optimum regions based on Shannon entropy. This component can measure the uncertainty level of the observations taken from random variables. We employ this principle on three well–known population–based bio–inspired optimization algorithms: particle swarm optimization, bat optimization, and black hole algorithm. The proposal’s performance is evidenced by solving twenty of the most challenging instances of the multidimensional knapsack problem. Computational results show that the proposed exploration approach is a legitimate alternative to manage the diversification of solutions since the improved techniques can generate a better distribution of the optimal values found. The best results are with the bat method, where in all instances, the enhanced solver with the Shannon exploration strategy works better than its native version. For the other two bio-inspired algorithms, the proposal operates significantly better in over 70% of instances.

Original languageEnglish
Article number1293
JournalEntropy
Volume24
Issue number9
DOIs
StatePublished - Sep 2022
Externally publishedYes

Keywords

  • bio–computing methods
  • improved global search
  • multidimensional knapsack problem
  • Shannon entropy

Fingerprint

Dive into the research topics of 'Entropy–Based Diversification Approach for Bio–Computing Methods'. Together they form a unique fingerprint.

Cite this