Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad
El problema de la mochila cuadrática (QKP) es una generalización del clásico pro-blema de la mochila (KP), su diferencia radica en que ahora los elementos a ingresar en la mochila tienen aparte de su beneficio propio un beneficio asociado a los demás elementos a ingresar en la mochila, y su propósit...
- Autores:
-
Paz Duarte, Paz Duarte
Cepeda, Daniel Felipe
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2018
- Institución:
- Universidad del Cauca
- Repositorio:
- Repositorio Unicauca
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unicauca.edu.co:123456789/1765
- Acceso en línea:
- http://repositorio.unicauca.edu.co:8080/xmlui/handle/123456789/1765
- Palabra clave:
- Quadratic Knapsack Problem
Optimizacion combinatoria
MOS
GRASP
VNS
- Rights
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
id |
REPOCAUCA2_a6e4343ea90b27c463e259dce51d4914 |
---|---|
oai_identifier_str |
oai:repositorio.unicauca.edu.co:123456789/1765 |
network_acronym_str |
REPOCAUCA2 |
network_name_str |
Repositorio Unicauca |
repository_id_str |
|
dc.title.spa.fl_str_mv |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
title |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
spellingShingle |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad Quadratic Knapsack Problem Optimizacion combinatoria MOS GRASP VNS |
title_short |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
title_full |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
title_fullStr |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
title_full_unstemmed |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
title_sort |
Algoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidad |
dc.creator.fl_str_mv |
Paz Duarte, Paz Duarte Cepeda, Daniel Felipe |
dc.contributor.author.none.fl_str_mv |
Paz Duarte, Paz Duarte Cepeda, Daniel Felipe |
dc.subject.spa.fl_str_mv |
Quadratic Knapsack Problem Optimizacion combinatoria MOS GRASP VNS |
topic |
Quadratic Knapsack Problem Optimizacion combinatoria MOS GRASP VNS |
description |
El problema de la mochila cuadrática (QKP) es una generalización del clásico pro-blema de la mochila (KP), su diferencia radica en que ahora los elementos a ingresar en la mochila tienen aparte de su beneficio propio un beneficio asociado a los demás elementos a ingresar en la mochila, y su propósito es encontrar la mejor combinación posible con el fin de maximizar la función objetivo sujeto a una restricción de capa-cidad. Este problema de optimización combinatoria tiene complejidad NP-Hard y en los últimos años se han intensificado las investigaciones debido la gran cantidad de aplicaciones que puede tener como son: el trafico global entre estaciones satelitales, la localización de aeropuertos, terminales o estaciones de ferrocarril, el diseño de compiladores, la gestión de redes VLCI, el problema del clique, entre otros. En este proyecto de investigación se diseñó, implementó y evaluó un algoritmo hibrido que combina las adaptaciones de los algoritmos SGVNS [1] y GRASPr [2] bajo un gestor de técnicas denominado MOS para resolver el problema 0-1 QKP. La primera técni-ca, SGVNS, cuenta con un algoritmo de búsqueda local VND con dos vecindarios, un componente de sacudida para escapar de estancamientos en el espacio de soluciones y se incorpora una fase de construcción tipo GRASP para añadir una funcionalidad de inicio múltiple, que es precedida por otra fase de construcción por peso para la exploración de diferentes espacios de soluciones. La segunda técnica denominada GRASPr cuenta también con una fase de pre-construcción por peso, construcción por densidad con una lista reducida de candidatos (RCL), la búsqueda local de selección de estructura de vecindad aleatoria, moviendo la fase de actualización de la solución con que contaba el algoritmo original a MOS, el cual actualiza la solución al final de cada iteración y sirve como coordinador de la participación de las metaheuristicas como técnicas subordinadas a las cuales se les provee una participación dinámica de acuerdo a su desempeño en cada iteración, competencia que inicia equitativamente. El algoritmo metaheuristico MOS fue probado en 80 instancias de prueba para (1000 y 2000 elementos) y fue comparado con el estado del arte IHEA y GRASP+Tabu, y se reportan los resultados y un análisis comparativo de estos. |
publishDate |
2018 |
dc.date.issued.none.fl_str_mv |
2018-03 |
dc.date.accessioned.none.fl_str_mv |
2019-12-02T21:42:05Z |
dc.date.available.none.fl_str_mv |
2019-12-02T21:42:05Z |
dc.type.spa.fl_str_mv |
Trabajos de grado |
dc.type.coarversion.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
dc.type.driver.none.fl_str_mv |
info:eu-repo/semantics/bachelorThesis |
dc.type.coar.none.fl_str_mv |
http://purl.org/coar/resource_type/c_7a1f |
format |
http://purl.org/coar/resource_type/c_7a1f |
dc.identifier.uri.none.fl_str_mv |
http://repositorio.unicauca.edu.co:8080/xmlui/handle/123456789/1765 |
dc.identifier.instname.none.fl_str_mv |
|
dc.identifier.reponame.none.fl_str_mv |
|
dc.identifier.repourl.none.fl_str_mv |
|
url |
http://repositorio.unicauca.edu.co:8080/xmlui/handle/123456789/1765 |
identifier_str_mv |
|
dc.language.iso.spa.fl_str_mv |
spa |
language |
spa |
dc.rights.coar.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
dc.rights.uri.none.fl_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
dc.rights.creativecommons.none.fl_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
rights_invalid_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ http://purl.org/coar/access_right/c_abf2 |
dc.publisher.spa.fl_str_mv |
Universidad del Cauca |
dc.publisher.faculty.spa.fl_str_mv |
Facultad de Ingeniería Electrónica y Telecomunicaciones |
dc.publisher.program.spa.fl_str_mv |
Ingeniería de Sistemas |
institution |
Universidad del Cauca |
bitstream.url.fl_str_mv |
http://repositorio.unicauca.edu.co/bitstream/123456789/1765/1/ALGORITMO%20METAHEUR%c3%8dSTICO%20BASADO%20EN%20EL%20ENFOQUE%20MOS%20PARA%20RESOLVER%20EL%20PROBLEMA%200-1%20DE%20LA%20MOCHILA%20CUADR%c3%81TICA.pdf http://repositorio.unicauca.edu.co/bitstream/123456789/1765/2/license.txt |
bitstream.checksum.fl_str_mv |
4e083d78050de8005d77645aadc28649 8a4605be74aa9ea9d79846c1fba20a33 |
bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 |
repository.name.fl_str_mv |
Dspace - Universidad del Cauca |
repository.mail.fl_str_mv |
biblios@unicauca.edu.co |
_version_ |
1808396261416501248 |
spelling |
Paz Duarte, Paz DuarteCepeda, Daniel Felipe2019-12-02T21:42:05Z2019-12-02T21:42:05Z2018-03http://repositorio.unicauca.edu.co:8080/xmlui/handle/123456789/1765El problema de la mochila cuadrática (QKP) es una generalización del clásico pro-blema de la mochila (KP), su diferencia radica en que ahora los elementos a ingresar en la mochila tienen aparte de su beneficio propio un beneficio asociado a los demás elementos a ingresar en la mochila, y su propósito es encontrar la mejor combinación posible con el fin de maximizar la función objetivo sujeto a una restricción de capa-cidad. Este problema de optimización combinatoria tiene complejidad NP-Hard y en los últimos años se han intensificado las investigaciones debido la gran cantidad de aplicaciones que puede tener como son: el trafico global entre estaciones satelitales, la localización de aeropuertos, terminales o estaciones de ferrocarril, el diseño de compiladores, la gestión de redes VLCI, el problema del clique, entre otros. En este proyecto de investigación se diseñó, implementó y evaluó un algoritmo hibrido que combina las adaptaciones de los algoritmos SGVNS [1] y GRASPr [2] bajo un gestor de técnicas denominado MOS para resolver el problema 0-1 QKP. La primera técni-ca, SGVNS, cuenta con un algoritmo de búsqueda local VND con dos vecindarios, un componente de sacudida para escapar de estancamientos en el espacio de soluciones y se incorpora una fase de construcción tipo GRASP para añadir una funcionalidad de inicio múltiple, que es precedida por otra fase de construcción por peso para la exploración de diferentes espacios de soluciones. La segunda técnica denominada GRASPr cuenta también con una fase de pre-construcción por peso, construcción por densidad con una lista reducida de candidatos (RCL), la búsqueda local de selección de estructura de vecindad aleatoria, moviendo la fase de actualización de la solución con que contaba el algoritmo original a MOS, el cual actualiza la solución al final de cada iteración y sirve como coordinador de la participación de las metaheuristicas como técnicas subordinadas a las cuales se les provee una participación dinámica de acuerdo a su desempeño en cada iteración, competencia que inicia equitativamente. El algoritmo metaheuristico MOS fue probado en 80 instancias de prueba para (1000 y 2000 elementos) y fue comparado con el estado del arte IHEA y GRASP+Tabu, y se reportan los resultados y un análisis comparativo de estos.spaUniversidad del CaucaFacultad de Ingeniería Electrónica y Telecomunicaciones Ingeniería de Sistemashttps://creativecommons.org/licenses/by-nc-nd/4.0/https://creativecommons.org/licenses/by-nc-nd/4.0/http://purl.org/coar/access_right/c_abf2Quadratic Knapsack ProblemOptimizacion combinatoriaMOSGRASPVNSAlgoritmo metaheurístico basado en el enfoque MOS para resolver el problema 0-1 de la mochila cuadrática en instancias de alta dimensionalidadTrabajos de gradoinfo:eu-repo/semantics/bachelorThesishttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/version/c_970fb48d4fbd8a85ORIGINALALGORITMO METAHEURÍSTICO BASADO EN EL ENFOQUE MOS PARA RESOLVER EL PROBLEMA 0-1 DE LA MOCHILA CUADRÁTICA.pdfALGORITMO METAHEURÍSTICO BASADO EN EL ENFOQUE MOS PARA RESOLVER EL PROBLEMA 0-1 DE LA MOCHILA CUADRÁTICA.pdfapplication/pdf1856950http://repositorio.unicauca.edu.co/bitstream/123456789/1765/1/ALGORITMO%20METAHEUR%c3%8dSTICO%20BASADO%20EN%20EL%20ENFOQUE%20MOS%20PARA%20RESOLVER%20EL%20PROBLEMA%200-1%20DE%20LA%20MOCHILA%20CUADR%c3%81TICA.pdf4e083d78050de8005d77645aadc28649MD51LICENSElicense.txtlicense.txttext/plain; charset=utf-81748http://repositorio.unicauca.edu.co/bitstream/123456789/1765/2/license.txt8a4605be74aa9ea9d79846c1fba20a33MD52123456789/1765oai:repositorio.unicauca.edu.co:123456789/17652021-05-28 09:34:42.662Dspace - Universidad del Caucabiblios@unicauca.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo= |