Lösung sehr großer Instanzen des Handlungsreisendenproblems mit verteilten evolutionären Algorithmen in Peer-to-Peer-Netzen

• Applicant: Professor Dr.-Ing. Peter Merz
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 21542345

Das Potential von Peer-to-Peer-Systemen (P2P-Systemen) erstreckt sich nicht nur auf den Austausch von Dokumenten, sondern umfasst auch andere Einsatzgebiete, insbesondere das verteilte Rechnen. Die enorme kumulierte Rechenleistung von P2P-Systemen wird dabei verteilten Anwendungen zugeführt. Wegen der Dynamik dieser Systeme eignen sich hierfür vor allem Anwendungen, die den Ausfall eines mitrechnenden Teilnehmers tolerieren können. Hierzu zählen Implementierungen evolutionärer Algorithmen, die u.a. zur heuristischen Lösung NP-harter kombinatorischer Optimierungsprobleme geeignet sind. Das Problem des Handlungsreisenden (Traveling Salesman Problem, TSP) stellt das wohl am besten erforschte Problem dieser Art dar. Große TSP-Instanzen können bislang nicht adäquat gehandhabt werden. Dieses Forschungsprojekt befasst sich daher mit der Entwicklung einer verteilten evolutionären Heuristik zur Lösung großer TSP-Instanzen, welche auf eine ebenfalls zu entwickelnde Middleware aufsetzt, die auf jedem teilnehmenden Peer Verwendung findet.

• DFG Programme: Research Grants