Diseño de un algoritmo memético para resolver el problema de coloración del vértice

Suárez Quiroz, Aylin Brigett Amairany; Oliveros Cala, María Camila

Diseño de un algoritmo memético para resolver el problema de coloración del vértice

dc.contributor.advisor	Lamos Díaz, Henry
dc.contributor.author	Suárez Quiroz, Aylin Brigett Amairany
dc.contributor.author	Oliveros Cala, María Camila
dc.contributor.evaluator	Garavito Hernández, Edwin Alberto
dc.contributor.evaluator	Talero Sarmiento, Leonardo Hernán
dc.date.accessioned	2022-06-30T14:08:45Z
dc.date.available	2022-06-30T14:08:45Z
dc.date.created	2022-06-29
dc.date.issued	2022-06-29
dc.description.abstract	El problema de coloración del vértice consiste en colorear todos los vértices de un grafo de manera que los vértices que están conectados por una arista o borde no compartan el mismo color, esto dado que son vértices adyacentes y el hecho de tener el mismo color representa un conflicto en la coloración, a su vez se busca minimizar el número de colores usados. En el mundo real dicho problema es usado para resolver problemas tales como asignación de asientos, tareas, horarios, la planificación de actividades, la asignación de recursos, en problemas de control de producción, para proyectar redes de ordenadores, en la logística, robótica, genética, sociología, el diseño de redes, el cálculo de rutas óptimas y los problemas de almacenamiento, donde se tiene un conjunto de elementos que deben ser asignados a determinados recursos mientras se optimiza una función objetivo y se satisfacen las restricciones planteadas. En la presente investigación se usa el problema de coloración del vértice para resolver un problema de programación de horario a través de un algoritmo memético programado en Matlab, dicho algoritmo es validado con datos aleatorios donde a través de un diseño factorial completo se evalúan los factores que influyen en el desempeño del mismo con el fin de decidir el valor que van a tomar al implementar el algoritmo en el caso de estudio de Escuela de Estudios Industriales y Empresariales de la Universidad Industrial de Santander, se concluye que el algoritmo tiene un mejor desempeño al emplear un conjunto reducido de datos y a su vez se reduce el tiempo de ejecución por lo cual se decide dividir los datos del caso de estudio en 4 subproblemas obteniendo resultados aceptables.
dc.description.abstractenglish	The vertex coloring problem consists of coloring all the vertices of a graph in such a way that the vertices that are connected by an edge do not share the same color since they are adjacent vertices, and the fact of having the same color represents a conflict in coloration, in turn, it seeks to minimize the number of colors used. In the real world, this problem is used to solve problems such as seat allocation, tasks, schedules, activity planning, resource allocation, production control problems, design of computer networks, logistics, robotics, and son on. Genetics, sociology, network design, the calculation of optimal routes, and storage problems, where a set of elements must be assigned to specific resources while an objective function is optimized and the posed restrictions are satisfied. In the present investigation, the vertex coloring problem is used to solve a timetabling problem through a memetic algorithm programmed in Matlab. This algorithm is validated with random data, and through a complete factorial design, the factors that influence are evaluated in order to decide the value that they are going to take when implementing it in the case study of the School of Industrial and Business Studies of the Industrial University of Santander, it is concluded that the algorithm has a better performance when using a reduced set of data and in turn, the execution time is reduced for which it is decided to divide the data of the case study into four subproblems obtaining acceptable results.
dc.description.degreelevel	Pregrado
dc.description.degreename	Ingeniero Industrial
dc.format.mimetype	application/pdf
dc.identifier.instname	Universidad Industrial de Santander
dc.identifier.reponame	Universidad Industrial de Santander
dc.identifier.repourl	https://noesis.uis.edu.co
dc.identifier.uri	https://noesis.uis.edu.co/handle/20.500.14071/11270
dc.language.iso	spa
dc.publisher	Universidad Industrial de Santander
dc.publisher.faculty	Facultad de Ingeníerias Fisicomecánicas
dc.publisher.program	Ingeniería Industrial
dc.publisher.school	Escuela de Estudios Industriales y Empresariales
dc.rights	info:eu-repo/semantics/openAccess
dc.rights.accessrights	info:eu-repo/semantics/openAccess
dc.rights.coar	http://purl.org/coar/access_right/c_abf2
dc.rights.creativecommons	Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
dc.rights.license	Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject	problema de coloración del vértice
dc.subject	teoría de grafos
dc.subject	algoritmo memético
dc.subject	programación de horarios
dc.subject.keyword	vertex coloring problem
dc.subject.keyword	graph theory
dc.subject.keyword	memetic algorithm
dc.subject.keyword	timetabling
dc.title	Diseño de un algoritmo memético para resolver el problema de coloración del vértice
dc.title.english	Design of a memetic algorithm to solve the vertex coloring problem
dc.type.coar	http://purl.org/coar/resource_type/c_7a1f
dc.type.hasversion	http://purl.org/coar/version/c_b1a7d7d4d402bcce
dc.type.local	Tesis/Trabajo de grado - Monografía - Pregrado
dspace.entity.type