Cómo funciona Crear zonas equilibradas
La herramienta Crear zonas equilibradas utiliza un algoritmo genético para crear zonas espacialmente contiguas en el área de estudio en función de los criterios que 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 hay opciones para seleccionar zonas con áreas aproximadamente iguales, que sean lo más compactas posible y que mantengan estadísticas de resumen coherentes (como promedios y proporciones) de otras variables.
Ejemplos de escenarios
Esta herramienta se puede utilizar en estos tipos de escenarios:
Una empresa minorista quiere crear distritos en los que cada gerente sea responsable de un volumen de ventas y número de empleados iguales, independientemente del número de tiendas en cada distrito.
El cambio climático está contribuyendo a un aumento del número de incendios forestales anuales en muchas zonas, lo que incrementa los costes en esas zonas. Los gobiernos locales y nacionales pueden utilizar esta herramienta para igualar tanto la carga de trabajo como los costes de combatir incendios creando distritos administrativos.
Se pueden crear distritos de patrulla policial para equilibrar la carga de trabajo y las llamadas entre los agentes. El exceso de personal o la falta de personal en algunas zonas puede aliviarse equilibrando el índice de criminalidad de cada grupo de manzanas y asegurando la puntualidad y eficacia de la respuesta policial.
Definición de criterios para la creación y selección de zonas
Para que la herramienta cree zonas óptimamente equilibradas, debe proporcionar los criterios que definan qué significa que una zona sea óptima. Hay dos tipos de criterios que puede proporcionar: criterios de creación de zonas y criterios de selección de zona. La herramienta equilibra las zonas alternando entre la creación y la selección de zonas, y los criterios que especifique para cada paso determinan las zonas equilibradas finales recomendadas por la herramienta.
El paso de creación de zonas genera muchas zonas que crecen aleatoriamente hasta que se cumplen los criterios de creación de zonas. Los criterios para la creación de zonas deben considerarse requisitos de sus zonas, y todas crecerán de manera que cumplan estos criterios (en la sección zonas de cultivo con el algoritmo genético se proporcionan más detalles sobre cómo crecen las zonas). El paso de selección de zonas clasifica cada conjunto de zonas y selecciona las mejores en función de lo estrictamente que respetan los criterios de selección. En general, los criterios de selección de zonas deben considerarse preferencias más que requisitos, y se utilizan para seleccionar entre las zonas que ya cumplen con los criterios de creación de zonas.
La elección de los criterios que se van a utilizar en la creación y selección de zonas depende de sus circunstancias particulares, y se ofrecen las siguientes opciones para el parámetro Método de creación de zonas para ayudarle a definir correctamente sus criterios:
Objetivo de atributo: cada zona tendrá aproximadamente la misma suma total de un atributo, y esta suma total debe especificarse. El número de zonas que se crean depende del total general del atributo. Por ejemplo, esta opción puede usarse para crear áreas de servicio que contengan aproximadamente 1.000 clientes. Si hay 5.000 clientes en total entre todas las entidades de entrada, se crearán aproximadamente 5 zonas, cada una con cerca de 1.000 clientes. Con dos millones de clientes en total, se crearán aproximadamente 2.000 zonas, cada una con cerca de 1.000 clientes.
Número definido de zonas: el número de zonas debe ser igual a un número especificado, y cada zona está compuesta aproximadamente por el mismo número de entidades. Esta opción es útil cuando se sabe cuántas zonas se necesitan y se necesita que cada zona contenga el mismo número de entidades de entrada.
Número de zonas y objetivo de atributo: combina las dos opciones anteriores equilibrando la suma de un atributo entre un número determinado de zonas. Por ejemplo, esta opción se puede utilizar para crear exactamente 20 áreas de servicio que tengan aproximadamente el mismo volumen de ventas dentro de cada zona. Para esta opción, no se proporciona la suma de atributo deseada, ya que se determina dividiendo 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, se puede proporcionar una preferencia por un número igual de entidades como criterio de selección de zona, tal como se describe más adelante en este tema.
Ubicaciones de valores de inicialización personalizadas: cada zona crecerá a partir de un conjunto fijo de ubicaciones de valores de inicialización en función de los parámetros Puntos de ubicación de valores de inicialización y Entidades de entrada. El número total de zonas creadas se determina por el número de ubicaciones de valores de inicialización. El número de ubicaciones de valores de inicialización se basa en los puntos de ubicación de valores de inicialización y las entidades de entrada de la siguiente manera:
Si las entidades de entrada son polígonos, se seleccionarán como ubicaciones iniciales los polígonos que intersequen con los puntos de ubicación de valores de inicialización. Las zonas crecerán a partir de estas ubicaciones de valores de inicialización agregando entidades cercanas.
Si las entidades de entrada son puntos, se seleccionarán como valores de inicialización los puntos más cercanos a cada punto de ubicación de valores de inicialización.
Puede proporcionar variables adicionales y sus ponderaciones mediante el parámetro Criterios de creación de zonas.
Seleccione esta opción si tiene ubicaciones fijas alrededor de las cuales quieres que crezcan sus zonas. Por ejemplo, puede crear un espacio de defensa contra incendios alrededor de las rampas contra incendios existentes.
Criterios de creación de zonas
Se requieren criterios de creación de zonas diferentes para cada una de las opciones del parámetro Método de creación de zonas, y todas las zonas crecen hasta que satisfacen estos criterios.
Objetivo de atributo: debe proporcionar el atributo que quiere equilibrar y especificar una suma en el parámetro Criterios de creación de zonas con objetivo. Opcionalmente, puede proporcionar varios atributos con sumas diferentes y asignar ponderaciones a cada uno de ellos, de modo que algunos atributos se prioricen sobre otros al seleccionar ubicaciones con las puntuaciones de adecuación más bajas.
Número definido de zonas: debe proporcionar el número de zonas mediante 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 se va a equilibrar en el parámetro Criterios de creación de zonas. Puede volver a proporcionar múltiples atributos y ponderaciones para priorizarlos.
Ubicaciones de valores de inicialización personalizadas: debe proporcionar las ubicaciones de valores de inicialización a partir de las cuales crecerán las zonas en el parámetro Puntos de ubicación de valores de inicialización. El número de zonas vendrá determinado tanto por el número de puntos de ubicación de valores de inicialización como por las entidades de entrada. Puede proporcionar variables adicionales y sus ponderaciones mediante el parámetro Criterios de creación de zonas.
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 junto con los criterios de creación de zonas para determinar qué zonas recomendará finalmente la herramienta. La mayoría de los criterios de selección de zonas se aplican a todas las opciones del parámetro Método de creación de zonas. Las secciones siguientes describen cada una de las opciones de selección de zonas y cuándo son aplicables.
Criterios de características de zona
Las opciones del parámetro Características de zona generalmente se relacionan con el tamaño y la forma de las zonas. Puede utilizar cualquiera o todas las siguientes opciones:
Área igual: se da preferencia a zonas que son casi iguales en área. Esta opción solo se aplica cuando las entidades de entrada son polígonos.
Compactación: se da preferencia a zonas que son de forma casi circular. Esta opción siempre es aplicable.
Igual número de entidades: se da preferencia a zonas compuestas por aproximadamente el mismo número de entidades. Esta opción no se aplica cuando se utiliza la opción Número definido de zonas porque ese método de creación de zonas ya garantiza un número igual de entidades con criterios de creación de zonas.
Criterios de consideración de atributos
El parámetro Atributo para tener en cuenta permite especificar atributos adicionales que deben tenerse en cuenta y que no se usaron como criterios de creación de zonas. Esto permite incluir zonas que mantengan una suma, un promedio, una varianza o una mediana coherentes de un atributo. También puede proporcionar varios atributos, de modo que, por ejemplo, pueda incluir zonas que tengan la misma población total (suma) y aproximadamente la misma renta mediana (mediana).
Este criterio de selección se aplica a todos los métodos de creación de zonas. Los atributos deben ser continuos en lugar de categóricos para poder usarse en este parámetro.
Mantener proporciones de variables categóricas
El parámetro Variable de categorías para mantener las proporciones permite especificar una variable categórica que se usará para equilibrar las proporciones de las categorías en las zonas. También debe elegir un Método de proporción para especificar cómo deben equilibrarse las proporciones. Se proporcionan los siguientes 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 categórica que usas para mantener proporciones representa una clasificación binaria de cobertura del suelo entre bosque y no bosque, y el 60 por ciento de las características tienen un tipo de cobertura del suelo de tipo forestal y el 40 por ciento un tipo de cobertura del suelo no forestal, esta opción favorecerá zonas donde cada zona individual esté compuesta por un 60 por ciento de bosque y un 40 por ciento de no bosque.
Mantener proporción general: las zonas se crearán de modo que las proporciones generales de predominio de categorías coincidan con las proporciones de las categorías globales. Por ejemplo, si la variable categórica representa si la entidad está en tierra o en agua, y el 60 por ciento de las entidades están en tierra, esta opción favorecerá zonas en las que aproximadamente el 60 por ciento de las zonas estén predominantemente en tierra y el 40 por ciento de las zonas estén predominantemente en agua.
Este criterio de selección se aplica a todos los métodos de creación de zonas. La variable debe ser categórica, y no continua, para poder utilizarse en este parámetro.
Criterios basados en la distancia
El parámetro Distancia a tener en cuenta permite favorecer zonas que estén cerca de un conjunto diferente de entidades (o de varios conjuntos de entidades). Por ejemplo, si está creando distritos de administración sanitaria, puede favorecer zonas que estén cerca de hospitales existentes. La distancia entre una zona y una entidad se define mediante la distancia mediana desde todas las entidades de la zona hasta la entidad más cercana proporcionada como distancia que se va a considerar.
Escenarios para elegir los criterios de zona
Existen muchas opciones disponibles para los criterios de creación de zonas y selección de zonas, y puede que no resulte evidente de inmediato qué parámetros utilizar en función de sus requisitos y preferencias en cuanto a las zonas. A continuación, se presentan algunos escenarios junto con los parámetros que deben utilizarse para ellos.
Escenario 1: Asignar anuncios inmobiliarios a agentes inmobiliarios
Es analista en una agencia inmobiliaria. Tiene una clase de entidad con todos los anuncios inmobiliarios disponibles y sus precios en el área. Hay 12 agentes inmobiliarios en su agencia y quiere asignarles los anuncios inmobiliarios de modo que cada agente reciba el mismo número de anuncios y que el precio total de las propiedades de cada zona sea aproximadamente el mismo. También quiere que las zonas estén cerca de las sucursales inmobiliarias existentes.
Para lograrlo, puede utilizar 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 precio de cada propiedad en el parámetro Criterios de creación de zonas. Elija la opción Igual número de entidades en el parámetro** Características de zona** para favorecer zonas en las que a cada agente inmobiliario se le asigne un número aproximadamente igual de propiedades. Para tener en cuenta la distancia a la sucursal 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 distrito
Crear nuevos límites de distrito que equilibren el número de personas dentro de cada distrito es una tarea complicada y difícil que debe realizarse con frecuencia en casi todos los niveles de gobierno. Utilizando datos de población y demográficos recopilados en barrios pequeños, quiere crear distritos que tengan cada uno aproximadamente 10.000 habitantes. Además, cerca del 75 por ciento de la población vive en zonas urbanas y el 25 por ciento en zonas rurales. Quiere que aproximadamente el 75 por ciento de las zonas sean mayoritariamente urbanas y el 25 por ciento mayoritariamente rurales para representar a cada grupo de manera adecuada.
Para lograrlo, puede usar la opción Objetivo de atributo en el parámetro Método de creación de zonas. Elija el campo que representa el número de personas en cada barrio 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 barrio es urbano o rural en el parámetro Variable de categorías para mantener las proporciones, y elija la opción Mantener proporción general en el parámetro Método de proporción.
Escenario 3: Asignar la carga de trabajo a agentes de libertad condicional
Es analista SIG de la división de fuerzas del orden y se le ha encargado equilibrar la carga de trabajo de 25 agentes de libertad condicional. Tiene las ubicaciones de todos los delincuentes de la ciudad, junto con una evaluación numérica del riesgo de cada uno, y quiere dividirlos de forma equitativa entre los agentes de libertad condicional, manteniendo al mismo tiempo un riesgo total de los delincuentes aproximadamente igual. Sin embargo, el equilibrio del riesgo no es tan importante como asignar el mismo número de delincuentes a cada agente de libertad condicional. Además, quieres que las zonas sean lo más compactas posible para reducir los costes de desplazamiento de los agentes de libertad condicional.
Para lograrlo, 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 delincuente en el parámetro Atributo para tener en cuenta y elija la opción Compactación en el parámetro Características de zona para crear zonas compactas.
Escenario 4: Crear zonas equilibradas de respuesta a emergencias a partir de los parques de bomberos existentes
Es analista de SIG en el departamento de gestión de emergencias de una ciudad y necesita definir zonas de cobertura de servicio para la respuesta ante incendios y emergencias sanitarias. La ciudad cuenta con parques de bomberos existentes, y cada parque debe actuar como una ubicación fija de valor de inicialización para una zona de respuesta.
Tiene datos que representan bloques censales y la demanda de incidentes, y quiere asignar estas áreas a los parques de bomberos para que cada parque atienda una carga de trabajo total similar, como población y volumen histórico de llamadas. Aunque equilibrar la carga de trabajo es importante, también es fundamental que se pueda llegar a cada zona dentro de un tiempo de respuesta aceptable desde el parque de bomberos asignado. Por lo tanto, quiere que las zonas sean geográficamente compactas para reducir la distancia de desplazamiento y mejorar la eficiencia de la respuesta.
Para lograrlo, puede utilizar la opción Ubicaciones de valores de inicialización personalizadas del parámetro Método de creación de zonas y proporcionar las ubicaciones de los parques de bomberos como puntos de ubicación de valores de inicialización. Especifique los campos que representan la población y la demanda total de llamadas en el parámetro Criterios de creación de zonas, y priorice la compacidad en el parámetro Características de zona. Esto garantiza que las zonas crezcan hacia fuera desde cada parque de bomberos, sigan siendo espacialmente cohesivas y distribuyan la carga de trabajo de la forma más equitativa posible, respetando al mismo tiempo las ubicaciones fijas de los parques de bomberos.
Zonas de cultivo con el algoritmo genético
Usando los criterios que definió para la creación y selección de zonas, la herramienta Crear zonas equilibradas incrementa las zonas óptimas usando el algoritmo genético (GA), dadas las restricciones espaciales de las entidades de entrada.
AG se basa en la teoría evolutiva de la selección natural y la genética, tal como la explicó por primera vez Charles Darwin. Según el principio darwiniano de la supervivencia del más apto, los organismos más aptos de una población tienden a sobrevivir y a producir más descendencia.
Dado que el número de soluciones posibles suele ser muy elevado, AG busca una solución optimizada comenzando con búsquedas aleatorias y dirigiendo las búsquedas hacia direcciones más prometedoras. La optimización mediante AG es una abstracción de la evolución biológica natural, en la que cada solución posible (en este caso, cada posible disposición de zonas) es análoga a un organismo individual de una población. A medida que avanzan las generaciones, solo los individuos más aptos siguen sobreviviendo, y solo se permite continuar a las búsquedas más productivas.
El algoritmo comienza creando una población aleatoria en la que cada individuo de la población es una solución posible. Se calcula una puntuación de adecuación para cada solución; los individuos con la puntuación de adecuación más baja (las mejores soluciones) de la población existente pasan a la siguiente generación, y las soluciones restantes no aptas se eliminan. Los individuos más aptos se designan como progenitores y pueden crear descendencia por parejas utilizando operadores genéticos como el cruce y la mutación. Cada nueva generación es una combinación de los individuos más aptos de la generación anterior y su descendencia. A veces, se introducen aleatoriamente individuos (que no son ni progenitores ni descendencia, denominados individuos externos) en la siguiente generación para ampliar el abanico de posibles soluciones descubiertas por el algoritmo. La puntuación de adecuación se calcula para todos los individuos de cada nueva generación, y el proceso se repite durante un número determinado de generaciones (50 generaciones, de forma predeterminada). El individuo más apto de la generación final corresponde a las zonas equilibradas que devuelve la herramienta.
Elección de la población inicial
La población inicial para el algoritmo se elige seleccionando aleatoriamente entidades en el área de estudio o utilizando ubicaciones de valores de inicialización personalizadas. De forma predeterminada, la población estará compuesta por 100 individuos, pero el número puede cambiarse en el parámetro Tamaño de población. Cada entidad seleccionada aleatoriamente es una ubicación inicial (denominada valor de inicialización) a partir de la cual la zona crece agregando entidades cercanas. Una zona seguirá agregando entidades y creciendo hasta que el valor total alcance el umbral de los criterios de creación de zonas. Por ejemplo, si proporcionas una población de 100.000 y un número de hogares de 50.000 como criterios de creación de zonas, los valores 100.000 y 50.000 son los valores de umbral de población y hogares, respectivamente, y la zona deja de crecer una vez alcanzados todos los umbrales. Para la siguiente zona, se selecciona un nuevo valor de inicialización fuera de la primera zona y se permite que crezca aleatoriamente. El proceso continúa hasta que todas las entidades se asignan a una zona.
En biología, el material genético de un individuo está contenido en los cromosomas. Los cromosomas están compuestos por genes, la unidad hereditaria de la vida. Para esta herramienta, una posible solución es análoga a un cromosoma, y los valores de inicialización son análogos a los genes. Estos genes son las unidades hereditarias transferidas de los progenitores a su descendencia y, por tanto, se utilizan para crear generaciones futuras. La imagen siguiente 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:
Cálculo de la puntuación de aptitud
La puntuación de aptitud de cada posible solución es una medida de hasta qué punto las zonas resultantes cumplen los distintos criterios de creación de zonas y selección de zonas proporcionados en la herramienta; las puntuaciones de aptitud más bajas indican un mejor ajuste a los criterios. Por tanto, el objetivo final es encontrar una solución que proporcione una puntuación baja de aptitud (idealmente, será la solución que proporcione la puntuación de aptitud más baja posible, que se denomina mínimo global). La puntuación de aptitud correspondiente a una posible solución se calcula usando la siguiente fórmula:
\(n\): número total de zonas en la solución.
\(c\): número total de criterios utilizados para crear zonas y seleccionar soluciones.
\(V_j\): valor de umbral del criterio jth.
\(V_{ij}\): suma de los criterios jth de la zona ith.
La fórmula de la puntuación de aptitud debe entenderse como la suma de cuánto difieren los valores de cada criterio de los valores idealmente perfectos de cada zona de la solución. En una solución perfecta (que generalmente no es posible), los valores de los criterios de todas las zonas igualan sus valores ideales, y la puntuación de aptitud es cero. Dividir entre el valor umbral (Vj) garantiza que la puntuación de adecuación no tenga unidades. Que no tenga unidades es importante porque, por ejemplo, utilizar metros cuadrados o pies cuadrados para las mediciones de área no afectará a la puntuación de aptitud.
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. Se crea un gráfico de convergencia con la tabla de salida para mostrar cómo cambian estas puntuaciones de aptitud a lo largo de las generaciones. El algoritmo intenta encontrar una solución mejor que la existente, por lo que la línea de aptitud total del gráfico suele disminuir a medida que avanzan las generaciones, hasta que finalmente se estabiliza. Este aplanamiento indica que la puntuación de aptitud ha alcanzado un mínimo local (aunque probablemente no el mínimo global), y es probable que continuar con generaciones futuras no mejore la solución.
Además de la tabla de convergencia de salida, los mensajes de geoprocesamiento también le ayudarán a comprender hasta qué punto se han generado correctamente las zonas. Se proporciona la raíz del error cuadrático medio para cada uno de los criterios de creación de zonas y selección de zonas. Cuanto menor sea el valor, mejor cumplirán las zonas los criterios.
Crear nuevas generaciones mediante cruce
Una vez que el algoritmo genera la población inicial, la mitad de los individuos puede participar en la siguiente generación y crear descendencia de nuevas soluciones posibles. Estos individuos se eligen en función de su aptitud (determinada por las puntuaciones de aptitud más bajas) y se emparejan aleatoriamente para producir descendencia mediante un proceso denominado cruce. El cruce (a veces denominado recombinación) es un operador genético que combina la información de dos progenitores para generar descendencia. La imagen siguiente muestra un ejemplo de los valores de inicialización de dos progenitores que se cruzan para crear dos nuevos descendientes:
Como resultado, la mitad de los individuos de las nuevas generaciones fueron padres de la generación anterior y la otra mitad son sus descendientes. Para esta nueva generación, de nuevo se calcula la puntuación de aptitud y la mitad superior avanza a la siguiente generación, impulsando la búsqueda de una mejor solución.
Ampliar las soluciones posibles con mutaciones e individuos externos
La diversidad es muy importante en una población en evolución, y una forma de mantenerla es a través de la mutación. Las mutaciones son pequeños cambios o alteraciones introducidos en una secuencia de genes para crear individuos con diferentes códigos genéticos. En esta herramienta, cualquier individuo que sufra una mutación tendrá sus valores de inicialización reorganizados (permutados) aleatoriamente. La imagen siguiente muestra una posible solución que pasa por una mutación y cuyos valores de inicialización se reorganizan:
La probabilidad de que una descendencia sufra una mutación puede controlarse con el parámetro Factor de mutación, y el valor predeterminado es 0,1. Introducir mutaciones amplía las soluciones posibles y, a menudo, permite que el algoritmo converja rápidamente hacia una solución localmente óptima. Sin embargo, los factores de mutación muy altos introducirán tantos cambios que el algoritmo perderá eficiencia y convergerá lentamente (o no convergerá en absoluto).
Otra forma de ampliar las soluciones posibles consiste en introducir nuevos individuos en la población (denominados individuos externos) que no forman parte de generaciones anteriores ni de su descendencia. La introducción de individuos externos aumenta la probabilidad de obtener un mínimo global (en lugar de un mínimo local), manteniendo al mismo tiempo una tasa de convergencia elevada. El factor de mutación controla la proporción de descendientes de cada generación que serán sustituidos por un individuo externo compuesto por valores de inicialización generados aleatoriamente.
Grupos desconectados
Debido a limitaciones espaciales, a veces puede haber grupos desconectados cuyas entidades no son vecinas de ninguna entidad del área de estudio más amplia. Esto es más habitual cuando las entidades de entrada son polígonos no contiguos, como islas. Las zonas solo pueden crecer agregando vecinos espaciales de las entidades existentes en la zona. Para resolverlo, la herramienta genera un vínculo entre cada grupo desconectado y la entidad más cercana fuera del grupo para establecer una vecindad y permitir que la zona siga creciendo. El campo ID de grupo desconectado se agrega a la tabla de atributos de las entidades de salida que le permite visualizar qué entidad o grupo de entidades estaban desconectados en el á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. (2010, October). Alien Genetic Algorithm for Exploration of Search Space. AIP Conference Proceedings (Vol. 1298, No. 1, pp. 325-330). AIP.