Evaluación de un algoritmo de recocido simulado con superficies de respuestas

• Loranca, Maria Beatriz Bernábe ; Espinosa Rosales, José E. ^[1] ; Ramírez Rodríguez, Javier ^[2]
  1. [1] Benemérita Universidad Autónoma de Puebla

     Benemérita Universidad Autónoma de Puebla

     México

     
  2. [2] Universidad Autónoma Metropolitana

     Universidad Autónoma Metropolitana

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 16, Nº. 1, 2009, págs. 159-177
• Idioma: español
• DOI: 10.15517/rmta.v16i1.1425
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En la soluci´on al problema de conglomerado geogr´afico est´a impl´?cito un procesode clasificaci´on combinatorio sobre unidades geogr´aficas. La agregaci´on propuesta eneste trabajo considerara como funci´on objetivo la minimizaci´on de distancias entrelos objetos a agrupar con el fin de lograr la compacidad geogr´afica (tan deseable enproblemas de dise˜no geogr´afico). Este problema es NP duro [1], por lo que es necesarioel uso de m´etodos heur´?sticos para obtener una soluci´on satisfactoria tanto enla bondad de las soluciones como en tiempo de c´omputo en problemas grandes. Ladiscusi´on se centra en evaluar la calidad de las soluciones obtenidas bajo procedimientossistem´aticos. Este trabajo presenta la modelaci´on del problema de conglomeradogeogr´afico, el uso de un algoritmo de Recocido Simulado en el algoritmo de particionamientocon el fin de obtener soluciones aproximadas y finalmente, para evaluarla calidad de las soluciones generadas, la aplicaci´on de un Dise˜no de ExperimentosBox-Behnken y Superficies de Respuestas para encontrar un balance y adecuaci´on delos valores de los par´ametros de Recocido Simulado en el control de la obtenci´on debuenas soluciones.Palabras clave: conglomerado geogr´afico, evaluaci´on de par´ametros, superficies de respuestas.

  • English

    The solution of the geographical clustering problem includes a combinatorial classificationof the geographical units. The aggregation proposed in this work requiresan objective function that minimizes the distance between the objects that will beclustered together, in order to achieve geo-graphical compactness (a desirable goal inproblems of geographical design). Because this problem is NP hard [10], it is usuallysolved with heuristic methodologies that can proportionate satisfactory so-lutions in areasonable amount of computational time, even for large problems. The main purposeof this research, it is to propose a Box-Behnken experimental design applied into theresponse’s surface, in order to evaluate the quality of the generated solutions. Thebalance and adequacy of Simulated Annealing’s parameters would help to control anddirect the heuristic method to obtain good solutions for the partitioning problem.Keywords: Geographical Clustering, Experimental Design, Response’s Surface, SimulatedAnnealing.

• Referencias bibliográficas
  • Bação, F.; Lobo, V.; Painho, M. (2004) “Applying genetic algorithms to zone design”, in Springer Verlag.
  • Barr R.S.; Golden J.P.; Resende M.G.C.; Stewart W.R. (1995) “Designing and Reporting on Computational Experiments with Heuristics Methods”,...
  • Bernábe, L.B.; López, S. (2004) “Statistical classificatory analysis applied to population zones”, 8th. World Multiconference on Systemics,...
  • Bernábe, L.B.; Osorio, M.A.; Duque, J.C. (2006) “Clasificación sobre zonas geográficas: un enfoque de optimización combinatoria para el...
  • Bernábe, L.B.; Aguirre, V.R.; López, S.R. (2004) “Application of non-supervised classification to population data”, ICEEE/CIE2004, International...
  • Bernábe, L.B. (2006) “Desarrollo de un modelo para la determinación de zonificación óptima”, Proyecto de tesis doctoral en desarrollo,...
  • Cliff, A.D.; Haggett, P.; Ord, J.K.; Bassett, K.A.; Davies, R.B. (1975), Elements of Spatial Structure: a Quantitative Approach. Cambridge...
  • Hess S.W.; Samuels S.A. (1971) “Experiences with a sales districting model: criteria and implementation”, Management Science, Series B: Application...
  • Kalcsics, J.; Nickel, S.; Schröder, M. (2005) Towards a Unified Territory Design Approach. Applications, Algorithms and GIS Integration....
  • Kaufman, L.; Rousseeuw, P. (1987) “Clustering by means of medoids”, Statistical Data Analysis: 405–416.
  • Kirkpatrick, S.; Gelatt, D.; Vecchi, M.P. (1983) “Optimization by simulated annealing”, Science 220: 671–680.
  • Lebster, I. (1995) “Adaptative simulated annealing”, in: (ASA): lesson learned. Technical Report, Control and Cybernetic, McLean VA.
  • Macmillan, W.; (2001) “Redistricting in a GIS environment: an optimization algorithm using switching points”, Journal of Geographical Systems...
  • Mehrotra, A.; Johnson, E.; Nemhauser, G. (1998) “An optimization based heuristic for political districting”, Management Science 44: 1100–1114.
  • Montgomery, D. (1991) Design and Analisis of Experiments, 2nd edition. Wiley, New York.
  • Murtagh F. (1985) “A survey of algorithms for contiguity–constrained clustering and related problems”, Computer Journal 28: 82–88.
  • Openshaw S.; Taylor P. (1981) “The modifiable area unit problem”, in: N. Wrigley & R. Bennett(Eds.) Quantitative Geography, London: 60–70.
  • Romero, D.; Burguete, J.; Martínez, E.; Velasco, J. (2004) “Parcelación del territorio nacional: un enfoque de optimización combinatoria...
  • Rousseeuw, P.J.; Hubert, M.; Struyf, A. (1997) “Clustering in an object-oriented environment”, Journal of Statistical Software 1: 2–10.
  • MapX Developers Guide, MapInfo corporation, Troy NY.
  • Takeshi, S. (2004) “A model of contiguity for spatial unit allocation”, Geographical Analysis, Institute for Geoinformation, Technical University...
  • Zamora, A.E. (2006) “Implementación de un algoritmo compacto y homogéneo para la clasificación de zonas geográficas AGEBs bajo una interfaz...
  • Zoltners, A.; Sinha, P. (1983) “Towards a unified territory alignment: a review and model”, Management Science 29: 1237–1256.
  • http://www.inegi.gob.mx, Instituto Nacional de Estadística, Geografía e Infomática (INEGI), México.