Cómo funciona Crear zonas equilibradas

La herramienta Crear zonas equilibradas utiliza un algoritmo genético para crear en su área de estudio zonas espacialmente contiguas basadas en los criterios que usted especifique. Puede crear zonas que contengan un número idéntico de entidades, zonas que sean similares en función de un conjunto de valores de atributos, o siguiendo ambos criterios. También existen opciones para seleccionar zonas con áreas aproximadamente iguales, que sean lo más compactas posibles y que mantengan estadísticas de resumen uniformes (por ejemplo, promedios y proporciones) de otras variables.

Escenarios de ejemplo

Esta herramienta se puede utilizar en estos tipos de escenarios:

• Una empresa de venta minorista desea crear distritos en los que cada gerente sea responsable de un volumen de ventas y número de empleados idénticos, independientemente de la cantidad de establecimientos que tenga cada distrito.
• El cambio climático contribuye a aumentar la cifra anual de incendios forestales en muchas áreas, lo cual aumenta a su vez los costes en dichas regiones. Las administraciones públicas nacionales y locales pueden utilizar esta herramienta para igualar la carga de trabajo y los costes para sofocar incendios al crear distritos administrativos.
• Es posible crear distritos de patrullaje policial para repartir de forma equilibrada la carga de trabajo y las llamadas entre los agentes. Es posible eliminar el exceso o la escasez de personal en algunas áreas al equilibrar el índice delictivo de cada grupo de bloques y garantizar la oportunidad y eficacia de la respuesta policial.

Definir criterios para la selección y creación de zonas

Para que la herramienta cree zonas con un equilibrio óptimo, debe proporcionar los criterios que definan lo que significa que una zona sea óptima. Puede proporcionar dos tipos de criterios: los de creación de zonas y los de selección de zonas. La herramienta equilibra zonas alternando entre la creación y la selección de zonas, y los criterios que especifique para cada paso determinan las zonas finales equilibradas que recomienda la herramienta.

El paso de creación de zonas crea varias zonas que crecen aleatoriamente hasta que se cumplen los criterios de creación de zonas. Los criterios para la creación de zonas se deben entender como requisitos de sus zonas, y todas las zonas crecerán respetando dichos criterios (se ofrecen más detalles sobre el crecimiento de las zonas en la sección Crecimiento de zonas con el algoritmo genético). Después, el paso de selección de zonas clasifica cada conjunto de zonas y selecciona las mejores en función de lo que respeten los criterios de selección de zonas. En general, los criterios de selección de zonas se deben entender como preferencias más que como requisitos, y se utilizan para seleccionar de entre las zonas que ya cumplen los criterios de creación de zonas.

La elección de los criterios para la creación y selección de zonas depende de su circunstancia concreta; se ofrecen las siguientes opciones para el parámetro Método de creación de zonas para ayudarle a definir sus criterios correctamente:

• Objetivo de atributo: cada zona tendrá aproximadamente la misma suma total de un atributo, la cual se debe especificar. La cantidad de zonas creadas dependerá del total general del atributo. Por ejemplo, se puede utilizar esta opción para crear áreas de servicio que contengan unos 1.000 clientes. Si hay un total de 5.000 clientes entre todas las entidades de entrada, se crearán unas 5 zonas, cada una con unos 1.000 clientes. En caso de un total de dos millones de clientes, se crearán unas 2.000 zonas, cada una con unos 1.000 clientes.
• Número definido de zonas: el número de zonas debe ser igual que un número especificado, y cada zona estar compuesta de aproximadamente el mismo número de entidades. Esta opción resulta útil si sabe cuántas zonas necesita, y es necesario que cada zona contenga el mismo número de entidades de entrada.
• Número de zonas y objetivo de atributo: combina ambas opciones anteriores equilibrando la suma de un atributo entre un número concreto de zonas. Por ejemplo, se puede utilizar esta opción para crear justo 20 áreas de servicio que tengan aproximadamente el mismo volumen de ventas dentro de cada zona. Para esta opción, usted no proporciona la suma de atributo deseada, porque se determina al dividir la suma total del atributo entre el número de zonas. Esta opción no iguala el número de entidades de cada zona (sin embargo, es posible indicar la preferencia de un número idéntico de entidades como criterios de selección de zonas, tal y como se describe más adelante en este tema).

Criterios de creación de zonas

