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 BU?SQUEDA TABU? CON CRITERIO DE ASPIRACIO?N PROBABILI?STICO APLICADA A LA GENERACIO?N DE HORARIOS ESCOLARES Ch?vez Bosquez, Oscar Pozos Parra, Pilar G?mez Ramos, Jos? Luis 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?. 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 bu?squeda tabu?
criterio de aspiracio?n
programacio?n de horarios
metaheuri?stica
spellingShingle bu?squeda tabu?
criterio de aspiracio?n
programacio?n de horarios
metaheuri?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_ 1650735553759412224
score 11.754696