Abschlussarbeiten der FG Wissensbasierte Systeme

• Offene Themen
• Laufende Abschlussarbeiten
• Abgeschlossene Abschlussarbeiten

Die hier aufgeführten Abschlussarbeiten sollen einen Überblick über mögliche Themen unseres Lehrstuhls bieten. Grundsätzlich ist es immer möglich eine persönliche Aufgabenstellung auszuarbeiten, falls Sie hier kein für Sie interessantes Thema finden. Insbesondere bei den abgeschlossenen Arbeiten können Aufgabenstellungen abgeleitet werden, die vorherige Arbeiten erweitern und ausbauen. Schauen Sie deshalb auch dort nach einer interessanten Aufgabenstellung. Wenn Sie Fragen zu einem Thema haben oder ein vorgeschlagenes Thema bearbeiten möchten, wenden Sie sich bitte an die entsprechende Kontaktperson.

Offene Abschlussarbeitsthemen

Plugin für die Genre Analyse von Web-Seiten (Bachelorarbeit)

Thema
Die Suche nach Informationen im Web wird durch Suchmaschinen hervorragend unterstützt. Allerdings läßt sich die Suche nicht auf Seiten bestimmter Klassen einschränken, z.B. auf Wiki-Seiten. Solche Klassen von Webseiten bezeichnet man auch als Genres und die Bestimmung von Genre-Zugehörigkeiten sowie das Ausnutzen dieser Information als Genre Analyse. Zur Unterstützung der Suche mit Suchmaschinen soll -- ein Eingriff in die Suche ist ja nicht möglich -- die Genre-Zugehörigkeit der gefundenen Webseiten bestimmt und angezeigt werden. Ein Prototyp einer solchen Anwendung existiert in Form eines Firefox-Plugin für die Suche mit Google.

Im Rahmen der Bachelorarbeit soll ein analoges Plugin erstellt werden, dass an die Ergebnisse einer neueren Arbeit zur Genre-Analyse nutzt. Da die für die Klassifikation benötigten Features einer Webseite bestimmt werden müssen und dadurch eine Verzögerung bei der Präsentation der Suchergebnisse verursacht wird, sollen Experimente durchgeführt werden, die Qualität und Effizienz der Genre Klassifikation für unterschiedliche Feature Sets in Beziehung setzen.

Beginn der Arbeit: Frühjahr 2012

Kontakt: Th. Lettmann

Evaluation kooperativer Bewegungsstrategien für Roboter in unbekannten merkmalsarmen Umgebungen (Bachelorarbeit)

Thema
In unbekannten merkmalsarmen Umgebungen können sich Agenten lokalisieren, indem sie künstliche Landmarken in die Umgebung einfügen und diese als Referenz verwenden. Bei Gruppen von Agenten können diese Rolle auch Teammitglieder übernehmen. Eine Vorwärtsbewegung einer Gruppe von Agenten folgt dann einer festen Choreographie, die die Fehler in der Lokalisierung minimieren soll.
In dieser Bachelorarbeit sollen in einer Simulationsumgebung einige Strategien für solche Bewegungen in Roboterteams implementiert und evaluiert werden. Je nach Leistungsstand des Studenten können auch Varianten und zusätzliche neue Strategien entwickelt werden.

Kontakt: Th. Lettmann

Fault Detection in Industrial Applications Using Behavior Models (Bachelor/Master Thesis)

(Description only available in English)

Topic
Dynamic evolution of today's industrial production systems has brought a big attention to their reliability and safety. These properties are ensured by process monitoring. Since production systems are hybrid in nature (i.e. comprise both discrete and continuous dynamics), process monitoring needs to include the following:

• Checking the correctness of observed sequences and timings of control signals
• Checking the measurable process variables with regard to tolerances

When a discrepancy is found in either of these two cases, an alarm is raised for the operator, signalizing a detected fault.

Process monitoring relies on a behavior model of the system, thus it belongs to a model-based approaches to fault detection and diagnosis. State of the art research in this field has offered the means of learning behavior models of hybrid systems in an automated way. The learning is done in a formalism of hybrid automata. The tasks of this thesis are summarized in the following:

