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...

Full description

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=