Modelación Matemática en la
Distritación
Miguel Ángel Gutiérrez Andrade
Universidad Autónoma Metropolitana
Contenido
•
•
•
•
•
Definición del problema
Técnicas heurísticas empleadas
Instancias
Comparaciones
Conclusiones
El problema de diseño de zonas
Agrupar un conjunto de unidades geográficas en zonas, tales que
minimizan una función objetivo y satisfacen ciertas restricciones
El problema de diseño de zonas
Agrupar un conjunto de unidades geográficas en zonas, tales que
minimizan una función objetivo y satisfacen ciertas restricciones
El problema de diseño de zonas
Agrupar un conjunto de unidades geográficas en zonas, tales que
minimizan una función objetivo y satisfacen ciertas restricciones
El problema de diseño de zonas
Agrupar un conjunto de unidades geográficas en zonas, tales que
minimizan una función objetivo y satisfacen ciertas restricciones
Características del problema
• Problema de optimización combinatoria
• NP-Duro
• Crear un plan de zonificación conexo y con equilibrio poblacional
es un problema NP-duro
• Crear un plan de zonificación que maximice la compacidad es un
problema NP- duro
Complejidad computacional
El número total de soluciones para dividir n UG en k zonas está
dado por el número de Stirling del segundo tipo:
S  n, k  
1
k!
k

i 0


n
k!
  1 
  k  i 
 k  i ! i ! 
i
Unidades geográficas
10
50
80
150
250
Número de planes
511
5.6 x 1014
6.04 x 1023
7.13 x 1044
9 x 1074
Años requeridos
6.4 x 10-21
7.1 x 10-9
7.6
9.0 x 1021
1.1 x 1052
Se muestra el número posible de planes de zonificación para
dividir un estado hipotético en dos zonas.
Se considera una computadora capaz de realizar 2.5 x 1015
planes por segundo.
Zonas electorales
Diseño de
zonas
electorales
Zonas electorales
Conexidad
Equilibrio
poblacional
Compacidad
geométrica
Diseño de
zonas
electorales
Características del problema
Conexidad
Equilibrio
poblacional
Compacidad
geométrica
Características del problema
Conexidad
Equilibrio
poblacional
Compacidad
geométrica
Capacidad de conectar
unidades geográficas
de
una
zona
mediante unidades
que también formen
parte de dicha zona.
Es una restricción del
problema.
Características del problema
Conexidad
Equilibrio
poblacional
Compacidad
geométrica
Busca que todas las
zonas contengan la
misma cantidad de
habitantes y penaliza
las diferencias.
Se incluye en
función objetivo
la
Características del problema
Conexidad
Equilibrio
poblacional
Compacidad
geométrica
Busca que las zonas
sean homogéneas y
sin irregularidades o
figuras confusas.
Se incluye en la
función objetivo
Equilibrio poblacional
Conforme al Acuerdo del Consejo General CG-104-2004
PT
n

PN
d
( 300 ) (100 )
PT
 Ps 

PN
d
( 300 ) (100 )
n
donde :
PN  población
total nacional.
Ps  población
del distrito
PT  población
total de la entidad.
d  porcentaje
de desviación
aceptable
n  número
por distrito
de distritos
s.
poblaciona
l
(10% o 15% según caso).
en la entidad.
Equilibrio poblacional
2

s S
 100 PT
  PS
1
 

 
n
 d ( PN 300)   PT
2
Compacidad geométrica

s S
PS
4  AS

1
2
Donde
Ps es el perímetro de la zona s
As es el área de la zona s
Función objetivo
Minimizar C(P) = α1C1(P) + α2C2(P)
Donde
Zs = { i : xis = 1}, es el conjunto de UG en la zona s S
P = {Z1, Z2, Z3,…, Zn}, es un plan de zonificación
C1(P), es el costo de equilibrio poblacional del plan P
C2(P), es el costo de compacidad del plan P
α1, α2, factores de ponderación
Técnicas heurísticas
• Para el proceso electoral del 2006 el IFE utilizó un algoritmo
basado en recocido simulado.
• Se diseñaron:
• Recocido simulado
• Optimización por Enjambre de Partículas (PSO).
• Colonia de abejas artificiales (ABC).
• Se aplicaron a los estados de Baja California, Chiapas , Distrito
Federal, Guanajuato y México.
Recocido simualdo
• Heurística propuesta por Kirkpatrick en 1983.
• Se basa en una analogía entre el proceso de optimización y el
recocido de sólidos.
• Inicia con una solución y en cada iteración genera soluciones
vecinas.
• La solución actual es reemplazada por la nueva si esta última
mejora el costo de la función objetivo.
• En caso contrario, utilizar el criterio de Metrópolis para
aceptar o rechazar.
 f P   f P  
