Frameworks basados en metaheurísticas para resolver el problema de la mochila
Fuente:
Redalyc
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Artículo científico |
| Lingua: | es |
| Pubblicazione: |
Universidad de Carabobo
2019
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1876450368456491008 |
|---|---|
| author | Isela Jiménez-Castellano |
| author_facet | Isela Jiménez-Castellano |
| contents | Frameworks basados en metaheurísticas para resolver el problema de la mochila Isela Jiménez-Castellano Betania Hernández-Ocaña José Hernández-Torruco Oscar Chávez-Bosquez Ingeniería software Heurísticas optimización Actualmente existen frameworks que permiten reutilizar código diseñado ex profeso para resolver diversos problemas, entre los que destacan aquellos que implementan metaheurísticas para resolver problemas de optimización. El problema de la mochila es uno de los ejemplos de optimización clásicos usado a menudo como problema de prueba debido a su sencillez y al mismo tiempo su complejidad: pertenece a la categoría de problemas NP-Completos, considerados difíciles computacionalmente. En este artículo se implementaron los algoritmos de tres frameworks de metaheurísticas de diferentes familias para resolver una variante del problema: el problema de la mochila 0-1. Los frameworks seleccionados fueron: JACOF (Algoritmos de Colonia de Hormigas), JAMES (Algoritmos basados en Trayectoria), y MOEA (Algoritmos Evolutivos). Se desarrolló un prototipo de software incluyendo las metaheurísticas más representativas de cada framework y se utilizaron como benchmark un conjunto de instancias públicas del problema. Se diseñó un factor de finalización común para los algoritmos de cada framework, y a partir del diseño experimental se ejecutaron 30 pruebas por algoritmo cuyos resultados demuestran que JAMES obtienen mejores soluciones, aunque con mayor desviación estándar. Sin embargo, MOEA es el framework más sencillo de implementar, ya que implica menos líneas de código necesarias para resolver el problema. 2019 artículo científico 1316-6832 https://www.redalyc.org/articulo.oa?id=70758484005 https://www.redalyc.org/journal/707/70758484005/ https://www.redalyc.org/journal/707/70758484005/html/ https://www.redalyc.org/journal/707/70758484005/70758484005.epub https://www.redalyc.org/journal/707/70758484005/movil es http://www.redalyc.org/revista.oa?id=707 Revista INGENIERÍA UC application/pdf Universidad de Carabobo Revista INGENIERÍA UC (República Bolivariana de Venezuela) Num.1 Vol.26 |
| format | Artículo científico |
| id | redalyc_70758484005 |
| institution | Redalyc |
| language | es |
| publishDate | 2019 |
| publisher | Universidad de Carabobo |
| spellingShingle | Frameworks basados en metaheurísticas para resolver el problema de la mochila Isela Jiménez-Castellano Ingeniería software Heurísticas optimización Frameworks basados en metaheurísticas para resolver el problema de la mochila Isela Jiménez-Castellano Betania Hernández-Ocaña José Hernández-Torruco Oscar Chávez-Bosquez Ingeniería software Heurísticas optimización Actualmente existen frameworks que permiten reutilizar código diseñado ex profeso para resolver diversos problemas, entre los que destacan aquellos que implementan metaheurísticas para resolver problemas de optimización. El problema de la mochila es uno de los ejemplos de optimización clásicos usado a menudo como problema de prueba debido a su sencillez y al mismo tiempo su complejidad: pertenece a la categoría de problemas NP-Completos, considerados difíciles computacionalmente. En este artículo se implementaron los algoritmos de tres frameworks de metaheurísticas de diferentes familias para resolver una variante del problema: el problema de la mochila 0-1. Los frameworks seleccionados fueron: JACOF (Algoritmos de Colonia de Hormigas), JAMES (Algoritmos basados en Trayectoria), y MOEA (Algoritmos Evolutivos). Se desarrolló un prototipo de software incluyendo las metaheurísticas más representativas de cada framework y se utilizaron como benchmark un conjunto de instancias públicas del problema. Se diseñó un factor de finalización común para los algoritmos de cada framework, y a partir del diseño experimental se ejecutaron 30 pruebas por algoritmo cuyos resultados demuestran que JAMES obtienen mejores soluciones, aunque con mayor desviación estándar. Sin embargo, MOEA es el framework más sencillo de implementar, ya que implica menos líneas de código necesarias para resolver el problema. 2019 artículo científico 1316-6832 https://www.redalyc.org/articulo.oa?id=70758484005 https://www.redalyc.org/journal/707/70758484005/ https://www.redalyc.org/journal/707/70758484005/html/ https://www.redalyc.org/journal/707/70758484005/70758484005.epub https://www.redalyc.org/journal/707/70758484005/movil es http://www.redalyc.org/revista.oa?id=707 Revista INGENIERÍA UC application/pdf Universidad de Carabobo Revista INGENIERÍA UC (República Bolivariana de Venezuela) Num.1 Vol.26 |
| title | Frameworks basados en metaheurísticas para resolver el problema de la mochila |
| topic | Ingeniería software Heurísticas optimización |
| url | https://www.redalyc.org/articulo.oa?id=70758484005 https://www.redalyc.org/journal/707/70758484005/ https://www.redalyc.org/journal/707/70758484005/html/ https://www.redalyc.org/journal/707/70758484005/70758484005.epub https://www.redalyc.org/journal/707/70758484005/movil |