Revista de Matema´tica: Teor´ıa y Aplicaciones 2009 16(1) : 159–177
cimpa – ucr issn: 1409-2433
evaluacio´n de un algoritmo de recocido
simulado con superficies de respuestas
Maria Beatriz Berna´be Loranca∗ Jose´ E. Espinosa Rosales†
Javier Ram´ırez‡
Recibido/Received: 20 Feb 2008 — Aceptado/Accepted: 8 Dic 2008
Resumen
En la solucio´n al problema de conglomerado geogra´fico esta´ impl´ıcito un proceso
de clasificacio´n combinatorio sobre unidades geogra´ficas. La agregacio´n propuesta en
este trabajo considerara como funcio´n objetivo la minimizacio´n de distancias entre
los objetos a agrupar con el fin de lograr la compacidad geogra´fica (tan deseable en
problemas de disen˜o geogra´fico). Este problema es NP duro [1], por lo que es nece-
sario el uso de me´todos heur´ısticos para obtener una solucio´n satisfactoria tanto en
la bondad de las soluciones como en tiempo de co´mputo en problemas grandes. La
discusio´n se centra en evaluar la calidad de las soluciones obtenidas bajo procedimien-
tos sistema´ticos. Este trabajo presenta la modelacio´n del problema de conglomerado
geogra´fico, el uso de un algoritmo de Recocido Simulado en el algoritmo de parti-
cionamiento con el fin de obtener soluciones aproximadas y finalmente, para evaluar
la calidad de las soluciones generadas, la aplicacio´n de un Disen˜o de Experimentos
Box-Behnken y Superficies de Respuestas para encontrar un balance y adecuacio´n de
los valores de los para´metros de Recocido Simulado en el control de la obtencio´n de
buenas soluciones.
Palabras clave: conglomerado geogra´fico, evaluacio´n de para´metros, superficies de re-
spuestas.
Abstract
∗Departamento de Sistemas, DEPFI, Universidad Nacional Auto´noma de Me´xico, Me´xico D.F.; y Fac-
ultad de Ciencias de la Computacio´n, Beneme´rita Universidad Auto´noma de Puebla, Puebla, Me´xico.
E-Mail: beatriz.bernabe@gmail.com
†Facultad de Ciencias F´ısico Matema´ticas, Beneme´rita Universidad Auto´noma de Puebla. E-Mail
pepe-espinosa@hotmail.com.
‡Universidad Autnoma Metropolitana – Unidad Azcapotzalco, Departamento de Sistemas, Avenida San
Pablo 180, 02200 Me´xico D.F., Me´xico. E-Mail: jararo@correo.azc.uam.mx
159
160 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
The solution of the geographical clustering problem includes a combinatorial clas-
sification of the geographical units. The aggregation proposed in this work requires
an objective function that minimizes the distance between the objects that will be
clustered together, in order to achieve geo-graphical compactness (a desirable goal in
problems of geographical design). Because this problem is NP hard [10], it is usually
solved with heuristic methodologies that can proportionate satisfactory so-lutions in a
reasonable amount of computational time, even for large problems. The main purpose
of this research, it is to propose a Box-Behnken experimental design applied into the
response’s surface, in order to evaluate the quality of the generated solutions. The
balance and adequacy of Simulated Annealing’s parameters would help to control and
direct the heuristic method to obtain good solutions for the partitioning problem.
Keywords: Geographical Clustering, Experimental Design, Response’s Surface, Simulated
Annealing.
Mathematics Subject Classification: 62H30, 62K20.
1 Introduccio´n
El problema de Conglomerado Geogra´fico (CG) consiste en la clasificacio´n de unidades
geogra´ficas (UG) sujetas al cumplimiento de ciertos criterios como el de compacidad
geome´trica, que es el nos ha ocupado en los u´ltimos trabajos [3, 4, 5]. Las UG que se
han considerado corresponden a AGEBSs (reas Geoestad´ısticas Ba´sicas) [24].
Dada la complejidad combinatoria del problema de CG [1, 13, 14, 18, 23], en este
trabajo se presenta una propuesta matema´tica y computacional para plantear y resolver
la tarea espec´ıfica de agrupacio´n geogra´fica bajo el cumplimiento de una medida de disi-
militud como funcio´n objetivo. El problema se centra entonces en minimizar dicha funcio´n
de costo entendida como compacidad sobre AGEBS. Para optimizar esta funcio´n objetivo
se utiliza un me´todo de gran eficiencia en la resolucio´n heur´ıstica de problemas dif´ıciles
de optimizacio´n combinatoria: Recocido Simulado (RS). Con el propo´sito de cuantificar
la calidad de las soluciones generadas se ha aplicado una metodolog´ıa estad´ıstica factorial
[15].
1.1 Aspectos generales de CG
El problema de CG cae en la categor´ıa de Disen˜o Territorial (DT) de donde se desprende la
cual desprende una gran diversidad de problemas que han sido abordados desde diferentes
a´ngulos [1, 8, 9, 13, 16, 23].
En te´rminos generales, DT puede ser visto como un problema de agrupacio´n de a´reas
geogra´ficas pequen˜as (a´reas ba´sicas o unidades geogra´ficas ba´sicas) en grupos geogra´ficos
ma´s grandes llamados territorios, de tal forma que la agrupacio´n aceptable es aquella
u´ltima que cumpla con criterios predeterminados del problema que ocupa [23]. Estos
criterios a cumplir obedecen a la naturaleza de un particular problema donde restricciones
espaciales son muy demandadas [1, 7, 17, 21].
La condicio´n NP-duro de un problema de DT implica resolver un gran nu´mero de tareas
geogra´ficas donde destaca el proceso de clasificacio´n sujeto al cumplimiento de una funcio´n
algoritmo de recocido simulado con superficies de respuesta 161
de costo que minimice distancias entre los objetos a agrupar [1]. A nivel internacional han
existido esfuerzos similares encaminados a generar de manera automa´tica agrupaciones
geogra´ficas. Sin embargo, y hasta donde sabemos, ninguno ha abordado la agregacio´n
del territorio utilizando un me´todo de optimizacio´n combinatoria como apoyo para la
generacio´n de grupos considerando como unidades territoriales a los AGEBS.
En Me´xico, se cuenta con importantes contribuciones pioneras para esta l´ınea de inves-
tigacio´n, como lo son parcelacio´n de territorio nacional y distritacio´n electoral [18, 24]. En
ambos casos consideran a las manzanas como las unidades geogra´ficas a agrupar (lo que
facilita establecer la compacidad geome´trica entre manzanas recurriendo a la geometr´ıa
computacional como una excelente herramienta). Sin embargo, al considerar AGEBS como
unidades geogra´ficas para clasificar, los me´todos de adyacencia conocidos para obtener tal
compacidad, no facilitan el proceso dado que los AGEBS esta´n separadas por distancias
no uniformes y su estructura espacial es heteroge´nea entre cada UG. Justamente esta es
la naturaleza espacial de los AGEBS en Me´xico.
Debido al cara´cter combinatorio del problema CG, la propuesta de este trabajo se
situ´a en el disen˜o, desarrollo e implementacio´n de un algoritmo de particionamiento sobre
unidades geogra´ficas AGEBS de una zona metropolitana. Para evitar la generacio´n de
mı´nimos locales, en este algoritmo se hace necesaria la insercio´n de me´todos heur´ısticos,
donde la funcio´n de costo considera los aspectos fundamentales de agregacio´n territorial:
compacidad para ubicacio´n geogra´fica de los datos.
Con la inclusio´n de RS es posible escapar favorablemente de mı´nimos locales y al mismo
tiempo mejorar el desempen˜o del algoritmo de particionamiento que hemos disen˜ado. Por
otro lado de Experimentos Box-Benhken y Superficies de Respuestas [15] para obtener
condiciones favorables de ajuste de para´metros de la heur´ıstica y contar con valores que
posibiliten la obtencio´n de soluciones subo´ptimas de calidad en problemas pequen˜os.
Dado que actualmente no se disponen de metodolog´ıas claras para determinar co´mo
calibrar para´metros de una heur´ıstica para lograr calidad de soluciones, nuestra aportacio´n
se centra justamente en este punto. Conscientes de que RS tiene propiedades de para´metros
que la definen y que el control de estos bajo procesos sistema´ticos permiten encontrar
bondad en los resultados, en este trabajo estamos presentando una te´cnica para balancear
estos para´metros que orienten a la generacio´n de soluciones buenas y cercanas al o´ptimo
para CG.
Se han considerado trabajos sobre clasificacio´n bajo criterios de minimizacio´n de dis-
tancias que han sido de apoyo en este art´ıculo pero sin ofrecer me´todos sistema´ticos que de-
muestren co´mo la variacio´n de sus para´metros hacen que sus instancias garanticen buenas
soluciones. En particular PAM (Partitioning Around Mediods) propuesto por Kaufman y
Rousseeuw (1987) [10, 19], es un buen algoritmo de particionamiento exacto con la desven-
taja de tener alto costo computacional [19]. Sin embargo, ha sido necesario implementar
PAM para clasificar AGEBS con el fin de obtener una solucio´n exacta y comparar las
soluciones generadas por RS para problemas pequen˜os y los hemos utilizado para calibrar
los para´metros de la heur´ıstica.
Los datos que hemos considerado a clasificar corresponden a los AGEBS de la Zona
Metropolitana del Valle de Toluca (ZMVT) [24]. Las variables de clasificacio´n esta´n con-
formadas por 57 variables socioecono´micas disponibles para dichas a´reas.
162 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
Se ha integrado a RS al algoritmo de particionamiento que presentamos en la seccio´n
2. La estrategia consiste en elegir k AGEBS como centroides de manera aleatoria para
identificar el nu´mero de grupos (conglomerados). Aquellos AGEBS que no son centroides
sera´n parte de un determinado grupo si la distancia hacia el centroide es menor que la
distancia hacia otro centroide. Considerada as´ı una solucio´n inicial, se crea una solucio´n
vecina de la misma manera eligiendo nuevos k centroides. Se compara esta solucio´n vecina
(solucio´n actual) con la solucio´n inicial para determinar que tan buena es con respecto a
la anterior.
Una vez que se ha obtenido una solucio´n final se hace necesario proponer me´todos para
validar la calidad de la solucio´n [2]. Para ello, bajo la aplicacio´n de Box-Benhken, hemos
encontrado un conjunto de instancias para ser evaluadas y a su vez con la aplicacio´n de la
metodolog´ıa de Superficies de Respuestas se obtuvieron valores para la calibracio´n de los
para´metros de RS que facilitan la generacio´n de soluciones hacia un mı´nimo global.
En congruencia con lo descrito anteriormente, el documento se encuentra organizado
como sigue: esta introduccio´n como seccio´n 1, se describe el disen˜o de un modelo de
optimizacio´n para cluster geogra´fico en la siguiente seccio´n. Para dar inicio a la validacio´n
de los para´metros, en el apartado 3 se presentan las instancias y validacio´n del modelo
estad´ıstico experimental. En la seccio´n 4 se concluye la validacio´n de los resultados y
finalmente en la seccio´n 5 presentamos las conclusiones y trabajo futuro.
2 Un modelo matema´tico para cluster geogra´fico
Existen diversas propuestas para resolver problemas de agregacio´n geogra´fica, una de ellas
es el disen˜o de zonas donde los autores lo implementaron con un algoritmo gene´tico [1]. De
acuerdo con esta propuesta, el modelo para el problema del CG para AGEBS se presenta
en esta seccio´n (Modelo CG). En el problema de CG las UG son AGEBS, cada AGEB
esta´ separado por distancias diferentes de estructura geome´trica no uniforme debido a que
las AGEBS son datos espaciales [6, 7], su ubicacio´n geogra´fica esta´ dada por latitud y
longitud lo que ha facilitado el ca´lculo de distancias entre las AGEBS.
Se resuelve la agrupacio´n de AGEBS de tal forma que las AGEBS que componen los
grupos este´n entre ellas muy cercanas geogra´ficamente donde se requiere el uso de una
funcio´n de costo que minimice distancias entre estas. Ba´sicamente, la estrategia se basa
en elegir aleatoriamente AGEBS como centroides que determinan el nu´mero de grupos.
Aquellos AGEBS no centroides que tengan la distancia ma´s corta hacia un determinado
centroide-AGEB, son los integrantes de un grupo. Esta idea informal es la que se entiende
como compacidad geome´trica. Definir formalmente compacidad no es simple [21], sin
embargo, en la definicio´n 1 se plantea la compacidad para UG [6, 22]:
Definicio´n 1. Compacidad
Si denotamos por Z = {1, 2, . . . , n} al conjunto de n objetos a clasificar, se trata de dividir
Z en k grupos {G1, G2, . . . , Gk} con k < n, de tal forma que:⋃k
i=1
Gi = Z
Gi ∩Gj = ∅, i 6= j
algoritmo de recocido simulado con superficies de respuesta 163
|Gi| ≥ 1, i = 1, 2, . . . , k
Un grupo Gm con |Gm| > 1 es compacto si para cada objeto t ∈ Gm cumple:
min
i∈Gm
d(t, i) < min
j∈Z−Gm
d(t, j), i 6= t. (CV 1)
Un grupo Gm con |Gm| = 1 es compacto si su objeto t cumple:
min
i∈Z−{t}
d(t, i) > min
j,l∈Gf
d(j, l),∀f 6= m.
El criterio de vecindad entre objetos para lograr la compacidad esta´ dado por los pares
de distancias descritos en (CV 1).
Con la idea de la definicio´n 1 y con el fin de resolver el problema de CG, se presenta la
siguiente modelacio´n:
2.1 Modelo para conglomerado geogra´fico (Modelo CG)
Sea UG el nu´mero total de AGEBS. Sea el conjunto inicial de nUG, UG = {x1, x2, . . . , xn},
donde: xi es la i−e´sima unidad geogra´fica, (i es el ı´ndice de UG), y k es el nu´mero de
zonas (grupos). Dado que se desean formar grupos y para referirnos a e´stos, definimos: Zi
como el conjunto de las UG que pertenecen a la zona i, Ct es el centroide, y d(i, j) es la
distancia euclidiana del nodo i al nodo j (de un AGEB a otro). Entonces se tienen como
restricciones: Zi 6= ∅ para i = 1, . . . , k (los grupos no son vac´ıos), Zi ∩ Zj = ∅ para i 6= j
(no existen AGEBS repetidos en distintos grupos), y
⋃k
i=1 Zi = UG (la unio´n de todos los
grupos son todos los AGEBS).
Una vez que se ha decidido el nu´mero k de centroides ct, t = 1, . . . , k, a utilizar hay
que seleccionarlos en forma aleatoria y enseguida asignar los AGEBS a los centroides de
la siguiente manera: para cada AGEB i
min
t=1,...,k
{d(i, ct)}
cada AGEB es asignado al centroide ma´s cercano ct.
Para cada valor de k se calcula la suma de las distancias de los AGEBS asignados
a cada centroide y se escoge el mı´nimo y nit es el nu´mero de iteraciones. Esto puede
expresarse como:
min
k=1,...,nit
{
min
{
k∑
t=1
∑
i∈ct
d(i, ct)
}}
. (1)
2.2 Algoritmo de recocido simulado para la obtencio´n de soluciones sub-
o´ptimas en CG
Para garantizar la generacio´n de buenas soluciones, se requiere de la inclusio´n de una
heur´ıstica dentro del algoritmo de particionamiento de CG. Se ha considerado a RS por
ser conocido como un me´todo eficiente que escapa satisfactoriamente de o´ptimos locales
[11, 12]. RS es un me´todo de bu´squeda por entornos caracterizado por un criterio de
164 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
aceptacio´n de soluciones vecinas que se adapta a lo largo de su ejecucio´n. Hace uso de
las variables ya conocidas: Temperatura inicial Ti, Temperatura final Tf , alfa (α) y L(t).
Estos para´metros son los que se evalu´an en la seccio´n siguiente.
En RS, el criterio de Metropolis que permite aceptar soluciones vecinas se define como
sigue.
Definicio´n 2. Criterio de Metropolis.
Sea (S,C) un caso de un Problema de Optimizacio´n Combinatorio e i y j dos soluciones
con costo C(i) y C(j) respectivamente. Entonces el criterio, de Metropolis, para j es:
PT {aceptar j} =
{
1 si C(j) < C(i)
exp
(
C(i)−C(j)
T
)
si C(j) > C(i)
T > 0 es el para´metro de control, denominado generalmente temperatura. Si se permite
que T alcance valores suficientemente pequen˜os ya no habra´ ma´s movimientos a peores
soluciones y la convergencia sera´ a un o´ptimo local [11, 12].
El siguiente algoritmo de RS puede ser adaptable pra´cticamente a cualquier problema
de optimizacio´n combinatoria.
Algoritmo de RS (RS 1)
Sean C(s) el costo de la solucio´n actual y V (s) una vecindad
Seleccionar una solucio´n inicial sn
Seleccionar una temperatura inicial Ti > 0
Seleccionar funcio´n de reduccio´n de temperatura
Seleccionar un nu´mero de iteraciones nrep
Seleccionar un criterio de parada
REPETIR
REPETIR
seleccionar aleatoriamente una solucio´n s ∈ V (sn)
δ = C(s)− C(s0)
si δ < 0 entonces sn = s
si no
generar aleatoriamente x ∈ U(0, 1)
si x < exp(−δ/t), sn = s
fin si no
hasta que cuenta-iteraciones = nrep
t = α(t)
Hasta criterio de parada
Por otro lado, el algoritmo (RS 1), permite adecuarse al problema de CG. Se imple-
mentara´ la funcio´n de Costo 1 del Modelo CG con una variante sencilla del algoritmo
anterior y se ha escrito en pseudococo´digo con el fin de que sea adaptable al algoritmo de
particionamiento para CG.
Pseudoco´digo de RS (RS 2)
INPUT (T0, α, L(t), Tf )
algoritmo de recocido simulado con superficies de respuesta 165
T ← T0 (Valor inicial del para´metro de control)
Sact← Genera solucio´n inicial
WHILE T ≥ Tf DO (Condicio´n de parada)
BEGIN
FOR cont ← 1 TO L(T ) DO (Velocidad de Enfriamiento (T ))
BEGIN
Scand←Selecciona solucio´n N(Sact) (Generacio´n de una nueva solucio´n)
δ ← costo(Scand) − costo(Sact) (Ca´lculo de la diferencia de costos)
IF U(0, 1) < e(−δ/T ) OR (Aplicacio´n del criterio de aceptacio´n)
END
T ← α(T ) (Mecanismo de enfriamiento)
END
{Escribe como solucio´n la mejor de las Sact visitadas}
Finalmente el algoritmo de particionamiento para AGEBS con la inclusio´n de RS2
para CG queda integrado de la manera descrita en la seccio´n siguiente.
2.3 Algoritmo de recocido simulado y particionamiento para cluster geo-
gra´fico (RS-CG)
Sea n el nu´mero de objetos a clasificar.
UGij denota que el objeto i esta´ asignado al centroide j
i = 1, . . . , n; j = 1, . . . , k
Sea M = {M1,M2, . . . ,Mk} una solucio´n de K centroides
T0 es la temperatura inicial
Tf es la temperatura final
L(t) es el nu´mero de iteraciones que se van a realizar con la misma temperatura
1. Inicio
Obtiene Solucio´n inicial
Generar aleatoriamente centroides iniciales M =M1,M2, . . . ,Mk
Cualquier ageb puede ser centroide obtenido de forma aleatoria
costo act← Costo(M)∗
Esta asignacio´n representa ya una Solucio´n inicial, es una Solucio´n propuesta generada
por el paso anterior. En los siguientes pasos se genera otra Solucio´n (Solucio´n vecina)
para determinar que´ tan buena es con respecto a la actual y decidir si se cambia o no la
Solucio´n actual.
Mientras T ≥ Tf
mientras el sistema No este´ frio
Para cont = 1 hasta L(t) hacer
nu´mero de ciclos a realizar con la misma temperatura (parametro de RS)
C ← Genera una Solucio´n aleatoria
se genera la Solucio´n que se compara con *
costo cand← Costo(C)
166 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
se obtiene el costo de Solucio´n candidata que se ha generado
δ ← costo cand− costo act
diferencia de costos para obtener el valor de probabilidad de aceptacio´n de la solucio´n can-
didata
Si U(0, 1) < e−δ−T o´ δ < 0 hacer
si la probabilidad de aceptacio´n au´n es alta
M← C
si se acepta la Solucio´n candidata
costo act ← costo cand
Fin Si
Fin para
T ← α(T )
se esta´ enfriando el sistema
Fin Mientras
Fin
2. Funcio´n Costo (Sol)
determina que´ tan buena es la solucio´n SOL, es decir, que´ tanto minimiza el objetivo
i← 1
inicializa primer objeto
cost← 0
Mientras i ≤ n
para cada objeto en Ug hacer
si Ugi no es centroide entonces
dmin← dist(Sol1, Ugi)
representa la distancia del objetoi hacia Sol1 (primer centroide donde Sol representa al
conjunto de todos los centroides. Se calcula la distancia cada objeto a su centroide ma´s
cercano, (distancia de un objeto i que no es centroide hacia Sol1 que es el centroide 1)
j ← 2
paso al segundo centroide
Mientras j ≤ k
Si dist (Solj , Ugi) < dmin
se calcula la distancia del objeto i hacia Solj (otro centroide)
dmin← dist(Solj , Ugi)
Fin si
j ← j + 1
paso al siguiente centroide
Fin Mientras
cost← cost+ dmin
Fin si
i← i+ 1
Fin Mientras
algoritmo de recocido simulado con superficies de respuesta 167
Costo (Sol)← cost
Una vez implementado (RS − CG) y para observar la diferencia entre un o´ptimo y
las soluciones que genera dicho algoritmo, estas se han comparado con los resultados de
PAM dado que su proceso de clasificacio´n agota todas las combinaciones posibles y crea
un valor exacto en problemas pequen˜os pero con alto costo computacional [10, 20].
3 Ajuste de para´metros
Una de las pruebas que es importante realizar sobre los resultados obtenidos es evaluar la
calidad de los resultados usando para esto un me´todo sistema´tico que permita identificar
el efecto de los para´metros de control sobre el valor de la funcio´n de costo, modelar la
dependencia de esta funcio´n respecto a los para´metros y finalmente poder hacer un estudio
sobre la influencia de los para´metros en la bu´squeda por encontrar mı´nimos ya sea locales
o generales de la funcio´n [2]. Para ello hemos considerado un disen˜o experimental de
superficies de respuestas que nos ha permitido observar los efectos descritos en el pa´rrafo
anterior. Este tipo de experimento es una prueba o serie de pruebas en las cuales se
inducen cambios deliberados en algunas variables de entrada del sistema mientras otras
se mantienen fijas, de tal forma que es posible identificar las fuentes de los cambios en las
variables de salida [15].
3.1 Disen˜o de un experimento que permita modelar los resultados del
efecto de los predictores de la funcio´n de costo
La metodolog´ıa de superficies de respuesta es una combinacio´n de te´cnicas de disen˜o y
ana´lisis de experimentos que, utilizadas en forma secuencial, permiten determinar condi-
ciones de operacio´n que son o´ptimos locales para el problema a tratar. Una funcio´n
compleja suave puede aproximarse localmente (es decir, en zonas “pequen˜as” de la regio´n
de operacio´n) mediante polinomios de orden bajo. Si la zona donde se realiza la aprox-
imacio´n local esta´ “lejos” de la zona donde se encuentra un ma´ximo local entonces un
polinomio de primer orden debera´ ser una buena aproximacio´n. En cambio, si la zona
esta´ “cerca” del ma´ximo local sera´ necesario utilizar un polinomio de segundo orden para
describir a la funcio´n [15].
El ana´lisis sistematizado que hemos mencionado se desarrollo´ utilizando un disen˜o
tipo Box-Behnken (BB), este tipo de disen˜o por sus caracter´ısticas es fa´cil de llevar a
cabo definiendo niveles adecuados de los para´metros de disen˜o, adema´s de que es un
disen˜o rotable o sea con igual varianza para todos los puntos de experimentacio´n que se
encuentran a la misma distancia del centro del disen˜o, y por otro lado es posible hacer ex-
perimentos secuenciales para estudiar los efectos individuales de los para´metros de control
y los efectos combinados de los mismos de manera simultanea. Otra de las ventajas de
este disen˜o es que permite modelar los resultados con una funcio´n de segundo orden y por
lo tanto desarrollar un ana´lisis del comportamiento de la funcio´n de costo utilizando la
metodolog´ıa de superficies de respuesta. Los disen˜os BB se forman combinado factoriales
168 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
Para´metro Nivel Alto Nivel Central Nivel bajo
Ti 5500 5250 5000
Tf 0.1 0.055 0.01
A 0.99 0.985 0.98
L(t) 5 4 3
Grupos 24 18 12
Tabla 1: Niveles y para´metros utilizados en el experimento BB para el problema CG.
2k con disen˜o de bloques incompletos. Los disen˜os resultantes suelen ser ma´s eficientes en
te´rminos del nu´mero de corridas facilitando su generacio´n [15].
Para nuestro problema se ha utilizado un disen˜o BB con cinco para´metros de control
que giran alrededor de 24 grupos, el cual es un nu´mero que habla sobre un buen punto de
inflexio´n en la agrupacio´n [3, 5]. Con esta informacio´n introducida a BB, el experimento
resultante ha sido una muestra de 46 corridas significativas dado se han utilizado cuatro
puntos centrales [15]. La eleccio´n de los niveles de los para´metros usados en la construccio´n
del experimento obedece a los resultados obtenidos por el me´todo heur´ıstico, lo que ha
permitido definir una regio´n de experimentacio´n. Los niveles integrados se muestran en la
tabla 1.
Con estos nivles y el disen˜o BB se han llevado a cabo las 46 corridas experimentales
que se muestran en la tabla 2. La nomenclatura utilizada en la tabla es: C (corrida),
Ti (Temperatura Inicial), Tf (Temperatura final), α (alpha), Lt (L(t)), G (Grupos), FC
(Funcio´n Objetivo). En esta tabla, para la corrida 29 se obtiene el o´ptimo 14.12 para 12
grupos y para la corrida 31 se obtiene el o´ptimo 9.279 para 24 grupos.
Las figuras 1 y 2 muestran el comportamiento de la heur´ıstica para dos casos: 24
grupos que se ha identificado como el experimento ma´s confiable y 12 grupos como el
menos adecuado, es decir, al comparar la diferencia de la funcio´n de costo contra las
instancias de la tabla 2 para 24 grupos, notamos que el valor es menor que la diferencia de
otra funcio´n de costo hacia las corridas restantes. Para las corridas asociadas a 12 grupos
se observa que la diferencia que existe hacia el valor exacto es mayor que las corridas
respectivas para 18 y 24 grupos. En dichas figuras se observa el costo de la funcio´n
objetivo contra el nu´mero de iteraciones. Cada caso se ha extra´ıdo de la tabla anterior
eligiendo la corrida 36 como aquella que mejor se ha acercado al o´ptimo siendo el principal
para´metro de referencia el nu´mero de grupos. En la corrida 36 observamos que con 24
grupos y con los para´metros de Ti = 5500, Tf = .055, α = .985, L(t) = 4, se genero´ un
costo de la funcio´n objetivo de 11.2403, el ma´s cercano al o´ptimo obtenido por PAM que
es de 9.279. En contraste con el tiempo que logra PAM para generar la solucio´n exacta
que fue de 17 horas [6], RS con 3049 iteraciones, 2183 soluciones aceptadas, reduce el costo
computacional a un segundo.
algoritmo de recocido simulado con superficies de respuesta 169
C Ti Tf α Lt G FC C Ti Tf α Lt G FC
2 5500 0.01 0.985 4 18 13.588 25 5000 0.055 0.985 3 18 13.660
3 5000 0.1 0.985 4 18 14.034 26 5500 0.055 0.985 3 18 13.535
4 5500 0.1 0.985 4 18 14.122 27 5000 0.055 0.985 5 18 14.026
5 5250 0.055 0.98 3 18 13.917 28 5500 0.055 0.985 5 18 13.067
6 5250 0.055 0.99 3 18 14.129 29 5250 0.055 0.98 4 12 16.850
7 5250 0.055 0.98 5 18 13.235 30 5250 0.055 0.99 4 12 17.108
8 5250 0.055 0.99 5 18 13.893 31 5250 0.055 0.98 4 24 12.215
9 5250 0.01 0.985 4 12 16.216 32 5250 0.055 0.99 4 24 11.728
10 5250 0.1 0.985 4 12 16.55 33 5000 0.055 0.985 4 12 16.696
11 5250 0.01 0.985 4 24 11.539 34 5500 0.055 0.985 4 12 16.783
12 5250 0.1 0.985 4 24 12.029 35 5000 0.055 0.985 4 24 11.884
13 5000 0.055 0.98 4 18 16.302 36 5500 0.055 0.985 4 24 11.240
14 5500 0.055 0.98 4 18 14.110 37 5250 0.01 0.985 3 18 13.558
15 5000 0.055 0.99 4 18 13.916 38 5250 0.1 0.985 3 18 13.211
16 5500 0.055 0.99 4 18 13.955 39 5250 0.01 0.985 5 18 13.700
17 5250 0.055 0.985 3 12 15.635 40 5250 0.1 0.985 5 18 14.760
18 5250 0.055 0.985 5 12 16.084 41 5250 0.055 0.985 4 18 13.927
19 5250 0.055 0.985 3 24 12.331 42 5250 0.055 0.985 4 18 13.822
20 5250 0.055 0.985 5 24 11.638 43 5250 0.055 0.985 4 18 13.583
21 5250 0.01 0.98 4 18 13.520 44 5250 0.055 0.985 4 18 13.989
22 5250 0.1 0.98 4 18 14.304 45 5250 0.055 0.985 4 18 13.639
23 5250 0.01 0.99 4 18 13.3445 46 5250 0.055 0.985 4 18 12.901
Tabla 2: Corridas experimentales determinadas por el experimento BB.
170 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
Figura 1: Corrida 36 con 24 grupos. Figura 2: Corrida 17 con 12 grupos.
3.2 Verificacio´n del modelo experimental
En la figura 3 se observan los resultados de verificacio´n del modelo, concluyendo que los
datos se comportan normalmente, que el modelo de segundo orden es adecuado y que no
existen efectos de una corrida a otra en el experimento.
Figura 3: Verificacio´n del modelo.
Una vez desarrollado este experimento y analizando la informacio´n obtenida, se ha
ajustado los resultados con un modelo de regresio´n de segundo orden, obtenie´ndose la
ecuacio´n de prediccio´n mostrada en la tabla 3.
algoritmo de recocido simulado con superficies de respuesta 171
Te´rmino Coeficiente SE Coef T P
Constant 16963.0 6707.0 2.529 0.018
TI -0.5 0.2 -2.360 0.026
TF 358.1 1106.2 0.324 0.749
alfa -31921.4 13443.1 -2.375 0.026
l(t) -16.2 49.8 -0.326 0.747
grupos 6.2 8.3 0.742 0.465
TI*TI 0.0 0.0 1.301 0.205
TF*TF -0.4 84.0 -0.005 0.996
alfa*alfa 15020.8 6801.6 2.208 0.037
L(t)*L(t) -0.1 0.2 -0.692 0.495
grupos*grupos 0.0 0.0 2.323 0.029
TI*TF 0.0 0.0 0.028 0.978
TI*alfa 0.4 0.2 2.220 0.036
TI*l(t) 0.0 0.0 -0.831 0.414
TI*grupos 0.0 0.0 -0.727 0.174
TF*alpha -395.8 1116.3 -0.355 0.726
TF*l(t) 7.8 5.6 1.401 0.173
TF*grupos 0.1 0.9 0.152 0.880
alfa*L(t) 22.3 50.2 0.445 0.660
alfa*grupos -6.2 8.4 -0.742 0.465
l(t)*grupos 0.0 0.0 -1.138 0.266
Tabla 3: Regresio´n de segundo orden, con S = 0.5023, R2 = 93.8% y R˜2 = 88.8%.
172 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
4 Validacio´n de la variacio´n de los para´metros
En esta seccio´n mostramos las gra´ficas de superficies de respuestas y de prediccio´n que
son obtenidas con el modelo descrito en la seccio´n anterior. Se presentan los gra´ficos
de contorno que a su vez son generadas por conclusiones que responden al ana´lisis de
las superficies de respuesta. Esto es, al identificarse en que regiones se alcanzan valores
cercanos al o´ptimo de la funcio´n objetivo, y con el fin de observar gra´ficamente este
comportamiento, se han graficado contornos que revelan como esta funcio´n se ajusta para
regiones donde los para´metros de prediccio´n de la misma son los adecuados.
Figura 4: Funcio´n de costo 1. Figura 5: Funcio´n de costo 2.
En la funcio´n de costo 1 se ha mantenido fija la temperatura inicial, alfa y el nu´mero de
iteraciones. Como se puede observar al cambiar la temperatura final y el nu´mero de grupos,
se logra un mı´nimo de la funcio´n de costo para temperaturas finales pequen˜as y grandes
nu´meros de grupos. La funcio´n de costo 2 muestra el efecto sobre la funcio´n de costos
de variar la temperatura inicial y el nu´mero de grupos considerados en el experimento,
se ha mantenido en niveles fijos la temperatura final, α y el nu´mero de iteraciones para
L(t). En este punto se concluye que se logra un mı´nimo de la funcio´n de costo para una
temperatura inicial alta y el mayor nu´mero de grupos posibles (Figuras 4 y 5).
La figura 6 revela el resultado de la modelacio´n de la funcio´n de costo manteniendo fijas
la temperatura inicial y final con α. Considerando el comportamiento antes observado, el
mı´nimo continu´a apareciendo para el mayor numero de grupos, sin embargo en este caso
el mejor mı´nimo corresponde a un nu´mero bajo de iteraciones, incrementando su valor al
crecer el nu´mero de iteraciones. Este comportamiento es contrastante. En la funcio´n de
costo-4 se ha mantenido fija la temperatura inicial, la temperatura final y el nu´mero de
iteraciones, nuevamente encontramos que esta funcio´n es mı´nima para un numero grande
de grupos, en este caso adema´s observamos que alfa debe ser grande para lograr el mejor
mı´nimo; este comportamiento es consistente con lo observado en las anteriores figuras.
Del ana´lisis de las gra´ficas de modelacio´n antes mostradas podemos concluir lo siguien-
te:
1. La funcio´n de costo siempre tiene un mı´nimo para el nu´mero mayor de grupos.
algoritmo de recocido simulado con superficies de respuesta 173
Figura 6: Funcio´n de costo 3. Figura 7: Funcio´n de costo 4.
2. El mı´nimo ocurre para un nu´mero de iteraciones pequen˜as en el ca´lculo.
3. El valor de alfa debe ser grande
4. La temperatura final debe ser pequen˜a.
5. Y la temperatura inicial alta.
Este ana´lisis permite acotar la magnitud de los para´metros de impacto de la funcio´n de
costo, para buscar que esta sea un mı´nimo. A continuacio´n presentamos algunas gra´ficas
de contorno donde se obtienen mı´nimos de la funcio´n de costos, cuando hacemos uso de
las conclusiones antes obtenidas.
4.1 Gra´fico de contornos (curvas de nivel)
La figura 8 representa la curva de nivel de la funcio´n de costos ajustada para regiones
cercanas al o´ptimo para 24 grupos.
En el contorno para 24 grupos se ha fijado Tf a .01, α (alfa) a .98 y 24 grupos en la
regio´n donde se observan funciones de costo mı´nimas. Se distingue el comportamiento de
la funcio´n de costo para valores de Ti y L(t) cercanos al o´ptimo y al mismo tiempo destaca
el mı´nimo de la FC obtenido con los mejores para´metros.
4.2 Optimizacio´n de la funcio´n de costo usando el modelo de regresio´n
Recurriendo al modelo de segundo orden, en la siguiente figura se ha encontrado que con
la variacio´n de todos los para´metros en conjunto sin fijar a alguno en particular, es posible
obtener un valor muy cercano al o´ptimo. Siendo el costo real de la funcio´n objetivo de
9.27 para 24 grupos, el mı´nimo alcanzado en este caso es de y = 10.3597 y esta´ dado por
los para´metros de Ti = 5477.6723, Tf = 0.102, α = .980 y L(t) = 4.9775.
174 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
Figura 8: Contorno para 24 grupos.
Figura 9: Representacio´n del modelo de segundo orden para 24 grupos.
algoritmo de recocido simulado con superficies de respuesta 175
5 Conclusiones
De los resultados obtenidos en este trabajo, hemos podido concluir que los para´metros de
la heur´ıstica de recocido simulado implementada para el problema de cluster geogra´fico,
son sensibles para diferentes condiciones.
a.) En te´rminos generales entre mayor sea el nu´mero de grupos ma´s cerca estamos del
o´ptimo.
b.) La temperatura inicial debe estar pro´xima a 5000 unidades independientemente del
nu´mero de grupos el costo de la funcio´n objetivo converge al o´ptimo.
c.) Al fijar la temperatura final y alfa en los contornos, la variacio´n de los otros para´metros
restantes debe estar bajo control tal y como se muestra en las gra´ficas de contorno de
la seccio´n anterior. Se ha determinado entonces que para los 3 contornos resultantes,
fijando .01 para temperatura final y .98 en alfa se logra un buen mı´nimo en la funcio´n
de costo.
d.) Cuando se han considerado la variacio´n de todos los para´metros, es claro que un valor
de alfa de .980 debe ser exigido mientras que la temperatura final debe ser pequen˜a
con un valor de .01.
Dado que el experimento se inicio´ a partir de los resultados analizados en corridas
emp´ıricas donde se determino´ que 24 era un buen nu´mero de grupos [3, 5], el disen˜o que
hemos presentado en este trabajo fue alimentado tal y como se muestra en la tabla 1. Con
estos datos se desarrollo´ todo el trabajo correspondiente. No se reporto´ en este art´ıculo
el proceso para encontrar un punto estacionario debido a que no pudo ser observable y
por tanto no logramos encontrar la ecuacio´n cano´nica, tan u´til en experimentos como el
que hemos descrito. Una de las l´ıneas de trabajo a seguir parte de justamente este punto:
ampliar el experimento con un mayor nu´mero de grupos debido que este fue determinante
para alcanzar un mı´nimo.
Suponemos que al aumentar el valor de los para´metros y generar ma´s instancias, el
experimento siendo ma´s extenso dar´ıa lugar a encontrar la ecuacio´n cano´nica.
Por otro lado se esta´ trabajando con la heur´ıstica de vecindad variable para el problema
de cluster geogra´fico y construir un disen˜o de experimentos para esta heur´ıstica.
Finalmente estamos reportando la inclusio´n de un Sistema de Informacio´n Geogra´fica
con el fin de revelar los resultados en mapas de tal forma que sea evidente la agrupacio´n
geogra´fica compacta [21].
Referencias
[1] Bac¸a˜o, F.; Lobo, V.; Painho, M. (2004) “Applying genetic algorithms to zone de-
sign”, in Springer Verlag.
176 M. B. Berna´be – J. E. Espinosa – J. Ram´ırez Rev.Mate.Teor.Aplic. (2009) 16(1)
[2] Barr R.S.; Golden J.P.; Resende M.G.C.; Stewart W.R. (1995) “Designing and
Reporting on Computational Experiments with Heuristics Methods”, Journal of
Heuristics, 1: 9–32.
[3] Berna´be, L.B.; Lo´pez, S. (2004) “Statistical classificatory analysis applied to popula-
tion zones”, 8th. World Multiconference on Systemics, Cybernetics and Informatics,
Orlando.
[4] Berna´be, L.B.; Osorio, M.A.; Duque, J.C. (2006) “Clasificacio´n sobre zonas ge-
ogra´ficas: un enfoque de optimizacio´n combinatoria para el problema de regional-
izacio´n”, XIII CLAIO Congreso Latino-Iberoamericano de Investigacio´n Operativa,
Montevideo.
[5] Berna´be, L.B.; Aguirre, V.R.; Lo´pez, S.R. (2004) “Application of non-supervised
classification to population data”, ICEEE/CIE2004, International Conference on
Electrical and Electronics Engineering, Acapulco. ISBN 0-7803-8531-4.
[6] Berna´be, L.B. (2006) “Desarrollo de un modelo para la determinacio´n de zonificacio´n
o´ptima”, Proyecto de tesis doctoral en desarrollo, Posgrado de Ingenier´ıa UNAM,
Investigacio´n de Operaciones.
[7] Cliff, A.D.; Haggett, P.; Ord, J.K.; Bassett, K.A.; Davies, R.B. (1975), Elements
of Spatial Structure: a Quantitative Approach. Cambridge University Press, Cam-
bridge.
[8] Hess S.W.; Samuels S.A. (1971) “Experiences with a sales districting model: criteria
and implementation”, Management Science, Series B: Application 18: 41–54.
[9] Kalcsics, J.; Nickel, S.; Schro¨der, M. (2005) Towards a Unified Territory Design
Approach. Applications, Algorithms and GIS Integration. Universita¨t des Saarlandes,
Germany.
[10] Kaufman, L.; Rousseeuw, P. (1987) “Clustering by means of medoids”, Statistical
Data Analysis: 405–416.
[11] Kirkpatrick, S.; Gelatt, D.; Vecchi, M.P. (1983) “Optimization by simulated anneal-
ing”, Science 220: 671–680.
[12] Lebster, I. (1995) “Adaptative simulated annealing”, in: (ASA): lesson learned.
Technical Report, Control and Cybernetic, McLean VA.
[13] Macmillan, W.; (2001) “Redistricting in a GIS environment: an optimization algo-
rithm using switching points”, Journal of Geographical Systems 3: 167–80.
[14] Mehrotra, A.; Johnson, E.; Nemhauser, G. (1998) “An optimization based heuristic
for political districting”, Management Science 44: 1100–1114.
[15] Montgomery, D. (1991) Design and Analisis of Experiments, 2nd edition. Wiley,
New York.
algoritmo de recocido simulado con superficies de respuesta 177
[16] Murtagh F. (1985) “A survey of algorithms for contiguity–constrained clustering and
related problems”, Computer Journal 28: 82–88.
[17] Openshaw S.; Taylor P. (1981) “The modifiable area unit problem”, in: N. Wrigley
& R. Bennett(Eds.) Quantitative Geography, London: 60–70.
[18] Romero, D.; Burguete, J.; Mart´ınez, E.; Velasco, J. (2004) “Parcelacio´n del territorio
nacional: un enfoque de optimizacio´n combinatoria para la construccio´n de marcos
de muestreo en hogares”, INEGI, Me´xico.
[19] Rousseeuw, P.J.; Hubert, M.; Struyf, A. (1997) “Clustering in an object-oriented
environment”, Journal of Statistical Software 1: 2–10.
[20] MapX Developers Guide, MapInfo corporation, Troy NY.
[21] Takeshi, S. (2004) “A model of contiguity for spatial unit allocation”, Geographical
Analysis, Institute for Geoinformation, Technical University of Viena, Austria, ISSN
0016-7363.
[22] Zamora, A.E. (2006) “Implementacio´n de un algoritmo compacto y homoge´neo para
la clasificacio´n de zonas geogra´ficas AGEBs bajo una interfaz gra´fica”, Tesis de
Ingenier´ıa en Ciencias de la Computacio´n, BUAP, Puebla.
[23] Zoltners, A.; Sinha, P. (1983) “Towards a unified territory alignment: a review and
model”, Management Science 29: 1237–1256.
[24] http://www.inegi.gob.mx, Instituto Nacional de Estad´ıstica, Geograf´ıa e In-
foma´tica (INEGI), Me´xico.