Mit Algorithmen den kürzesten Weg

DHBW-Studenten entwickeln Software zur effizienten Lösung von Optimierungsproblemen

ChinesischeMauer

(Foto: privat)

Mosbach (pm) Welchen Weg muss ein Reisender einschlagen, um viele Stationen zu besuchen und trotzdem möglichst schnell und preiswert ans Ziel zu kommen? Zwei Informatik-Studenten der Dualen Hochschule Baden-Württemberg Mosbach haben mit ihrer Studienarbeit einen Beitrag dazu geleistet, wie solche Optimierungsprobleme gelöst werden können. Ihr pragmatischer Ansatz bescherte ihnen eine Einladung als Referenten auf einer internationalen Konferenz in Peking, die vom Institute of Electrical and Electronics Engineers (IEEE) ausgerichtet wurde. „Das ist angesichts des Review-Prozesses gar nicht hoch genug einzuschätzen: Alle Einreichungen werden von Wissenschaftlern geprüft. Dabei wird nur ein kleiner Teil der Einreichungen als gut genug eingeschätzt, um als Konferenzbeitrag im Programm aufzutauchen“, so Studiengangsleiter Prof. Dr.-Ing. Wolfgang Funk.

Andre Hofmeister und Markus Breckner studieren Angewandte Informatik an der Dualen Hochschule Baden-Württemberg (DHBW) Mosbach. Eine Optimierungsaufgabe aus dem Studium haben sie in einer Studienarbeit detailliert untersucht: Die Ziele auf einer Reiseroute sollen so angesteuert werden, dass die insgesamt zurückgelegte Strecke möglichst kurz ist. Diese Fragestellung ist als „Problem des Handlungsreisenden“ bekannt. Bereits vor mehr als 100 Jahren wurde es erstmals beschrieben und wissenschaftlich untersucht. Die grundlegende Herausforderung besteht darin, in angemessener Zeit aus unzähligen Möglichkeiten eine möglichst passende zu wählen. In der Praxis spielt diese Fragestellung eine große Rolle, betrifft sie doch nicht nur Wegstrecken für Kundenbesuche, sondern auch die Logistik, das Design von Schaltkreisen oder die Belegung von Maschinen.

Eine praktische Lösung für ein nicht nur theoretisches Problem

Je mehr Parameter wie Kosten, Zeit oder Ressourcenaufwand einberechnet werden, desto schlechter lassen sich solche Fragestellungen mathematisch exakt berechnen. „Für unsere Studienarbeit haben wir eine Situation mit 25 Städten konstruiert. Für die mathematisch eindeutige Lösung hätte der Computer 300 Trilliarden Möglichkeiten berechnen müssen – eine Trilliarde hat 21 Nullen – und dafür mehrere 100.000 Jahre gebraucht“, erklärt Andre Hofmeister. Stattdessen gehe man heuristisch heran, suche also nicht ewig nach der einen optimalen Lösung, sondern versuche, in kürzerer Zeit eine Lösung zu finden, die möglichst nahe an das Optimum herankommt. Hofmeister und Breckner entwickelten eine Software, die verschiedene Algorithmen für solche Optimierungsprobleme vergleicht, also Lösungswege mit vielen wohldefinierten Einzelschritten.

Aus einer Reihe möglicher Parameter und komplexer Algorithmen empfiehlt das Programm die zur Problemlösung passendsten. Die beiden DHBW-Studenten entwickelten ein Grundgerüst, das jeder Nutzer für sich anpassen kann, indem er die Software mit beliebigen Problemen füttert und Algorithmen in der Datenbank erweitert oder hinzufügt. „Die beiden haben damit eine softwaretechnische Lösung für die intelligente Berechnung komplexer Algorithmen entwickelt“, erklärt Studiengangsleiter Funk. „Damit haben sie in idealer Weise die theoretischen Überlegungen aus den Vorlesungen zu Optimierungsalgorithmen in die Praxis transferiert.“

Zukünftige Spielwiese für Optimierungsprobleme

So sah das auch das Programmkomitee der „2014 5th IEEE International Conference on Software Engineering and Service Science“. Diese internationale Konferenz richtet sich speziell an Softwareentwickler und behandelt Themengebiete wie Informationssicherheit, Künstliche Intelligenz, Automatisierung und Big Data. Sie wird vom weltweiten Berufsverband „Institute of Electrical and Electronics Engineers“ (IEEE) ausgerichtet. Die dort organisierten Ingenieure und Wissenschaftler aus den Bereichen Elektrotechnik und Informationstechnik bzw. Informatik beschäftigen sich unter anderem mit der Standardisierung von Hardware und Software und der Organisation des wissenschaftlichen Austauschs.

Und das Feedback der Konferenzteilnehmer? „Das war gut – eine spannende Diskussion, aufschlussreiche neue Ideen und viele interessierte Fragen an uns!“, sagen Hofmeister und Breckner, die sich insbesondere über die Unterstützung ihres Dozenten und Betreuers Dr. Carsten Müller bei der Veröffentlichung gefreut haben. Die Software soll bald auf einem Server zukünftigen Studierenden oder Schülern als Spielwiese für Optimierungsprobleme und zur Bewertung komplexer Algorithmen dienen. Damit wird sie zu einem Baustein für den Theorie-Praxis-Transfer, der ein zentrales Element des dualen Studiums an der DHBW Mosbach ist.

Unsere News jetzt auch einmal täglich per Mail

© www.NOKZEIT.de


Artikel empfehlen: