Textprobe: Kapitel 3.2, Konzept: Um den im vorherigen Kapitel beschriebenen Effekt der Distanzsummenabnahme mit Genetischen Algorithmen in ein Konzept zu bringen, müssen verschiedene Überlegungen bezüglich der Gestaltung des Algorithmus vorhergehen. Die Haltung verschieden dimensionierter Teilpopulationen innerhalb einer Population erfordert eine Anpassung derbisher vorgestellten Genetischen Algorithmen in Bezug auf Selektion- und Rekombination von Individuen, sowie die Beachtung des Suchfortschritts in den jeweiligen Teilpopulationen. Durch die Kostenfunktion werden alle Individuen einer Population in ihrer Fitness vergleichbar gemacht, sodass über eine fitnessproportionale Selektion ein Individuum aus der Gesamtpopulation zur Rekombination ausgesucht werden kann. Die Selektion des ersten Elters ist unabhängig von der Teilpopulation und erfolgt auf Basis der Fitnessberechnung der Gesamtpopulation. Die Auswahl des zweiten Elters zur Rekombination hingegen erfolgt innerhalb der Teilpopulation des ersten Elters, da Rekombination nur innerhalb gleich dimensionierter Lösungen einen Sinn macht. Durch entsprechende Restriktionen, wie zum Beispiel die Rekombination lediglich aufwärtskompatibel9 zu gestalten, wäre dies auch unter ungleich dimensionierten Individuen zwar möglich, ist aber für den Zweck dieser Arbeit ungeeignet. Eine Begründung dafür erfolgt im weiteren Verlaufe der Erarbeitung des Konzeptes. Um wiederrum einen geeigneten Paarungspartner aus der Teilpopulation zu bestimmen, muss innerhalb dieser, ebenfalls eine Fitnessberechnung durchgeführt werden, da sich die bisherige Fitness lediglich auf die Gesamtpopulation bezieht und nicht zur Ermittlung des erfolgversprechendsten Individuums aus einer Teilpopulation herangezogen werden kann. Für die Rekombination müssen also folgende Restriktionen aufgestellt werden. 1. Auswahl des ersten Elters, also indirekt auch auf welche Teilpopulation ein Genetischer Operand angewandt werden kann, erfolgt über die Berechnung der Fitness der Gesamtpopulation. Dabei werden alle Individuen so behandelt als wären sie gleich dimensioniert, somit hat jede Teilpopulation ungefähr gleiche Chancen bei der Auswahl zur Rekombination. Dies dient auch der Vereinheitlichung des Suchfortschrittes der Teilpopulationen. 2. Rekombination zwischen Individuen ist nur innerhalb einer Teilpopulation möglich, damit ein Suchfortschritt innerhalb der jeweiligen Gruppe sukzessiv stattfinden kann und dieser in allen Teilpopulation gleichermaßen fortschreitet. 3. Aus Punkt 2 folgt, zur Bestimmung eines geeigneten Paarungspartners erfolgt eine Neubewertung aller in Betracht kommenden Individuen, diesmal bezieht sich also die Fitnessberechnung auf die jeweilige Teilpopulation. Um den Suchfortschritt in allen Teilpopulationen gleichermaßen zu gewährleisten reicht allein die Gleichstellung der Teilpopulationen bei der Auswahl zur Rekombination nicht aus. Der Suchfortschritt kann verzerrt werden, falls sich die Teilpopulationen in ihrer Größe unterscheiden. In diesem Fall wäre die Wahrscheinlichkeit für Individuen ausgewählt zu werden umso höher, je größer die jeweilige Teilpopulation ist. Im Schnitt wäre also innerhalb einer Generation der Suchfortschritt bei größeren Teilpopulationen weiter als bei kleineren Populationen. Um dem entgegenzuwirken, ist die Gesamtpopulation so aufzuteilen, dass die Teilpopulationen die gleiche Anzahl von Lösungen beinhalten. Die Umweltselektion erfolgt auf Basis der Fitnesswerte bezogen auf die Gesamtpopulation. Das bedeutet, alle Individuen werden gleich behandelt, unabhängig von ihrer jeweiligen Dimension. Dabei werden die schlechtesten Elternindividuen einer Generation von besseren Kinderindividuen verdrängt. Diese Vorgehensweise ermöglicht die Kostenfunktion, welche den Effekt der Distanzsummenverringerung entgegenwirkt und somit Individuen ausverschiedenen Teilpopulationen vergleichbar macht. Unter Umständen kann aber bei einem solchen Vorgehen eine Teilpopulation gänzlich aus der Population verdrängt werden. Das passiert, wenn zum Beispiel durch Zufall eine Teilpopulation über einige Generationen hinweg weniger Kinder zeugt: Dann können die Kinder anderer Teilpopulationen diese verdrängen, da deren Suchfortschritt dann bereits vorangeschritten ist und sie somit vergleichsweise bessere Fitnesswerte aufweisen, werden diese immer häufiger zur Rekombination ausgesucht bis schließlich die immer kleiner werdende Teilpopulation so wenig Nachkommen hat, dass sie gänzlich verdrängt wird. Im ungünstigsten Fall könnte es die Teilpopulation mit der optimalen Dimensionierung sein, welche verdrängt wird. Aus dieser Überlegung heraus ist zu gewährleisten, dass die anfängliche Diversität bezogen auf die Anzahl der Dimensionen über den gesamten Verlauf des Verfahrens konstant bleibt. Durch Beibehaltung aller Teilpopulationen über die gesamte Verfahrensdauer kann dieser unerwünschte Zufallseffekt ausgeschlossen werden. Dieses kann durch den in Kapitel 'Selektion' beschriebenen Crowding Selektionsmechanismus erreicht werden, indem nicht wahllos die schlechtesten Elternindividuen durch bessere Kindindividuen verdrängt werden, sondern Kinder lediglich ihre eigenen Eltern in der Population ersetzten dürfen, sofern sie eine bessere oder mindestens äquivalente Güte aufweisen. Dadurch wird zum einen eine sukzessive Verbesserung der Teilpopulationen erreicht, und zum anderen der Erhalt aller Teilpopulationen einer Population gesichert. Durch die Vereinheitlichung der Fitnesswerte ist es möglich, am Ende des Verfahrens die Lösung mit dem besten Fitnesswert bezogen auf die Gesamtpopulation zu ermitteln. Im günstigsten Fall ist das die Lösung mit der optimalen Clusteranzahl und weist entweder bereits eine fortgeschrittene Optimierung bezüglich der Distanzsummen auf, oder ist sogar ein globales Optimum.