Fonctionnement de l’outil Créer des zones équilibrées

L’outil Créer des zones équilibrées utilise un algorithme génétique pour créer des zones spatialement contiguës dans votre zone d’étude en fonction de critères que vous précisez. Vous pouvez créer des zones qui contiennent un nombre égal d’entités, qui sont similaires du point de vue d’un ensemble de valeurs attributaires, ou les deux à la fois. Certaines options permettent également de sélectionner des zones avec des surfaces approximativement égales, qui sont aussi compactes que possible et qui assurent la cohérence des résumés statistiques (moyennes et proportions, par exemple) des autres variables.

Exemples de scénarios

Il est possible d’utiliser cet outil dans les types de scénarios suivants :

• Une société de vente au détail désire créer des secteurs dans lesquels chaque dirigeant est responsable d’un volume de ventes et d’un nombre d’employés égal, quel que soit le nombre de points de vente implantés dans chaque secteur.
• Le changement climatique contribue à la hausse du nombre annuel de feux de forêt dans de nombreuses zones, ce qui a pour effet d’accroître les coûts dans ces régions. Les autorités locales et nationales peuvent utiliser cet outil pour égaliser à la fois la charge de travail et les coûts induits par la lutte contre les incendies en créant des secteurs administratifs.
• Les patrouilles de police peuvent être divisées en secteurs afin d’équilibrer la charge de travail et les appels parmi les agents. Dans certaines zones, le problème des sureffectifs et des sous-effectifs peut être résolu en équilibrant l’indice de criminalité de chaque groupe d’îlots et en garantissant la rapidité et l’efficacité de la réaction policière.

Définition des critères de création et de la sélection des zones

Pour que l’outil génère des zones correctement équilibrées, vous devez fournir les critères définissant une zone optimale. Il existe deux types de critères à fournir : les critères de création de zones et les critères de sélection de zones. L’outil équilibre les zones en alternant entre la création de zones et la sélection de zones ; les critères que vous spécifiez pour chaque phase déterminent les zones équilibrées finales recommandées par l’outil.

La phase de création de zones génère des zones dont le nombre augmente de façon aléatoire jusqu’à ce que les critères de création de zones soient remplis. Les critères de création de zones doivent être considérés comme obligatoires pour vos zones ; toutes les zones se développent conformément aux critères (vous trouverez plus d’informations sur le développement des zones dans la section Développement des zones avec l’algorithme génétique). La phase de sélection des zones classe ensuite chaque jeu de zones et sélectionne les zones les plus adaptées selon qu’elles respectent le plus fidèlement les critères de sélection. En général, les critères de sélection de zones doivent être considérés comme des préférences plutôt que des obligations ; ils permettent de sélectionner parmi les zones qui répondent déjà aux critères de création de zones.

Choisir les critères à utiliser dans le cadre de création de zones et de la sélection de zones varie selon la situation. Les options suivantes du paramètre Zone Creation Method (Méthode de création de zones) sont fournies pour contribuer à définir vos critères comme il convient :

• Attribute target (Cible d’attribut) : chaque zone comportera à peu près la même somme totale d’un attribut, ce total devant être spécifié. Le nombre de zones qui sont créées dépend du nombre total de l’attribut. Par exemple, cette option permet de créer des zones de desserte qui contiennent 1 000 clients environ. S’il existe un total d’à peu près 5 000 clients parmi les entités en entrée, 5 zones seront créées, chaque zone comptant 1 000 clients environ. Pour un total de deux millions de clients, près de 2 000 zones seront créées, chacun comptant 1 000 clients environ.
• Defined number of zones (Nombre défini de zones) : le nombre de zones doit être égal au nombre spécifié, et chaque zone se compose d’à peu près le même nombre d’entités. Cette option est utile lorsque vous connaissez le nombre de zones dont vous avez besoin et que vous voulez que chaque zone comporte le même nombre d’entités en entrée.
• Number of zones and attribute target (Nombre de zones et cible d’attribut) : combine les deux options précédentes en équilibrant la somme d’un attribut parmi un nombre donné de zones. Cette option permet de créer, par exemple, exactement 20 zones de desserte ayant quasiment le même volume des ventes. Pour cette option, vous n’indiquez pas la somme attributaire désirée car elle est déterminée en divisant la somme totale de l’attribut par le nombre de zones. Cette option n’égalise pas le nombre d’entités figurant dans chaque zone (à noter toutefois qu’une préférence en termes de nombre égal d’entités peut être fournie comme critères de sélection de zones, comme décrit par la suite dans cette rubrique).