Existen distintos criterios de creación de zonas obligatorios para cada una de las opciones del parámetro Método de creación de zonas, y todas las zonas crecen hasta que se satisfacen estos criterios.

• Objetivo de atributo: debe proporcionar el atributo que desea equilibrar, así como una suma en el parámetro Criterios de creación de zonas con objetivo. Si lo desea, puede proporcionar varios atributos con sumas distintas y ponderaciones para cada atributo; así, algunos tendrán prioridad sobre otros.
• Número definido de zonas: debe proporcionar el número de zonas con el parámetro Número objetivo de zonas.
• Número de zonas y objetivo de atributo: debe proporcionar el número de zonas en el parámetro Número de zonas y proporcionar el atributo que equilibrar en el parámetro Criterios de creación de zonas. Puede volver a proporcionar varios atributos y ponderaciones para darles prioridad.

Criterios de selección de zonas

Los criterios de selección de zonas son opciones adicionales que le permiten especificar sus preferencias entre las zonas creadas en el paso de creación de zonas. Estos criterios se utilizan con los de creación de zonas para determinar qué zonas terminará recomendando la herramienta. La mayoría de criterios de selección de zonas son aplicables a todas las opciones del parámetro Método de creación de zonas. Las secciones que aparecen a continuación describen todas las opciones de selección de zonas y cuándo se aplican.

Criterios de características de zona

Las opciones del parámetro Características de zona suelen estar relacionadas con el tamaño y forma de las zonas. Puede usar alguna de estas opciones o todas ellas:

• Área igual: se da preferencia a las zonas cuya área es prácticamente igual. Esta opción solo se aplica cuando las entidades de entrada son polígonos.
• Compactación: se da preferencia a las zonas cuya área tiene una forma prácticamente circular. Esta opción se puede aplicar siempre.
• Número idéntico de entidades: se da preferencia a zonas compuestas aproximadamente por el mismo número de entidades. Esta opción no se aplica si se utiliza la opción Número definido de zonas, puesto que ese método de creación de zonas ya garantiza un número idéntico de entidades con los criterios de creación de zonas.

Criterios a tener en cuenta sobre los atributos

El parámetro Atributos para tener en cuenta permite especificar atributos adicionales que tener en cuenta y que no se utilizaron como criterios de creación de zonas. De esta manera, puede incluir zonas que mantienen una suma, promedio, varianza o mediana uniformes de un atributo. También tiene la opción de proporcionar varios atributos y así poder incluir zonas con la misma población total (suma) y aproximadamente la misma mediana de ingresos (mediana), por ejemplo.

Estos criterios de selección se aplican a todos los métodos de creación de zonas. Estos atributos deben ser continuos en lugar de ser de categorías a fin de poder utilizarse en este parámetro.

Mantener proporciones de variables de categorías

Con el parámetro Variable de categorías para mantener las proporciones puede especificar una variable de categorías que se utilizará para equilibrar las proporciones de las categorías de las zonas. También debe elegir un Método de proporción para especificar cómo se deben equilibrar las proporciones. Se ofrecen estos métodos de proporción:

• Mantener dentro de la proporción: se da preferencia a zonas que mantienen las mismas proporciones relativas de las categorías dentro de cada zona individual. Por ejemplo, si la variable de categorías que utiliza para mantener las proporciones representa una clasificación de cobertura de suelo binaria de bosque y sin bosque, y un 60 por ciento de las entidades tienen un tipo de cobertura de suelo de bosque y un 40 por ciento tienen un tipo de cobertura de suelo sin bosque, esta opción favorecerá las zonas en las que cada zona individual esté formada por un 60 por ciento de bosque y un 40 por ciento sin bosque.
• Mantener proporción general: se crearán zonas para que las proporciones generales del predominio de categorías coincidan con las proporciones de las categorías generales. Por ejemplo, si la variable de categorías representa si la entidad está en el suelo o en el agua, y un 60 por ciento de ellas están en el suelo, esta opción favorecerá las zonas en las que aproximadamente un 60 por ciento de ellas estén predominantemente en el suelo y un 40 por ciento estén predominantemente en el agua.

Estos criterios de selección se aplican a todos los métodos de creación de zonas. La variable debe ser de categorías en lugar de continua a fin de poder utilizarse en este parámetro.

Criterios basados en distancia

