Funktionsweise von "Ausgeglichene Zonen erstellen"

Beim Werkzeug Ausgeglichene Zonen erstellen wird ein genetischer Algorithmus eingesetzt, um räumlich zusammenhängende Zonen in Ihrem Untersuchungsgebiet basierend auf von Ihnen festgelegten Kriterien zu erstellen. Die Zonen können so erstellt werden, dass sie die gleiche Anzahl von Features enthalten, und/oder, dass sie sich bei einer Gruppe von Attributwerten ähneln. Es gibt auch Optionen zur Auswahl von Zonen mit annähernd gleichen Flächen, von Zonen, die so kompakt wie möglich sind, und von Zonen, die konsistente Summenstatistiken (wie Durchschnittswerte oder Anteile) anderer Variablen beibehalten.

Beispielszenarien

Dieses Werkzeug kann in den folgenden Szenarien verwendet werden:

• Ein Einzelhandelsunternehmen möchte sein Geschäftsgebiet so auf Bezirke aufteilen, dass jeder Manager für das gleiche Umsatzvolumen und die gleiche Anzahl an Mitarbeitern verantwortlich ist, unabhängig von der Anzahl der Filialen in diesem Bezirk.
• Durch den Klimawandel steigt die Zahl der Waldbrände pro Jahr in vielen Gebieten, was die Kosten in diesen Regionen erhöht. Lokale und nationale Behörden können mit diesem Werkzeug Verwaltungsbezirke erstellen, bei denen sowohl der Arbeitsaufwand als auch die Kosten der Brandbekämpfung besser verteilt sind.
• Es können Bezirke für Polizeistreifen geschaffen werden, um die Arbeitsbelastung und die eingehenden Notrufe besser auf die Beamten zu verteilen. Eine Über- oder Unterbesetzung in einigen Bereichen kann ausgeglichen werden, indem die Blockgruppen anhand des Kriminalitätsindex erstellt werden, sodass die Rechtzeitigkeit und Wirksamkeit von Polizeiaktionen gewährleistet wird.

Definieren von Kriterien für die Zonenerstellung und -auswahl

Damit das Werkzeug optimal ausgeglichene Zonen erstellen kann, müssen Sie die Kriterien angeben, die definieren, was eine optimale Zone ausmacht. Sie können zwei Arten von Kriterien angeben: Kriterien für die Zonenerstellung und Kriterien für die Zonenauswahl. Das Werkzeug gleicht die Zonen aus, indem es zwischen der Zonenerstellung und der Zonenauswahl wechselt. Die Kriterien, die Sie für jeden Schritt angeben, bestimmen die endgültigen ausgeglichenen Zonen, die von dem Werkzeug empfohlen werden.

In dem Schritt der Zonenerstellung werden viele Zonen erstellt, die zufällig wachsen, bis die Kriterien für die Zonenerstellung erfüllt sind. Die Kriterien für die Zonenerstellung sollten als Anforderungen für die Zonen betrachtet werden. Alle Zonen wachsen auf diese Art und Weise, um diese Kriterien zu erfüllen. (Weitere Informationen zum Wachstum von Zonen finden Sie im Abschnitt Zonenwachstum mit dem genetischen Algorithmus). In dem Schritt der Zonenauswahl werden die einzelnen Zonengruppen in einer Rangfolge sortiert. Basierend darauf, wie genau sie die Kriterien für die Zonenauswahl erfüllen, werden die besten Zonen ausgewählt. Im Allgemeinen sollten die Kriterien für die Zonenauswahl eher als Voreinstellungen betrachtet werden und nicht als Anforderungen. Sie werden verwendet, um eine Auswahl aus den Zonen zu treffen, die bereits die Kriterien für die Zonenerstellung erfüllt haben.

Die Auswahl der Kriterien, die bei der Zonenerstellung und der Zonenauswahl angewendet werden, ist von Ihrer jeweiligen Situation abhängig. Die folgenden Optionen für den Parameter Zonenerstellungsmethode werden bereitgestellt, um Sie bei der richtigen Definition der Kriterien zu unterstützen:

