Es ist soweit: Am Mittwoch habe ich meine Bachelorarbeit zur Post gebracht. Das war zwei Tage vor dem Abgabetermin. DHL hat die Sache dann noch ein bisschen spannend gemacht. Am nächsten Abend war mein Paket nämlich gerade einmal 10 km weit "gekrochen". Aber am übernächsten Tag kam es doch noch fristgerecht in Dortmund an.

 

Natürlich sind mir schon am Tag nach der Abgabe Fehler aufgefallen, die ich auch beim x-ten Korrekturlesen nicht gesehen hatte. Ebenfalls typisch für mich: Sofort nach der Abgabe ist eine Erkältung ausgebrochen. Die hätte ich mir vorher nicht "gegönnt".

 

Eigentlich hatte ich zur Entstehung der Bachelorarbeit ja mehrere Blogbeiträge schreiben wollen. Aber letztlich musste ich die knapp werdende Zeit in die Bachelorarbeit investieren. Mein Fernstudien-Blog war leider nicht das einzige Hobby, das in den letzten Monaten auf der Strecke blieb.

 

Trotzdem nun ein paar Worte, die wie Sache nun eigentlich gelaufen ist.

 

Inhaltliches

 

Die Grundidee meiner Arbeit war ja ein Vergleich objektorientierter und funktionaler Programmierung an einem Fallbeispiel. Das Fallbeispiel war eine Variante des klassischen Travelling Salesman Problems: In eine Platine sollen von einem Roboter Löcher gebohrt werden. Ein Optimierer solle ein möglichst effiziente Abfolge der Löcher finden. Was genau effizient ist, bestimmt eine Bewertungsfunktion. Hier gab es als einfachste Funktion die euklidische Distanz. Eine Variante nahm an, dass ein Motor des Roboters defekt ist, und daher vertikale Bewegungen nur halb so schnell möglich sind wie horizontale. Eine andere Variante sah vor, dass der Bohrer für einen Bohrerwechsel zurück zum Ursprung kehren muss, falls der Durchmesser aufeinander folgender Löcher sich unterscheidet. Das hatte natürlich große Auswirkungen auf die gefundenen Routen. Die Routen wurden ja auch visualisiert und das war visuell z.T. ganz attraktiv, wie die Anmutung der Routen sich änderte, wenn eine andere Bewertungsfunktion gewählt wurde.

 

Die Routen wurden mit drei verschiedenen Heuristiken optimiert:

• mit der einfachen und schnellen Nearest-Neighbour-Heuristik
• mit dem Sintflut-Algorithmus
• und mit einer Evolutionsstrategie

 

Die beiden letzten Heuristiken ahmen einen Evolutionsprozess nach. Der Sinflut-Algorithmus erzeugt dabei Routenvarianten allein durch Mutation. Außerdem arbeitet er mit einer minimalen Population von nur zwei Individuen: Der bisherigen Lösung und einer neuen Lösung, die akzeptiert oder verworfen wird. Die Evolutionsstrategie simuliert eine größere Population. Sie erzeugt Routenvarianten nicht nur durch Mutation sondern auch durch Rekombination. Sie ahmt also "sexuelle Fortpflanzung" nach. Interessant war dann z.B. die Frage, was geeignete Mutations- und Rekombinationsoperatoren für ein Travelling Salesman Problem sind.

 

Die beiden Heuristiken unterscheiden sich auch beim Selektionsmechanismus. Sintflut arbeitet mit der Metapher eines steigenden Wasserspiegels. Eine Routenvariante wird akzeptiert, solange ihre "Fitness" nur besser als der momentane Wasserspiegel ist. Auch dann, wenn sie gegenüber der letzten Routenvariante schlechter ist. Das ist entscheidend, damit der Algorithmus ein lokales Optimum überwinden kann. Mit steigendem Wasserspiegel wird die Selektion immer härter, so dass gegen Ende der Optimierung nur noch Verbesserungen akzeptiert werden. Sintflut geht also nach und nach in einen sogenannten Bergsteiger-Algorithmus über. Meine Fallstudie arbeitete mit einer variablen Regenrate. Wenn die Optimierung stagnierte, regnete es gar nicht. Wenn sie voran schritt, regnete es umso stärker, je größer die Differenz zwischen momentaner Fitness und Wasserspiegel war.

 

Bei der Evolutionsstrategie wurde die Selektion durch den Wettbewerb innerhalb eine Population bestimmt. Meine Implementierung arbeitete mit einer (µ+λ)-Selektion. Dabei steht µ für die Elterngeneration und λ für die durch Rekombination von Genen und Mutation entstandenen Kinder. Die Kinder geraten also in Wettbewerb mit der Generation ihrer Eltern. Theoretisch könnte man dieser Form der Selektion ein Individuum beliebig viele Generationen überlegen, wenn seine Fitness nur hoch genug ist. Es gibt viele mögliche Selektionsoperatoren. Individuen mit hoher Fitness haben eine höhere Chance, die Selektion zu überleben, aber wie bei der natürlichen Selektion spielt i.d.R. auch der Zufall eine Rolle.

 

Am besten funktionierte der noch vergleichsweise einfache Sintflut-Algorithmus. Die Evolutionsstrategie war nicht nur langsamer sondern brachte auch etwas schlechtere Ergebnisse. Ich vermute, dass lag am früh einsetzenden Selektionsdruck durch Wettbewerb innerhalb der Population. Der führte dazu, dass die Optimierung früher als bei Sintflut in einem lokalen Optimum hängenblieb. Es wäre spannend gewesen, mehr mit den Selektionskriterien zu spielen, um zu schauen, ob man Sinflut so nicht doch einholen kann. Auch weiß ich inzwischen, dass es bessere Rekombinationsoperatoren gegeben hätte. Leider fehlte mir die Zeit, diese noch zu implementieren und auszuprobieren. Aber es war schon faszinierend anzusehen, wie das Duo aus Mutation und Selektion eine Route optimiert. Die Software hatte ein einfaches GUI, das periodisch Momentaufnahmen der laufenden Optimierung zeigte. Der Moment, in dem es erstmals klappte, und man zuschauen konnte, wie die Routenlängen fielen, war schon sehr befriedigend.

 

Allerdings war heuristische Optimierung ja nur das Fallbeispiel für einen Vergleich der Programmierparadigmen. Darum habe ich die gleichen Heuristiken in Java, Scala und Clojure implementiert.

 

Meine persönliche Motivation für dieses Thema war, dass ich eine empfundene fachliche Lücke meines Studiums schließen wollte. Ich wollte funktionale Programmierung und funktionale Programmiersprachen besser kennenlernen, als das im Curriculum meines Studiums vorgesehen war. Dieser Wunsch ging für mich in Erfüllung. Bei der Implementierung der Optimierer in Scala und Clojure konnte ich viele Aspekte funktionaler Programmierung erleben und anwenden: Funktionen höherer Ordnung, (End-)Rekursion, Verwendung persistenter Datenstrukturen, Closures, partielle Funktionen, Lazy Evaluation und Lazy Sequences und einiges mehr. Wie erwartet, war es so in vielen Fällen möglich, kompakteren und dennoch gut lesbaren Code zu schreiben. Vor allem war der funktionale Code oft deklarativer als der imperative. Er war also eher eine Beschreibung der Problemlösung als eine kleinschrittige Handlungsanweisung für den Computer. Im Vergleich zur objektorientierten Programmierung war es schon faszinierend, sich als Programmierer so gegenüber der Maschine ausdrücken zu können.

 

