logo móvil
Contáctanos

Resolviendo el problema de programación de exámenes en GPUs

Autores: Kolonias, Vasileios; Goulas, George; Gogos, Christos; Alefragis, Panayiotis; Housos, Efthymios

Idioma: Inglés

Editor: MDPI

Año: 2014

Descargar PDF

Acceso abierto

Artículo científico
2014

Resolviendo el problema de programación de exámenes en GPUs


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Problema de planificación de horarios de exámenes
Problemas de optimización combinatoria
Algoritmo evolutivo híbrido
GPU
Algoritmo genético
Descenso más empinado codicioso

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 36

Citaciones: Sin citaciones


Descripción
El problema de planificación de exámenes pertenece a la clase de problemas de optimización combinatoria y es de gran importancia para cada Universidad. En este documento, se emplea un algoritmo evolutivo híbrido que se ejecuta en una GPU para resolver el problema de planificación de exámenes. El algoritmo evolutivo híbrido propuesto tiene un componente de algoritmo genético y un componente de descenso más empinado codicioso. Las capacidades computacionales de la GPU permiten el uso de tamaños de población muy grandes, lo que conduce a una exploración más exhaustiva del espacio de soluciones del problema. La implementación en GPU, dependiendo del tamaño del problema, es hasta veintiséis veces más rápida que la implementación en CPU de un solo hilo idéntica del algoritmo. El algoritmo se evalúa con los conocidos conjuntos de datos de Toronto y se compara bien con los mejores resultados encontrados en la bibliografía. Además, se examinan y optimizan la selección de la codificación de los cromosomas y el tamaño de la selección de torneos a medida que crece la población. Se utiliza el formato de fila dispersa comprimida para la matriz de conflictos y se demostró que es esencial para el proceso, ya que la mayoría de los conjuntos de datos tienen una baja densidad de conflictos, lo que se traduce en una matriz extremadamente dispersa.

Otros recursos que podrían interesarte

Temas Virtualpro