• Attributziel: Jede Zone weist ungefähr dieselbe Gesamtsumme eines Attributs auf. Diese Gesamtsumme muss angegeben werden. Die Anzahl der erstellten Zonen ist von der Gesamtsumme des Attributs abhängig. Diese Option kann beispielsweise verwendet werden, um Einzugsgebiete zu erstellen, die alle etwa 1.000 Kunden enthalten. Wenn alle Eingabe-Features insgesamt 5.000 Kunden enthalten, werden etwa 5 Zonen mit jeweils ungefähr 1.000 Kunden erstellt. Bei zwei Millionen Kunden insgesamt werden ungefähr 2.000 Zonen erstellt, die jeweils ca. 1.000 Kunden umfassen.
• Definierte Anzahl an Zonen: Die Anzahl an Zonen muss der angegebenen Zahl entsprechen. Jede Zone besteht ungefähr aus derselben Anzahl an Features. Diese Option ist hilfreich, wenn Ihnen die Anzahl der benötigten Zonen bekannt ist, und jede Zone dieselbe Anzahl an Eingabe-Features enthalten muss.
• Anzahl an Zonen und Attributziel: Kombiniert die zwei vorherigen Optionen, indem die Summe eines Attributs in einer bestimmten Anzahl an Zonen ausgeglichen wird. Diese Option kann beispielsweise verwendet werden, um genau 20 Einzugsgebiete zu erstellen, deren Zonen alle ungefähr dasselbe Umsatzvolumen haben. Bei dieser Option müssen Sie die gewünschte Attributsumme nicht angeben, da sie ermittelt wird, indem die Gesamtsumme des Attributs durch die Anzahl an Zonen geteilt wird. Diese Option gleicht die Anzahl an Features in den einzelnen Zonen nicht aus. (Sie können jedoch eine Voreinstellung für eine gleiche Anzahl an Features als Kriterium für die Zonenauswahl angeben. Eine entsprechende Beschreibung finden Sie weiter unten in diesem Thema.)

Kriterien für die Zonenerstellung

Für jede Option des Parameters Zonenerstellungsmethode gibt es verschiedene erforderliche Kriterien für die Zonenerstellung, und alle Zonen wachsen, bis sie diese Kriterien erfüllen.

• Attributziel: Sie müssen das auszugleichende Attribut sowie eine Summe im Parameter Kriterien für die Zonenerstellung mit Ziel angeben. Optional können Sie Mehrfachattribute mit unterschiedlichen Summen sowie Gewichtungen für die einzelnen Attribute bereitstellen, sodass einige Attribute Priorität vor anderen haben.
• Definierte Anzahl an Zonen: Sie müssen die Anzahl an Zonen mithilfe des Parameters Angestrebte Anzahl an Zonen angeben.
• Anzahl an Zonen und Attributziel: Sie müssen die Anzahl an Zonen im Parameter Anzahl an Zonen sowie das Attribut angeben, um den Parameter Kriterien für die Zonenerstellung auszugleichen. Auch hier besteht die Möglichkeit, Mehrfachattribute anzugeben und Gewichtungen bereitzustellen, um diese zu priorisieren.

Kriterien für die Zonenauswahl

Bei den Kriterien für die Zonenauswahl handelt es sich um zusätzliche Optionen, mit denen Sie die Voreinstellungen für die Zonen angeben können, die im Schritt der Zonenerstellung erstellt werden. Diese Kriterien werden mit den Kriterien für die Zonenerstellung verwendet, um zu bestimmen, welche Zonen von dem Werkzeug letztlich empfohlen werden. Die meisten Kriterien für die Zonenauswahl können auf alle Optionen des Parameters Zonenerstellungsmethode angewendet werden. In den nachfolgenden Abschnitten werden die einzelnen Zonenauswahloptionen sowie die Situationen beschrieben, in denen sie angewendet werden.

Kriterien der Zoneneigenschaften

Die Optionen des Parameters Zoneneigenschaften beziehen sich in der Regel auf die Größe und die Form der Zonen. Sie können eine oder alle der folgenden Optionen verwenden:

