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

Angewandte Informatik und Mathematik
Fachhochschule Südwestfalen
Meschede

Erste Idee: Bewertung aller Möglichkeiten

Ein erster Lösungsansatz war schnell gefunden. Wieso nicht mit einem Computerprogramm alle möglichen Hammeranordnungen bewerten und so die beste Möglichkeit herausfinden? Eingegeben werden müssten in dieses Programm neben Geometriedaten des Hammerbrechers nur die gemessenen, unterschiedlichen Massen der Hämmer. Eine kurze Überlegung zeigt sofort die Undurchführbarkeit dieses Ansatzes.

Geht man davon aus, dass optimistisch gerechnet ein schnelles PC-Programm ca. 10 Millionen Möglichkeiten (d.h. mögliche Hammeranordnungen) pro Sekunde bewerten kann, so lässt sich leicht die benötigte Rechenzeit abschätzen, wenn die Anzahl aller möglichen Hammeranordnungen bekannt ist.

Doch wie viel unterschiedliche Möglichkeiten, die Hämmer am Rotor anzuordnen, gibt es aber nun? Es ist leicht einzusehen, dass es bei n Hämmern genau n! Möglichkeiten gibt. (Hierbei bezeichnet n! die Fakultät von n, also das Produkt der ersten n natürlichen Zahlen 1, 2, 3, ... , n-1, n)


Anzahl n der Hämmer
Ungefähre Anzahl der Möglichkeiten
Ungefähre Dauer
10
4 * 106
0,4 s
11
40 * 106
4 s
12
480 * 106
48 s
13
6 * 109
10 min
14
87 * 109
2,4 h
15
1 * 1012
36 h
16
21 * 1012
24 Tage
17
360 * 1012
412 Tage
18
6 * 1015
20 Jahre
19
120 * 1015
385 Jahre
20
2 * 1018
7715 Jahre
Tabelle 1: Exponentielles Wachstum der Rechenzeit (bei 10 Millionen Bewertungen pro Sekunde)

Bei 4 Hämmern gibt es folglich 24 und bei 5 Hämmer gibt es bereits 120 Möglichkeiten. Tabelle 1 zeigt, wie schnell die Möglichkeiten bei der Montage mit der Anzahl n der Hämmer wachsen. Für die untersuchten Anwendungsfälle ist 40 eine realistische Größe für die Anzahl der Hämmer. Zusätzlich aufgelistet ist in Tabelle 1 die theoretisch benötigte Rechenzeit eines schnellen Computerprogramms, das pro Sekunde 10 Millionen Möglichkeiten (Hammeranordnungen) bewerten kann.

Tabelle 1 zeigt, dass ein solches Computerprogramm bei nur 20 Hämmern mehrere tausend Jahre braucht, um alle Möglichkeiten zu bewerten. Selbst mit schnelleren Rechnern und einer besseren Implementierung kommt man nicht zum Ziel. Eine grobe Überschlagsrechnung zeigt, dass bei 40 Hämmern sogar ein imaginärer Superrechner bestehend aus 10 Milliarden parallelen Prozessoren, wobei jeder Prozessor 10 Milliarden mal schneller als der schnellste PC-Prozessor wäre, mehr als 10 Milliarden Jahre bräuchte!

Die kombinatorische Mächtigkeit dieses scheinbar harmlosen Problems ist wie bei vielen anderen Problemen, deren Möglichkeiten exponentiell wachsen, enorm. Reine Brute-Force-Methoden, die alle möglichen Konfigurationen untersuchen, müssen daher zwangsläufig an der immensen Zahl der unterschiedlichen Möglichkeiten scheitern.


weiter

nach oben

Impressum
nach oben

29.7.2003