HOPE²D

In unserem Projekt HOPE²D befassen wir uns mit der Optimierung von Hardwarelayout für die Chipentwicklung. Bei der Implementierung logischer Funktionen auf Computerchips tragen unter anderem die Länge der Leitungen sowie mögliche Überkreuzungen der Kabel zu erhöhten Kosten bei. In diesem Zusammenhang beschäftigen wir uns darum mit der Minimierung von Kreuzungen, was ein NP schweres Problem darstellt. Deshalb ist das Ziel unseres Projekts die Entwicklung Algorithmen, welche die Kabelkreuzungen minimieren und trotzdem eine effiziente Laufzeit haben. Dafür nutzen wir funktionsevaluationsbasierte Techniken, wie Ant-Colony-Optimization oder Simulated Annealing, sowie Heuristiken, welche auf dem Dijkstra Algorithmus basieren. Diese haben wir anhand ihrer Laufzeit, Qualität der Lösungen und deren Fähigkeit komplexere Probleminstanzen zu lösen bewertet und verglichen.