Zum Inhalt springen

  • Einträge
    72
  • Kommentare
    239
  • Aufrufe
    11.313

Bachelorarbeit begonnen


kurtchen

495 Aufrufe

 Teilen

Ich hatte ja in Aussicht gestellt, ab und zu etwas zur Erstellung meiner Bachelorarbeit zu schreiben, falls die Zeit dafür reicht. Eigentlich reicht sie nicht, aber heute tut es mir trotzdem ganz gut, mal einen Schritt zurück zu treten und auf das Ganze zu schauen.

 

Themenfindung

 

An meiner FH entwickeln viele Studierende die Bachelorarbeit auf der Grundlage ihrer Projektarbeit. Das eigentlich praxisbezogene Thema der Projektarbeit wird dann mit einer wissenschaftlichen Fragestellung verknüpft und so fortgeführt und erweitert. Ich habe eine Weile geschwankt, ob ich das auch so machen soll.

 

Mein Projekt war ja die Entwicklung einer Steuersoftware für ein chronobiologisches Experiment. Im Rahmen des Projektes wurde eine erste Entwicklungsstufe erreicht, aber es gab noch einige Anforderungen, die nicht realisiert werden konnten. Insofern hätte hier durchaus die Möglichkeit bestanden, die nächsten Entwicklungsschritte zum Thema meiner Bachelorarbeit zu machen. Allerdings soll die Bachelorarbeit stärker als die Projektarbeit eine wissenschaftliche Fragestellung bearbeiten. Nun soll mein Projekt zwar einem wissenschaftlichen Zweck dienen, aber eben innerhalb der Disziplin der Biologie. Softwaretechnisch gesehen hat es verschiedene Aspekte: Physical Computing, Kommunikation übers Netz, GUI-Programmierung und so weiter. Dennoch tat ich mich zunächst schwer damit, eine für die Informatik relevante Forschungsfrage zu formulieren.

 

Meine Steuersoftware läuft auf einem Raspberry Pi und bietet ihre Funktionen als WebService im Intranet an. Eine Idee war daher ein Vergleich verschiedener Microframeworks für REST basierte Webservices, die sich gut für Physical Computing (auf vergleichsweise schwachbrüstiger Hardware) eignen. Mein Projekt nutzt z.B. inzwischen das Spark Framework. Der Vorteil wäre gewesen, dass ich die Weiterentwicklung meines Projektes zeitlich mit meiner Bachelorarbeit hätte verbinden können. Wer weiß, vielleicht wäre ich dann sogar schon fertig.

 

Es gab aber eine Sache, die mir daran nicht so gut gefiel. Die Informatik ist ja meist in einer dienenden Rolle. Sie ist aber auch eine Strukturwissenschaft mit eigenen Erkenntnisgegenständen. Die Bachelorarbeit ist (vielleicht eine letzte) Gelegenheit, sich mit diesem Aspekt der Informatik ausführlicher zu befassen. Darum hatte ich eigentlich Lust auf eine Bachelorarbeit, die einen stärkeren Theorieaspekt hat. Es gab zwei Themen, die mir seit einer Weile im Kopf herumspukten und die ich gerne verbinden wollte.

 

Funktionale Programmierung

 

Ich hatte ja hier im Forum mal von einem "Urlaubsprojekt" berichtet, bei dem ich ein bisschen mit dem Lisp-Dialekt Scheme herumexperimentiert habe. Das war in diesem Thread. Das lag daran, dass ich den Wunsch hatte, wenigstens ein anderes Programmierparadigma als die objektorientierte Programmierung kennenzulernen. Die Beschäftigung mit der funktionalen Sprache Scheme hinterließ bei mir viele Fragen und offene Wünsche:

  • Scheme wurde als Lehrsprache entwickelt. Ich hatte den Wunsch auch eine funktionale Sprache zu lernen, die für den produktiven Einsatz entwickelt wurde. Mögliche Kandidaten waren hier z.B. Scala, Clojure oder Erlang.
  • Mit dem Erlernen einer funktionalen Sprache ist es ja nicht getan. Schwieriger ist es, seine Denkweise zu ändern. Im Studium habe ich gelernt, Probleme objektorientiert zu modellieren. Ich habe objektorientierte Entwurfsmuster gelernt, die bestimmte Klassen von Problemen lösen. Das führt allerdings auch dazu, dass ich Probleme "durch eine objektorientierte Brille" anschaue.
  • Für die objektorientierte Programmierung gibt es die UML. Wie modelliere ich funktionale Softwaresysteme?
  • Besonders ungewohnt war für mich der Umgang mit unveränderlichen Datenstrukturen. Objektorientierte Programmierung versucht ja, Zuständsveränderungen zu beherrschen, indem Zustände in Objekten gekapselt werden. Funktionale Programmierung versucht, Zustandsveränderungen möglichst zu vermeiden. Allerdings konnte ich mir nicht so richtig vorstellen, wie ein größeres Softwaresystem ohne Zustandsveränderungen auskommen kann.

 

