Das nächste Beispiel ist ein klassisches Downside der Teilmengenpartitionierung, bei dem unser Ziel darin besteht, eine Teilmenge von Elementen aus einem ungerichteten Graphen zu finden G(V, E) mit der maximalen Anzahl von Elementen, sodass keine Kanten irgendein Paar aus der gegebenen Teilmenge verbinden.
Beginnen wir mit der Erstellung von Klassen, die mit den Graphelementen dieses Issues arbeiten. Die Klasse Node wird verwendet, um einen Knoten (oder Knotenpunkt) aus unserem ungerichteten Graphen darzustellen. Es hat folgende Attribute:
neighbors: Eine Liste von Nachbarknotenindex: Seine Kennungchosen: Ein Boolescher Wert, der angibt, wann es in die Lösung aufgenommen wurde
Immer wenn ein Node Instanz aus unserer möglichen Teilmenge von Elementen gelöscht wird, müssen wir sie aus der Liste der Nachbarn ihrer Nachbarn entfernen, additionally erstellen wir eine Methode delete zu erleichtern.
Die Eigenschaft diploma berechnet die Anzahl der Nachbarn eines gegebenen Knotens und wird als Kriterium für die Auswahl des nächsten Parts im gierig Ansatz.
import copy
from typing import Dict, Checklist, Non-obligatory, Tupleclass Node:
neighbors: Checklist('Node')
index: int
chosen: bool
def __init__(self, index):
self.index = index
self.neighbors = ()
self.chosen = False
def __repr__(self) -> str:
return f"N{self.index}"
def add_neighbor(self, node: 'Node'):
if node not in self.neighbors:
self.neighbors.append(node)
def delete(self):
for n in self.neighbors:
n.neighbors.take away(self)
@property
def diploma(self):
return len(self.neighbors)
Lassen Sie uns nun unsere Graph Klasse. Sie sollte aus einer Liste von Kanten und einer optionalen Liste von Knoten instantiiert werden. Sie sollte ein Attribut haben N Dies ist ein Wörterbuch vorhandener Knoten (oder Eckpunkte).
Die Eigenschaft queue sollte eine Liste noch nicht ausgewählter Knoten zurückgeben, die wir bei jedem Schritt unserer konstruktiven Heuristik in die Lösung einbeziehen sollten.
Immer wenn ein neuer Node Instanz ausgewählt ist, wird die Methode choose aufgerufen werden soll, was seine chosen Attribut und nennt dessen delete Methode.
class Graph:N: Dict(int, Node)
def __init__(
self,
edges: Checklist(Tuple(int, int)),
nodes: Non-obligatory(Checklist(int)) = None
):
# Begin the set
if nodes is None:
self.N = {}
else:
self.N = {i: Node(i) for i in nodes}
# Embody all neighbors
for i, j in edges:
self._new_edge(i, j)
@property
def active_nodes(self):
return (node for node in self.N.values() if node.chosen)
@property
def inactive_nodes(self):
return (node for node in self.N.values() if not node.chosen)
@property
def nodelist(self):
return listing(self.N.values())
@property
def queue(self):
return (n for n in self.nodelist if not n.chosen)
def _new_node(self, i: int):
if i not in self.N:
self.N(i) = Node(i)
def _new_edge(self, i: int, j: int):
self._new_node(i)
self._new_node(j)
self.N(i).add_neighbor(self.N(j))
self.N(j).add_neighbor(self.N(i))
def choose(self, node: Node):
node.chosen = True
selected_neighbors = node.neighbors.copy()
for n in selected_neighbors:
different = self.N.pop(n.index)
different.delete()
def deactivate(self):
for n in self.N.values():
n.chosen = False
def copy(self):
return copy.deepcopy(self)
Lassen Sie uns nun eine Abstraktion für unsere konstruktive Heuristik erstellen. Sie sollte instantiiert werden, da ihre entsprechende Graphaus einer Liste von Kanten und einer optionalen Liste von Knoten. Bei der Instanziierung wird sein Attribut graph wird aus dem Originalgraphen der Probleminstanz definiert.
from abc import ABC, abstractmethod
from mis.graph import Graph, Node
from typing import Checklist, Non-obligatory, Tupleclass BaseConstructive(ABC):
graph: Graph
def __init__(
self,
edges: Checklist(Tuple(int, int)),
nodes: Non-obligatory(Checklist(int)) = None,
):
self.graph = Graph(edges, nodes)
Der clear up Methode wird der Kern unseres Lösungsverfahrens sein. Sie sollte einen Teilgraphen von G(V, E) mit einer Kandidatenlösung. Wenn Sie eine Instanz des Lösungsverfahrens als aufrufbares Objekt verwenden, sollte es die chosen Attribute basierend auf dem Ergebnis, das vom clear up Methode.
Beachten Sie die selection Die Methode hier ist eine Abstraktion, die noch von untergeordneten Klassen überschrieben werden muss.
class BaseConstructive(ABC):
# Examine earlier definitionsdef __call__(self, *args, **kwargs):
S = self.clear up(*args, **kwargs)
for i, n in S.N.objects():
self.graph.N(i).chosen = n.chosen
@property
def price(self):
return len(self.graph.active_nodes)
def clear up(self, *args, **kwargs) -> Graph:
self.graph.deactivate()
G = self.graph.copy()
for i in vary(len(G.N)):
n = self.selection(G)
G.choose(n)
if len(G.queue) == 0:
assert len(G.N) == i + 1, "Surprising conduct in remaining nodes and iterations"
break
return G
@abstractmethod
def selection(self, graph: Graph) -> Node:
go
Lassen Sie uns zunächst einen Algorithmus erstellen, der zufällig den nächsten Knoten auswählt, der in unsere Lösung aufgenommen werden soll.
import randomclass RandomChoice(BaseConstructive):
rng: random.Random
def __init__(
self,
edges: Checklist(Tuple(int, int)),
nodes: Non-obligatory(Checklist(int)) = None,
seed=None
):
tremendous().__init__(edges, nodes)
self.rng = random.Random(seed)
def selection(self, graph: Graph) -> Node:
return self.rng.selection(graph.queue)
Es kann bereits in unserem Lösungsverfahren verwendet werden und schafft praktikable Lösungen, die maximale unabhängige Mengen (nicht maximal). Die Leistung variiert jedoch je nach Zufallssequenz und es besteht die Gefahr schlechter Ergebnisse.
Anpassungsfähig gierig
Alternativ hätten wir bei jedem Schritt den nächsten Knoten wählen können, der den geringsten Einfluss auf den „Pool“ der möglichen Elemente aus dem Grundsatz hat. Das würde bedeuten, das nächste Aspect zu wählen, das im Teilgraphen die geringste Anzahl von Nachbarn hat. Mit anderen Worten, mit der kleinsten diploma Attribut. Dies ist derselbe Ansatz, den Feo et al. (1994) verfolgten.
Beachten Sie die diploma unserer Knoten können variieren, wenn sich die Teillösung ändert und Elemente aus dem Teilgraphen entfernt werden. Es kann daher definiert werden als anpassungsfähig gierig Verfahren.
Es gibt weitere Situationen, in denen die Kosten des Beitrags eines Parts von den vorherigen Elementauswahlen des Algorithmus beeinflusst werden. Wir nennen diese adaptiven Grasping-Algorithmen (Resende & Ribeiro, 2016).
Wir implementieren nun einen Algorithmus, der als nächstes Aspect dasjenige aus dem Teilgraphen mit dem kleinsten diploma.
class GreedyChoice(BaseConstructive):def selection(self, graph: Graph) -> Node:
return min((n for n in graph.queue), key=lambda x: x.diploma)
Obwohl er keinen Beweis für Optimalität liefert, kann der adaptive Grasping-Ansatz auch eine interessante Strategie sein, um bei diesem Downside schnell und qualitativ hochwertige Ergebnisse zu erzielen. Aber versuchen Sie, den Zufallsansatz mehrmals auszuführen … In einigen Fällen könnte er die Grasping-Strategie übertreffen (zumindest in einem oder mehreren Durchläufen). Warum dann nicht ein Multi-Begin-Framework implementieren?
Mehrfachstarts
Bei diesem Ansatz werden mehrere unabhängige Durchläufe durchgeführt und ein Register der besten Lösungen geführt. Am Ende wird die beste Lösung zurückgegeben.
class MultiRandom(RandomChoice):def clear up(self, n_iter: int = 10) -> Graph:
best_sol = None
best_cost = 0
for _ in vary(n_iter):
G = tremendous().clear up()
if len(G.N) > best_cost:
best_cost = len(G.N)
best_sol = G
return best_sol
In meinem GitHub-Repositoryfinden Sie ein Beispiel für einen Graphen mit 32 Knoten, in dem die anpassungsfähig gierig hat eine Teilmenge von 5 Knoten gefunden, aber ein zufälliges Framework mit mehreren Begins hat eine Lösung mit 6 gefunden. Das Lösungsverfahren ist unten dargestellt.