• Gleiche Fläche: Zonen, die nahezu flächengleich sind, werden bevorzugt. Diese Option gilt nur, wenn die Eingabe-Features Polygone sind.
• Kompaktheit: Zonen, die nahezu kreisförmig sind, werden bevorzugt. Diese Option gilt immer.
• Gleiche Anzahl Features: Zonen, die aus ungefähr derselben Anzahl an Features bestehen, werden bevorzugt. Diese Option gilt nicht, wenn die Zonenerstellungsmethode Definierte Anzahl an Zonen verwendet wird, da mit deren Kriterien für die Zonenerstellung bereits eine gleiche Anzahl an Features gewährleistet wird.

Kriterien zur Berücksichtigung von Attributen

Mit dem Parameter Zu berücksichtigendes Attribut können Sie zusätzliche zu berücksichtigende Attribute angeben, die nicht als Kriterien für die Zonenerstellung verwendet wurden. Es besteht die Möglichkeit, Zonen einzubeziehen, die eine konsistente Summe, einen Durchschnitt, eine Varianz oder einen Medianwert eines Attributs beibehalten. Darüber hinaus können Sie Mehrfachattribute angeben. Sie sind also beispielsweise in der Lage, Zonen einzubeziehen, welche die gleiche Gesamtbevölkerung (Summe) und ungefähr das gleiche mittlere Einkommen (Medianwert) haben.

Dieses Auswahlkriterium gilt für alle Zonenerstellungsmethoden. Die Attribute müssen kontinuierlich sein und nicht kategorisch, um in diesem Parameter verwendet zu werden.

Beibehalten der Proportionen von Kategorievariablen

Der Parameter Kategorievariable zum Beibehalten von Proportionen ermöglicht die Angabe einer Kategorievariablen, mit der die Proportionen der Kategorien in den Zonen ausgeglichen werden. Sie müssen eine Proportionsmethode auswählen, um festzulegen, wie die Proportionen ausgeglichen werden sollen. Folgende Proportionsmethoden werden bereitgestellt:

• In Proportion erhalten: Bevorzugt werden Zonen, bei denen in jeder einzelnen Zone die gleichen relativen Proportionen der Kategorien beibehalten werden. Wenn die Kategorievariable, die für die Beibehaltung der Proportionen verwendet wird, beispielsweise die binäre Bodenbedeckungsklassifizierung "Wald" und "Kein Wald" darstellt und 60 % der Features den Bodenbedeckungstyp "Wald" und 40 % den Bodenbedeckungstyp "Kein Wald" aufweisen, werden bei dieser Option Zonen bevorzugt, bei denen jede einzelne Zone 60 % Wald und 40 % andere Bodenbedeckung als Wald aufweist.
• Gesamtproportion erhalten: Zonen werden so erstellt, dass die Gesamtproportionen der Kategoriedominanz den Proportionen der Gesamtkategorien entspricht. Wenn die Kategorievariable beispielsweise angibt, ob das Feature sich an Land oder im Wasser befindet, und 60 % der Features sich an Land befinden, werden bei dieser Option Zonen bevorzugt, bei denen sich ungefähr 60 % der Zonen vorwiegend an Land und 40 % der Zonen hauptsächlich im Wasser befinden.

Dieses Auswahlkriterium gilt für alle Zonenerstellungsmethoden. Die Variable muss kategorisch und nicht kontinuierlich sein, um in diesem Parameter verwendet zu werden.

Entfernungsbasierte Kriterien

Der Parameter Zu berücksichtigende Entfernung ermöglicht das Favorisieren von Zonen, die in der Nähe einer anderen Gruppe von Features (oder mehrerer Gruppen von Features) liegen. Wenn Sie beispielsweise administrative Gesundheitsbezirke erstellen, können Sie Zonen bevorzugen, die in der Nähe vorhandener Krankenhäuser liegen. Die Entfernung zwischen einer Zone und einem Feature wird durch den Medianwert für die Entfernung von allen Features in der Zone zum nächstgelegenen Feature definiert, was als zu berücksichtigende Entfernung angegeben wird.