• Reviewing the state of the art in model-based fault detection and diagnosis of hybrid systems
• Extending the existing behavior model learning algorithm with the Support Vector Regression method for estimating the process variables (continuous dynamics)
• Performing fault detection with different learned behavior models and comparing the results

Prerequisite: Good knowledge of Matlab. Thesis supervision is in English, and the thesis should also be written in English. Additional tasks exist for Master thesis (e.g. dealing with noisy data, using k-NN for regression etc.).

Contact: Asmir Vodencarevic

Laufende Abschlussarbeiten

Lernen mit neuronalen Netzen in Multiagentensystemen (Bachelorarbeit)

Thema
Viele Aufgaben in Multiagentensystemen erfordern zur Lösung Kooperation und Koordination der beteiligten Agenten. Bei der Betrachtung von Agenten als Modell für Roboter ist es beispielsweise wichtig, dass diese nicht kollidieren (Koordination) und dass sie zusammenarbeiten, wenn sie Aufgaben nicht alleine erfüllen können (Kooperation). Fest implementiertes Verhalten hat den Nachteil, dass sich die Agenten auf Veränderungen der Umwelt nur schwer einstellen können. Es ist daher sinnvoll, Verhalten zu lernen, so dass sich die Agenten zur Laufzeit an neue Situationen anpassen können. Neuronale Netze besitzen die Fähigkeit zur Adaption, d.h. sie können nach einigem Training auch unbekannte Daten erkennen.

In dieser Arbeit sollen verschiedene Anwendungsmöglichkeiten von neuronalen Netzen zum Lernen solcher Fähigkeiten in Multiagentensystemen untersucht werden. Das Ziel soll sein, dass Agenten in der Lage sind, ähnliche Situationen zu erkennen und sich entsprechend zu verhalten. Im Rahmen dieser Arbeit soll zuerst geeignete Literatur gesichtet werden um dann eine Auswahl der vorhandenen Verfahren theoretisch und experimentell zu vergleichen. Für diesen Vergleich soll ein einfaches Mehragenten-Problem ausgewählt werden, das Kooperation und/oder Koordination zur Lösung erfordert.

Kontakt: Michael Baumann

Learning in Local Movement Strategies (Bachelorarbeit)

Thema
Wir betrachten ein Problem, in dem ein Roboter (Explorer) eine unbekannte Umgebung explorieren soll. Dabei muss der Roboter ständig Funkkontakt zu einer Basisstation halten. Auf Grund beschränkter Funkreichweiten wird der Einsatz einer Kette von Relay-Robotern zur Aufrechterhaltung der Verbindung notwendig. Hierzu sollen möglichst wenige Relays verwendet werden und gleichzeitig die Bewegung des Explorers uneingeschränkt bleiben. Ein Relay kennt dabei nur die Positionen seiner Nachbarn in der Kette und muss daraufhin entscheiden, wie es sich bewegt, ohne das die Kette abreißt.
Zur Lösung diese Problems existieren bereits unterschiedliche Ansätze, für die auch theoretische Ergebnisse vorliegen. Einer dieser Ansätze verwendet die sogenannte Shorten-Operation, bei der ein Relay entfernt werden kann, wenn eine bestimmte Winkelbedingung erfüllt ist. Unter Verwendung dieser Bedingung können lokal und verteilt Kommunikationsketten erstellt werden, die höchstens Wurzel(2) mal die Anzahl der im Optimum benötigten Relays benutzen.
Die Fragestellung, die in dieser Bachelorarbeit bearbeitet werden soll, lautet wie folgt: Können andere Winkelbedingungen erlernt werden, so dass die Laufzeit des Algorithmus' reduziert wird? Hierzu soll zuerst ein überblick über vorhandene Lernverfahren und die Sichtung einschlägiger Literatur erfolgen. Darauf aufbauend soll ein Lernverfahren wie bspw. ein genetischer Algorithmus implementiert und die Fragestellung untersucht werden.
Diese Bachelorarbeit findet in Kooperation mit Barbara Kempkes (AG Meyer auf der Heide) statt.

