Revista: | Computación y sistemas |
Base de datos: | PERIÓDICA |
Número de sistema: | 000341049 |
ISSN: | 1405-5546 |
Autores: | Bernábe Loranca, Beatriz1 Espinosa Rosales, José E2 Ramírez Rodríguez, Javier3 Osorio Lama, María A4 |
Instituciones: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, Puebla. México 2Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias Físico Matemáticas, Puebla. México 3Universidad Autónoma Metropolitana, Departamento de Sistemas, México, Distrito Federal. México 4Benemérita Universidad Autónoma de Puebla, Facultad de Ingeniería Química, Puebla. México |
Año: | 2011 |
Periodo: | Ene-Mar |
Volumen: | 14 |
Número: | 3 |
Paginación: | 295-308 |
País: | México |
Idioma: | Inglés |
Tipo de documento: | Artículo |
Enfoque: | Aplicado, descriptivo |
Resumen en español | Este artículo describe un estudio estadístico factorial para comparar la calidad de las soluciones de dos heurísticas: Recocido Simulado (RS) y Búsqueda en Entorno Variable (BEV). Estos métodos son usados para resolver el problema de agregación geográfica, y se han comparado de acuerdo a la calidad de las soluciones obtenidas en tiempos específicos estimados. Con el objetivo de comparar la calidad de las soluciones, donde las dos heurísticas participen en una evaluación equitativa, se ha considerado el tiempo como el único elemento común para BEV y RS. En este punto, se diseñaron dos experimentos factoriales donde se modelaron cuidadosamente los parámetros correspondientes para cada heurística dejando como función de costo al tiempo. Estos experimentos implicaron la ejecución de dos conjuntos de pruebas para instancias de 24 objetos registrándose los resultados de los diferentes tiempos de respuesta y los valores asociados de la función objetivo para cada heurística. La solución a este problema requiere un proceso de particionamiento donde cada grupo está formado de objetos que cumplen mejor con el objetivo: la distancia mínima acumulada de los objetos al centroide en cada grupo. El problema de agregación geográfica es combinatorio NP–duro (Bação, Lobo and Painho, 2004) |
Resumen en inglés | This paper describes a factorial statistical study that compares the quality of solutions produced by two heuristics: Simulated Annealing (SA) and Variable Neighborhood Search (VNS). These methods are used to solve the Geographic Clustering Problem (GCP), and the quality of the solutions produced for specific times has been compared. With the goal of comparing the quality of the solutions, where both heuristics participate in an impartial evaluation, time has been the only common element considered for VNS and SA. At this point, two factorial experiments were designed and the corresponding parameters for each heuristic were carefully modeled leaving time as the cost function. In instances of 24 objects, the experiments involved the execution of two sets of tests recording the results of the different response times and the associated values of the objective function for each heuristic and instance conditions. The solution to this problem requires a partitioning process where each group is composed of objects that fulfill better the objective: the minimum accumulated distance from the objects to the centroid of each group. The GCP is a combinatorial NP–hard problem (Bação, Lobo and Painho, 2004) |
Disciplinas: | Ciencias de la computación, Geografía |
Palabras clave: | Matemáticas aplicadas, Estadística factorial, Agregación geográfica, Heurística, Algoritmos, Recocido simulado |
Keyword: | Computer science, Geography, Applied mathematics, Factorial statistics, Geographic clustering, Heuristics, Algorithms, Simulated annealing |
Texto completo: | Texto completo (Ver HTML) |