Critères de création de zones

Il existe différents critères obligatoires de création de zones pour chacune des options du paramètre Zone Creation Method (Méthode de création de zones) et toutes les zones se développent jusqu’à satisfaction de ces critères.

• Attribute target (Cible d’attribut) : vous devez fournir l’attribut à équilibrer et indiquer la somme désirée dans le paramètre Zone Building Criteria With Target (Critères de construction de zones avec cible). Vous pouvez aussi fournir plusieurs attributs avec des sommes différentes et attribuer des pondérations pour chaque attribut de façon à rendre prioritaires certains attributs par rapport aux autres.
• Defined number of zones (Nombre défini de zones) : vous devez indiquer le nombre de zones via le paramètre Target number of Zones (Nombre cible de zones).
• Number of zones and attribute target (Nombre de zones et cible d’attribut) : vous devez indiquer le nombre de zones dans le paramètre Number of zones (Nombre de zones) et indiquer l’attribut à équilibrer dans le paramètre Zone Building Criteria (Critères de création de zones). Vous pouvez à nouveau fournir plusieurs attributs et leur attribuer des pondérations afin de définir leur priorité.

Critères de sélection de zones

Les critères de sélection de zones sont des options supplémentaires qui permettent de spécifier vos préférences parmi les zones créées au cours de la phase de création des zones. Ces critères sont utilisés avec les critères de création de zones pour déterminer les zones que l’outil recommandera au final. La plupart des critères de sélection de zones sont applicables à toutes les options du paramètre Zone Creation Method (Méthode de création de zones). Les sections suivantes décrivent chacune des options de sélection des zones et indiquent lorsqu’elles sont applicables.

Critères de caractéristiques de zones

Les options du paramètre Zone Characteristics (Caractéristiques de zone) sont, en principe, liées à la taille et à la forme des zones. Vous pouvez utiliser l’une ou toutes les options suivantes :

• Equal area (Surface équivalente) : la préférence est donnée aux zones dont la surface est égale ou presque. Cette option s’applique seulement si les entités en entrée son des polygones.
• Compactness (Compacité) : la préférence est donnée aux zones dont la forme est quasi circulaire. Cette option est toujours applicable.
• Equal number of features (Même nombre d’entités) : la préférence est donnée aux zones qui sont composées d’environ le même nombre d’entités. Cette option ne s’applique pas lorsque l’option Defined number of zones (Nombre défini de zones) est utilisée, car la méthode de création des zones garantit déjà un nombre égal d’entités grâce aux critères de création de zones.

Critères de prise en compte des attributs

Le paramètre Attribute to Consider (Attribut à prendre en compte) permet de spécifier des attributs supplémentaires qui n’ont pas été utilisés en tant que critères de création de zones. Ceci permet d’inclure des zones qui préservent une somme, une moyenne, une variance ou une médiane cohérente d’un attribut. Vous êtes également libre de spécifier plusieurs attributs. Par exemple, vous pouvez inclure des zones qui possèdent une population totale identique (somme ) et un revenu médian identique (médiane).

Ces critères de sélection concernent toutes les méthodes de création de zones. Pour pouvoir être utilisés dans ce paramètre, les attributs doivent être continus plutôt que catégoriels.

Préservation des proportions de variables catégorielles