Kontakt: Thomas Kemmerich

Lokales Abschätzen globaler Systemzustände in Multiagentensystemen (Bachelorarbeit)

Thema
Im General Online Partitioning Problem (GOPP) geht es darum, dezentral eine Menge von Agenten gleichmäßig, distanz- und kostenminimal auf eine Menge von Zielen im euklidischen Raum zu verteilen. Die Umgebung kann dabei unterschiedliche Arten von Hindernissen sowie Regionen mit speziellen Eigenschaften enthalten. Die Agenten verfügen lediglich über lokales Wissen und können unter Berücksichtigung der Hindernisse mit ihren Nachbarn lokal kommunizieren.
Mit Hilfe eines verteilten Algorithmus sollen die Agenten lokal lernen dieses globale Optimierungsproblem im Sinne einer gegebenen Zielfunktion zu lösen. Ein Ansatz dazu verwendet Reinforcement Learning Techniken, bei denen die Aktionen der Agenten in den einzelnen Zuständen bewertet werden. Auf Basis der Bewertung entscheiden die Agenten, ob eine ausgeführte Aktion "gut" oder "schlecht" war und lernen somit in welchen Zuständen welche Aktionen sinnvoll sind, um das Problem effizient zu lösen. Da die Agenten im gegebenen Szenario keine Rückmeldungen von der Umwelt selbst erhalten können, soll eine globale Bewertung der aktuellen Situation als Feedback verwendet werden. Dies würde jedoch eine zentrale Instanz bzw. erhöhten Kommunikationsaufwand erfordern.
Das Ziel dieser Bachelorarbeit ist es, ein Verfahren zu entwickeln, bei dem jeder Agent lokal durch Nachrichtenaustausch eine gute Abschätzung des globalen Systemzustandes bestimmen kann. Hierzu ist zunächst eine übersicht über vorhandene Verfahren, z.B. aus dem Bereich der Peer-to-Peer Netze zu erstellen und deren Einsatz zu evaluieren. Darauf aufbauend soll ein Ansatz entwickelt und in einem vorhandenen Simulator als Modul realisiert werden. Abschließend soll eine Analyse hinsichtlich der Nachrichtenkomplexität und der Güte der Abschätzung erfolgen.

Kontakt: Thomas Kemmerich

Abgeschlossene Arbeiten

Detektion und Tracking von Gesichtern in Bildern (Bachelorarbeit)

Thema
In sicherheitskritischen Einsatzbereichen müssen technische Geräte überwacht werden, zum Beispiel durch Kameras. Um zu verhindern, dass autorisierte Benutzer durch andere Personen ausgespäht werden, sollen Sequenzen von Kamerabildern auf enthaltene Gesichter geprüft werden und die Bewegungen der Gesichter verfolgt werden, um autorisierte Benutzer, zufällige Passanten und Ausspähversuche unterscheiden zu können.
Verfahren zur Gesichtserkennung liegen als C-Code oder Java-Code vor. Im Rahmen der Arbeit ist auf dieser Basis eine Gesichtserkennung ausreichender Qualität (Kopfneigung, Profil) zu implementieren, die ein Tracking der erkannten Gesichter erlaubt. Mit Hilfe einfacher Entscheidungsverfahrens sollen potentielle Ausspähversuche erkannt werden. Im Rahmen der Arbeit sind aussagefähige Beschreibungen der Verfahren zu erstellen, die insbesondere Laufzeit- und Platzkomplexität enthalten. Die Anwendung soll in einer Experimentierumgebung mit verschiedenen Beispielfällen getestet werden können.
Die Bachelor-Arbeit wird in Zusammenarbeit mit der Wincor Nixdorf und dem s-lab durchgeführt.
Betreuer: Dr. St. Priesterjahn (Wincor Nixdorf), Dr. Th. Lettmann (Universität Paderborn)

Kontakt: Th. Lettmann

Vertrauensmechanismen in lokal offenen Multiagentensystemen (Masterarbeit)

