Präsentationsfolien

Folie 1:

Derzeit sind von der Telekom Control G.m.b.H. (TKC) mehr als 30 Lizenzen für festnetzgebundene Sprachtelelfonie erteilt. Da erfahrungsgemäß kein Anbieter für jedes Gespräch die geringsten Kosten hat, erreicht man eine optimale Einsparung nur mit einem Mix von mehreren Providern bzw. Tarifmodellen.

Dieses Projekt beschäftigt sich also mit dem Problem, aus der Vielfalt der Telekom-Anbieter, einen, für das Gesprächsverhalten des Kunden, adäquaten Mix von Anbietern zu finden. Ausgehend vom Telefonieverhalten des Kunden und der Kenntnis der Tarifmodelle der unterschiedlichen Telekom-Anbieter (Provider) wird ein Mix von Tarifmodellen errechnet, welcher die Gesamtkosten der Telefongspräche (über einen begrenzten Zeitraum) minimiert. Die Optimierung kann jedoch nur für bereits geführte Gespräche durchgeführt werden. Unter der Annahme, daß das Gesprächsverhalten eine gewisse Homogenität aufweist, ist eine Extrapolation des Vergangenen, auf das zukünftige Telefonieverhalten durchaus zulässig.

Folie 2:

Eine Möglichkeit den besten Tarifmodell-Mix zu ermitteln, ist die "Brute Force" - Methode. Hierbei werden alle möglichen Zuordnungen der Tarifmodelle zu den Gesprächen ermittelt, und die Gesamtkosten bestimmt. Durch die geringsten Gesamtkosten ergibt sich nun der optimale Tarifmodellmix. Für diesen Algorithmus ergibt sich eine Komplexität von k^n.

Folie 3:

Dieser Algorithmus läßt sich natürlich noch verbessern. Die Idee dabei ist, für alle 1 bis k elementigen Teilmengen der Gesamtmenge der Tarifmodelle die Gesamtkosten , d.h. die Grundkosten und die Gesprächskosten , zu berechnen, wobei eine bestehende Teilmenge optimal auf die Gespräche angewendet wird; jedes Gespräch wird mit dem billigsten, der in der Teilmenge zur Verfügung stehenden, Tarifmodell geführt. Auch hier ergeben die geringsten Gesamtkosten den optimalen Tarifmodellmix. Die Komplexität ist hier jedoch m* sum(i = 1, k, (k über i)* i).

Folie 4:

Als Rechtfertigung für den Einsatz eines GAs, wurden die notwendigen Rechenzeiten für die Brute Force Methode ermittelt. Das Diagramm zeigt die benötigte Rechenzeit in Abhängigkeit von a (maximale Anzahl der Tarifmodelle aus denen der Mix bestehen soll) und k (Anzahl der Tarifmodelle). Die Achse für die Rechenzeit wurde logarithmisch! gewählt. Für die konkreten Werte m = 19442, a = p = 9, ergab sich eine Gesamtrechenzeit tg = 28s (Pentium II, 350MHz, 128MB RAM). Somit ergibt sich für t ~ 6,25*10E-7s. Die Tabelle zeigt einige hochgerechnete Optimierungszeiten. Bei diesen Beispielen wurde a = p gesetzt.Bei 30 Tarifmodellen beträgt die geschätzte Rechenzeit 3,2 Jahre. Daraus leitet sich eindeutig eine Rechtfertigung für den Einsatz eines Genetischen Algorithmuses ab.

Folie 5:

Für den Genetischen Algorithmus wurden zwei verschiedene Kodierungen vorgeschlagen:

Folie 6:

Der GA wurde mit den banda[3] Java-Klassen realisiert. Die Testläufe wurden unter folgenden Nebenbedingungen durchgeführt:

Um zufällige Ergebnisse möglichts zu Unterdrücken, wurden jeweils 10 Messungen mit gleichen Parametern durchgeführt. Danach wurde das Mittel aus diesen 10 Messungen gebildet. Die Abbildungen zeigen, in Abhängikeit der Parameter Generation, Population, Mutationsw. und Crossoverw., die maximale gemittelte Fitness Aus diesen Abbildungen läßt sich zunächst erkennen, daß eine Vergrößerung der Population keinen wesentlichen Einfluß auf die Verbesserung der Ergebnisse hat. Eine Erhöhung der Generation verspricht hier die bessere Strategie zu sein. Dies muß jedoch noch in einer zweiten Meßreihe nachgeprüft werden (mit einer geringeren Zahl von Gesprächen, um den Rechenaufwand möglichst gering zu halten). Insgesammt wurden bei dieser ersten Meßreihe rund 20MB Daten aufgezeichnet - dies entspricht 13.756 Messungen. Der beste Tarifmodellmix wurde zuvor mitttels erschöpfender Suche bestimmt. Für den verwendeten Gesprächssampel wurde bei dieser Suche ein Mix aus 2 Tarifmodellen ermittelt (Tarifmodell 4 und 8). Die Tabelle zeigt, inwieweit diese beiden Tarifmodelle den Ergebnissen des GA entsprechen.

Bei der erschöpfenden Suche (Brute Force) wurde Tarifmodell 4 und 8 als bester Mix ermittelt. Die Tabelle zeigt nun, inwieweit die Ergebnisse des GA diese beiden Tarifmodelle enthalten (hierbei muß jedoch berücksichtigt werden, daß die Parameter des GA noch keineswegs abgestimmt waren, dennoch ist es bemerkenswert, daß bereits in rund 82% der Ergebnisse, daß beste Tarifmodell zumindest Element der Ergebnismenge war).

Der erste Versuchsdurchlauf zeigte, daß durch die Erhöhung der Population die Ergebnisse nicht - dem vergrößerten Aufwand entsprechend - verbessert werden können. Beim zweiten Testlauf wurde dieser Tatsache Rechnung getragen.

 

Verwendete Parameter:

Zu Kodierung b:

Vor der ausführlichen Messung wurden Probeaufzeichnungen durchgeführt und die Ergebnisse auf Plausibilität überprüft. Dabei wurde festgestellt, daß nicht die gewünschten Ergebnisse geliefert werden. Das gewünschte Ergebnis besteht darin, daß der Algorithmus nach einer bestimmten Anzahl von Generation "erkennt", daß die Gespräche mit einer Teilmenge der Tarifmodellen billiger geführt werden können. Bei den ersten Versuch wurde festgestellt, daß der Algorithmus immer alle Modelle verwendet und nur die Zuordnung zu den Gesprächen "optimiert".

Fehleranalyse

Da der GA die Zahl der verwendeten Tarifmodelle verringern soll, betrachten wir - in erster Näherung - die Wahlscheinlichkeit, daß in der Anfangspopulation, bei mindestens einem Inidviduum, k Tarifmodelle nicht vorkommen.

P (Ai = k) = ((p - k)^m)/p^m

P(Ai = 1) = 14^442/15^442 = 5,705*10E-14

D.h., selbst bei einer geringen Zahl von Gesprächen, ist es sehr unwahrscheinlich, daß in der Anfangspopulation ein Individuum ein Tarifmodell nicht enthält. Bei 10.000 Gesprächen ist P(Ai = 1) = 2,3322 *10E-300