Le paramètre Categorical Variable to Maintain Proportions (Variable catégorielle pour conserver les proportions) permet de spécifier une variable catégorielle qui permettra d’équilibrer les proportions des catégories figurant dans les zones. Vous devez également choisir une méthode de proportion (Proportion Method) afin de spécifier la façon d’équilibrer les proportions. Les méthodes de proportion suivantes sont proposées :

• Maintain within proportion (Maintenir dans une proportion) : la préférence est donnée aux zones qui préservent les mêmes proportions relatives des catégories figurant dans chaque zone. Imaginons que la variable catégorielle que vous utilisez pour préserver les proportions représente une classification d’occupation du sol binaire forêt et autre que forêt et que 60 pour cent des entités ont une occupation du sol de type forêt et 40 pour cent d’un autre type, cette option favorisera les zones dans lesquelles chaque zone compte 60 pour cent de forêt et 40 pour cent d’un autre type d’occupation du sol.
• Maintain overall proportion (Maintenir une proportion globale) : les zones seront créées de sorte que les proportions globales de prédominance de catégorie correspondent aux proportions de l’ensemble des catégories. Si, par exemple, la variable catégorielle indique que l’entité se trouve sur terre ou dans l’eau et que 60 pour cent des entités sont terrestres, cette option favorisera les zones qui se trouvent à environ 60 pour cent sur terre et 40 pour cent dans l’eau.

Ces critères de sélection concernent toutes les méthodes de création de zones. Pour pouvoir être utilisée dans ce paramètre, la variable doit être catégorielle plutôt que continue.

Critères basés sur la distance

Le paramètre Distance to Consider (Distance à prendre en compte) permet de privilégier les zones proches d’un autre jeu d’entités (ou de plusieurs jeux d’entités). Si, par exemple, vous construisez des secteurs administratifs dans le domaine de la santé, vous pouvez donner la priorité aux zones qui sont proches d’hôpitaux existants. La distance entre une zone et une entité est définie par la distance médiane de toutes les entités figurant dans la zone par rapport à l’entité la plus proche signalée comme la distance à prendre en compte.

Scénarios de détermination des critères de zones

Il existe de nombreuses options pour les critères de création et de sélection de zones. Or, il est loin d’être évident de déterminer instantanément les paramètres à utiliser selon vos contraintes et vos préférences en matière de zones. Voici quelques scénarios et leurs paramètres correspondants.

Scénario 1: Affecter des descriptifs de biens aux agents immobiliers

Vous travaillez en tant qu’analyste au sein d’une grande agence immobilière. Vous disposez d’une classe d’entités comportant tous les descriptifs de biens et leurs valeurs disponibles dans la région. L’agence compte 12 agents immobiliers. Vous désirez attribuer des descriptifs à chacun d’entre eux de telle manière que chaque agent obtienne un nombre équivalent de descriptifs et que la valeur totale des biens de chaque zone soit approximativement identique. Vous souhaitez également que les zones soient proches des succursales de l’agence.

Pour ce faire, vous pouvez utiliser l’option Number of zones and attribute target (Nombre de zones et cible d’attribut) dans le paramètre Zone Creation Method (Méthode de création de zones). Indiquez 12 pour le paramètre Target number of Zones (Nombre cible de zones) (un par agent immobilier) et choisissez le champ représentant la valeur du bien immobilier dans le paramètre Zone Building Criteria (Critères de création de zones). Choisissez l’option Equal number of features (Même nombre d’entités) dans le paramètre Zone Characteristics (Caractéristiques de zones) pour priviligier les zones dans lesquelles chaque agent immobilier s’est vu attribuer un nombre à peu près égal de biens. Pour tenir compte de la distance par rapport à la succursale la plus proche, fournissez une classe d’entités représentant les emplacements des succursales dans le paramètre Distance to Consider (Distance à prendre en compte).

Scénario 2 : Création de limites de circonscriptions