Szenarien für die Auswahl von Zonenkriterien

Für die Kriterien für die Zonenerstellung und die Zonenauswahl stehen zahlreiche Optionen zur Verfügung, und möglicherweise ist es nicht offensichtlich, welche Parameter basierend auf den Anforderungen und Voreinstellungen für Zonen verwendet werden müssen. Nachfolgend werden einige Szenarien sowie die zugehörigen Parameter aufgeführt, die in den entsprechenden Szenarien verwendet werden sollten.

Szenario 1: Zuweisen von Immobilienangeboten zu Maklern

Sie sind ein Analyst in einer Immobilienagentur. Sie verfügen über eine Feature-Class mit allen verfügbaren Immobilienangeboten und den entsprechenden Kosten in dem Gebiet. In der Agentur arbeiten 12 Makler. Sie möchten die Immobilienangebote so zuweisen, dass jeder Makler eine gleiche Anzahl an Angeboten erhält und die Gesamtkosten der Immobilien in jeder Zone ungefähr gleich ist. Darüber hinaus sollen die Zonen in der Nähe der vorhandenen Niederlassungen der Immobilienagentur liegen.

Um dies zu erreichen, können Sie die Option Anzahl an Zonen und Attributziel im Parameter Zonenerstellungsmethode verwenden. Geben Sie für den Parameter Angestrebte Anzahl an Zonen den Wert 12 an (eine Zone pro Makler), und wählen Sie im Parameter Kriterien für die Zonenerstellung das Feld aus, das die Kosten jeder Immobilie darstellt. Wählen Sie die Option Gleiche Anzahl Features im Parameter Zoneneigenschaften aus, um Zonen zu bevorzugen, in denen jedem Makler etwa eine gleiche Anzahl Immobilien zugewiesen ist. Um die Entfernung zur nächsten Niederlassung der Immobilienagentur zu berücksichtigen, stellen Sie eine Feature-Class bereit, welche die Positionen der Niederlassungen im Parameter Zu berücksichtigende Entfernung darstellt.

Szenario 2: Erstellen neuer Wahlbezirksgrenzen

Die Erstellung neuer Wahlbezirksgrenzen, in denen die Anzahl der Menschen innerhalb der einzelnen Bezirke ausgeglichen ist, ist eine komplizierte und schwierige Aufgabe, die auf nahezu jeder Regierungsebene häufig durchgeführt werden muss. Sie möchten unter Verwendung von Bevölkerungs- und demografischen Daten, die in kleinen Nachbarschaften gesammelt wurden, Bezirke erstellen, die jeweils ungefähr 10.000 Menschen umfassen. Zudem leben etwa 75 % der Bevölkerung in städtischen und 25 % in ländlichen Gebieten. 75 % der Zonen sollen hauptsächlich städtisch und 25 % hauptsächlich ländlich sein, damit jede Gruppe ordnungsgemäß repräsentiert wird.

Um dies zu erreichen, können Sie die Option Attributziel im Parameter Zonenerstellungsmethode verwenden. Wählen Sie das Feld aus, das die Anzahl der Menschen in jeder Nachbarschaft darstellt, und geben Sie 10.000 in den Spalten des Parameters Kriterien für die Zonenerstellung mit Ziel an. Geben Sie im Parameter Kategorievariable zum Beibehalten von Proportionen ein Feld an, das angibt, ob die Nachbarschaft städtisch oder ländlich ist, und wählen Sie die Option Gesamtproportion erhalten im Parameter Proportionsmethode aus.

Szenario 3: Zuweisen von Arbeitsaufgaben für Bewährungshelfer

Sie sind ein GIS-Analyst für die Strafverfolgungsbehörde und wurden damit beauftragt, die Arbeitsbelastung von 25 Bewährungshelfern auszugleichen. Sie verfügen über den Aufenthaltsort aller Straftäter in der Stadt sowie eine numerische Risikobewertung der einzelnen Straftäter. Sie möchten sie gleichmäßig auf alle Bewährungshelfer aufteilen und gleichzeitig das Gesamtrisiko der Straftäter auf gleichem Niveau halten. Das Risiko auszugleichen ist jedoch nicht so wichtig wie das Zuweisen der gleichen Anzahl an Straftätern zu jedem Bewährungshelfer. Darüber hinaus sollen die Zonen so kompakt wie möglich sein, um die Reisekosten der Bewährungshelfer zu senken.