Insgesamt blieb bei mir also der Wunsch, mich noch einmal ausführlicher mit funktionaler Programmierung und meinen offenen Fragen zu beschäftigen. Meine Idealvorstellung wäre ein Modul über Programmierparadigmen gewesen, bei dem man gleiche Programme in unterschiedlichen Paradigmen implementiert und durch den direkten Vergleich an Fallbeispielen die jeweiligen Eigenheiten der Paradigmen verstehen lernt. Da es so ein Modul nicht gab, hatte ich die Idee, in meiner Bachelorarbeit objektorientierte und funktionale Programmierung an einem Fallbeispiel zu vergleichen.

 

Ich war auch neugierig, ob so ein Vergleich meine Sichtweise auf Programmierung verändern würde. Vielleicht ist es ja ein bisschen wie mit Fremdsprachen. Wenn man eine fremde Sprache lernt, so lernt man zugleich eine Menge über die Eigenheiten seiner eigenen Sprache. Und das umso mehr, je fremdartiger die neue Sprache ist.

 

Die Grundidee war also ein Sprachvergleich an einem Fallbeispiel. Nun musste noch ein Fallbeispiel her, dass sich für diesen Vergleich eignen würde.

 

Heuristiken mit Evolutionsstrategie

 

In diesem Zusammenhang fiel mir ein Artikel über den Sintflut-Algorithmus ein, den Gunter Dueck 1993 in der Zeitschrift Spektrum der Wissenschaft veröffentlicht hatte. Der Sintflut-Algorithmus kann z.B. das Problem des Handlungsreisenden lösen. Hier geht es darum, eine möglichst kurze Rundreise durch eine Anzahl Städte zu finden. Das klingt auf den ersten Blick nicht weiter schwierig, aber die Anzahl der Möglichkeiten wächst sehr rasch. Bei n Städten gibt es (n-1)!/2 Möglichkeiten; also bei nur 16 Städten bereits über 653 Milliarden mögliche Rundreisen. Ein praktisches Rundreiseproblem wäre ein Roboter, der Löcher in eine Platine bohren soll. Damit er mehr Platinen pro Stunde schafft, wäre es wünschenswert, er würde die Löcher ist der bestmöglichen Reihenfolge bohren. Wenn die Platine mehrere hundert Löcher hat, ist die Anzahl der möglichen Routen zu groß, um alle auszuprobieren. Das Problem kann nicht optimal gelöst werden.

 

Heuristische Algorithmen versuchen den großen Lösungsraum einzuschränken. Sie untersuchen nur einen Teil der Möglichkeiten und finden so schneller eine Lösung, allerdings zu dem Preis, dass sie höchstwahrscheinlich die optimale Lösung übersehen. Ist die Suchstrategie clever, so wird die gefundene Lösung aber nur wenig von einer optimalen Lösung abweichen. Für praktische Anwendungsfälle ist eine gute Lösung, mit der man sofort arbeiten kann, interessanter als eine optimale Lösung, die erst in ein paar hundert Jahren zu bekommen ist.

 

Eine vergleichsweise einfache Heuristik für das Rundreiseproblem ist die Nearest Neighbour Heuristik. Man wählt eine zufällige Stadt als Startpunkt. Von hier reist man immer zur nächstgelegenen Stadt, die man noch nicht besucht hat. Das liefert oft schon ganz gute Ergebnisse, aber gelegentlich haut die Nearest Neighbour Heuristik auch mal ordentlich daneben. Gleichwohl hat man hier ein einfaches Verfahren, das als Referenz für komplexere Verfahren dienen kann.

 