Créer des limites de circonscriptions dans lesquelles le nombre de personnes est équilibré est une tâche complexe qui doit être régulièrement effectuée à presque tous les niveaux de l’administration locale. En utilisant les données démographiques et la population regroupée en petits quartiers, vous voulez créer des circonscriptions d’environ 10 000 personnes. Par ailleurs, environ 75 pour cent de la population vit dans les zones urbaines et 25 pour cent dans des zones rurales. Vous voulez qu’environ 75 pour cent des zones soit majoritairement urbaines et que 25 pour cent soit majoritairement rurale pour représenter correctement chaque groupe.

Pour ce faire, vous pouvez utiliser l’option Attribute target (Cible d’attribut) dans le paramètre Zone Creation Method (Méthode de création de zones). Choisir le champ représentant le nombre de personnes dans chaque quartier et spécifiez 10 000 dans les colonnes du paramètre Zone Building Criteria With Target (Critères de construction de zones avec cible). Indiquez un champ représentant si le quartier est urbain ou rural dans le paramètre Categorical Variable to Maintain Proportions (Variable catégorielle pour conserver les proportions) et choisissez l’option Maintain overall proportion (Maintenir une proportion globale) dans le paramètre Proportion Method (Méthode de proportion).

Scénario 3 : Attribution d’une charge de travail aux agents de probation

Vous êtes un analyste SIG au sein du tribunal d’application des peines et avez pour mission d’équilibrer les cas traités par les 25 agents de probation. Vous disposez de l’emplacement de tous les contrevenants de la ville ainsi que de l’évaluation des risques (sous forme numérique) de chaque contrevenant. Vous désirez les répartir entre les agents de probation tout en assurant un risque total à peu près équivalent. Toutefois, l’équilibre eu égard des risques n’est pas aussi important que l’affectation du même nombre de contrevenants à chaque agent de probation. De plus, vous voulez que les zones soient aussi compactes que possible afin de limiter les coûts de déplacement des agents.

Pour ce faire, vous pouvez utiliser l’option Defined number of zones (Nombre défini de zones) dans le paramètre Zone Creation Method (Méthode de création de zones) et spécifier 12 pour le paramètre Target number of Zones (Nombre cible de zones). Spécifiez le champ représentant le risque associé à chaque délinquant dans le paramètre Attribute to Consider (Attribut à prendre en compte) et choisissez l’option Compactness (Compacité) dans le paramètre Zone Characteristics (Caractéristiques de zone) pour créer des zones compactes.

Développer des zones avec l’algorithme génétique

Grâce aux critères que vous avez définis à la création et la sélection des zones, l’outil Créer des zones équilibrées développe des zones optimales à l’aide de l’algorithme génétique (GA) en tenant compte des contraintes spatiales des entités en entrée.

GA repose sur la théorie évolutionniste de la sélection naturelle et de la génétique, comme Charles Darwin fut le premier à l’expliquer. D’après le principe darwinien de la survie du plus fort, les organismes les mieux adaptés au sein d’une population ont plus de chances de survivre et de se reproduire.

Comme le nombre de solutions possibles est généralement très important, l’algorithme génétique (GA) recherche une solution optimisée en commençant par des recherches aléatoires et en dirigeant les recherches vers des directions plus prometteuses. L’optimisation GA est une abstraction de l’évolution biologique naturelle, où chaque solution possible (dans ce cas, chaque organisation possible des zones) est analogue à un organisme individuel au sein d’une population. Au fur et à mesure des générations, seuls les individus qui s’adaptent le mieux continuent à survivre et seules les recherches les plus productives sont autorisées à continuer.

