Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares

El criterio de aspiración es un elemento determinante en el funcionamiento del algoritmo de Búsqueda Tabú, siendo el criterio de aspiración por defecto y el criterio de aspiración por objetivo los dos utilizados mayormente en la literatura. En este artículo se propone una variante a estos crit...

Descripción completa

Detalles Bibliográficos
Autores principales:	Chávez-Bosquez, Oscar, Pozos-Parra, Pilar, Gómez-Ramos, José Luis
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2015
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/17560

id	RMTA17560
record_format	ojs
spelling	RMTA175602022-01-28T18:07:12Z Tabu search with aspiration criterion for the timetabling problem Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares Chávez-Bosquez, Oscar Pozos-Parra, Pilar Gómez-Ramos, José Luis tabu search aspiration criterion timetabling International Timetabling Competition metaheuristic búsqueda tabú criterio de aspiración programación de horarios metaheurística The aspiration criterion is an imperative element in the Tabu Search, with aspiration-by-default and the aspiration-by-objective the mainly used criteria in the literature. In this paper a new aspiration criterion is proposed in order to implement a probabilistic function when evaluating an element classified as tabu which improves the current solution, the proposal is called Tabu Search with Probabilistic Aspiration Criterion (BT- CAP). The test case used to evaluate the performance of the Probabilistic Aspiration Criterion proposed consists on the 20 instances of the problem described in the First International Timetabling Competition. The results are compared with 2 additional variants of the Tabu Search Algorithm: Tabu Search with Default Aspiration Criterion (BT-CAD) and Tabu Search with Objective Aspiration Criterion (BT-CAO). Wilcoxon test was applied to the generated results, and it was proved with 99 % confidence that BT-CAP algorithm gets better solutions than the two other variants of the Tabu Search algorithm. El criterio de aspiración es un elemento determinante en el funcionamiento del algoritmo de Búsqueda Tabú, siendo el criterio de aspiración por defecto y el criterio de aspiración por objetivo los dos utilizados mayormente en la literatura. En este artículo se propone una variante a estos criterios de aspiración, la cual implementa una función de probabilidad al momento de evaluar un elemento clasificado como tabú que mejore la solución actual: criterio de aspiración probabilístico. El caso de prueba utilizado para evaluar el desempeño del algoritmo de Búsqueda Tabú con Criterio de Aspiración Probabilístico (BT-CAP) propuesto lo constituyen las 20 instancias del problema descrito en the First International Timetabling Competition. Se compararon los resultados del BT-CAP contra 2 variantes adicionales del algoritmo de Búsqueda Tabú: Búsqueda Tabú con Criterio de Aspiración por Defecto (BT-CAD) y Búsqueda Tabú con Criterio de Aspiración por Objetivo (BT-CAO). Se aplicó una prueba de Wilcoxon con los resultados obtenidos, y se demostró con 99 % de confiabilidad que el algoritmo BT-CAP obtiene mejores soluciones que las otras dos variantes del algoritmo de Búsqueda Tabú. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2015-03-18 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/17560 10.15517/rmta.v22i1.17560 Revista de Matemática: Teoría y Aplicaciones; Vol. 22 No. 1 (2015): Revista de Matemática: Teoría y Aplicaciones; 153-177 Revista de Matemática: Teoría y Aplicaciones; Vol. 22 Núm. 1 (2015): Revista de Matemática: Teoría y Aplicaciones; 153-177 Revista de Matemática; Vol. 22 N.º 1 (2015): Revista de Matemática: Teoría y Aplicaciones; 153-177 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/17560/17060 Derechos de autor 2015 Revista de Matemática: Teoría y Aplicaciones
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Chávez-Bosquez, Oscar Pozos-Parra, Pilar Gómez-Ramos, José Luis
spellingShingle	Chávez-Bosquez, Oscar Pozos-Parra, Pilar Gómez-Ramos, José Luis Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
author_facet	Chávez-Bosquez, Oscar Pozos-Parra, Pilar Gómez-Ramos, José Luis
author_sort	Chávez-Bosquez, Oscar
description	El criterio de aspiración es un elemento determinante en el funcionamiento del algoritmo de Búsqueda Tabú, siendo el criterio de aspiración por defecto y el criterio de aspiración por objetivo los dos utilizados mayormente en la literatura. En este artículo se propone una variante a estos criterios de aspiración, la cual implementa una función de probabilidad al momento de evaluar un elemento clasificado como tabú que mejore la solución actual: criterio de aspiración probabilístico. El caso de prueba utilizado para evaluar el desempeño del algoritmo de Búsqueda Tabú con Criterio de Aspiración Probabilístico (BT-CAP) propuesto lo constituyen las 20 instancias del problema descrito en the First International Timetabling Competition. Se compararon los resultados del BT-CAP contra 2 variantes adicionales del algoritmo de Búsqueda Tabú: Búsqueda Tabú con Criterio de Aspiración por Defecto (BT-CAD) y Búsqueda Tabú con Criterio de Aspiración por Objetivo (BT-CAO). Se aplicó una prueba de Wilcoxon con los resultados obtenidos, y se demostró con 99 % de confiabilidad que el algoritmo BT-CAP obtiene mejores soluciones que las otras dos variantes del algoritmo de Búsqueda Tabú.
title	Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_short	Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_full	Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_fullStr	Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_full_unstemmed	Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_sort	búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares
title_alt	Tabu search with aspiration criterion for the timetabling problem
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2015
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/17560
work_keys_str_mv	AT chavezbosquezoscar tabusearchwithaspirationcriterionforthetimetablingproblem AT pozosparrapilar tabusearchwithaspirationcriterionforthetimetablingproblem AT gomezramosjoseluis tabusearchwithaspirationcriterionforthetimetablingproblem AT chavezbosquezoscar busquedatabuconcriteriodeaspiracionprobabilisticoaplicadaalageneraciondehorariosescolares AT pozosparrapilar busquedatabuconcriteriodeaspiracionprobabilisticoaplicadaalageneraciondehorariosescolares AT gomezramosjoseluis busquedatabuconcriteriodeaspiracionprobabilisticoaplicadaalageneraciondehorariosescolares
_version_	1811744091146289152

Búsqueda tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares

Ejemplares similares