El parámetro Distancia a tener en cuenta permite favorecer zonas cercanas a un conjunto distinto de entidades (o varios conjuntos de entidades). Por ejemplo, si está creando distritos de administración de salud, puede favorecer las zonas más cercanas a hospitales existentes. La distancia entre una zona y una entidad se define con la distancia mediana de todas las entidades de la zona hasta la entidad más cercana como distancia a tener en cuenta.

Escenarios para elegir criterios de zona

Dispone de varias opciones para los criterios de creación y selección de zonas, y puede que no resulte obvio qué parámetros utilizar en función de sus requisitos y preferencias de zonas. A continuación, se muestran algunos escenarios junto con los parámetros que deberían utilizarse con ellos.

Escenario 1: Asignar bienes inmuebles a agentes inmobiliarios

Usted es un analista de una agencia inmobiliaria. Tiene una clase de entidad con todos los bienes inmuebles disponibles y sus costes en el área. En su agencia trabajan 12 agentes inmobiliarios y desea asignarles los bienes inmuebles de forma que cada agente tenga los mismos que los demás y el coste total de las propiedades de cada zona sea más o menos el mismo. También desea que las zonas estén cerca de sucursales existentes de la inmobiliaria.

Para ello, puede usar la opción Número de zonas y objetivo de atributo del parámetro Método de creación de zonas. Especifique 12 en el parámetro Número objetivo de zonas (una por cada agente inmobiliario) y elija el campo que representa el coste de cada propiedad en el parámetro Criterios de creación de zonas. Seleccione la opción Número idéntico de entidades del parámetro Características de zona para primar las zonas en las que cada agente tiene asignado y un número más o menos igual de propiedades. Para tener en cuenta la distancia a la sucursal de la inmobiliaria más cercana, proporcione una clase de entidad que represente las ubicaciones de las sucursales en el parámetro Distancia a tener en cuenta.

Escenario 2: Crear nuevos límites de distritos

Crear nuevos límites de distritos que equilibren el número de personas de cada distrito es una tarea difícil y complicada que se debe realizar con frecuencia en prácticamente todos los niveles de la administración pública. Con datos demográficos y de población recopilados en vecindarios pequeños, desea crear distritos que tengan aproximadamente 10.000 personas cada uno. Además, un 75 por ciento de la población vive en áreas urbanas y un 25 por ciento lo hace en áreas rurales. Desea que aproximadamente el 75 por ciento de las zonas sean mayoritariamente urbanas y que un 25 por ciento sean mayoritariamente rurales para representar adecuadamente cada grupo.

Para ello, puede usar la opción Objetivo de atributo del parámetro Método de creación de zonas. Seleccione el campo que representa el número de personas de cada vecindario y especifique 10.000 en las columnas del parámetro Criterios de creación de zonas con objetivo. Especifique un campo que represente si el vecindario es urbano o rural en el parámetro Variable de categorías para mantener las proporciones y seleccione la opción Mantener proporción general en el parámetro Método de proporción.

Escenario 3: Asignar carga de trabajo a agentes de libertad vigilada

Usted es un analista SIG de la división de las fuerzas policiales y se le ha encargado equilibrar la cantidad de casos de 25 agentes de libertad vigilada. Cuenta con las ubicaciones de todos los infractores de la ciudad, además de una evaluación de riesgos numérica de cada uno de ellos, y desea dividirlos equitativamente entre los agentes de libertad vigilada y, al mismo tiempo, mantener más o menos igual el riesgo total de los infractores. Sin embargo, el equilibrio del riesgo no es tan importante como tener la misma cantidad de infractores asignados a cada agente. Además, desea que las zonas sean lo más compactas posible para reducir los costes de viaje de los agentes de libertad vigilada.

Para ello, puede usar la opción Número definido de zonas del parámetro Método de creación de zonas y especificar 12 en el parámetro Número objetivo de zonas. Especifique el campo que representa el riesgo de cada infractor en el parámetro Atributos para tener en cuenta y seleccione la opción Compactación del parámetro Características de zona para crear zonas compactas.

Crecimiento de zonas con el algoritmo genético

Con los criterios que definió en la creación y selección de zonas, la herramienta Crear zonas equilibradas hace crecer zonas óptimas con el algoritmo genético (GA), dadas las restricciones espaciales de las entidades de entrada.

GA se basa en la teoría evolutiva de la selección natural y la genética, planteada por primera vez por Charles Darwin. Según el principio darwiniano de la supervivencia del más apto, los organismos más aptos en una población tienden a sobrevivir y a producir más descendientes.

