Artículo

Reducción de los Experimentos Requeridos para Evaluar el Desempeño de Algoritmos Metaheurísticos

Centro de Investigación en Computación, Dirección General de Servicios de Cómputo Académico, IPN, publicado en Computación y Sistemas, y cosechado de Revistas UNAM

Procedencia del contenido

Entidad o dependencia
Centro de Investigación en Computación, Dirección General de Servicios de Cómputo Académico, IPN
Revista
Repositorio
Contacto
Revistas UNAM. Dirección General de Publicaciones y Fomento Editorial, UNAM en revistas@unam.mx

Cita

Reducción de los Experimentos Requeridos para Evaluar el Desempeño de Algoritmos Metaheurísticos. (2011). Computación y Sistemas; Vol 14, No 001, 2010. Recuperado de https://repositorio.unam.mx/contenidos/29519

Descripción del recurso

Colaborador(es)
Pazos Rangel, Rodolfo Abraham ; González Barbosa, Juan Javier ; Cruz Reyes, Laura ; Fraire Huacuja, Héctor Joaquín ; Martínez Flores, José A. ; Castilla Valdez, Guadalupe
Tipo
Artículo de Investigación
Área del conocimiento
Ciencias Sociales y Económicas
Título
Reducción de los Experimentos Requeridos para Evaluar el Desempeño de Algoritmos Metaheurísticos
Fecha
2011-06-29
Resumen
Cuando se evalúa el desempeño de algoritmos metaheurísticos, con un conjunto de instancias difíciles de un problema NP-completo, el tiempo requerido para realizar la experimentación puede ser muy grande. Una forma de reducir el esfuerzo necesario es incorporar técnicas de reducción de la varianza en los experimentos computacionales. Para incorporar dichas técnicas, los enfoques tradicionales proponen métodos que dependen de la técnica, del problema y del algoritmo usado. En este trabajo se propone desarrollar métodos de propósito general, los cuales permitan incorporar técnicas de reducción de la varianza, independientemente del problema y del algoritmo metaheurístico usado. Para validar la factibilidad del enfoque, se describe un método de propósito general, el cual permite incorporar la técnica de variables antitéticas en experimentos computacionales con algoritmos metaheurísticos aleatorizados. La evidencia experimental muestra que el método propuesto produce una reducción de la varianza de las salidas aleatorias en un 78% de las instancias consideradas y que el método tiene la capacidad de reducir simultáneamente la varianza de varias salidas aleatorias de los algoritmos probados. Los niveles globales de reducción alcanzados con las instancias usadas en los casos de prueba van del 14% al 55%.
Tema
Análisis Experimental De Algoritmos; Técnicas De Reducción De La Varianza Y Algoritmos Metaheurísticos
Idioma
spa
ISSN
1405-5546

Enlaces