Verwenden Sie zu diesem Zweck die Option Definierte Anzahl an Zonen im Parameter Zonenerstellungsmethode, und geben Sie für den Parameter Angestrebte Anzahl an Zonen den Wert 12 an. Geben Sie das Feld, welches das Risiko jedes Straftäters darstellt, im Parameter Zu berücksichtigendes Attribut an, und wählen Sie die Option Kompaktheit im Parameter Zoneneigenschaften aus, um kompakte Zonen zu erstellen.

Zonenwachstum mit dem genetischen Algorithmus

Unter Verwendung der Kriterien, die Sie für die Zonenerstellung und die Zonenauswahl definiert haben, legt das Werkzeug Ausgeglichene Zonen erstellen mithilfe des genetischen Algorithmus optimale Zonen an, wobei die räumlichen Einschränkungen der Eingabe-Features berücksichtigt werden.

Der GA basiert auf der evolutionären Theorie der natürlichen Selektion und Genetik, die erstmals von Charles Darwin aufgestellt wurde. Nach dem darwinistischen Prinzip des "Survival of the Fittest" überleben die am besten angepassten (in unserem Kontext die am besten geeigneten) Organismen in einer Population eher und produzieren auch mehr Nachkommen.

Da die Anzahl der möglichen Lösungen in der Regel sehr groß ist, wird bei der Suche nach einer optimierten Lösung zunächst mit zufälligen Suchen begonnen. Dann werden die Suchen in vielversprechendere Richtungen gelenkt. Die GA-Optimierung ist eine Abstraktion der natürlichen biologischen Evolution, bei der jede mögliche Lösung (in diesem Fall jede mögliche Anordnung von Zonen) analog zu einem Organismus in einer Population ist. Im Laufe der Generationen überleben nur die am besten geeigneten Individuen, das heißt, nur die produktivsten Suchen dürfen fortgesetzt werden.

Der Algorithmus erstellt zu Beginn eine zufällige Population, bei der jedes Individuum in der Population eine mögliche Lösung ist. Für jede Lösung wird ein Eignungs-Score berechnet. Die Individuen mit dem kleinsten Eignungs-Score (die besten Lösungen) in der bestehenden Population werden an die nächste Generation weitergegeben, und die verbleibenden, ungeeigneten Lösungen werden entfernt. Die am besten geeigneten Individuen werden als Eltern bestimmt und dürfen dann mithilfe von genetischen Operatoren wie Crossover und Mutation Nachkommen in Paaren erzeugen. Jede neue Generation ist eine Kombination aus den am besten geeigneten Individuen der vorherigen Generation und deren Nachkommen. Manchmal werden Individuen (die weder Eltern noch Nachkommen sind und "fremde Arten" genannt werden) in der nächsten Generation zufällig eingeführt, um das Spektrum der vom Algorithmus zu entdeckenden Lösungen zu erweitern. Der Eignungs-Score wird für alle Individuen in jeder neuen Generation berechnet, und der Prozess wird für eine bestimmte Anzahl von Generationen wiederholt (standardmäßig 50 Generationen). Das am besten geeignete Individuum der letzten Generation sind dann die ausgeglichenen Zonen, die vom Werkzeug zurückgegeben werden.

Auswählen der ersten Population