Leider hatte insbesondere die Verwendung persistenter Datenstrukturen ihren Preis. Die in Scala implementierten Optimierer liefen deutlich langsamer als ihre Gegenstücke in Java. Die Performance ließ sich verbessern, indem man (zumindest vorrübergehend) doch veränderliche Datenstrukturen verwendete. Leider fiel der Code dann nicht mehr so elegant und deklarativ aus. Er ähnelte wieder stärker den imperativen Lösungen. Auf einem höheren Abstraktionsniveau mit dem Computer zu kommunizieren hat also einen Preis.

 

Obwohl Scala Java syntaktisch viel ähnlicher ist als Clojure, dauerte es länger, eine Heuristik von Java nach Scala zu portieren. Die Portierung von Scala nach Clojure war dagegen meist sehr schnell erledigt, obwohl die lispoide Syntax für mich anfangs sehr fremdartig war. An dieser Stelle war spürbar, was es heißt, sich innerhalb eines Programmierparadigmas oder eben zwischen verschiedenen Programmierparadigmen zu bewegen. Bleibt man innerhalb eines Paradigmas, hat man das Gefühl, alle Sprachen sind gleich. Wechselt man zwischen den Paradigmen, merkt man, dass jede Sprache ihr Paket an impliziten Denkweisen und Lösungsstrategien mit sich trägt.

 

Clojure war als dynamisch typisierte Sprache natürlich noch einmal deutlich langsamer als Scala. Bei Clojure bedauere ich, dass die Zeit nicht reichte, um Metaprogrammierung mit Makros auszuprobieren.

 

Scala gefällt mir als Programmiersprache gut. Ich finde es z.B. toll, dass man es einerseits als funktionale aber andererseits auch als objektorientierte Sprache verwenden kann. Auch wenn man objektorientiert programmiert, erlaubt es an vielen Stellen kompakteren und zugleich besser lesbareren Code als Java. Ich glaube, es gibt in meiner Region sogar ein Softwareunternehmen, das diese Sprache produktiv einsetzt. Inzwischen wäre ich auch neugierig, mit Kotlin eine weitere multi-paradigmatische Sprache auf der JVM kennenzulernen.

 

Betreuung

 

Meinen Erstbetreuer kannte ich schon von der Projektarbeit. Er bekam fortlaufend Textbausteine geschickt. Wie in Aussicht gestellt, kamen anfangs mehr Rückmeldungen und mit fortschreitender Arbeit wurde es knapper. Das fand ich genau richtig. Ich habe mich gut begleitet gefühlt, hatte aber auch den Eindruck, selbst für meine Bachelorarbeit zuständig zu sein. Toll war für mich, dass mir das Studienbüro einen Betreuer vermitteln konnte, der für mein Wunschthema offen war.

 

Ich bin ein bisschen gespannt, was mein Zweitbetreuer zu meiner Arbeit sagen wird. Er bekam sie erst am Schluss, als sie fertig war, so dass ich ihn noch nicht richtig kennenlernen konnte. Aber beim Kolloquium muss ich mich ja den Fragen beider Betreuer stellen.

 

Mal schauen, wie lange es nun dauert, bis eine Rückmeldung kommt. Ich werde im Blog berichten.

 

Tools und Werkzeuge

 

Lohnend war in jedem Fall, dass ich mir schon letztes Jahr die Mühe gemacht hatte, eine brauchbare LaTeX-Vorlage zu erstellen. Für eine Arbeit mit vielen Abbildungen, Fußnoten, Querverweisen, Verzeichnissen und Quellenangaben ist es sehr angenehm, sich Dank LaTeX aufs Schreiben konzentrieren zu können und sich nicht mit dem Layout herumschlagen zu müssen.

 

Meine Quellen habe ich als einfache Textdatei mit einem Texteditor erfasst. Ich war anfangs der Ansicht, für eine Bachelorarbeit würden es ja wohl nicht so viele Quellen werden, so dass eine Literaturverwaltung mir übertrieben vorkam. Am Ende wurden es doch mehr Quellen als ich gedacht hätte. Stünde ich noch einmal am Anfang, würde ich eine Literaturverwaltung verwenden.

 

