Transformation (evolutionärer Algorithmus)

Transformation ist ein relativ neuer genetischer Operator^[1], der in evolutionären Algorithmen (EA) Verwendung findet. Ein EA ist eine Metaheuristik, die von der biologischen Evolution inspiriert ist und darauf abzielt, anspruchsvolle Optimierungsprobleme zumindest annähernd zu lösen. Dazu werden die Daten eines Lösungskandidaten (= Individuum) auf eine – meist lineare – Datenstruktur abgebildet, die entsprechend dem biologischen Vorbild Chromosom genannt wird und entsprechend heißen ihre Komponenten Gene. Die Individuen bilden eine Population von Lösungskandidaten, welche von den genetischen Operatoren verändert werden.

Der Transformationsoperator nimmt sich dazu die nicht-virale Übertragung von freier DNA in Bakterienzellen sowie in Pilze, Algen, Hefen und Pflanzen als biologisches Vorbild für die Implementierung als genetischer Operator. Dazu wird anfangs ein Pool aus Genabschnitten zufällig gebildet, mit dem die nachstehend beschriebenen Transformationen die Chromosome der Population verändern. Nach einer Iteration des Verfahrens wird ein Teil des Genpools mit Gensegmenten der Elterngeneration neu gebildet und der Rest zufällig bestimmt.^[1]

Folgende Transformationsoperatoren können die Chromosomen der Individuen verändern:^[2]

• Einfügung bzw. Ergänzung – Einfügen eines neuen Gens oder Segments
  • Zufällige Einfügung – Einfügen eines zufälligen Segments an einer zufälligen Stelle
  • Geführte Einfügung – Einfügen eines Segments anhand einer Heuristik oder anhand bestehenden Anwendungswissens
• Entfernung bzw. Löschung – Entfernen eines vorhandenen Gens oder Segments
  • Zufällige Entfernung – Entfernen eines zufälligen Segments
  • Geführte Entfernung – Entfernen eines Segments anhand einer Heuristik oder anhand bestehenden Anwendungswissens
• Kopie – Duplikation eines vorhandenen Gens oder Segments
  • Ermöglichung der Spezialisierung auf unterschiedliche Aufgaben
  • Bereitstellung der gleichen Funktion in einem anderen Kontext

Bei verschiedenen Anwendungen eines darauf aufbauenden Genetischen Algorithmus' (GA) kam es nicht zu vorzeitiger Konvergenz und die Ergebnisse waren besser als beim Standard-GA.^[2][3][4]