Die erste Population für den Algorithmus wird durch zufällige Auswahl von Features im Untersuchungsgebiet gebildet. Standardmäßig besteht die Population aus 100 Individuen, aber die Anzahl kann im Parameter Populationsgröße geändert werden. Jedes zufällig ausgewählte Feature ist eine Ausgangsposition (ein sogenannter Ursprung), von der aus die Zone wächst, indem nahegelegene Features aggregiert werden. Die Zone wächst durch Aggregieren weiter, bis der Gesamtwert die Schwelle der Zonenbildungskriterien erreicht. Wenn Sie beispielsweise eine Population von 100.000 sowie 50.000 Haushalte als Zonenerstellungskriterien haben, sind die Werte 100.000 und 50.000 jeweils die Schwellenwerte für Population und Haushalte. Die Zone wächst nicht mehr, sobald alle Schwellenwerte erreicht sind. Für die nächste Zone wird ein neuer Ursprung außerhalb der ersten Zone ausgewählt, der zufällig wachsen darf. Der Prozess wird fortgesetzt, bis alle Features einer Zone zugeordnet sind.

In der Biologie ist das Erbgut eines Individuums in Chromosomen enthalten. Chromosomen bestehen aus Genen, der Erbeinheit des Lebens. Für dieses Werkzeug ist eine mögliche Lösung mit einem Chromosom und Ursprungswerte mit Genen gleichzusetzen. Diese Gene sind die von den Eltern auf die Nachkommen übertragenen Erbeinheiten und dienen also zur Schaffung zukünftiger Generationen. Die folgende Abbildung zeigt ein Beispiel für eine mögliche Lösung zusammen mit den Objekt-ID-Werten der Ursprungswerte jeder Zone in der Lösung:

Berechnen des Eignungs-Score

Der Eignungs-Score jeder möglichen Lösung ist ein Maß dafür, wie sehr die resultierenden Zonen die verschiedenen Kriterien für die Zonenerstellung und -auswahl im Werkzeug erfüllen, wobei niedrigere Eignungs-Scores eine höhere Übereinstimmung mit den Kriterien anzeigen. Das letztendliche Ziel ist es also, eine Lösung zu finden, die einen niedrigen Eignungs-Score hat (im Idealfall ist es die Lösung mit dem kleinstmöglichen Lösungs-Score, die auch als globales Minimum bezeichnet wird). Der Eignungs-Score für eine mögliche Lösung wird nach folgender Formel berechnet:

• n: Die Gesamtzahl der Zonen in der Lösung
• c: Die Gesamtzahl der Kriterien, nach denen Zonen gebildet und Lösungen ausgewählt werden
• V_j: Der Schwellenwert für das j. Kriterium
• V_ij: Die Summe des j. Kriteriums der i. Zone.

Mit der Formel wird ermittelt, wie sehr sich die Werte jedes Kriteriums von den perfekten Werten für jede Zone in der Lösung unterscheiden. In einer perfekten Lösung (die in der Regel nicht möglich ist) entsprechen die Kriterienwerte aller Zonen ihren Idealwerten, und der Eignungs-Score ist Null. Durch die Division durch den Schwellenwert (V_j) wird sichergestellt, dass der Eignungs-Score einheitslos ist. Dies ist wichtig, denn es macht im Hinblick auf den Eignungs-Score beispielsweise keinen Unterschied, ob eine Fläche in Quadratmeter oder Quadratfuß angegeben wird.

Der Parameter Ausgabe-Konvergenztabelle liefert den Gesamt-Eignungs-Score der besten Lösung in jeder Generation zusammen mit den Werten der einzelnen Kriterien. Neben der Ausgabetabelle wird ein Konvergenzdiagramm erstellt, das zeigt, wie sich diese Eignungs-Scores im Laufe der Generationen verändern. Der Algorithmus versucht immer, eine bessere Lösung als die bestehende zu finden, sodass die Linie der Gesamteignung im Diagramm im Allgemeinen mit fortschreitender Entwicklung der Generationen abnimmt, bis sie schließlich ganz abflacht. Dieses Abflachen deutet darauf hin, dass der Eignungs-Score ein lokales Minimum erreicht hat (wahrscheinlich aber nicht das globale Minimum) und dass die Fortsetzung mit weiteren Generationen die Lösung wahrscheinlich nicht verbessern wird.

Erstellen neuer Generationen mit Crossover

