Vertex Cover Problem Archive - Blogofant

Allgemeine Übersicht In diesem Beitrag werden Heuristiken und Metaheuristiken sowie Grundlegendes Wissen über die Themen vermittelt. Heuristiken Heuristiken versuchen in möglichst kurzer Zeit eine Lösung zu finden. Dies kann, muss allerdings nicht die Optimallösung sein. Approximationsalgorithmen geben zudem auch die Güte an, also die maximale Abweichung zur Optimallösung. Bei der Heuristik findet also ein Trade-Off zwischen Zeit und Qualität statt. Aufgrund der Tatsache, dass Optimallösungen oftmals nicht in absehbarer Zeit gelöst werden können, bedarf es bei vielen Anwendungen Heuristiken. Teilweise performen diese auch recht gut. Tabu Search Memory: Liste der verbotenen SchritteNachbarschaft: Menge aller möglichen Schritte Metaheuristiken GRASP Verfahren & Greedy randomized algorithms „Greedy randomized adaptiv search procedures“, kurz GRASP, ist eine Metaheuristik aus einer Konstruktionsphase und einer lokalen Suche. Greedy Algorithmus (multi start und stufenweise Erstellung, stufenweise Konstruktion einer Lösung) liefert eine Startlösung. Dabei wird bei jeder Iteration ein neues Element aus der Grundgesamtheit ausgewählt. Die Auswahl erfolgt nach einer Funktion, der „greedy evaluation function“. Durch die Funktionsauswahl sind die Lösungen nicht unbedingt Optimal und es bedarf einer Verbesserung durch eine lokale Suche. Der Greedy Randomized Algorithmus verwendet eine „restricted candidate list“ (RCL, α bestimmt deren Größe, gute Ergebnisse liefern kleine Werte mit α 0,2 oder randomisierte Werte (Abhängig von der Güte)). Die Elemente auf der RCL sind die Elemente aus der Kandidatenliste unter Berücksichtigung der folgenden Formel: c(s) ≤ cmin + α(cmax – cmin) α 0 wobei c(s) cmin (reiner Greedy Algorithmus) α 1 wobei cmin ≤ c(s) ≤ cmax (zufällige Kombination) Eine Seperation von einer zufälligen Auswahl in den ersten k Schritte und danach bis zur vollständigen Lösung eine reine Greedy Konstruktion ist ebenso möglich. Die lokale Suche basiert auf der Untersuchung einer Nachbarschaft – entweder einer direkten oder erweiterten. Dabei werden schlechtere Lösungen durch bessere Lösungen ersetzt. Wenn keine bessere Lösung in der Nachbarschaft gefunden wird, endet die lokale Suche und man erreicht ein so genanntes lokales Optimum. Die Effektivität hängt dabei von der Nachbarschaftsstruktur, der Startlösung sowie der Technik der Nachbarschaftssuche (zum Beispiel „best-improving“ oder „first-improving“) ab. Die Anzahl der Lösungen kann durch eine Beschränkung der Nachbarschaft sowie der Erstellung von Kandidatenlisten (mit Verwendung einer Memory Struktur noch effizienter) begrenzt werden. Die Intensifikation (attraktive Regionen des Lösungsraums sowie Anregungen von move Kombinationen welche in der Vergangenheit gut waren) wird in GRASP mittels Pfad-relinking durchgeführt. „Path-Relinking“ ist eine eingeschränkte lokale Suche mit einer limitierten Anzahl an „moves“. Dabei werden von einer Startlösung Pfade erzeugt, welche nach besseren Lösungen abgesucht werden. Die Diversifikation (Erweiterung der Suche auf unerforschte Regionen oder die Generation von Lösungen welche sich signifikant unterscheiden) wird mittels „iterated local search“ umgesetzt. Path relinking Grundsätzlich ohne Memory Komponente (Hinzufügung aber möglich) zur Erhöhung der Intensifikation. Dadurch erfolgt eine genauere Betrachtung vielversprechender Lösungsbereiche. Das Relinking wird zwischen zwei Lösungspaaren angewandt: Erstens das mittels GRASP ermittelte lokale Optimum sowie die Lösung aus dem Elite-Pool (zufällig oder in Abhängigkeit der Unterschiedlichkeit der Lösungen). Das Elite Pool besteht aus guten und unterschiedlichen Lösungen bis zu einer maximalen Lösungsanzahl. Es gibt Forward, Backward, Forward-Backward, Mixed, Truncated, Evolutionary Path Relinking. Dabei kommt es auf den Trade off zwischen Berechnungszeit und Qualität an. Scatter Search Scatter Search ist ein Populationsverfahren sowie ein besseres Lösungsverfahren durch die Kombination von Elementen. Durch Linearkombinationen (konvexen als auch nicht konvexen) werden andere Punkte erreicht. Dies führt zu einer linearen Unabhängigkeit. Scatter Search ist eine Kombination von Entscheidungsregeln und Ersatzrestriktionen. Scatter Search beruht auf einem zirkulären Prozess. Populationsset: großes Set an Startlösungen, durch Diversifikations- und Verbesserungsmethoden erstelltReference Set: Sollte möglichste klein gehalten werden (etwa 20), Anzahl an Lösungen, deren Lösungen zu neuen Lösungen kombinieren, systematische Auswahl von Population Set, Elitelösungen Anzahl an Kombinationen (3*b-7)*b / 2 Ersatzrestriktionen: Informationen erfassen, welche einerseits im Originalvektor nicht enthalten sind sowie Methoden nutzen um durch Kombinationen neue Vektoren zu erstellen und Kombinationen zu bewerten. Clustering wird die Auswahl von Teilmengen genannt. Die neue Lösung kann sich auf den Zielfunktionswert oder der Erhöhung der Diversität beziehen. Methoden: Erstellung einer Diversifikation (diversification generation method): sorgt für unterschiedliche Startpunkte mit unterschiedlicher Qualität und unterschiedlicher Struktur / QualitätVerbesserung (improvement method): Versucht die Lösungen und Startpunkte zu verbessern, diese werden in das Populationsset aufgenommenAktualisierung des Reference Set (reference set update method): Diverse qualitativ hochwertige und wertvolle Lösungen aufzunehmen, z.B. gute Zielfunktionswerte oder eine gute DiversifikationAbfrage ob Anzahl der Iterationen erreicht oder keine neuen Lösungen gefunden werden (erneutes Starten von Diversifikation und Verbesserung und Erstellung eins Populationssets)Erstellung von Teilmenge (subset generation method): systematischer Ansatz, 2-elementrigen Subsets (Anzahl: (b²-b)/2), 2-elemtrigen plus beste verbleibende, usw.Erstellung von Kombinationen von Lösungen (Solution Combination Method):Improvement Method: Verbesserung der Lösungen, danach zur Update reference set method welche über eine Aufnahme der Lösungen ins Referenzset entscheidet Problematisches beziehungsweise systematisches Vorgehen: Kombinationen mit 2 ElementeKombinationen mit 3 Elemente (2 Elemente + beste verbleibende)Kombinationen mit 4 Elemente (vorherige Spalte + beste verbleibende) Linearkombinationen: Konvexe Linearkombinationen: 0,2 V1 + 0,5 V2 + 0,3 V3 (Multiplikationsfaktoren in Summe 1), bei 2 Punkten kann alles dazwischen vorkommenNicht Konvexe Linearkombinationen: Multiplikationsfaktoren jede beliebige Summe, bei 2 Punkten können auch Ergebnisse außerhalb vorkommen Mathheurustics als Metaheuristiken Metaheuristiken sind allgemeine Verfahren, die einfache Heuristiken mit Regeln kombinieren und koordinieren, um schnell Lösungen mit guter Qualität zu finden – zum Beispiel für schwere kombinatorische Optimierungsproblem. Im Gegensatz zu Heuristiken versuchen Metaheuristiken lokalen Optima zu entkommen. Large Neighborhood Search (Metaheuristiken) In der großen Nachbarschaftssuche wird eine (Start)Lösung durch eine schrittweise Zerstörung (destroy method) und Verbesserung (repair method) der Lösung optimiert. Gewünscht wird somit den lokalen Optima zu entweichen– allerdings ist dieser Prozess sehr zeitaufwendig. Darum wird in der LNS ein Subset verwendet, um schnell und effizient Lösungsräume abzusuchen. Von einer großen Nachbarschaft spricht man, wenn die Nachbarschaftssuche exponentiell mit der Größe der Instanz wächst. Very Large Scale Neighborhood Search (VLNS) Methoden mit variabler Tiefe (Variable Depth Methods): Dabei bestimmt ein Parameter k, wie viele Nachbarschaftselemente pro Durchgang ausgetauscht werden. Ein k von 2 bedeutet, dass 2 Nachbarschaften ausgetauscht werden.Verbesserungen des Netzwerkflusses (Network Flow based improvements): Die Verbesserungen können sich dabei auf die Zyklen, den Pfad oder die Zuteilung (Zuordnung) beziehen.Restriction to subclasses method: Hinzufügen von Bedingungen zum originalen Problem. Large Neighborhood Search (LNS) Die Herausforderung der LNS ist das effiziente Durchsuchen der Nachbarschaft. Akzeptanz: nur verbesserte Lösungen, Random Walk (jede neue Lösung), Greedy Acceptance (reduzierte Kosten), Simulated Anneling (mit abnehmender Wahrscheinlichkeit pro Iteration), Threshold Accepting (abnehmende Differenz pro Iteration), Old Bachelor Acceptance (Differenz reduziert bei Annahme oder vergrößert bei Ablehnung) oder Great Deluge Algorithm (abnehmendes Level wenn Lösung akzeptiert wird). Destroy Method: Ist das Ausmaß der Zerstörung zu groß wiederholt sich die Heuristik, ist sie zu klein geht der Effekt der großen Nachbarschaft verloren. Den Zerstörungsgrad allmählich zu erhöhen birgt gute Ergebnisse. Noch bessere Ergebnisse erhält man, wenn das Ausmaß der Zerstörung bei jeder Iteration zufällig in einem Bereich zwischen dmin und dmax ist. Strategien: konstant, Erhöhung nach dmax oder Verringerung nach dmin oder zufällig. Repair Method: Das Hinzufügen kann durch eine Greedy Heuristik erfolgen und wird sooft wiederholt, bis eine zulässige Lösung geliefert wird. Durch die Heuristik ist es lediglich eine gute Lösung der Teillösung (bezieht sich auf den übrig gebliebenen Teil nach der destroy method). Dafür besitzt die Heuristik eine kürzere Laufzeit sowie Diversifikationsvorteile. Rundungsheuristiken (Metaheuristiken) Integer Linear Program (ILP) ist ein Linear Program (LP) mit der zusätzlichen Einschränkung, dass die Variablen Integer Werte (binär) haben müssen. Vorteile: ausdrucksstarke Sprache um Optimierungsprobleme zu definieren, decken eine große Zahl von Kombinationsprobleme ab Nachteile: Sprache um kombinatorische Optimierungsprobleme zu definieren, Lösungssuche ist NP schwer Kombinatorische Optimierungsprobleme Die zulässigen Lösungen sind endlich. Zuerst ein ILP modellieren (für ein kombinatorisches Optimierungsproblem)ILP zu einem LP relaxieren (die Ganzzahligkeitsbedingung aufheben), der zulässiger Bereich wird somit erweitert, opt(LP) Rundungsheuristik anwenden) Rundungsheuristiken verwandeln nicht ganzzahlige Lösungen (x*) in gerundete ganzzahlige Lösungen (x‘), dabei gilt: (´)≤∗()≤∗() c > Approximationsfaktor Vertex Cover Probleme (Knotenüberdeckungsproblem) Bei einem ungerichteter Graph G (V, E) versucht das Knotenüberdeckungsproblem die geringste Anzahl an Knoten S zu finden, sodass alle Kanten berührt sind, sodass gilt, dass für jedes (u,v) E zumindest u oder v zu S gehört. Input: G (V,E)S : {}for each (u, v) E if u S und v S dann S : S vereinigt {u,v}return S Wenn die If-Bedingung k mal ausgeführt, dann ist |S| 2k und der Graph beinhaltet ein Match der Größe 2, wobei das Vertex Cover Optimum zumindest k ist und |S| höchstens das doppelte des Optimums ist. In dem einfachen Problem jeder Knoten hat Kosten von 1. Weighted Vertex Cover Problem (gewichtetes Knotenüberdeckungsproblem) Nun gibt es zusätzlich Kosten auf den Knoten, somit hat jeder Knoten die nicht-negative Kosten c(v). Gesucht ist S mit den geringsten totalen Kosten . Der einfache Algorithmus für das Vertex Cover Problem kann allerdings schlecht performen. Deshalb wird das gewichtete Knotenüberdeckungsproblem mit Hilfe von ILP gelöst. LP Relaxation of (weighted) Vertex Cover Rundungsheuristik anwenden, wenn X*v > 0.5 dann X’v 1, im schlechtesten Fall eine Güter von 2. Zulässig da durch erste Nebenbedingung mindestens eine der beiden Variablen über 0.5 ist. Iterative Verfahren (Metaheuristiken) Eine Anwendung von iterativen Verfahren ist die Lösung des „minimum weight bipartite perfect matching problems“. Für iterative Algorithmen empfiehlt es sich ein lineares Programm aufzustellen (System aus linearen Beschränkungen und einer Zielfunktion). Matching Probleme G(V,E) ist bipartit wenn die Knotenmenge V in Teilmenge V1 und V2 und keine Kante die Endpunkte in der selben Teilmenge besitztMatching Zuordnung von Knoten in V1 zu Knoten in V2, M EPerfektes Matching jeder Knoten in V1 zu Knoten in V2 zugeordnet, Matrixschreibweise Oftmals wird die Matrixschreibweise für die Bedingungen benützt. Die Vektoren halten die Entscheidungsvariable (x) sowie den Zielfunktionswert (z.B. Gewicht (w)). Die Matrix A haltet die Koeffizienten und der Vektor b haltet die Ergebnisse der Bedingungen, sodass A*x b. Iterative Algorithmus Optimale Lösung für das lineare Programm findenFalls eine Lösung bereits den (binären) Wert 1 liefert, wird diese Verbindung in die Lösung aufgenommen und aus dem nun kleinen/verkleinerten Problem gelöschtFalls eine Lösung den (binären) Wert 0 liefert, wird die Verbindung gelöscht und es entsteht ein verkleinertes ProblemWiederhole Schritt 1 bis 3 bis optimale Lösung gefunden ist Knotenüberdeckung bei bipartiter Graphen Anzahl der Bedingungen ist gleich Anzahl der Kanten, somit lösbar in polynomialer Zeit. Spannbaum / Spanning trees Bei gegebenen ungerichteten Graphen und Kosten auf den Kanten soll der Spannbaum mit den minimalen aufsummierten Kantenkosten gefunden werden. Jeder Knoten soll dabei zumindest mit einer Kante verbunden sein, sodass ein Netzwerk entsteht (z.B. Computernetzwerke). Zudem dürfen keine Zyklen enthalten sein und der Spanbaum muss zusammenhängend sein. Damit enthält ein Spannbaum genau eine Kante weniger als Knoten. (1) Mindestens eine Kante ist im Baum nicht enthalten (2) Alle Knoten werden wenigstens einmal verknüpft Quadratisches Orientierungs-Problem Orientierungsproblem Bei gegebenen Set von k Knoten ist jeder Strecke zwischen den Knoten die Distanz Dij zugeordnet. Zudem besitzt jeder Knoten einen Profit Pi. Gesucht wird jene Tour, welche die Summe der Profite unter Berücksichtigung einer Kapazitätsbeschränkung C maximiert. Die Anzahl der besuchten Knoten ist dabei unwesentlich und die Entfernungen werden nicht in der Zielfunktion berücksichtigt. Quadratisches Orientierungsproblem Zusätzlich zum Orientierungsproblem treten auch Synergieeffekte auf. Der Profit einer Tour ist somit nicht nur von den Profiten der in der Tour enthaltenen Knoten abhängig, sondern auch von den jeweiligen Synergien dazwischen. Die Synergien können dabei positiv oder negativ sein. Der gesamte Profit: Einzeleffekte + Synergieeffekte. Beispiel für positive bzw. negative Synergien: Ein Panini Album mit verschiedenen Karten (jede Karte nur einmal) als Knoten. Jede Karte hat einen gewissen Verkaufswert (Profit). Werden zwei Karten gleichzeitig verkauft, kann ein teurerer Preis verlangt werden (positive Synergien) oder vom Käufer ein besserer Preis (negative Synergien) verlangt werden. Je nach Kartenwahl bestehen verschiedene Synergien. Zwischen Karten 1, 2 und 3 bestehen Synergien 1-2, 2-3 und 1-3. Quadratisches Rucksackproblem Das Rucksackproblem ist ein Optimierungsproblem aus der Kombinatorik, wobei Objekte unter der Berücksichtigung einer (mehrerer) Kapazitätsbegrenzung (Volumen, Gewicht) so ausgewählt werden sollen, dass sich deren Nutzen maximiert. Die Zielfunktion ist somit die enthaltenden Items mal deren Nutzenwert. Das quadratische Rucksackproblem baut auf die das Rucksackproblem auf, mit dem Unterschied, dass zwischen den Items Synergien bestehen. Damit besteht die Zielfunktion aus den Einzelnutzen sowie aus der Nutzenkombination der enthaltenen Items. Euklidisch und Dreiecksungleichung Euklidische Datensätze und daraus resultierende euklidische Abstände sind eine Metrik und erfüllen die Dreiecksgleichung. Diese besagt, dass der direkte Weg (von Knoten zu Knoten / eine Seite) näher oder zumindest gleich nah sein muss, als der Weg über einen anderen Knoten (Summe der beiden anderen Seiten). Nicht euklidisch wären zum Beispiel Flugstrecken durch die Erdkrümmung oder Einbahnstraßen. Metaheuristiken Diese kann aus einer Konstruktions- sowie einer Verbesserungsheuristik bestehen. Der potentielle nächste Knoten kann zum Beispiel durch folgende Formel definiert sein: Pi (Profit) + Summe Sij (Summe der Synergien) / Dij (Distanz)Die Verbesserung kann durch Analyse einer potentiellen Einsparung bringen. Also der Profit plus den Synergien durch die Differenz der Strecke welche sich erspart werden könnte. IPL Sorgt für eine optimale Lösung. Die Entscheidungsvariablen sind dabei binär (0 oder 1). Weitere Informationen Travelling Salesman Probelm (TSP): Der Handelsreisende muss eine Tour durch alle Knoten besuchen, wobei die Summe der Kanten minimiert werden soll und die Tour geschlossen ist. Capacitated Vehicle Routing Problem (CVRP): Eine Flotte befindlich an einem Depot soll die Touren so effizient fahren, dass die Kundennachfrage mit einer möglichst geringen Anzahl an Fahrzeugen abgedeckt ist und Start- und Ausgangspunkt das Depot ist. 2 Opt Verfahren: 2 Kanten löschen und durch 2 neue Kanten ersetzen. Lokale Suche: Lösung durch andere ersetzt, welche in Nachbarschaft befindet: best (immer neuer Lauf) oder first improving (weitergehend mit geänderter Lösung, erst wenn ganze Runde seit letztem Tausch stoppen).

Blogofant - Elefantisch gut!

Verschlagwortet: Vertex Cover Problem

Heuristiken & Metaheuristiken

Werbung / Advertisement

Top Ratings

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Neueste Beiträge

Werbung / Advertisement

Werbung / Advertisement