Thema
Betrachtet werden große Agentenmengen und die Interaktionen zwischen den einzelnen Agenten. Die Agenten bilden einen Graphen, wobei die Knoten einzelne Agenten repräsentieren und die Kanten die Nachbarschaft eines Agenten beschreiben. Ein Agent darf nur mit seinen Nachbarn kommunizieren und interagieren. Die Agenten besitzen also nur lokale Informationen. Zudem ist das Agentennetz dynamischen Veränderungen unterworfen, da Agenten die Verbindung zu anderen lösen und mit neuen Agenten eine Verbindung aufbauen.

In der Literatur findet man unterschiedliche Vertrauensansätze zur Bewertung einzelner Agenten. Dort führen die Agenten Listen über die Bewertungen zu ihren Nachbarn. Kommen neue Nachbarn hinzu wächst eine solche Liste. Was passiert jedoch mit dem Wissen über Nachbarn, zu denen nun keine Verbindung mehr besteht aufgrund der Dynamik des Netzwerkes? Wenn man solches Wissen verwirft kann man von einem lokal offenen Multiagentensystem sprechen. Hier gilt es dennoch einen Ansatz zu entwickeln der dazu führt, dass Agenten aufgrund der Vertrauensbewertung kooperieren.

Als Anwendungsfall wird dabei ein Task Allocation Problem betrachtet, in dem die Agenten Aufgaben zu lösen haben, die bestimmte Fähigkeiten verlangen. Agenten in dieser Arbeit gehen nach dem Prinzip vor "hilfst du mir, so helfe ich dir". Dazu wird ein Vertrauenswert benötigt, der wiedergibt, wie sehr ein Agent glaubt, dass der Agent, der nun um Hilfe bittet, meine (zukünftige) Anfrage(n) positiv beantwortet.

Kontakt: Markus Eberling

Coalition Formation for Task Allocation in Multiagent Systems (Bachelorarbeit)

Thema
Task Allocation in Multiagentensystemen ist das Problem der dezentralen Zerlegung und Verteilung von Aufgaben innerhalb einer Menge von Agenten. Unter Coalition Formation versteht man im weitesten Sinne Teambildungsstrategien um eine Aufgabe gemeinsam zu lösen. Ziel dieser Arbeit soll es sein einen Überblick über Coalition Formation im Zusammenhang mit dem Task Allocation Problem zu geben. Darauf aufbauend soll ein vorhandenes oder eigenes Modell beschrieben und implementiert werden. Mit Hilfe dieses Modells sollen dann eine Auswahl verschiedener Ansätze aus der Literatur umgesetzt und bewertet werden.

Dabei sollen die Agenten in einem Agentennetzwerk angeordnet sein. Die Knoten repräsentieren die Agenten und die Kanten repräsentieren die Interaktionsmöglichkeiten der Agenten. Die Menge an Aufgaben ist den Agenten bekannt, jedoch dürfen die Helfer nur direkte Nachbarn sein. Zudem haben die Agenten nur begrenzte Ressourcen zur Verfügung was dieses Problem NP-hart macht. Dennoch soll versucht werden den Gesamtnutzen des Systems zu maximieren.

Kontakt: Markus Eberling

Interaktion und vertrauenswürdiges Verhalten in Multiagentensystemen (Bachelorarbeit)

Thema
Betrachtet werden große Agentenmengen und die Interaktionen zwischen den einzelnen Agenten. Die Agenten bilden einen Graphen, wobei die Knoten einzelne Agenten repräsentieren und die Kanten die Nachbarschaft eines Agenten beschreiben. Ein Agent darf nur mit seinen Nachbarn kommunizieren und interagieren. Die Agenten besitzen also nur lokale Informationen.
Basierend auf diesen Informationen sollen die Agenten Aufgaben erledigen, für die Kooperation in den meisten Fällen unerlässlich ist. Um Aufgaben zu erledigen, müssen die Agenten ihre zur Verfügung stehenden Ressourcen einsetzen. Hier stellt sich die Frage, wie viele Ressourcen und zu welchem Preis ein Agent diese einsetzen möchte. Es entstehen dabei Probleme, dass zu viele Ressourcen angeboten werden oder zu wenig. In beiden Fällen kann es dazu führen, dass eine Aufgabe nicht erledigt werden kann. Allerdings kann dies den Nutzen des einzelnen Agenten erhöhen.
Ziel dieser Bachelorarbeit ist die Entwicklung eines Ansatzes, der diese Probleme umgeht, ohne den Agenten ihre Autonomie zu nehmen. Dabei gilt es zunächst die einschlägige Literatur zu sichten und eine übersicht über existierende Ansätze zu erstellen. Darauf aufbauend soll dann das Modell und dessen Evaluation erfolgen.