Als IDE habe ich IntelliJ verwendet. Die hat eine gute Unterstützung für Scala. Man kann sie auch für Clojure verwenden. Allerdings hat es sich als etwas schwierig erwiesen, Scala und Clojure im gleichen Projekt zu verwenden. (Dazu nur ein Beispiel: Scala-Projekte nutzen als Build Tool bevorzugt das SBT. Clojure-Projekte verwenden meist Leinigen. Prinzipiell müsste es möglich sein, mit dem SBT auch Clojure oder mit Leiningen auch Scala zu compilieren, aber ein entsprechendes Setup habe ich nicht hinbekommen.)

 

Für die Erstellung von UML-Diagrammen habe ich UMLet verwendet. Es ist ein bisschen "spartanisch", aber dafür ist es auch schlank und erschlägt einen nicht mit der Vielfalt seiner Features.

 

Zeitmanagement

 

Im Großen und Ganzen hat meine Zeiteinteilung funktioniert. Inzwischen bin ich alt genug, um begriffen zu haben, dass ein noch so guter Plan nie hinhaut und man daher stets Puffer für Unerwartetes einplanen muss.

 

Die hätten allerdings noch ein bisschen üppiger ausfallen dürfen. Insgesamt habe ich mir doch mehr vorgenommen, als im Rahmen einer Bachelorarbeit realistisch war. So musste ich gegen Ende auf ein paar Themen und Aspekte verzichten, die ich gerne noch erkundet hätte. Zum Beispiel bietet Scala nebenläufige Programmierung auf einem höheren Abstraktionsniveau mit Aktoren. Die hätte ich gerne für die Evolutionsstrategie verwendet, aber dafür reichte die Zeit nicht mehr.

 

Es wäre auch gut gewesen, am Ende mehr Zeit für Korrekturen zu haben. Eigentlich hatte ich dafür eine ganze Woche eingeplant, aber dann musste es doch schneller gehen. Zwar hatte ich zwischendurch immer wieder Kapitel gelesen und überarbeitet, aber ich war doch jedes Mal wieder erstaunt, dass man auch nach dem x-ten Durchgang wieder etwas findet.

Das Drucken und Binden war diesmal stressfrei, weil ich schon eine ganze Weile vorher im Copyshop vorstellig geworden war und vorgefühlt hatte, wie ausgelastet die Mitarbeiter waren. So konnte ich eine klare Vereinbarung treffen und das lief dann auch genau so.

 

Ausblick

 

Nun heißt es, loslassen und abwarten, was meine Betreuer sagen. Somit habe ich, eigentlich zum ersten Mal seit Beginn meines Studium, so etwas wie "Leerlauf". Das kann ich inzwischen aber auch gut gebrachen. In den letzten Monaten ist einiges auf der Strecke geblieben; Hobbies zum Beispiel. Gestern habe ich zum ersten Mal wieder ein bisschen Klavier geübt. Das möchte ich nun wieder regelmäßiger machen.

 

Ich hoffe ein bisschen, dass es noch vor Jahresende zum Kolloquium kommt. Wäre schön, wenn ich das Studium mit dem alten Jahr abschließen könnte.

 

Auch aus einem praktischen Grund wäre das gut. Der Kindergarten, in dem ich während meines gesamten Studiums gearbeitet habe, kann mich ab Januar nicht mehr beschäftigen. Es sind Zuschüsse weggefallen, die für die Finanzierung meiner Stelle wesentlich waren. Darum stehen zwingend berufliche Veränderungen an.

 

Meine Idee bei Aufnahme des Studiums war ja, einen Branchenwechsel hinzulegen: Von der Frühpädagogik zur IT. Das Problem dürfte dabei mein Alter werden. Man liest zwar beinahe täglich in der Zeitung, dass Informatiker gesucht werden. Aber bald werde ich erleben, ob das auch gilt, wenn sie Berufseinsteiger im mittleren Alter sind.

 