L’algorithme commence par créer une population aléatoire au sein de laquelle chaque individu est une solution possible. Un score de conformité est calculé pour chaque solution et les individus dont le score est le plus faible (meilleures solutions) dans la population existante sont transmis à la génération suivante, tandis que les solutions inadaptées restantes sont éliminées. Les individus les plus adaptés, désignés comme les parents, ont le droit de créer des descendants par paire à l’aide d’opérateurs génétiques, tels que le croisement et la mutation. Chaque nouvelle génération est une combinaison des individus les plus adaptés de la génération précédente et de leurs descendants. Il arrive parfois que des individus (qui ne sont ni les parents ni les descendants, et qu’on appelle des étrangers) sont introduits de manière aléatoire dans la génération suivante en vue d’élargir la plage des solutions possibles découvertes par l’algorithme. Le score de conformité est calculé pour tous les individus dans chaque nouvelle génération et le processus recommence pour un nombre donné de générations (par défaut, 50 générations). L’individu le plus adapté de la génération finale correspond aux zones équilibrées qui sont renvoyées par l’outil.

Choix de la population initiale

La population initiale de l’algorithme est choisie en sélectionnant de manière aléatoire des entités dans la zone d’étude. Par défaut, la population se compose de 100 individus, mais vous pouvez modifier ce nombre à l’aide du paramètre Population Size (Taille de population). Chaque entité sélectionnée de manière aléatoire constitue un emplacement de départ (une origine) à partir duquel la zone croît en s’agrégeant à d’autres entités situées à proximité. Une zone continue à s’agréger et à croître jusqu’à ce que la valeur totale atteigne le seuil des critères de création de zone. Si, par exemple, les critères de création de zones que vous indiquez sont une population de 100 000 et un nombre de ménages de 50 000, les valeurs 100 000 et 50 000 sont respectivement les valeurs de seuil de la population et des ménages. La zone arrête de croître à partir du moment où tous les seuils sont atteints. Pour la zone suivante, un nouvelle germe est sélectionné à l’extérieur de la première zone et est autorisé à croître de manière aléatoire. Le processus se poursuit jusqu’à ce que toutes les entités soient affectées à une zone.

En biologie, le patrimoine génétique d’un individu est contenu dans les chromosomes. Les chromosomes se composent de gènes, qui sont l’unité héréditaire de la vie. Pour cet outil, une solution possible est analogue à un chromosome et les origines s’apparentent aux gènes. Ces gènes étant les unités héréditaires que les parents transmettent à leurs descendants, ils permettent d’engendrer les générations futures. L’image suivante illustre un exemple de solution possible avec les valeurs Object ID (ID d’objet) des germes de chaque zone dans la solution.

Calcul du score de conformité

Le score de conformité de chaque solution possible permet de mesurer le degré d’adéquation entre les zones obtenues et les différents critères de création et de sélection des zones fournis dans l’outil. Les scores de conformité les plus faibles indiquent un meilleur respect des critères. Ainsi, l’objectif final consiste à trouver une solution qui offre un score de conformité faible (dans l’idéal, il s’agit de la solution qui fournit le score de conformité le plus faible possible, désigné sous le nom de minimum global). La formule suivante permet de calculer le score de conformité pour une solution possible :

• n : nombre total de zones dans la solution
• c : nombre total de critères utilisés pour construire des zones et sélectionner des solutions.
• V_j : valeur de seuil pour le j^ème critère.
• V_ij : somme des j^èmes critères de la i^ème zone.

La formule du score de conformité doit être vue comme le cumul de la différence entre les valeurs de chaque critère et les valeurs idéales pour chaque zone de la solution. Dans une solution parfaite (qui n’est généralement pas possible à obtenir), les valeurs des critères de toutes les zones sont égales à leurs valeurs idéales et le score de conformité est égal à zéro. La division par la valeur de seuil (V_j) permet de s’assurer que le score de conformité ne subit pas l’influence des unités. Ce dernier point est important car si vous choisissez, par exemple, les mètres carrés ou les pieds carrés comme unités de mesure, cela n’a pas d’incidence sur le score de conformité.

