TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM

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

Full description

Main Authors: Chávez Bosquez, Oscar, Pozos Parra, Pilar, Gómez Ramos, José Luis
Format: Artículo
Language: Español
Published: 2015
Subjects:
Online Access: http://revistas.ucr.ac.cr/index.php/matematica/article/view/17560
http://hdl.handle.net/10669/13068
id RepoKERWA13068
recordtype dspace
spelling RepoKERWA130682017-08-08T18:50:28Z 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 búsqueda tabú criterio de aspiración programación de horarios metaheurí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 aspiración es un elemento determinante en el funcionamiento del algoritmo de Búsqueda Tabú, siendo el criterio de aspiración por defecto y el criterio de aspiración por objetivo los dos utilizados mayormente en la literatura. En este artículo se propone una variante a estos criterios de aspiración, la cual implementa una función de probabilidad al momento de evaluar un elemento clasificado como tabú que mejore la solución actual: criterio de aspiración probabilístico. El caso de prueba utilizado para evaluar el desempeño del algoritmo de Búsqueda Tabú con Criterio de Aspiración Probabilí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 Búsqueda Tabú: Búsqueda Tabú con Criterio de Aspiración por Defecto (BT-CAD) y Búsqueda Tabú con Criterio de Aspiración por Objetivo (BT-CAO). Se aplicó una prueba de Wilcoxon con los resultados obtenidos, y se demostró con 99 % de confiabilidad que el algoritmo BT-CAP obtiene mejores soluciones que las otras dos variantes del algoritmo de Búsqueda Tabú. 2015-05-19T19:12:59Z 2015-05-19T19:12:59Z 2015-01-01 00:00:00 2015-05-19T19:12:59Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion http://revistas.ucr.ac.cr/index.php/matematica/article/view/17560 http://hdl.handle.net/10669/13068 10.15517/rmta.v22i1.17560 es Revista de Matemática: Teoría y Aplicaciones Vol. 22 Núm. 1 2015 153-177 application/pdf
institution Universidad de Costa Rica
collection Repositorio KERWA
language Español
topic búsqueda tabú
criterio de aspiración
programación de horarios
metaheurística
spellingShingle búsqueda tabú
criterio de aspiración
programación de horarios
metaheurística
Chávez Bosquez, Oscar
Pozos Parra, Pilar
Gómez Ramos, José Luis
TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
description 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.
format Artículo
author Chávez Bosquez, Oscar
Pozos Parra, Pilar
Gómez Ramos, José Luis
author_sort Chávez Bosquez, Oscar
title TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
title_short TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
title_full TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
title_fullStr TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
title_full_unstemmed TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM
title_sort tabu search with aspiration criterion for the timetabling problem
publishDate 2015
url http://revistas.ucr.ac.cr/index.php/matematica/article/view/17560
http://hdl.handle.net/10669/13068
_version_ 1673491384950063104
score 11.820457