Entropy–Based Diversification Approach for Bio–Computing Methods
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 al...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-09-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/9/1293 |
| _version_ | 1827661244038905856 |
|---|---|
| author | Rodrigo Olivares Ricardo Soto Broderick Crawford Fabián Riquelme Roberto Munoz Víctor Ríos Rodrigo Cabrera Carlos Castro |
| author_facet | Rodrigo Olivares Ricardo Soto Broderick Crawford Fabián Riquelme Roberto Munoz Víctor Ríos Rodrigo Cabrera Carlos Castro |
| author_sort | Rodrigo Olivares |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T00:05:45Z |
| format | Article |
| id | doaj.art-dd7ceb4fa3064d388c43dbc15ee6d077 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T00:05:45Z |
| publishDate | 2022-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-dd7ceb4fa3064d388c43dbc15ee6d0772023-11-23T16:09:14ZengMDPI AGEntropy1099-43002022-09-01249129310.3390/e24091293Entropy–Based Diversification Approach for Bio–Computing MethodsRodrigo Olivares0Ricardo Soto1Broderick Crawford2Fabián Riquelme3Roberto Munoz4Víctor Ríos5Rodrigo Cabrera6Carlos Castro7Escuela de Ingeniería Informática, Universidad de Valparaíso, Valparaíso 2362905, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Universidad de Valparaíso, Valparaíso 2362905, ChileEscuela de Ingeniería Informática, Universidad de Valparaíso, Valparaíso 2362905, ChileEscuela de Ingeniería Informática, Universidad de Valparaíso, Valparaíso 2362905, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileDepartamento de Informática, Universidad Técnica Federico Santa María, Valparaíso 2390123, ChileNature–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.https://www.mdpi.com/1099-4300/24/9/1293Shannon entropybio–computing methodsimproved global searchmultidimensional knapsack problem |
| spellingShingle | Rodrigo Olivares Ricardo Soto Broderick Crawford Fabián Riquelme Roberto Munoz Víctor Ríos Rodrigo Cabrera Carlos Castro Entropy–Based Diversification Approach for Bio–Computing Methods Entropy Shannon entropy bio–computing methods improved global search multidimensional knapsack problem |
| title | Entropy–Based Diversification Approach for Bio–Computing Methods |
| title_full | Entropy–Based Diversification Approach for Bio–Computing Methods |
| title_fullStr | Entropy–Based Diversification Approach for Bio–Computing Methods |
| title_full_unstemmed | Entropy–Based Diversification Approach for Bio–Computing Methods |
| title_short | Entropy–Based Diversification Approach for Bio–Computing Methods |
| title_sort | entropy based diversification approach for bio computing methods |
| topic | Shannon entropy bio–computing methods improved global search multidimensional knapsack problem |
| url | https://www.mdpi.com/1099-4300/24/9/1293 |
| work_keys_str_mv | AT rodrigoolivares entropybaseddiversificationapproachforbiocomputingmethods AT ricardosoto entropybaseddiversificationapproachforbiocomputingmethods AT broderickcrawford entropybaseddiversificationapproachforbiocomputingmethods AT fabianriquelme entropybaseddiversificationapproachforbiocomputingmethods AT robertomunoz entropybaseddiversificationapproachforbiocomputingmethods AT victorrios entropybaseddiversificationapproachforbiocomputingmethods AT rodrigocabrera entropybaseddiversificationapproachforbiocomputingmethods AT carloscastro entropybaseddiversificationapproachforbiocomputingmethods |