Kontakt: Markus Eberling

Learning to Cooperate in Agent Networks (Masterarbeit)

Thema
Ein Agentennetz ist ein Graph, wobei die Knoten einzelne Agenten repräsentieren und die Kanten die Nachbarschaft eines Agenten beschreiben. Nur mit seinen Nachbarn darf ein Agent kommunizieren und interagieren. Die Agenten besitzen also nur lokale Informationen.
Basierend auf diesen Informationen sollen die Agenten lernen mit wem sie kooperieren. Ein Ansatz kann sein, dass die Agenten unterschiedliche Zustände besitzen und somit die lokalen Informationen die Zustände ihrer Nachbarn bilden. Der Agent selbst soll dann entscheiden, mit welchen seiner Nachbarn er kooperieren würde oder ob er das Netzwerk verändern möchte, indem er bestehende Verbindungen durch neue Verbindungen ersetzt.
Ziel dieser Masterarbeit ist die Entwicklung eines Ansatzes, wie Agenten in dem gegebenen Szenario auf Basis der lokalen Informationen Strategien lernen. Dabei gilt es zunächst die einschlägige Literatur zu sichten und den Einsatz konventioneller Lernverfahren zu analysieren. Darauf aufbauend soll dann ein Lösungsansatz entwickelt werden inklusive einer Evaluierung und Machbarkeitsanalyse.

Kontakt: Markus Eberling

Cooperative Agents in Uncooperative Environments (Diplomarbeit)

Thema
In dieser Arbeit soll es um Umgebungen gehen, in denen eigennütziges Handeln von Agenten zu einer Erhöhung des eigenen Nutzens führt. Dies kann beispielsweise die Nichtkooperation sein, da Kooperation zu eigenen Kosten (Zeit, Rechenaufwand, usw.) führt. Umgebungen dieser Art haben meist die Gestalt einer Variante des aus der Spieltheorie bekannten Prisoner's Dilemmas. Die Nichtkooperation dort kann nicht zu schlechterem Nutzen führen, während die Kooperation Risiken birgt. Global gesehen ist allerdings die Kooperation die bessere Alternative für den Gesamtnutzen.
In dieser Arbeit soll die Kooperation in solchen Umgebungen anhand eines Aufgabenverteilungsproblems betrachtet werden. Agenten haben nur bestimmte Fähigkeiten, die nur ausreichen und Teilaufgaben zu lösen. Größere Aufgaben können sie nur in einem Team leisten, was allerdings für einige Teammitglieder zu Kosten führt. In diesem Szenario sollen Möglichkeiten untersucht werden, wie globale Kooperation entstehen kann.

Kontakt: Markus Eberling

Meme und Kooperation in Multiagentensystemen (Diplomarbeit)

Thema
Neben der genetischen Evolution, die relativ langsam voranschreitet, gibt es auch den Begriff der kulturellen Evolution. Der Begriff "Mem" wurde erstmals von Dawkings 1976 eingeführt als Analogon zu einem Gen. Ein Mem ist ein Gedanke, der sich von Individuum zu Individuum fortpflanzt und sich auch verändert kann.
Ziel dieser Arbeit ist die Entwicklung eines Ansatzes, wie durch diesen Mechanismus Kooperation in einem Multiagentensystem entstehen kann. Dabei ähneln sich Agenten, wenn ihre Meme ähnlich sind. In diesem Bereich gibt es eine Reihe an Veröffentlichungen, die es zu lesen und zu klassifizieren gilt. Anschließend soll das erworbene Wissen zu einem Ansatz führen, der in einer zu entwickelnden Umgebung eine hohe Kooperationsrate entstehen lässt.

