Evolutionäre Algorithmen:
Chancen für die praxisorientierte Optimierung
Prof. Dr. J. Willms

Angewandte Informatik und Mathematik
Fachhochschule Südwestfalen
Meschede

Erfahrungen in der industriellen Praxis

Es ist stets schwierig im Vorfeld abzuschätzen, wie gut ein Evolutionärer Algorithmus tatsächlich einen gegebenen Anwendungsfall lösen kann. Dies ist natürlich insofern problematisch, da mit der Entwicklung eines Evolutionären Algorithmus stets Kosten verbunden sind. Auch kann nicht in allen theoretisch möglichen Fällen gewährleistet werden, dass ein Evolutionärer Algorithmus immer eine Lösung in vernünftiger Zeit findet, die sich nicht zu sehr von einer optimalen Lösung unterscheidet.

Auf der anderen Seite kann (und sollte) ein Evolutionärer Algorithmus bei Optimierungsproblemen eingesetzt werden, wo es keine bekannten deterministischen Optimierungsalgorithmen gibt oder wo bekannte deterministische Optimierungsalgorithmen in einem vernünftigen Rechnerleistungs- und Zeitrahmen keine Lösung finden. Hinzu kommt, dass bei vielen industriellen Anwendungsproblemen oft nachträglich zusätzliche Nebenbedingungen ins Spiel kommen, die bekannte deterministische Optimierungsalgorithmen dann doch nicht handhaben können. Evolutionäre Algorithmen sind in dieser Hinsicht viel robuster. Die Form der Bewertungsfunktion spielt erst einmal keine entscheidende Rolle: unerheblich ist, ob sie linear, quadratisch oder von sonstiger Form ist. Zusätzliche oder modifizierte Nebenbedingungen können oft schnell und unproblematisch in die Bewertungsfunktion oder die Mutations- und Selektionsmechanismen eingebaut werden. Diese Flexibilität ist in der Praxis sehr wichtig. Im Gegensatz zu vielen konventionellen, deterministischen Verfahren erschüttern bei Evolutionären Algorithmen leicht geänderte Rahmenbedingungen in der Regel den gewählten Ansatz nicht.

Das von uns behandelte konkrete Hammer-Optimierungsproblem erwies sich als besonders geeignet für Evolutionäre Algorithmen. Es zeigte sich, dass auf einem gewöhnlichen PC oft bereits nach wenigen Sekunden eine pseudo-optimale Lösung gefunden wurde. Diese konnte dann zwar noch leicht verbessert werden, aber spätestens nach einigen Minuten Laufzeit ergaben sich nur noch ganz selten weitere Verbesserungen. Bei einer zufälligen Verteilung der Hämmer (mit realistischen Gewichten) ergaben sich im Leerlauf typischerweise Unwuchtkräfte im Bereich von mehreren tausend Newton (bei wenigen, ungünstigen Anordnungen sogar von mehreren zehntausend Newton). Innerhalb weniger Sekunden konnten Lösungen mit Unwuchtkräften von weniger als 20 Newton gefunden werden. Fast immer konnten diese Lösungen innerhalb weniger Minuten noch einmal um mehr als 50% verbessert werden. Für den praktischen Einsatz der Hammerbrecher macht eine noch weitere Optimierung keinen Sinn, da sogar Unwuchtkräfte in der Größenordnung von 100 Newton noch als akzeptabel angesehen werden können.

Wir haben auch untersucht, wie der Algorithmus sich verhält, wenn man den vorgesehen Bereich der Eingabewerte erweitert. Lässt man z.B. größere Differenzen der Hammergewichte zu (z.B. Differenzen im Bereich von 100 bis 200 kg), so bekommt man natürlich in der Regel größere Unwuchtkräfte. Unwuchtkräfte zufälliger Anordnungen scheinen sich oft im Bereich von mehreren zehntausend Newton zu bewegen, Unwuchtkräfte von über 500 kN sind durchaus möglich. Bei einem typischen Optimierungslauf erhielten wir zum Beispiel Lagerkräfte von 51 Newton nach 4 Sekunden, 33 Newton nach 12 Sekunden und 17 Newton nach 600 Sekunden. Andere, ähnliche Hammergewichte dieser Größenordnung lieferten vergleichbare Resultate.

Die Rückmeldungen der Anwender auf das entwickelte Programm sind uneingeschränkt positiv. Die aus anderen Windowsprogrammen vertraute grafische Benutzeroberfläche und die unkomplizierte und intuitive Benutzerführung ermöglichen sehr kurze Einarbeitungszeiten. Da der eigentliche Mechanismus des Evolutionären Algorithmus den Anwendern verborgen bleibt, ergaben sich aus Anwendersicht keinerlei Akzeptanzprobleme. Auch wurden stets pseudo-optimale Lösungen mit sehr kleinen Unwuchtkräften gefunden, die mit einer "manuellen" Optimierung auch nicht annähernd erreicht worden wären. Durch die Nutzung des Programms zur Ermittlung der optimalen Hammeranordnung können die Unwuchtkräfte in den Wälzlagern der Rotorwelle im Leerlauf von Hammerbrechern zuverlässig minimiert werden. Verschleißen alle Hämmer nahezu gleichmäßig und sind über dem gesamten Rotor im statistischen Mittel ähnlich ausgeprägte Hammerbewegungen bei der Aufgabegutzerkleinerung zu beobachten, so lassen sich auf diese Weise auch die Unwuchtkräfte für den Betriebszustand von Hammerbrechern deutlich reduzieren.

Die in dem Programm entwickelten Ideen haben sich seit nunmehr zwei Jahren in der Praxis bewährt. Dies zeigt sich auch darin, dass das Programm auf weitere Typen von Hammerbrechern mehrfach erweitert worden ist. Weiterhin wird überlegt, ob andere Brecherbauarten (wie zum Beispiel Hammermühlen, Prallbrecher und Prallmühlen) in das Programm integriert werden sollen.

Der hier vorgestellte Lösungsansatz hat den Vorteil, dass er sich grundsätzlich auf viele, ganz unterschiedliche Problembereiche übertragen lässt. Reihenfolge-Optimierungen wie sie bei der Auftragsbearbeitung, Produktionsplanung oder bei Maschinenbelegungsplänen vorkommen sind verwandte Problemstellungen. Andere Anwendungsbereiche finden sich bei Lager- und Transportproblemen oder bei Schneide- und Partitionierungsproblemen, aber auch bei der Kalibrierung oder Parameterschätzung in komplexen Simulationsmodellen. Auch bei der Design-Optimierung und Modellierung industrieller Prozesse sind Evolutionäre Algorithmen eingesetzt worden. Detaillierte Beschreibungen vieler Anwendungsfälle von Evolutionären Algorithmen findet man z.B. in den Büchern [11], [12] und [13].


weiter

nach oben

Impressum     Datenschutz
nach oben

29.7.2003