Como el número de soluciones posibles normalmente es muy amplio, GA busca una solución optimizada: empieza con búsquedas aleatorias para después conducirlas hacia direcciones más prometedoras. La optimización de GA es una abstracción de la evolución biológica natural en la que cada posible solución (en este caso, cada posible disposición de zonas) es semejante a un organismo individual de una población. A medida que las generaciones avanzan, solamente los individuos más aptos siguen sobreviviendo, y solamente se permite continuar a las búsquedas más productivas.

El algoritmo empieza creando una población aleatoria en la que cada individuo de la misma es una posible solución. Se calcula una puntuación de aptitud para cada solución, los individuos con la puntuación de aptitud más baja (las mejores soluciones) en la población existente pasan a la nueva generación y las soluciones no aptas restantes se eliminan. Los individuos más aptos se designan como padres y pueden tener descendientes en parejas con operadores genéticos tales como los cruces y las mutaciones. Cada nueva generación es una combinación de los individuos más aptos de la generación anterior y sus descendientes. En algunas ocasiones, se introducen aleatoriamente individuos (que no son ni padres ni descendientes, denominados foráneos) en la siguiente generación para ampliar el rango de soluciones posibles descubiertas por el algoritmo. La puntuación de aptitud se calcula para todos los individuos de cada nueva generación, y el proceso se repite para un número concreto de generaciones (50 generaciones de forma predeterminada). El individuo más apto de la generación final representa las zonas equilibradas que devuelve la herramienta.

Elegir la población inicial

La población inicial del algoritmo se elige seleccionado aleatoriamente entidades del área de estudio. De forma predeterminada, la población estará formada por 100 individuos, pero esta cifra se puede modificar en el parámetro Tamaño de la población. Cada entidad seleccionada aleatoriamente es una ubicación de partida (denominada valor de inicialización) a partir de la cual la zona crece al incorporar entidades cercanas. La zona seguirá consolidándose y creciendo hasta que el valor total alcance el umbral de los criterios de creación de zonas. Por ejemplo, si proporciona una población de 100.000 y una cantidad de viviendas de 50.000 como los criterios de creación de zonas, los valores 100.000 y 50.000 son los valores de umbral de población y viviendas, respectivamente, y la zona deja de crecer una vez alcanzados todos los umbrales. En la siguiente zona, se selecciona un nuevo valor de inicialización fuera de la primera zona, que puede crecer aleatoriamente. El proceso continúa hasta que todas las entidades tengan una zona asignada.

En biología, el material genético de un individuo está comprendido en cromosomas. Los cromosomas están compuestos de genes, la unidad hereditaria de la vida. Para esta herramienta, una posible solución se asemeja a un cromosoma; y, los valores de inicialización, a los genes. Estos genes son las unidades hereditarias que los padres transfieren a sus descendientes y, por tanto, se utilizan para crear generaciones futuras. La siguiente imagen muestra un ejemplo de una posible solución junto con los valores de Id. de objeto de los valores de inicialización de cada zona de la solución:

Calcular la puntuación de aptitud

La puntuación de aptitud de cada posible solución es una medida del grado de precisión con el que las zonas resultantes respetan los diversos criterios de creación y selección de zonas proporcionados en la herramienta; las puntuaciones de aptitud más bajas indican una mejor adecuación a los criterios. Por tanto, el objetivo final consiste en encontrar una solución que proporcione una puntuación de aptitud baja (lo ideal sería la solución que proporcione la puntuación de aptitud más baja posible, denominada mínimo global). La puntuación de aptitud de una posible solución se calcula con la siguiente fórmula:

• n: cantidad total de zonas de la solución
• c: cantidad total de criterios utilizados para crear zonas y seleccionar soluciones.
• V_j: valor de umbral del criterio j^th.
• V_ij: suma del criterio j^th de la zona i^th.

La fórmula de la puntuación de aptitud debería entenderse como la suma de la diferencia de los valores de cada criterio respecto de los valores idealmente perfectos de cada zona de la solución. En una solución perfecta (la cual no suele ser posible), los valores de los criterios de todas las zonas equivalen a sus valores ideales, y la puntuación de aptitud es cero. Dividir entre el valor de umbral (V_j) garantiza que la puntuación de aptitud no tenga unidades. Es importante no tener unidades, ya que, por ejemplo, la puntuación de aptitud no se verá afectada por elegir metros cuadrados o pies cuadrados para las mediciones de área.

