Der Approximationsalgorithmus

Für verschiedene Probleme lassen sich nur durch Annäherung bzw. Approximation optimale Lösungen finden. Durch einen geeigneten Approximationsalgorithmus versuchen Informatiker, sich dem optimalen Ergebnis anzunähern, so etwa in der Graphentheorie, die Beziehungen in Netzwerken darstellt.

Anbieter zum Thema

MicroConsult Microelectronics Consulting & Training GmbH

Parasoft® Deutschland GmbH

RTI Real-Time Innovations

In der Informatik und der Betriebswirtschaftslehre sind Approximationsalgorithmen effiziente Berechnungsmethoden, um angenäherte Lösungen für NP-harteOptimierungsprobleme zu finden. Diese Lösungen müssen beweisbare Garantien hinsichtlich der Entfernung der gelieferten Lösung von der optimalen vorlegen.

„Im Banking werden Approximationsalgorithmen für das Kredit-Scoring genutzt“, sagt Benjamin Aunkofer, Chief Data Scientist bei Datanomiq. „Als Anwendungsfall ist Kredit-Scoring zwar alt, kann aber eine stetige Verbesserung mit Machine Learning vorweisen.“ Aunkofer zählt weitere Use Cases auf, so etwa im Versicherungswesen: „Da geht es um Schadensprognosen.“

Bildergalerie

Bildergalerie mit 5 Bildern

In der Industrie tauchen Approximationsalgorithmen in der prädiktiven Wartung alias Predictive Maintenance auf. „Hier geht es um die Beobachtung der Abnutzung und die anschließende Vorhersage der idealen Wartungsintervalle.“ Eine optimale Wartung kann über Menschenleben entscheiden.

Im Handel werden sehr große Summen umgesetzt, aber nur minimale Margen erzielt. Daher lohnt sich jeder Prozentpunkt hinterm Komma, um die Marge zu vergrößern. „Approximationsalgorithmen lassen sich hier zur Vorhersage der Nachfrage und der Retouren nutzen, also von der Produkt-Ebene über die Shop-Ebene bis hin zur Kunden-Ebene. Sie geben die Retouren-Wahrscheinlichkeit für jede einzelne Kundenbestellung an. Es lassen sich also Verlustrisiken ebenso berechnen wie die Kundenbevorzugung – etwa in einem Bonusprogramm – steuern.

Erstaunliche Theorien

In der theoretischen Informatik ergeben sich Approximationsalgorithmen aus der weithin akzeptierten Vermutung, dass P ungleich NP. Aufgrund dieser Vermutung lässt sich eine große Klasse von Optimierungsprobleme nicht in polynomieller Zeit lösen. Approximationsalgorithmen versuchen daher, sich optimalen Lösungen für solche Probleme in polynomieller Zeit zu nähern.

In der großen Mehrheit aller Fälle wird die o. a. Garantie durch Multiplikationsalgorithmen ausgedrückt: als Annäherungsrate oder -faktor. Das heißt, die die optimale Lösung liegt innerhalb eines (festgelegten) Multiplikationsfaktors der gelieferten Lösung. Auch die Addition lässt sich für diesen Zweck heranziehen.

Ein erwähnenswertes Beispiel für einen Approximationsalgorithmus, der beide Methoden mit Lösungen nutzt, ist der klassische Approximationsalgorithmus von Lenstra, Shmoys und Tardos namens „Scheduling on Unrelated Parallel Machines“. Dabei werden Maschinen, Aufgaben und Kosten miteinander korreliert. Man sieht: Es gibt handfeste Anwendungsgebiete für diese scheinbar so abstrakte Methode, wie die auch die oben genannten Anwendungsfälle illustrieren.

Weitere Optimierungsprobleme

In der theoretischen Informatik gibt es mehrere Optimierungsprobleme. So wird etwa nach einem Algorithmus gesucht, der hinsichtlich des Metric-Traveling-Salesman-Problems (TSP) den „1,5-Approximationsalgorithmus“ von Christofides übertrifft. Siehe dazu den ersten Teil über das TSP-Problem. Das TSP-Problem spielt überall in der Logistik eine bedeutende Rolle. Ein weiteres Beispiel ist der Algorithmus für „Maximalen Schnitt“. Dieser Algorithmus löst ein theoretisches Graphen-Problem mithilfe von hochdimensionaler Geometrie (siehe Anblaufbild).

Ein einfaches Beispiel für einen Approximationsalgorithmus ist die Lösung für das Minimum-Vertex-Cover-Problem, wobei Vertex ein Begriff aus der Graphentheorie sein kann, der einen Knoten bezeichnet. Dabei gibt es erstaunlicherweise einen konstant großen Faktor für den Approximationsalgorithmus, nämlich genau 2. Berücksichtigt man die Vermutung für einzigartige Spiele (Unique Games Conjecture), dann ist dieser Faktor sogar der bestmögliche. Die Graphentheorie wird auf alle Arten von vernetzten Beziehungen angewandt, so etwa in sozialen Netzwerken wie Facebook.