p  exp  

A
B
T


• Este proceso se repite hasta que la temperatura de
enfriamiento es alcanzada.
Optimización por enjambre de partículas
• Heurística de inteligencia colectiva (Kennedy, Eberhart, 1995)
• Una población de partículas se mueve en el espacio de
soluciones
• Cada partícula toma en cuenta dos factores:
• El conocimiento y habilidades propias adquiridas durante su vida.
• La influencia del líder.
Optimización por enjambre de partículas
Movimiento
actual
Nueva dirección
Mejor global
Mejor personal
Colonia de abejas artificiales
• Heurística inspirada en el proceso de recolección de las abejas
(Karaboga, 2005).
• Cada fuente de alimento representa una solución.
• Existe tres tipos de abejas:
• Recolectora: Tiene asignada una fuente de alimento, explora
regiones vecinas, reporta la calidad de la fuente actual.
• Observadoras: Elige una fuente de alimento con base en su
calidad, explora regiones vecinas, evalúa la calidad de las fuentes.
• Exploradoras: Buscan nuevas fuentes de alimento cuando se
deben abandonar las fuentes agotadas.
Implementación
Estados
Baja California
Chiapas
Distrito Federal
Guanajuato
Estado de México
Población
2, 487, 367
3, 920, 892
8, 605, 239
4, 663, 032
13, 096, 686
UG´s Zonas
319
8
229
12
860
27
454
14
836
40
Implementación
• Se consideraron los factores de ponderación
α1 = {0.9, 0.8,…, 0.1, 0.01}, α2 = 1 - α1
• Para disminuir el efecto estocástico se realizaron 10 corridas
para cada factor.
• Cada ejecución produce una solución. Las 100 soluciones de
cada algoritmo fueron filtradas para obtener las soluciones no
dominadas.
• Para promover igualdad en la comparación cada algoritmo
puede realizar 200,000 llamadas a la función objetivo.
Chiapas
Chiapas
Equilibrio poblacional
4.5
4
3.5
3
2.5
RS
2
PSO
1.5
ABC
1
0.5
0
20.5
21.5
22.5
23.5
Compacidad
24.5
25.5
Estado de México
Estado de México
Equilibrio poblacional
11.7
11.5
11.3
11.1
10.9
RS
10.7
PSO
10.5
ABC
10.3
10.1
9.9
63
65
67
69
71
73
Compacidad
75
77
Distrito Federal
Equilibrio poblacional
8.5
8
7.5
7
6.5
RS
6
PSO
5.5
ABC
5
4.5
4
33
35
37
39
41
Compacidad
43
45
47
Baja California
Equilibrio poblacional
1.57
1.37
1.17
0.97
RS
PSO
0.77
ABC
0.57
0.37
0.17
11
11.5
12
12.5
13
Compacidad
13.5
14
14.5
Guanajuato
Equilibrio poblacional
4.7
4.6
4.5
4.4
4.3
4.2
RS
4.1
PSO
4
ABC
3.9
3.8
3.7
25
25.5
26
26.5
27
27.5
Compacidad
28
28.5
29
Conclusiones
• Se presentaron 3 algoritmos basados en técnicas heurísticas.
• Se aplicaron en 5 estados de la República Mexicana.
• Los resultados de cada algoritmo fueron evaluados en
términos de su convergencia y dispersión.
• Colonia de Abejas Artificiales presenta resultados de mejor
calidad.
• Se propone implementar versiones multi-objetivo y
determinar si la calidad de las soluciones puede ser mejorada.
Gracias por su atención
Descargar

DISEÑO DE ZONAS