Genetische Algorithmen für kombinatorische Optimierungsprobleme
| Talking persons: |
| Dipl.-Inf. Jens Arnold |
| Abstract: |
| Viele in der Praxis auftretende und theoretisch interessante Probleme können nach heutigem Kenntnisstand in polynomieller Zeit nicht exakt gelöst werden, da der Rechenzeitaufwand typischerweise exponentiell mit der Problemgröße wächst. Genetische Algorithmen (GA) stellen heuristische Problemlösungsmethoden dar, mit denen sich komplexe kombinatorische Optimierungsprobleme - wie zum Beispiel das Traveling Salesman Problem (TSP) - in vertretbarer Rechenzeit approximativ lösen lassen. Im Vortrag werden verschiedene GA-Codierungsansätze für kombinatorische Optimierungsprobleme vorgestellt und es wird gezeigt, dass die genetischen Standardoperatoren nicht auf Codierungen mittels Permutationsvektoren anwendbar sind. Basierend auf den Arbeiten von Larranaga, Kuijpers, Murga, Inza und Dizdarevic werden spezielle genetische Sequenzoperatoren für Mutationen und Rekombinationen vorgestellt und hinsichtlich ihrer Performance bei der Lösung des TSP vergleichend bewertet. Als Ergebnis wird eine Auswahl der besten Operatoren für die Optimierung von Anordnungsreihenfolgen von Fertigungsplätzen in Fabriklayouts vorgeschlagen und diskutiert. |
| Times: |
| Wednesday 5th June 2002, 11.00 am, room 1/367A |