Güte von Approximationsalgorithmen

Um die Optimierung beurteilen und verwalten zu können, muss der Nutzer herausfinden, was sein Approximationsalgorithmus überhaupt taugt. Das herauszufinden, ist kein Hexenwerk. Man muss nur ein paar Faktoren und Variablen formulieren und in den Algorithmus einsetzen.

Es sei S ( I ) die zu einer Eingabe I gehörige Menge zulässiger Lösungen. Zu jeder möglichen Lösung y ∈ S ( I )\ in S(I) sei v ( y ) der Wert der Zielfunktion für y. Der Zielfunktionswert einer optimalen Lösung für Eingabe I sei v *. Ein Approximationsalgorithmus (oder Approximationsverfahren) gibt bei Eingabe I eine Lösung y ∈ S aus, sodass (v ( y ) relativ nah an v * liegt.

Ist die von einem Approximationsverfahren für die Eingabe berechnete Lösung, so ist die Güte des Approximationsverfahrens bei der Eingabe

• bei Maximierungsaufgaben als r l = v * v ( y ) frac {v^{*}}{v(y)}}} und bei

• Minimierungsaufgaben als r l = v ( y ) v * frac {v(y)}{v^{*}}}} definiert.

Es ist also immer r l ≥ 1. Gilt r l = 1, liefert der Algorithmus eine optimale Lösung für I .

Hat ein Approximationsverfahren für alle möglichen Eingaben I eine Güte von r l höchstens α, so spricht man von einer α-Approximation.

Klassen von Approximationsalgorithmen

Optimierungsprobleme werden in der Theoretischen Informatik in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

1. APX

Die Abkürzung APX steht für „approximable“ und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effizient approximierbar ist. Ein Problem liegt innerhalb der Klasse APX, wenn eine Zahl r und ein polynomieller Algorithmus, der bei jeder zulässigen Eingabe I eine Lösung mit einer Güte ≤ r liefert, existieren.

2. PTAS/PAS

PTAS oder PAS steht für „polynomial time approximation scheme“. Anders als bei der Klasse APX wird hier für jedes δ ∈ ( 0 , 1) gefordert, dass ein polynomieller Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte r ≤ 1 + δ liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte (s. o.) effizient sein.

3. FPTAS

FPTAS steht für „fully polynomial time approximation scheme“. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe I und jedem k ∈ N eine Lösung mit der Güte r ≤ 1 + 1 / k ausgibt und seine Laufzeit polynomiell in x und k ist.

Es gilt: P O ⊆ F P T A S ⊆ P T A S ⊆ A P X ⊆ N P O .

Unter der Annahme P ≠ N P sind die obigen Inklusionsabbildungen echte Inklusionen. Das heißt, es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse PTAS liegt, aber nicht in der Klasse FPTAS. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in APX liegt.

FPTAS-Beispiel: das Cliquenproblem

Das oben Gesagte lässt sich unter der Annahme P ⊊ N P zum Beispiel für das Cliquenproblem zeigen. Dieses Entscheidungsproblem der Graphentheorie liefert seit rund fünfzig Jahren zahlreiche interessante Lösungen.

Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine Clique einer bestimmten Mindestgröße enthält, wird „Cliquenproblem“ genannt und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig.

Es ist gefragt, ob es zu einem einfachen Graphen G und einer Zahl n eine Clique der Mindestgröße n in G gibt; das heißt, ob G zumindest n Knoten hat, die alle untereinander paarweise verbunden sind. Das Optimierungsproblem fragt nach der Cliquenzahl eines Graphen: Wie viele kann er enthalten?

Das zugehörige Suchproblem fragt nach einer größten Clique. Eine größte Clique lässt sich unter bestimmten Bedingungen in polynomieller Zeit berechnen, dauert also nicht ewig. Die Berechnung einer maximalen Clique gelingt bereits mit einem einfachen Greedy-Algorithmus. Dieser wird Gegenstand eines weiteren Grundlagenartikels sein.

„BI-Systeme sind noch weitgehend frei von Approximationsalgorithmen“, befindet Benjamin Aunkofer. „BI-Systeme bestehen heute noch im Wesentlichen aus Data Warehousing (= saubere Datenbereitstellung) und Dashboarding (= Nutzung dieser Daten via Standard Reporting). Zukünftig werden BI-Systeme aber vermehrt Predictive Analytics aufnehmen.“

So deckt der Local Outlier Factor Anomalien auf

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Der Rete-Algorithmus: Speed für Mustererkennung

Dieser Beitrag stammt von unserem Partnerportal Bigdata-Insider.de.

(ID:46112104)