Kontakt: Markus Eberling

Dezentrale Aufgabenverteilung in Multiagentensystemen (Bachelorarbeit)

Thema
In serverlosen Peer-to-Peer Netzwerken werden Anfragen direkt an Knoten des Netzwerkes gestellt. Diese Anfragen können vermehrt an bestimmte Knoten gestellt werden, was zu einer unausgewogenen Abarbeitung dieser Anfragen führen kann.
Ziel dieser Arbeit ist die Entwicklung einer dezentralen Anfragenverteilung zwischen Netzwerkknoten, die als Multiagentensystem betrachtet werden sollen. Innerhalb des Netzwerkes soll die Aufgabenabarbeitung ausgewogen erledigt werden. Durch diesen Mechanismus soll Kooperation in dem Netzwerk entstehen. Dabei ist ein wichtiger Punkt die Betrachtung unterschiedlicher Anfrageszenarios. Für diese sollen optimale Verteilungen gefunden werden, wenn eine zentrale Instanz vorhanden wäre. Anschließend sollen die Ergebnisse des dezentralen Ansatzes mit dem zentralen Ansatz verglichen werden.

Kontakt: Markus Eberling

Experimenteller Vergleich von Penalty-Funktionen für Evolutionsstrategien (Bachelorarbeit)

Thema
Unter einem numerischen restringierten Optimierungsproblem versteht man das Problem, eine Funktion zu maximieren oder zu minimieren unter der Bedingung eines eingeschränkten Suchraums. Die Beschränkung des Suchraums kann z.B. durch eine Reihe von Gleichungen oder Ungleichungen gegeben sein. Die gängigsten Restriktionsbehandlungsmethoden für evolutionäre Algorithmen sind die so genannten Penalty-Funktionen oder auch Straffunktionen genannt. Dabei wird die Fitness eines Individuums, das sich im ungültigen Bereich des Suchraums befindet, durch einen Strafterm reduziert.

Ziel dieser Arbeit ist die Implementierung und der experimentelle Vergleich verschiedener Penalty-Funktionen. Folgende Formen von Penalty-Funktionen sollen hierbei berücksichtigt werden:

• Statische Penalty-Funktionen
• Dynamische Penalty-Funktionen
• Annealing Penalty-Funktionen
• Adaptive Penalty-Funktionen
• Death Penalty

Neben der Einarbeitung in evolutionäre Algorithmen erfordert die Studienarbeit Interesse an der Fragestellung der experimentellen Erforschung der Restriktionsbehandlungsmethoden. Die Implementierung der Algorithmen kann wahlweise in Java oder C++ erfolgen.

Kontakt: Oliver Kramer

Evolutionäre Algorithmen und Geschlechter (Bachelorarbeit)

Thema
Im Laufe der Evolution hat sich in der Natur das Konzept von Geschlechtern als überaus erfolgreich erwiesen und durchgesetzt.  Die unterschiedlichen Geschlechter selektieren ihre Sexualpartner nach verschiedenen Kriterien. Das Geschlechterkonzept in evolutionäre Algorithmen integriert und hat sich bei der Behandlung restringierter Problemräume als erfolgreich erwiesen. In der Praxis ist der Suchraum vieler numerischer Probleme stark eingeschränkt, z.B. durch Materialeigenschaften oder ingenieurwissenschaftliche Randbedingungen. Um mit derartigen Suchräumen umgehen zu können,  müssen Optimierheuristiken um Modifikationen erweiterter werden, die die Behandlung restringierter Probleme ermöglichen. Für Evolutionsstrategien wurde die Methode TSES (two sexes evolution strategy) vorgeschlagen, die darauf basiert, jedem Individuum ein Merkmal zuzuordnen, das über sein Selektionsziel entscheidet. Entweder wird das Individuum nach der unrestringierten Zielfunktion oder nach Erfüllung der Restriktionen hin optimiert. Der Kern des Verfahrens liegt darin, dass mit Hilfe der Rekombination, die nur zwischen Individuen unterschiedlichen Geschlechts durchgeführt werden darf, Lösungen nahe des Optimums des Gesamtproblems entstehen.

Ziel der Arbeit ist die experimentelle Erforschung der TSES (two sexes evolution strategy). Offenbar ist deren Erfolg stark abhängig von der Wahl geeigneter Parameter. Die TSES soll mit verschiedenen Modifikationen und Parametrisierungen auf einer breiten Auswahl von Testfunktionen experimentell untersucht werden. Die Arbeit setzt Interesse im Bereich evolutionäre Algorithmen und Kenntnisse in Java zur Implementierung des Verfahrens voraus.

Kontakt: Oliver Kramer

Überblick über schwarmbasierte Algorithmen und Implementierung eines beispielhaften Swarm Based Routing Ansatzes (Bachelorarbeit)

Thema
Das von natürlichen Phänomenen inspirierte Schwarmverhalten von Ameisen- oder Bienenkolonien ist seit mehreren Jahren Grundlage für erfolgreich eingesetzte Algorithmen aus dem Bereich Swarm Intelligence. Die durch Pheromone gesteuerte Futtersuche bei Ameisen wird zur Netzwerk Optimierung eingesetzt und der Nestbau unterschiedlicher Wespen- oder Termitenarten wird in Hinblick auf Einsatzmöglichkeiten zur Strukturbildung untersucht.

Ziel dieser Arbeit ist es, einen Überblick über existierende Einsatzfelder von natürlichen Schwarm-Algorithmen zu geben und die Lösungen qualitativ mit anderen Heuristiken zu vergleichen. Ein besonderes Augenmerk soll auf Routing-Lösungen geworfen werden. Diese sollen beispielhaft zur Steuerung eines Verkehrsfluss-Optimierungssystems implementiert werden.

Der Schwerpunkt der Arbeit richtet sich danach, ob es sich um eine Studien- oder Diplomarbeit handelt und wo die Interessen der Studentin/des Studenten liegen.

Kontakt: Andreas Goebels

Evolutionär gesteuertes Lernen von Regelmengen für zelluläre Automaten (Bachelorarbeit)

Thema
Zelluläre Automaten (CA) sind seit Beginn der Informatik ein interessantes und vieluntersuchtes Vorschungsgebiet, das bereits 1970 durch Conway’s Game of Life einer breiten Öffentlichkeit nahegebracht wurde. Mit Hilfe von sehr einfachen Regeln wird hier versucht, emergentes Verhalten zu produzieren. Vor einigen Jahren wurden von Melanie Mitchell Versuche unternommen, die Regelmengen für einfache, eindimensionale zelluläre Automaten durch genetische Algorithmen zu erzeugen. Das Ziel war, eine Klassifizierung einer zufälligen Anfangsbelegung eines CA zu erreichen.

Ziel dieser Arbeit ist es, die Forschungsergebnisse von Mitchell nachzuvollziehen und eine einsetzbare und gut Dokumentierte Implementierung eines CA zur Verfügung zu stellen, die für verschiedenste Aufgabenstellungen genutzt werden kann. Die Regelgenerierung soll wie bei Mitchell durch einen genetischen Algorithmus erfolgen, dessen Parameter optimiert werden müssen.

Zu untersuchen ist auch die Erweiterung vom 1D auf den 2D Fall für kleine Probleminstanzen. Die Implementierung sollte möglichst in Java durchgeführt werden, um auch den Einsatz der Software auf Webseiten mit Hilfe von Applets zu ermöglichen.

Kontakt: Andreas Goebels

Überblick über den Einsatz und die Entstehung von Hierarchien in speziellen Algorithmen und Umgebungen (Bachelorarbeit)

Thema
Hierarchien sind in den unterschiedlichsten Bereich unseres Alltags bzw. unseres Umfeldes vertreten, innerhalb der Gesellschaft, in Unternehmen, aber auch im Tierreich bei in Gruppen zusammenleben Tierkolonien, z.B. diverse Affenarten. Dieses häufige Auftreten legt nahe, dass eine Hierarchisierung gleicher oder ähnlicher Individuen sinnvoll bzw. notwendig ist, abhängig von der zu bewältigenden Problemstellung.

