next up previous contents
Next: Kodierung a Up: Implementierung Previous: Implementierung

Brute Force

Da neben dem GA der beste Mix auch durch eine erschöpfende Suche ermittelt werden kann, läßt sich die Qualität der Ergebnisse des GA's besonders gut bestimmen. Dies gilt jedoch nur bis zu einer begrenzten Anzahl, von zu berücksichtigenden, Tarifmodellen. Nachdem die Brute-Force-Methode implementiert war, wurden erste Performaceuntersuchungen vorgenommen. Getestet wurde das System mit 9 Tarifmodellen und 19442 (zufällig erzeugten) Gesprächen. Dabei läßt sich der nötige Rechenaufwand folgendermaßen charakterisieren:

t
... mittlerer Zeitaufwand für die Berechnug der Kosten eines Telefongesprächs (mit einem bestimmten Tarifmodell)
tg
... Gesamtaufwand für die Optimierung
m
... Anzahl der Gespräch über die optimiert wird
p
... Anzahl der verwendeten Tarifmodelle
a
... maximale Anzahl der Tarifmodelle aus denen der Mix bestehen soll

\begin{displaymath}t_{g}=m\cdot t\cdot \sum _{i=1}^{a}\left( \begin{array}{c}
p\\
i
\end{array}\right) \cdot i\end{displaymath}

Für dir konkreten Werte m = 19442, a = p = 9, ergab sich eine Gesamtrechenzeit tg=28s (auf einem Pentium II, 350MHz, 128MB RAM). Somit ergibt sich für \( t\simeq 6.25\cdot 10^{-7}s \).


 
Table: Diese Tabelle enthält die (hochgerechnete) Optimierungszeit (Pentium II, 350MHz, 128MB RAM) für eine ausgesuchte Anzahl von Tarifmodellen, dabei ist die Anzahl der verwendeten Tarifmodelle gleich der maximalen Anzahl der Tarifmodelle aus denen der Mix besehen soll. Es wird hier über 10.000 Gespräche optimiert.
Tarifmodelle 5 10 14 16 20 22 24 26 28 30
Rechenzeit(h) 0,0001 0,008 0,19 0,91 18 80 349 1514 6524 27962


Tabelle [*] zeigt einige hochgerechnete Optimierungszeiten. Bei diesen Beispielen wurde a=p gesetzt. Abbildung [*] zeigt sehr schön den großen Anstieg des Rechenaufwandes bei Erhöhung der Anzahl der Tarifmodelle. Bei 30 Tarifmodellen beträgt die geschätzte Rechenzeit, auf der oben angegebenen Maschine, in etwa 3,2 Jahre.


  
Figure: Diagramm über das Verhalten der Rechenzeit in Abhängigkeit von a (maximale Anzahl der Tarifmodelle aus denen der Mix besteht) und p (Anzahl der verwendeten Tarifmodelle), mit logarithmischen z-Achse (Rechenzeit).

\resizebox*{0.7\columnwidth}{!}{\includegraphics{images/performance.eps}}



next up previous contents
Next: Kodierung a Up: Implementierung Previous: Implementierung
root
1999-11-02