Schon mal die Strecke für eine Rundreise zusammengestellt? Über Karten und Reiseführern gekauert, nur um möglichst viel in möglichst kurzer Zeit abdecken zu können? Den letzten Versuch dieser Art habe ich zum Glück schon fast 20 Jahre hinter mir gelassen. Seither folge ich lieber dem Motto „Gelegenheit macht Diebe“ und tucker im Zick Zack dorthin, wo für mich grad die Sonne scheint.
Abgesehen von einer lustigen Kniffelei, dem ein oder anderen Staunen und einem Schnuppertag in die Welt der stochastischen, metaheuristischen Optimierungsverfahren, brachte mir die Arbeit für diesen Beitrag also eigentlich keinen sonderlichen Mehrwert. Hätte sie diesen erbracht, würden wir uns heute aber vermutlich auch nicht auf casualscience treffen, wo das Credo Motto ist. Oder so ähnlich.
Während ich also seit 20 Jahren versuche, nicht unbedingt Teil der Zielgruppe dieses Optimierungsverfahrens zu werden, sind die eigentliche Zielgruppe ganz andere. Nämlich Handelsreisende. Zumindest sind sie die Namensgeber*innen des „Problems der*des Handelsreisenden“ (Traveling Salesman Problem, TSP). Ein Problem, das die Wissenschaft schon seit langer Zeit beschäftigt und auf das die Gentechnik auch ein Antwort weiß. Naja. Vielleicht eher ein Teilfeld eben dieser. Aber seht selbst…
Wenn eine*r eine Reise tut
Das Traveling Salesman Problem beschäftigt die Wissenschaft – wie schon erwähnt – seit recht geraumer Zeit und ist dementsprechend auch schon gut beforscht.
Zu lösen ist dabei die folgende Aufgabe: ein*e Handelsreisende*r soll auf ihrer*seiner Tour eine gewisse Anzahl von Städten abklappern. Dabei muss/darf sie*er jede Stadt der Tour nur exakt ein Mal besuchen. Noch dazu gilt es nicht irgendeine, sondern die kürzeste Route zu finden, die diesen Kriterien entspricht. Als Ausnahme von der Regel bildet der Ausgangspunkt der unternommenen Reise gleichzeitig auch deren Endpunkt. Soweit so gut. Das klingt ja mal durchaus schaffbar.
Als gut ausgearbeitetes, kombinatorisches Optimierungsproblem, wurden und werden daran verschiedene Optimierungsverfahren entwickelt und erprobt. Ein Gruppe von Verfahren, um sich der Fragestellung anzunehmen, bilden evolutionäre Algorithmen (genetic algorithm), die wir uns in einer Grobskizze kurz ansehen, bevor es dann ins Testlabor geht.
Gentechnik. Muss das sein?
Die Aufgabe, ein paar Punkte auf einer Karte zu einer möglichst kurzen Strecke zu verbinden, gibt es – in zarter Abwandlung – sogar schon in Rätselheften für Kindergartenkinder. Einerseits also keine all zu herausfordernde Problemstellung für die meisten von uns, die den Absprung aus dieser Institution schon geschafft haben. Andererseits aber auch wiedermal ein Grund zum Staunen, mit welcher Leichtigkeit unser Gehirn es schafft diese Herausforderung bis zu einer guten handvoll von Punkten in einer angemessenen Qualität zu meistern.
Wie komplex das Thema nämlich wirklich ist, zeigt sich, wenn wir uns die Zahl möglicher Routen anschauen, die sich fiktiven Handelsreisenden darbietet. Angenommen, es ist uns egal, ob wir von A nach B oder von B nach A reisen, gibt es bei zwei Punkten genau einen möglichen Weg. Überschaubar. Bei vier Destinationen, gibt es allerdings schon 12, bei 8 dann 20.160 und bei 10 satte 1.814.400 Optionen. Mit anderen Worten handelt es sich hier um ein Problem, das schon sehr früh nicht mehr direkt und exakt lösbar ist. Alle Entfernungen durchzurechnen, würde einfach zu schnell zu viel Zeit kosten.
Und genau hier hilft uns die Gentechnik. Genauer gesagt eben das Feld evolutionärer Algorithmen, in dem Ideen dazu entwickelt wurden, wie wir möglichst zielstrebig und behände durch diesen rießigen search space gleiten können. In Anlehnung an das Motto der neuen Sozialdemokratie „der Markt, der Markt, der hat immer recht“ gestehen evolutionäre Algorithmen diese Weitsicht eher der Natur zu. Durch Kreuzung, Mutation und Selektion der besten Lösungsansätze über mehrere Generationen hinweg, sollen so immer bessere Lösungsansätze entstehen. Ziel ist es, sich der tatsächlichen Lösung so schrittweise zu nähern.
Willkommen bei Frankenstein
Das hört sich aufs Erste dann mal doch etwas gruselig und ethisch fragwürdig an. Da das ganze Mutationszeugs dann aber doch auf einer eher theoretischen Ebene verbleibt, sollte sich dieser Schauder schnell abschütteln lassen und vielleicht sogar einem leichten Gefühl des Staunens Platz machen.
Etwas abstrahiert lässt sich das dann in etwa so darstellen:
1. In einem ersten Schritt lassen wir einen Gen-Pool einlaufen, in dem sich alle abzuklappernden Destinationen befinden. Jede Stadt, die bereist werden kann, nennen wir „Gen“ und sie ist Teil des Pools.
2. Als nächstes erschaffen wir uns eine Population, die aus verschiedenen Individuen besteht. Für jedes Individuum schöpfen wir, nachdem wir ordentlich umgerührt haben, das ganze Wasser aus unserem (eigentlich niemals leer werdenden) Gen-Pool. Etwas anders ausgedrückt, stellen wir auf Basis unserer Destinationen verschiedene, in ihrer Reihenfolge zufällig zusammengewürfelte Touren zusammen. Da sich die Individuen also auch als verschiedene Touren/Problemlösungen beschreiben lassen, ist die Population ein Haufen verschiedener Touren/möglicher Lösungen.
3. Auf der Suche nach der besten Lösung versuchen wir dann erstmal zu quantifizieren, was wir beim Zusammenwürfeln der Genstrukturen so erschaffen haben. Dazu wird die Länge jeder Tour berechnet. Auf Basis dieser Größe wird im weiteren entschieden welche Tour bzw. welches Individuum in den Pool möglicher Eltern der nächsten Generation eintreten darf. Da wir der Optimierung hinterher jagen, nehmen wir hier natürlich auch nur die Besten.
4. So langsam beginnt der Spaß. Wir schmeißen eine wilde Sause, an deren Ende sich aus dem Elternpool heraus lauter Paare finden, die miteinander Kinder zeugen (wollen). Das mit den Bienen und Blumen ist zwar ein netter Einstieg in die sexuelle Aufklärung. Soviel Wärme und Farbe von einem evolutionären Algorithmus abzuverlangen, wäre dann aber wohl doch übertrieben. Hier bildet eher Funktionalität die Basis der Romantik. Und wie wir weiter unten sehen können: es funktioniert.
5. Sobald sich zwei Eltern (Touren) gefunden haben, zeugen sie ein Kind. Kinder sind in der Regel das Produkt ihrer Eltern. Und so tauschen die beiden Eltern nicht nur Körperflüssigkeiten, sondern jeweils auch einen Teil ihrer Genstruktur miteinander aus. Anders gesagt nehmen wir einen Teil von Route A und fügen diesen an ein Teilstück der Route B. Immer bedacht natürlich, dass auch nach dieser Kreuzung die oberste Regel gilt: jede Stadt darf und muss genau ein Mal in unserer Route vorkommen.
6. Nachdem alle Kinder gezeugt wurden, versuchen wir – da und dort – durch kleine Mutationen das Leben etwas bunter zu machen und vielleicht einen Glückstreffer bei der Lösungssuche zu landen.
Nachdem dieser Schritt abgeschlossen ist, haben wir eigentlich schon die Population einer neuen Generation und es geht zurück zu Punkt 3. Das geht dann so lange weiter, bis wir einen Schlussstrich ziehen, eine annehmbare Lösung gefunden oder uns in einer Sackgasse heillos verrannt haben.
Im Detail gäbe es dazu natürlich noch viel mehr zu sagen. Auf welcher Basis Eltern ausgewählt werden etwa oder unter welchen Bedingungen die Kinder gezeugt und deren Genmaterial mutiert wird.
Vorerst belass ichs aber mal dabei. Zum Nachschauen und für Details findet sich der passende Code in [R] umgesetzt auf Github. An dieser Stelle gibts dafür die weitgehende Umsetzung des Codes in einer Shiny-App zum Anschauen und Ausprobieren.