Eine Reihe von Algorithmen versuchen, Prinzipien der Evolution für Optimierungsprobleme fruchtbar zu machen. Die Grundidee ist, dass zunächst zufällige Lösungen erzeugt werden, die natürlich nicht besonders gut sind. Diese Lösungen werden nun kleinschrittig variiert, was bedeutet, dass die Varianten der ursprünglichen Lösung "ähneln" sollen. Mutationsoperatoren erzeugen solche zufälligen Varianten. Rekombinationsoperatoren erzeugen Lösungen als Kombination von zwei bisherigen Lösungen. Die bisherigen Lösungen nennt man dann Eltern und die erzeugten Varianten Nachkommen oder Kinder. Zur Strategie wird das aber erst, wenn ein Selektionsmechanismus hinzukommt. Die Varianten werden bewertet, verworfen oder sie verdrängen die bisherigen Lösungen.

 

Im Falle des Sintflut-Algorithmus ist der Selektionsmechanismus vergleichsweise anschaulich. Man stellt sich den Lösungsraum als Gebirge vor. Die Höhe über dem Meeresspiegel entspricht der Güte der Lösung entsprechend der Bewertungskriterien. Im Falle des Rundreiseproblems wäre also eine kürzere Rundreise ein höherer Punkt im Gebirge. Den Optimierer kann man sich als Wanderer vorstellen, der versucht, im Gebirge einen hohen Punkt zu erreichen. Eine naive Strategie wäre, immer nur bergauf zu gehen. Dann würde man allerdings auf dem ersten kleinen Gipfel "hängenbleiben". Manchmal muss man akzeptieren, dass es schlechter wird, bevor es besser werden kann. Man braucht also eine bessere Strategie als HINAUF. Sintflut fügt diesem Bild einen Regen hinzu, der den Wasserspiegel kontinuierlich ansteigen lässt. Nacheinander versinken so alle Gipfel im Wasser. Der Wanderer streift im Gebirge umher. Er geht rauf oder runter, solange er nur trockene Füße behält. Diese einfache Strategie liefert gute Lösungen für das Rundreiseproblem. Ich finde an solchen Algorithmen persönlich faszinierend, dass hier grundlegende biologische Prinzipien wie Anpassung durch Mutation und Selektion für die Informatik fruchtbar gemacht werden.

 

Aus verschiedenen Gründen hielt ich derartige Optimierungsverfahren auch für ein interessantes Thema für meine Fallstudie:

  • Die Erzeugung von Varianten durch Mutation und Rekombination wäre einen interessanter Anwendungsfall für immutable Datenstrukuren.
  • Simuliert man eine Population von Lösungen, so können Verarbeitungsschritte parallelisiert werden. Von funktionalen Sprachen wird behauptet, dass sie nebenläufige Berechnungen handhabbarer machen.
  • Andererseits sprechen wir hier von randomisierten Algorithmen. Ein Zufallsgenerator ist aber zustandsbehaftet. D.h. man kann auch etwas über den Umgang mit Seiteneffekten lernen, die in der funktionalen Programmierung eigentlich vermieden werden sollen.

 

Die Idee für meine Bachelorarbeit war also ein Vergleich objektorientierter und funktionaler Programmierung am Fallbeispiel verschiedener heuristischer (evolutionärer) Algorithmen zur Lösung des Rundreiseproblems. Ich hatte das Glück an meiner FH einen Professor zu finden, der für diese Idee offen war.

 

Stand der Bearbeitung

 

Die Arbeit ist inzwischen angemeldet. Hier ist zu bemerken, dass die Anmeldung einer Bachelorarbeit ein bisschen formaler abläuft als die Anmeldung einer Projektarbeit. Es muss ein Dokument als physischer Gegenstand herumgeschickt und von verschiedenen Personen unterzeichnet werden, weshalb das ganze ein bisschen länger dauern kann als man im Zeitalter elektronischer Kommunikation gewohnt ist. Insofern ist es empfehlenswert, frühzeitig Kontakt zum Erst- und Zweitprüfer und auch zum Studienbüro aufzunehmen.

 

Den Theorieteil der Arbeit konnte ich inzwischen fertigstellen. Hier geht es vor allem darum, das funktionale Programmierparadigma und verschiedene Heuristiken mit Evolutionsstrategie vorzustellen. Aktuell arbeite ich an der objektorientierten Implementierung meiner Optimierer. Leider geht es im Moment noch gar nicht um die Algorithmen, sondern um GUI- und Graphik-Programmierung, denn ich möchte ja nachvollziehen können, was z.B. meine Mutations- und Rekombionationsoperatoren mit Routen machen. Das geht hoffentlich leichter, wenn ich das visualisieren lassen kann. Ich bin nun schon sehr gespannt darauf, verschiedene Evolutionsstrategien auszuprobieren und ihnen beim Optimieren der Routen zuzuschauen.

 