In unserem Umfeld soll untersucht werde, inwieweit sich Hierarchien emergent bilden können und ob dieses abhängig von Problemstellungen unterschiedlich ausfallen.

Ziel dieser Arbeit ist es, einen Überblick über existierende Hierarchie-Ansätze in der Informatik bzw. Wirtschaftsinformatik zu geben. Betrachtet werden sollen in diesem Zusammenhang Multi Agenten Systeme, in denen ein einzelner Agent koordinierende Fähigkeiten besitzt, natürliche Schwärme (Ameisen- / Wespenkolonien), in denen einzelne Individuen andere steuern bzw. beeinflussen können (Bienenkönigin), aber auch Unternehmensstrukturen, die hierarchisch aufgebaut sind.

Es soll untersucht werden, welche Arten von Hierarchien häufig auftreten und ob es "typische" Probleme gibt, die gut/schlecht mit Hierarchien gelöst werden können.

Kontakt: Andreas Goebels

Überblick über Routen-Planungs-Systeme und eingesetze Algorithmen zur Navigation in unbekannten Verkehrsnetzen (Bachelorarbeit)

Thema
In einer Vielzahl der aktuellen Automodelle gehört ein Routenplanungssystem zur Standardausstattung, auch im Internet erfreuen sich solche Routenplaner immer größerer Beliebtheit. Die Qualität eines solchen Systems lässt sich u.a. an den folgenden drei Punkten beurteilen:

1. Qualität der gefundenen Route
2. Quantität des Datenbestandes
3. Benutzerfreundlichkeit / Integration ins Fahrzeug

Aktuelle Routenplaner arbeiten in den meisten Fällen mit globalen Informationen und einer statischen Datenbasis, lediglich einzelne Staumeldungen des Verkehrsfunks werden ggfs. berücksichtigt.

Ziel dieser Arbeit ist es, einen Überblick über existierende Routenplanungs-Systeme, speziell in Fahrzeugen, zu geben. Im Einzelnen sollen die eingesetzten Algorithmen zur Wegberechnung und das Datenformat, auf dem die Berechnungen durchgeführt werden, beschrieben und verglichen werden. Wenn eine Schnittstelle zur Datenbasis existiert, soll auch auf diese eingegangen werden.

Kontakt: Andreas Goebels

A Study of Evolutionary Algorithms for the Satisfiability Problem (SAT) (Bachelor-/Diplomarbeit)

(Beschreibung nur auf Englisch verfügbar)

Topic
The satisfiability problem (SAT) is a classic NP-complete problem and has been applied on several practical problems, such as consistency check and circuit design. The solutions to SAT can be divided into two categories: complete and incomplete methods. The complete methods include the approaches based on the Davis-Putnam (DP) algorithm. This sort of approaches can exactly determine the satisfiability of a given formula; however, it is computationally intensive with the increasing size of atoms. The incomplete methods include local search and evolutionary algorithms. These approaches can find the solution efficiently but not determinately.Evolutionary algorithms (EAs), including genetic algorithm (GA), genetic programming (GP), evolutionary strategies (ES),…etc.), are well-known heuristic algorithms based on the simulation of natural mechanisms and Darwin’s “Survival of the Fittest”. The effectiveness of EAs has been widely validated in search and optimization problems. Recently, some researchers proposed the evolutionary algorithms for SAT, but until now, their performance is not comparable with the state-of-the-art methods. In this study, we plan to investigate the existing evolutionary algorithms for SAT and analyze the influence of genetic operators upon their performance in SAT. Finally, we propose to develop a new algorithm based on a specific statistic heuristic.

Job Description

• Survey and study the existing evolutionary algorithms for SAT.
• Investigate the influence of genetic operators (chromosome representation, fitness function, crossover, mutation, and incorporation of local search) on SAT.
• Performance comparison and analysis.
• Develop a new evolutionary approach based on statistic heuristics.

Kontakt: Chuan-Kang Ting