Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria

Un Sistema de Hormigas es un sistema artificial basado en el comportamiento de colonias de hormigas reales, que se utiliza para resolver problemas combinatorios. Este es un algoritmo distribuido compuesto por un conjunto de agentes cooperantes llamados hormigas que cooperan entre ellos para encontra...

Full description

Autores:
Aguilar, José
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2001
Institución:
Universidad Autónoma de Bucaramanga - UNAB
Repositorio:
Repositorio UNAB
Idioma:
spa
OAI Identifier:
oai:repository.unab.edu.co:20.500.12749/9077
Acceso en línea:
http://hdl.handle.net/20.500.12749/9077
Palabra clave:
Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Combinatorial optimization prohlem
Ant system
The graph partitioning and the traveling salesman problems
Innovaciones tecnológicas
Ciencias de la computación
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Problema de optimización combinatoria
Sistema de hormigas
la partición de grafos y los problemas del viajante de comercio
Desarrollo tecnológico
Rights
License
Derechos de autor 2001 Revista Colombiana de Computación
id UNAB2_39913be00f89086d6d094769ec89ce2c
oai_identifier_str oai:repository.unab.edu.co:20.500.12749/9077
network_acronym_str UNAB2
network_name_str Repositorio UNAB
repository_id_str
dc.title.spa.fl_str_mv Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
dc.title.translated.eng.fl_str_mv A general ant colony model to solve combinatorial optimization problems
title Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
spellingShingle Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Combinatorial optimization prohlem
Ant system
The graph partitioning and the traveling salesman problems
Innovaciones tecnológicas
Ciencias de la computación
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Problema de optimización combinatoria
Sistema de hormigas
la partición de grafos y los problemas del viajante de comercio
Desarrollo tecnológico
title_short Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
title_full Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
title_fullStr Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
title_full_unstemmed Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
title_sort Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria
dc.creator.fl_str_mv Aguilar, José
dc.contributor.author.spa.fl_str_mv Aguilar, José
dc.contributor.googlescholar.spa.fl_str_mv Aguilar, José [L3C_ixQAAAAJ]
dc.contributor.orcid.spa.fl_str_mv Aguilar, José [0000-0003-4194-6882]
dc.subject.none.fl_str_mv Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
topic Innovaciones tecnológicas
Ciencia de los computadores
Desarrollo de tecnología
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y las comunicaciones
TIC´s
Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Combinatorial optimization prohlem
Ant system
The graph partitioning and the traveling salesman problems
Innovaciones tecnológicas
Ciencias de la computación
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
Problema de optimización combinatoria
Sistema de hormigas
la partición de grafos y los problemas del viajante de comercio
Desarrollo tecnológico
dc.subject.keywords.eng.fl_str_mv Technological innovations
Computer science
Technology development
Systems engineering
Investigations
Information and communication technologies
ICT's
Combinatorial optimization prohlem
Ant system
The graph partitioning and the traveling salesman problems
dc.subject.lemb.spa.fl_str_mv Innovaciones tecnológicas
Ciencias de la computación
Ingeniería de sistemas
Investigaciones
Tecnologías de la información y la comunicación
dc.subject.proposal.spa.fl_str_mv Problema de optimización combinatoria
Sistema de hormigas
la partición de grafos y los problemas del viajante de comercio
Desarrollo tecnológico
description Un Sistema de Hormigas es un sistema artificial basado en el comportamiento de colonias de hormigas reales, que se utiliza para resolver problemas combinatorios. Este es un algoritmo distribuido compuesto por un conjunto de agentes cooperantes llamados hormigas que cooperan entre ellos para encontrar buenas soluciones a problemas de optimización combinatoria. La cooperación sigue el comportamiento de hormigas reales utilizando una forma indirecta de comunicación mediada por una feromona. En este trabajo, presentamos un nuevo algoritmo distribuido basado en conceptos de Ant System, llamado General Ant System, para resolver problemas de optimización combinatoria. Nuestro enfoque consiste en mapear el espacio de solución del Problema de Optimización Combinatoria sobre el espacio donde se emparedarán las hormigasc, y en definir la probabilidad de transición del Sistema Hormiga de acuerdo a la función objetivo del Problema de Optimización Combinatoria. Probamos nuestro enfoque sobre la partición de grafos y los problemas del viajante de comercio. Los resultados muestran que nuestro enfoque tiene el mismo rendimiento que las versiones anteriores de Ant Systems.
publishDate 2001
dc.date.issued.none.fl_str_mv 2001-06-01
dc.date.accessioned.none.fl_str_mv 2020-10-27T00:21:37Z
dc.date.available.none.fl_str_mv 2020-10-27T00:21:37Z
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/article
dc.type.local.spa.fl_str_mv Artículo
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.redcol.none.fl_str_mv http://purl.org/redcol/resource_type/CJournalArticle
format http://purl.org/coar/resource_type/c_7a1f
dc.identifier.issn.none.fl_str_mv 2539-2115
1657-2831
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/20.500.12749/9077
dc.identifier.instname.spa.fl_str_mv instname:Universidad Autónoma de Bucaramanga UNAB
dc.identifier.repourl.none.fl_str_mv repourl:https://repository.unab.edu.co
identifier_str_mv 2539-2115
1657-2831
instname:Universidad Autónoma de Bucaramanga UNAB
repourl:https://repository.unab.edu.co
url http://hdl.handle.net/20.500.12749/9077
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1118/1089
dc.relation.uri.none.fl_str_mv https://revistas.unab.edu.co/index.php/rcc/article/view/1118
dc.relation.references.none.fl_str_mv E. Bonabeau, M. Dorigo and G. Theraulaz, From Natural to Artificial Swarm Intelligence, Oxford University Press, 1999.
A. Coloni, M. Dorigo and V. Maniczzo, Distributed Optimization by Ant Colonias. In: Proc. European Conference on Artificial Lif e, pp. 134-142, 1991.
D. Come, M. Dorigo and E Glove, New ideas in Optimization, McGrmv Ha 1999.
Costa D. and A. Hertz, Ants Can Colour Graphs. Journal of the Operational Revean* Society, 48: 295-305,1997.
M. Dorigo, Optimization, Leaming and Natural Algorithms, Ph.D Tizesis, Politecnico de Milano, Italy, 1992.
M. Dorigo and L. Gambardella, Ant Colony System: A Cooperativa Leaming Approach to the Traveling Salesman Problem, IEEE Trans. on Evolutionary Computation, 1(1): 53-66, 1997.
L. Gambardella and M. Dorigo, Ant-Q: A Rcinforcement Lemming Approach to the Traveling Salesman Problem. In: Proc. ofI 2th Int. Con! on Machine Learning, pp. 252-260, 1995.
E Hidrobo and .1. Aguilar "Toward a Parallel Genetic Algorithm Approach Basad on Collective Intelligence for Combinatorial Optimization Problems", In: Proc. of the IEEE International Conference on Evolutionary Computation, pp. 715-720, 1998.
] P. Kuntz and D. Snyers. Emergent Colonization and Graph Partitioning. In: Proc of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animals 3, 1994.
] P. Kuntz, P. Layzell and D. Snyers. A Colony of Ant-hlce Agents for Partitioning in VLSI Technology. In: Proc. of the Fourth European Conference on Artificial Lije, pp. 417424, 1997.
R. Schoonderwoerd, O. Holland, J. Broten and L. Rothlcrantz, Ant-based Load Balancing in Telecommunications Networks, Adaptive Behavior, 5(2): 169-207,1997.
Y. Stutzk and H. Hoos, The Max-Min Ant System and Local Search for the Traveling Salesman Problem, In: Proc. 4th hit. Conf ort Evolutionary Computation, pp. 309-314, 1997
dc.rights.none.fl_str_mv Derechos de autor 2001 Revista Colombiana de Computación
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.uri.none.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/2.5/co/
dc.rights.creativecommons.*.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv Derechos de autor 2001 Revista Colombiana de Computación
http://creativecommons.org/licenses/by-nc-sa/4.0/
http://creativecommons.org/licenses/by-nc-nd/2.5/co/
Atribución-NoComercial-SinDerivadas 2.5 Colombia
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
publisher.none.fl_str_mv Universidad Autónoma de Bucaramanga UNAB
dc.source.none.fl_str_mv Revista Colombiana de Computación; Vol. 2 Núm. 1 (2001): Revista Colombiana de Computación; 7-18
institution Universidad Autónoma de Bucaramanga - UNAB
bitstream.url.fl_str_mv https://repository.unab.edu.co/bitstream/20.500.12749/9077/1/2001_Articulo_Un%20modelo%20general%20de%20colonia%20de%20hormigas%20para%20resolver%20problemas%20de%20optimizacion%20combinatoria.pdf
https://repository.unab.edu.co/bitstream/20.500.12749/9077/2/2001_Articulo_Un%20modelo%20general%20de%20colonia%20de%20hormigas%20para%20resolver%20problemas%20de%20optimizacion%20combinatoria.pdf.jpg
bitstream.checksum.fl_str_mv a431f925eb08341292afbbf05434ac64
93224be7b926fa4455b822c46fd489ad
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional | Universidad Autónoma de Bucaramanga - UNAB
repository.mail.fl_str_mv repositorio@unab.edu.co
_version_ 1808410677575942144
spelling Aguilar, José6cad883d-ac23-43e3-b74e-e8aea2f9b8fdAguilar, José [L3C_ixQAAAAJ]Aguilar, José [0000-0003-4194-6882]2020-10-27T00:21:37Z2020-10-27T00:21:37Z2001-06-012539-21151657-2831http://hdl.handle.net/20.500.12749/9077instname:Universidad Autónoma de Bucaramanga UNABrepourl:https://repository.unab.edu.coUn Sistema de Hormigas es un sistema artificial basado en el comportamiento de colonias de hormigas reales, que se utiliza para resolver problemas combinatorios. Este es un algoritmo distribuido compuesto por un conjunto de agentes cooperantes llamados hormigas que cooperan entre ellos para encontrar buenas soluciones a problemas de optimización combinatoria. La cooperación sigue el comportamiento de hormigas reales utilizando una forma indirecta de comunicación mediada por una feromona. En este trabajo, presentamos un nuevo algoritmo distribuido basado en conceptos de Ant System, llamado General Ant System, para resolver problemas de optimización combinatoria. Nuestro enfoque consiste en mapear el espacio de solución del Problema de Optimización Combinatoria sobre el espacio donde se emparedarán las hormigasc, y en definir la probabilidad de transición del Sistema Hormiga de acuerdo a la función objetivo del Problema de Optimización Combinatoria. Probamos nuestro enfoque sobre la partición de grafos y los problemas del viajante de comercio. Los resultados muestran que nuestro enfoque tiene el mismo rendimiento que las versiones anteriores de Ant Systems.An Ants System is an artificial system basad on the bchavior of real ant colonies, which is used to solvc combinatorial problems. This is a distributed algorithm composed by a set of cooperating agents called ants which cooperatc among them to find good solutions to combinatorial optimization problerns. The cooperation follows the bchavior of real ants using an indircct forro of communication mediated by a pheromone. In Chis worlc, we present a ncw distributed algorithm basad on Ant System concepts, called the General Ant System, to solvc Combinatorial Optimization Problems. Our approach consist on mapping the solution space of the Combinatorial Optimization Problem on the space where the ants will wallc, and on defining the transition probability of the Ant System according to the objective function of the Combinatorial Optimization Problem. We test our approach on the Graph Partitioning and The Traveling Salesman Problems. The results show that our approach has the same performzumes than previous versions of Ant Systems.application/pdfspaUniversidad Autónoma de Bucaramanga UNABhttps://revistas.unab.edu.co/index.php/rcc/article/view/1118/1089https://revistas.unab.edu.co/index.php/rcc/article/view/1118E. Bonabeau, M. Dorigo and G. Theraulaz, From Natural to Artificial Swarm Intelligence, Oxford University Press, 1999.A. Coloni, M. Dorigo and V. Maniczzo, Distributed Optimization by Ant Colonias. In: Proc. European Conference on Artificial Lif e, pp. 134-142, 1991.D. Come, M. Dorigo and E Glove, New ideas in Optimization, McGrmv Ha 1999.Costa D. and A. Hertz, Ants Can Colour Graphs. Journal of the Operational Revean* Society, 48: 295-305,1997.M. Dorigo, Optimization, Leaming and Natural Algorithms, Ph.D Tizesis, Politecnico de Milano, Italy, 1992.M. Dorigo and L. Gambardella, Ant Colony System: A Cooperativa Leaming Approach to the Traveling Salesman Problem, IEEE Trans. on Evolutionary Computation, 1(1): 53-66, 1997.L. Gambardella and M. Dorigo, Ant-Q: A Rcinforcement Lemming Approach to the Traveling Salesman Problem. In: Proc. ofI 2th Int. Con! on Machine Learning, pp. 252-260, 1995.E Hidrobo and .1. Aguilar "Toward a Parallel Genetic Algorithm Approach Basad on Collective Intelligence for Combinatorial Optimization Problems", In: Proc. of the IEEE International Conference on Evolutionary Computation, pp. 715-720, 1998.] P. Kuntz and D. Snyers. Emergent Colonization and Graph Partitioning. In: Proc of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animals 3, 1994.] P. Kuntz, P. Layzell and D. Snyers. A Colony of Ant-hlce Agents for Partitioning in VLSI Technology. In: Proc. of the Fourth European Conference on Artificial Lije, pp. 417424, 1997.R. Schoonderwoerd, O. Holland, J. Broten and L. Rothlcrantz, Ant-based Load Balancing in Telecommunications Networks, Adaptive Behavior, 5(2): 169-207,1997.Y. Stutzk and H. Hoos, The Max-Min Ant System and Local Search for the Traveling Salesman Problem, In: Proc. 4th hit. Conf ort Evolutionary Computation, pp. 309-314, 1997Derechos de autor 2001 Revista Colombiana de Computaciónhttp://creativecommons.org/licenses/by-nc-sa/4.0/http://creativecommons.org/licenses/by-nc-nd/2.5/co/Atribución-NoComercial-SinDerivadas 2.5 Colombiahttp://purl.org/coar/access_right/c_abf2Revista Colombiana de Computación; Vol. 2 Núm. 1 (2001): Revista Colombiana de Computación; 7-18Innovaciones tecnológicasCiencia de los computadoresDesarrollo de tecnologíaIngeniería de sistemasInvestigacionesTecnologías de la información y las comunicacionesTIC´sTechnological innovationsComputer scienceTechnology developmentSystems engineeringInvestigationsInformation and communication technologiesICT'sCombinatorial optimization prohlemAnt systemThe graph partitioning and the traveling salesman problemsInnovaciones tecnológicasCiencias de la computaciónIngeniería de sistemasInvestigacionesTecnologías de la información y la comunicaciónProblema de optimización combinatoriaSistema de hormigasla partición de grafos y los problemas del viajante de comercioDesarrollo tecnológicoUn modelo general de colonia de hormigas para resolver problemas de optimización combinatoriaA general ant colony model to solve combinatorial optimization problemsinfo:eu-repo/semantics/articleArtículohttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/redcol/resource_type/CJournalArticleORIGINAL2001_Articulo_Un modelo general de colonia de hormigas para resolver problemas de optimizacion combinatoria.pdf2001_Articulo_Un modelo general de colonia de hormigas para resolver problemas de optimizacion combinatoria.pdfArtículoapplication/pdf69557https://repository.unab.edu.co/bitstream/20.500.12749/9077/1/2001_Articulo_Un%20modelo%20general%20de%20colonia%20de%20hormigas%20para%20resolver%20problemas%20de%20optimizacion%20combinatoria.pdfa431f925eb08341292afbbf05434ac64MD51open accessTHUMBNAIL2001_Articulo_Un modelo general de colonia de hormigas para resolver problemas de optimizacion combinatoria.pdf.jpg2001_Articulo_Un modelo general de colonia de hormigas para resolver problemas de optimizacion combinatoria.pdf.jpgIM Thumbnailimage/jpeg7689https://repository.unab.edu.co/bitstream/20.500.12749/9077/2/2001_Articulo_Un%20modelo%20general%20de%20colonia%20de%20hormigas%20para%20resolver%20problemas%20de%20optimizacion%20combinatoria.pdf.jpg93224be7b926fa4455b822c46fd489adMD52open access20.500.12749/9077oai:repository.unab.edu.co:20.500.12749/90772022-11-23 14:19:58.309open accessRepositorio Institucional | Universidad Autónoma de Bucaramanga - UNABrepositorio@unab.edu.co

Publicaciones similares