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

• Antragsteller: Professor Dr.-Ing. Peter Merz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2006 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen