| Journal: | Computación y sistemas |
| Database: | PERIÓDICA |
| System number: | 000360496 |
| ISSN: | 1405-5546 |
| Authors: | Bernábe Loranca, María Beatriz1 Guillén Galván, Carlos1 |
| Institutions: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, Puebla. México |
| Year: | 2012 |
| Season: | Jul-Sep |
| Volumen: | 16 |
| Number: | 3 |
| Pages: | 335-348 |
| Country: | México |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Analítico, descriptivo |
| Spanish abstract | El problema de particionamiento siendo un problema NP difícil, ha sido ampliamente estudiado debido a varias razones, en particular, por su vulnerabilidad al obtener óptimos locales de los criterios que optimiza. Para problemas particionamiento en optimización combinatoria, existen diversos trabajos que han propuesto la inclusión de heurísticas con el fin de lograr óptimos globales. Muchos han sido los esfuerzos para resolver el particionamiento y encontrar buenas soluciones cuando en el proceso de optimización discreta se optimiza un solo objetivo, sin embargo, ha sido poco atendido el problema de particionamiento con más de un objetivo debido a la dificultad de obtener el conjunto de soluciones eficientes, óptimas y no dominadas. En este trabajo se expone el problema de multiobjetivo en particionamiento para datos espaciales con dos objetivos: minimización de distancias y de variables censales. El algoritmo de particionamiento que se ha diseñado es una extensión del grupo geográfico que optimiza solo un objetivo. En este trabajo para escapar de óptimos locales se ha hecho uso de Búsqueda por Entorno Variable (VNS) y para obtener el conjunto de soluciones no dominadas se han aprovechado las propiedades del conjunto Máxima |
| English abstract | The problem of partitioning is NP hard and has been studied extensively for several reasons including vulnerability to obtain local optima. For partitioning problems in combinatorial optimization, several works have proposed the inclusion of heuristics in order to achieve global optima. There have been made many efforts to solve the partitioning problem and find good solutions when the discrete optimization process optimizes a single objective. However, the partitioning problem with more than one goal has not been addressed due to the difficulty of obtaining the set of efficient optimal and non-dominated solutions. This paper presents the multi-objective partitioning problem with two objectives: minimization of distances and of census variables. The designed partitioning algorithm is an extension of the geographic cluster that optimizes only one objective. In this work, we used Variable Neighborhood Search (VNS) to escape local optima, and to obtain the set of non-dominated solutions, our methodology takes advantage of the properties of the set Maxima |
| Disciplines: | Ciencias de la computación |
| Keyword: | Procesamiento de datos, Particionamiento multiobjetivo, Algoritmos heurísticos |
| Keyword: | Computer science, Data processing, Multiobjective partitioning, Heuristic algorithms |
| Full text: | Texto completo (Ver HTML) |