El parámetro Tabla de convergencia de salida proporciona la puntuación de aptitud total de la mejor solución en cada generación junto con las puntuaciones de cada criterio individual. Con la tabla de salida se crea un gráfico de convergencia para mostrar cómo estas puntuaciones de aptitud cambian de generación en generación. El algoritmo intenta encontrar una solución mejor que la existente, de modo que la línea de aptitud total del gráfico suele descender a medida que las generaciones progresan, hasta que finalmente se aplana. Este aplanamiento indica que la puntuación de aptitud ha alcanzado un mínimo local (que probablemente no sea el mínimo global), de modo que continuar con las generaciones futuras probablemente no mejore la solución.

Crear nuevas generaciones con cruces

Una vez el algoritmo ha generado la población inicial, se permite a la mitad de los individuos formar parte de la nueva generación y generar descendientes de nuevas posibles soluciones. Estos individuos se eligen en función de su aptitud (determinada por las puntuaciones de aptitud más bajas) y se emparejan aleatoriamente para generar descendientes mediante un proceso denominado cruce. Un cruce (en ocasiones denominado recombinación) es un operador genético que combina la información de dos padres para generar descendientes. La siguiente imagen muestra un ejemplo de los valores de inicialización de dos padres cruzados para crear dos nuevos descendientes:

Como resultado, la mitad de los individuos de las nuevas generaciones eran padres en la generación anterior, y la otra mitad son sus descendientes. Para esta nueva generación, se vuelve a calcular la puntuación de aptitud y la mitad superior avanza a la nueva generación, orientando la búsqueda hacia una mejor solución.

Ampliar las soluciones posibles con mutaciones y especies foráneas

La diversidad es muy importante en una población cambiante, y una forma de mantener dicha diversidad es la mutación. Las mutaciones son pequeños cambios o alteraciones introducidos en una secuencia de genes para crear individuos con códigos genéticos distintos. En esta herramienta, cualquier individuo que sufra una mutación tendrá sus valores de inicialización reorganizados aleatoriamente (permutados). Las siguientes imágenes muestran la única solución posible con una mutación y sus valores de inicialización reorganizados:

Puede controlar la probabilidad de que un descendiente sufra una mutación con el parámetro Factor de mutación, cuyo valor predeterminado es 0,1. Al introducir mutaciones se amplían las soluciones posibles y, muchas veces, permite al algoritmo converger rápidamente a una solución óptima a nivel local. Sin embargo, si los factores de mutación son muy elevados, se introducirán tantos cambios que el algoritmo perderá eficacia y tardará en converger (o directamente no lo hará).

Otra forma de ampliar las soluciones posibles consiste en introducir en la población nuevos individuos (denominados foráneos), los cuales ni forman parte de generaciones anteriores ni son descendientes. La introducción de individuos foráneos aumenta la probabilidad de obtener un mínimo global (en lugar de un mínimo local), y al mismo tiempo mantener una tasa elevada de convergencia. El factor de mutación controla la proporción de descendientes de cada generación que serán sustituidos por un foráneo con valores de inicialización generados aleatoriamente.

Grupos desconectados

Debido a las restricciones espaciales, en ocasiones puede tener grupos desconectados cuyas entidades no son vecinas de ninguna entidad del área de estudio más grande. Suele ser más común cuando las Entidades de entrada son polígonos que no son contiguos, como las islas. Las zonas solo pueden crecer agregando vecinos espaciales de las entidades existentes de la zona. Para resolverlo, la herramienta genera un vínculo entre cada grupo desconectado y la entidad más cercana fuera del grupo a fin de establecer una vecindad y que la zona pueda seguir creciendo. El campo Id. de grupo desconectado se agrega a la tabla de atributos de las Entidades de salida, lo que permite visualizar qué entidad o grupo de entidades se desconectaron en su área de estudio.

Recursos adicionales

• Coley, D. A. (1999). An introduction to genetic algorithms for scientists and engineers. World Scientific Publishing Company.
• Lorena, L. A. N., & Furtado, J. C. (2001). Constructive genetic algorithm for clustering problems. Evolutionary Computation, 9(3), 309-327.
• Patel, N., & Padhiyar, N. (octubre de 2010). Alien Genetic Algorithm for Exploration of Search Space. AIP Conference Proceedings (Vol. 1298, No. 1, pp. 325-330). AIP.