Besonders neugierig bin ich natürlich auf die Programmierung in funktionalen Sprachen. Ich möchte Scala und Clojure nutzen. Scala ist eine Hybridsprache, die versucht objektorientierte und funktionale Programmierung zu verbinden. Sie verschafft mir vielleicht einen sanften Einstieg und Übergang. Scala ist auch eine statisch typisierte Sprache mit Typinferenz. In dieser Hinsicht ähnelt es Haskell. Clojure ist ein moderner Lisp-Dialekt. Es ist daher dynamisch typisiert und hat eine fremdartige Lisp-Syntax. Ich bin mit beiden Sprachen nicht vertraut, so dass ich hier einige Überraschungen erwarte.

 

Scala und Clojure sind JVM-Sprachen, d.h. sie compilieren zu Java-Bytecode, können Java-Code rufen und von Java-Code gerufen werden. Man spricht auch von Java-Interop. Das ist interessant, weil es in der Regel nicht sinnvoll ist, eine komplette Anwendung funktional zu implementieren. Insbesondere GUI-Code ist in hohem Maße zustandsbehaftet, was nicht so gut zum funktionalen Programmierparadigma passt. (Diese Aussage muss man heute eigentlich relativieren, z.B. weil es heute mit Elm eine funktionale Sprache für die Entwicklung von Web-Frontends gibt.) Daher wird das UI der Anwendung klassisch objektorientiert in Java implementiert, aber unter der Haube werkeln Optimierer in Java, Scala und Clojure.

 

Schreibwerkzeuge

 

Günstig war, dass ich mir vor Weihnachten Zeit genommen habe, mich in Latex einzuarbeiten und mir eine Dokumentenvorlage zu machen. Das war ein Stück Arbeit und hat mich z.T. auch bei der Bearbeitung meiner letzten Module ausgebremst. Allerdings ist es jetzt sehr schön, dass ich mich aufs Schreiben konzentrieren kann, statt mir über das Layout Gedanken zu machen. Ich würde also jedem empfehlen, sich mit diesem Thema VOR der Bachelorarbeit zu beschäftigen. Sich während dem Schreiben gleichzeitig in Latex einzuarbeiten, dürfte mühsam und ablenkend sein.

 

Viele Hochschulen bieten Dokumentenvorlagen zum Download an. Das ist natürlich komfortabel, weil man im Idealfall einfach losschreiben kann. Solche Vorlagen sind aber auch für Studierende anderer Hochschulen interessant, weil man sich etwas abschauen kann. Auch meine eigene Hochschule bietet im Rahmen des Moduls "Wissenschaftliches Arbeiten" so eine Vorlage. Die ist allerdings recht allgemein und auch nicht mehr ganz aktuell, so dass sie noch angepasst werden muss. Ich fand das aber zu schwierig, ohne Latex grundsätzlich zu begreifen. Für meine ersten Schritte hilfreich war das Buch "Wissenschaftliche Arbeiten schreiben" von Joachim Schlosser. Ganz alleine hätte das für die Erstellung meiner Vorlage nicht gereicht, aber es vermittelte mir ein Grundverständnis, das mir weitere Recherchen über das Netz erleichterte.

 

Zum Schreiben verwende ich Atom mit entsprechenden Latex-Plugins. Atom arbeitet schön mit Git zusammen, das ich für die Versionskontrolle nutze. UML-Diagramme erstelle ich meist mit UMLet. Eine Literaturverwaltung wie Zotero oder Citavi erschien mir bislang übertrieben. Bislang ist alles in einer einfachen BibTEX-Datei. Ich habe probiert, meine Einträge mit JabRef zu editieren, fand das aber gar nicht komfortabler, weil manche für mich relevante Felder über mehrere Tabs verteilt waren, so dass ich mehr mit "Mausschubsen" als mit Schreiben beschäftigt war. Möglicherweise könnte man sich das anders konfigurieren, aber ich komme mit einem einfachen Texteditor eigentlich gut zurecht. Allerdings werden es allmählich mehr Quellen. Vielleicht muss ich das mit der Literaturverwaltung also noch einmal überdenken. Lohnen dürfte sich das vor allem für Schreibende, die regelmäßig wissenschaftliche Arbeiten verfassen.

 