Le paramètre Output Convergence Table (Table de convergence en sortie) fournit le score de conformité total de la meilleure solution dans chaque génération, ainsi que les scores de chaque critère individuel. Un diagramme de convergence est créé avec la table en sortie pour montrer l’évolution de ces scores de conformité au fil des générations. L’algorithme tente de trouver une solution plus adaptée que la solution existante. C’est pourquoi la ligne de conformité totale dans le diagramme décroît généralement à mesure que les générations progressent, jusqu’à son aplatissement final. Cet aplatissement indique que le score de conformité a atteint un minimum local (probablement pas le minimum global) et que poursuivre avec d’autres générations ne permettra probablement pas d’améliorer la solution.

Création de nouvelles générations par croisement

Une fois la population initiale générée par l’algorithme, la moitié des individus est autorisée à participer à la génération suivante et à créer des descendants de nouvelles solutions possibles. Ces individus sont choisis en fonction de leur degré d’adaptation (déterminé par les scores de conformité les plus faibles) et sont appariés de manière aléatoire pour produire des descendants à l’aide d’un procédé appelé croisement. Le croisement (parfois nommé recombinaison) est un opérateur génétique qui combine les informations des deux parents pour générer des descendants. L’image suivante illustre un exemple des origines des deux parents croisés pour créer deux nouveaux descendants :

En conséquence, la moitié des individus des nouvelles générations étaient des parents dans la génération précédente, et la moitié sont leurs descendants. Pour cette nouvelle génération, le score de conformité est là encore calculé. La première moitié progresse vers la génération suivante, ce qui oriente la recherche vers une meilleure solution.

Développement des solutions possibles par mutation et introduction d’espèces étrangères

La diversité joue un rôle très important dans l’évolution d’une population, et la mutation permet de garantir cette diversité. Les mutations sont de petites modifications ou transformations introduites dans une séquence de gènes en vue d’engendrer des individus avec codes génétiques différents. Dans cet outil, un individu subit une mutation dont les germes sont réorganisés de manière aléatoire (permutés). Les images suivantes montrent la seule solution possible passant par une mutation et dont les germes ont été réorganisés :

Le paramètre Mutation Factor (Facteur de mutation) permet de contrôler la probabilité qu’un descendant fasse l’objet d’une mutation. La valeur par défaut est égale à 0,1. Les mutations ouvrent le champ des solutions possibles et permettent souvent à l’algorithme de converger vers une solution qui est localement optimale. Cependant, les facteurs de mutation très élevés provoquent de si nombreuses modifications que l’algorithme perd en efficacité et que la convergence est plus lente (voire inexistante).

Pour développer les solutions possibles, vous pouvez également introduire de nouveaux individus dans la population (des étrangers), qui ne font pas partie des générations précédentes et ne sont pas non plus leurs descendants. L’introduction d’individus étrangers augmente la probabilité d’obtention d’un minimum global (au lieu d’un minimum local) tout en maintenant un taux de convergence élevé. Le facteur de mutation contrôle la proportion dans laquelle les descendants de chaque génération sont remplacés par un étranger composé de germes générés aléatoirement.

Groupes déconnectés

En raison des contraintes spatiales, vous pouvez obtenir des groupes déconnectés dont les entités qui les constituent ne sont pas voisines des entités figurant dans la zone d’étude élargie. Cette situation est courante lorsque les entités en entrée sont des polygones non contigus, tels que des îles. Les zones ne peuvent se développer qu’en agrégeant les voisins spatiaux des entités présentes dans la zone. Pour résoudre ce problème, l’outil crée un lien entre chaque groupe déconnecté et l’entité la plus proche figurant hors du groupe afin d’établir un voisinage et permettre à la zone de continuer de croître. Le champ Disconnected Group ID (ID de groupe déconnecté) est ajouté à la table attributaire des entités en sortie (Output Features) qui permet de visualiser l’entité ou le groupe d’entités déconnecté dans votre zone d’étude.

Ressources supplémentaires

• 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. (octobre 2010). Alien Genetic Algorithm for Exploration of Search Space. AIP Conference Proceedings (Vol. 1298, No. 1, pp. 325-330). AIP.