Sorgen muss ich mir eigentlich nicht machen, denn in meiner Region kann man als Kindergärtner kaum arbeitslos werden. In den letzten Wochen habe ich neue Kinder eingewöhnt und wieder einmal gemerkt, wie identitätsstiftend diese Arbeit in der ersten Hälfte meines Berufslebens für mich war. Eigentlich bin ich immer noch stolz, dass ich mich als junger Erwachsener für diesen Beruf entschieden habe; zu einer Zeit, als es noch absolut unüblich war, dass Männer in Kindergärten arbeiteten. Insofern mache ich mich nicht verrückt. Falls die Arbeitgeber mir nicht zutrauen, in meinem Alter noch ein guter Informatiker zu werden, bleibe ich eben Kindergärtner. Das kann ich immer noch ganz gut.

 

Wenn die Bachelorarbeit bestanden ist, bleibt als letzter Baustein des Studiums tatsächlich nur noch das Kolloquium. Darüber mache ich mir im Moment aber noch keine Gedanken. Aktuell versuche ich, nach den intensiven letzten Monaten ein bisschen Abstand zu meiner Bachelorarbeit zu gewinnen.

 

Für diesen Blog heißt das, dass es wohl nicht mehr allzu viele Beiträge werden. Ich möchte noch über das Kolloquium berichten. Und danach noch einmal rückblickend, den Studiengang als Ganzes betrachten. Aber möglicherweise besuche ich vorher noch einmal einen Präsenztag in Dortmund, so dass es vielleicht auch noch drei Beiträge werden könnten.

 

Bildergalerie

 

 

Das erste Bild zeigt den implementierten Optimierer vor einem Lauf. Geladen ist das sogenannte 442-Problem, eine Platine mit 442 Bohrlöchern, die im Zusammenhang mit dem TSP gerne als Testfall benutzt wird. Die Koordinaten der Löcher wurden mir freundlicherweise von Dr. Johannes Josef Schneider von der ZHAW Winterthur zur Verfügung gestellt. Das Bild zeigt eine zufällig generierte - also noch nicht optimierte - Route. Das schöne am 442-Problem ist, dass dafür eine optimale Lösung bestimmt werden konnte. Gelbe Kanten zeigen an, dass aufeinander folgende Löcher den gleichen Durchmesser haben. Hellrote Kanten zeigen dagegen, dass die Lochdurchmesser sich unterscheiden, was einen Bohrerwechsel nötig macht. (Das originale 442-Problem kennt keine Lochdurchmesser. Das ist eine Variation, die ich eingebaut habe, weil ich mit verschiedenen Bewertungsfunktionen experimentieren wollte.)

 

 

Das zweite Bild zeigt die Anordnung der Löcher des 442-Problems. Eine optimale Lösung konnte im Jahr 1987 gefunden werden, weil viele Löcher in horizontalen oder vertikalen Linien angeordnet sind. Dies ließ sich mathematisch verwerten, um viele mögliche Routen auszuschließen. Wie genau das funktioniert, verstehe ich freilich nicht; ich bin leider nur Informatiker, kein Mathematiker. Relevant für mich war, dass eine optimale Rundreise nachweislich eine Länge von ca. 5078 mm hat. Das liefert einen Anhaltspunkt dafür, wie gut die Optimierung - z.B. mit dem Sintflut-Algorithmus -  funktioniert.

 

 

Das dritte Bild zeigt eine mit dem Sintflut-Algorithmus optimierte Tour. Hier wurde die Route in ca. 8 Sekunden auf 5321 mm verkürzt. Sie ist somit lediglich 4,7% länger als die optimale Route. Lässt man es langsamer regnen, so braucht die Optimierung etwas länger, aber der Algorithmus findet kürzere Routen, die nur noch ca. 2,5% länger sind als die optimale Route.