Fazit

 

Insgesamt macht die Arbeit an der Bachelorarbeit viel Spaß. Es ist schön, nach vielen Jahren des angeleiteten Lernens ein eigenes Thema recherchieren und einer eigenen Idee folgen zu können. Wichtig ist natürlich der Austausch mit dem Erstbetreuer, der diesen Prozess zurückhaltend begleitet.

 

Ich werde in Abständen wieder berichten.

 Teilen

3 Kommentare


Empfohlene Kommentare

  • Community Manager

Vielen Dank für deinen gewohnt ausführlichen Bericht. Ich habe den Eindruck, dass du dir ein durchaus anspruchsvolles und für eine Informatik-Bachelorarbeit angemessenes Thema ausgesucht hast.

 

Die gedanklichen Überlegungen und Hintergründe zum Problem des Handlungsreisenden fand ich sehr interessant.

 

Weiter viel Erfolg und ich bin gespannt auf das nächste Update.

Link zu diesem Kommentar

Eine charmante Darstellung des Rundreiseproblems findet sich im Artikel "Die optimierte Odyssee" der Zeitschrift "Spektrum der Wissenschaft". Aufhänger ist hier die von Homer besungene Irrfahrt des Odysseus von Ithaka. Bei effizienter Routenplanung hätte er schneller zu Hause sein können.

 

Eine zugängliche Darstellung des Sintflut-Algorithmus bietet der Artikel "Toleranzschwelle und Sintflut" ebenfalls in "Spektrum der Wissenschaft". Der Artikel hat mich auf die Idee gebracht, dieses Fallbeispiel für meinen Vergleich der Programmierparadigmen zu wählen. Leider enthalten beide online verfügbaren Artikel nicht die Illustrationen.

 

In diesem Youtube-Video kann man verschiedenen Optimierern zusehen, wie sie eine möglichst kurze Rundreise durch Städte der USA planen. Der komplexeste hier gezeigte Optimierer ist Simulated Annealing. Das natürliche Vorbild für dieses Verfahren ist das Abkühlen und Erstarren einer Metallschmelze. Am Anfang ist die Schmelze heiß, die Molekülbewegungen sind heftig. Für die Optimierung bedeutet dies, dass auch Änderungen akzeptiert werden, die zu einer Verlängerung der Route führen. Auf diese Weise können lokale Minima überwunden werden. Mit der Abkühlung der Schmelze werden die Molekülbewegungen langsamer. Die Wahrscheinlichkeit lokale Minima zu überwinden, sinkt, so dass gegen Ende nur noch Verbesserungen der Route akzeptiert werden.

 

Meinen Einstieg in das Thema funktionale Programmierung habe ich mit dem Buch "Schreibe Dein Programm" von Herbert Klaeren und Michael Sperber gefunden. Es ist eines der seltenen Beispiele für eine erste Einführung in die Programmierung mittels einer funktionalen Sprache. Als Lehrsprache wird Racket verwendet, ein Dialekt aus der Lisp-Scheme-Familie. Man kann das Buch nicht kaufen, aber es ist als PDF kostenlos unter der CC-Lizenz verfügbar. Es war mein "Urlaubsprojekt" im Sommer 2017.

 

Will man funktionale Programmierung in ihrer reinsten Form kennenlernen, sollte man sich mit Haskell beschäftigen. Das Buch "Learn you a Haskell for Great Good!" kann man online gratis lesen. Der Autor setzt voraus, dass man schon eine imperative Sprache gelernt hat. Das Kapitel "So what's Haskell?" bringt gut und knapp auf den Punkt, was funktionale Programmierung ist. Es vermittelt zugleich eine interessante Eigenschaft der Sprache Haskell: Die verzögerte Auswertung bzw. Lazy Evaluation.

Bearbeitet von kurtchen
Link zu diesem Kommentar

Erstelle ein Benutzerkonto oder melde Dich an, um zu kommentieren

Du musst ein Benutzerkonto haben, um einen Kommentar verfassen zu können

Benutzerkonto erstellen

Neues Benutzerkonto für unsere Community erstellen. Es ist einfach!

Neues Benutzerkonto erstellen

Anmelden

Du hast bereits ein Benutzerkonto? Melde Dich hier an.

Jetzt anmelden


×
×
  • Neu erstellen...