Sobald die erste Population durch den Algorithmus erzeugt wurde, kann die Hälfte der Individuen an der nächsten Generation teilnehmen und Nachkommen für neue Lösungsmöglichkeiten schaffen. Diese Individuen werden auf Grundlage ihrer Eignung ausgewählt (anhand des kleinsten Eignungs-Score) und nach dem Zufallsprinzip gepaart, um Nachkommen zu erzeugen. Dabei wird ein Prozess namens Crossover angewendet. Crossover (manchmal auch als Rekombination bezeichnet) ist ein genetischer Operator, der die Informationen von zwei Eltern kombiniert, um Nachkommen zu erzeugen. Die folgende Abbildung zeigt ein Beispiel dafür, wie die Ursprungswerte von zwei Elternteilen per Crossover gepaart werden, um zwei neue Nachkommen zu erzeugen:

Die Hälfte der Individuen der neuen Generationen waren Eltern in der vorherigen Generation und die andere Hälfte sind ihre Nachkommen. Für diese neue Generation wird wiederum der Eignungs-Score berechnet, und die obere Hälfte geht an die nächste Generation über, was die Suche nach einer besseren Lösung vorantreibt.

Erweitern der Lösungsmöglichkeiten mit Mutationen und fremden Arten

Vielfalt ist in einer sich entwickelnden Population sehr wichtig, und eine Möglichkeit, die Vielfalt zu erhalten, stellt die Mutation dar. Mutationen sind kleine Veränderungen oder Modifikationen in einer Gensequenz, die Individuen mit unterschiedlichen genetischen Codes hervorbringen. In diesem Werkzeug werden die Ursprünge jedes Individuums, das eine Mutation erfährt, beliebig neu angeordnet (randomisiert). Die folgenden Abbildungen zeigen die eine mögliche Lösung, bei der eine Mutation erfolgt und die Ursprünge neu angeordnet werden:

Die Wahrscheinlichkeit, dass ein Nachkomme eine Mutation erfährt, kann mit dem Parameter Mutationsfaktor gesteuert werden, und der Standardwert ist 0,1. Mutationen erweitern die Lösungsmöglichkeiten und ermöglichen es dem Algorithmus oft, schnell zu einer lokal optimalen Lösung zu konvergieren. Allerdings bewirken sehr hohe Mutationsfaktoren so viele Veränderungen, dass der Algorithmus an Effizienz verliert und langsam (oder gar nicht) zu einer Lösung kommt.

Eine weitere Methode zur Erweiterung der möglichen Lösungen besteht darin, neue Individuen in die Population einzuführen (sogenannte "fremde Arten"), die weder Teil früherer Generationen noch ihre Nachkommen sind. Die Einführung von Individuen fremder Arten erhöht die Wahrscheinlichkeit, ein globales Minimum (und nicht ein lokales Minimum) zu erreichen, während gleichzeitig eine hohe Konvergenzrate beibehalten wird. Der Mutationsfaktor steuert die Proportion der Nachkommen jeder Generation, die durch ein Individuum einer fremden Art ersetzt werden, das aus zufällig erzeugten Ursprüngen besteht.

Getrennte Gruppen

Aufgrund von räumlichen Einschränkungen gibt es mitunter getrennte Gruppen, in denen die Features in einer Gruppe keine Nachbarn von Features im größeren Untersuchungsgebiet sind. Dies tritt meistens dann auf, wenn die Eingabe-Features Polygone sind, die nicht kontinuierlich sind (beispielsweise Inseln). Zonen können nur wachsen, indem räumliche Nachbarn der vorhandenen Features in der Zone aggregiert werden. Um dies zu lösen, generiert das Werkzeug einen Link zwischen jeder getrennten Gruppe und dem nächsten Feature außerhalb der Gruppe, um eine Nachbarschaft einzurichten und das weitere Zonenwachstum zu ermöglichen. Das Feld ID der getrennten Gruppe wird der Attributtabelle der Ausgabe-Features hinzugefügt, mit der Sie visualisieren können, welches Feature bzw. welche Gruppe von Features im Untersuchungsgebiet getrennt wurden.

Zusätzliche Ressourcen

• 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, Oktober). Alien Genetic Algorithm for Exploration of Search Space. AIP Conference Proceedings (Bd. 1298, Nr. 1, S. 325–330). AIP.