El siguiente ejemplo es un problema clásico de partición de subconjuntos en el que nuestro objetivo es encontrar un subconjunto de elementos de un gráfico no dirigido. GRAMO(V, mi) con el número máximo de elementos tales que no haya aristas que conecten ningún par del subconjunto dado.
Comencemos creando clases para trabajar con los elementos gráficos de este problema. La clase Node se utilizará para representar un vértice (o nodo) de nuestro gráfico no dirigido. Tendrá como atributos:
neighbors: una lista de vértices vecinosindex: Su identificadorselected: Un valor booleano para indicar cuándo se incluyó en la solución.
Siempre que un Node instancia se elimina de nuestro subconjunto factible de elementos, debemos eliminarla de la lista de vecinos de sus vecinos, por lo que creamos un método delete Hacerlo más fácil.
La propiedad degree calcula el número de vecinos de un nodo dado y se utilizará como nuestro criterio para elegir el siguiente elemento en el avaro acercarse.
import copy
from typing import Dict, List, Optional, Tupleclass Node:
neighbors: List['Node']
index: int
selected: bool
def __init__(self, index):
self.index = index
self.neighbors = []
self.selected = 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.remove(self)
@property
def degree(self):
return len(self.neighbors)
Ahora vamos a crear nuestra Graph clase. Se debe crear una instancia a partir de una lista de aristas y una lista opcional de nodos. Debería tener un atributo N que es un diccionario de nodos (o vértices) existentes.
La propiedad queue debería devolver una lista de nodos aún no seleccionados para que consideremos incluirlos en la solución en cada paso de nuestra heurística constructiva.
Cada vez que un nuevo Node Se selecciona la instancia, el método select debería ser llamado, lo que cambia su selected atributo y llama a su delete método.
class Graph:N: Dict[int, Node]
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None
):
# Start the set
if nodes is None:
self.N = {}
else:
self.N = {i: Node(i) for i in nodes}
# Include 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.selected]
@property
def inactive_nodes(self):
return [node for node in self.N.values() if not node.selected]
@property
def nodelist(self):
return list(self.N.values())
@property
def queue(self):
return [n for n in self.nodelist if not n.selected]
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 select(self, node: Node):
node.selected = True
selected_neighbors = node.neighbors.copy()
for n in selected_neighbors:
other = self.N.pop(n.index)
other.delete()
def deactivate(self):
for n in self.N.values():
n.selected = False
def copy(self):
return copy.deepcopy(self)
Ahora, creemos una abstracción para nuestra heurística constructiva. Se debe instanciar, como su correspondiente Graph, de una lista de bordes y una lista opcional de nodos. Cuando se crea una instancia, su atributo graph se define a partir del gráfico original de la instancia del problema.
from abc import ABC, abstractmethod
from mis.graph import Graph, Node
from typing import List, Optional, Tupleclass BaseConstructive(ABC):
graph: Graph
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None,
):
self.graph = Graph(edges, nodes)
El solve El método será el núcleo de nuestro procedimiento de solución. Debería devolver un subgrafo de GRAMO(V, mi) con una solución candidata. Cuando se utiliza una instancia del procedimiento de solución como invocable, se debe sobrescribir la información de sus nodos. selected atributos basados en el resultado devuelto por el solve método.
Observe la choice El método aquí es una abstracción que las clases secundarias aún deben sobrescribir.
class BaseConstructive(ABC):
# Check previous definitionsdef __call__(self, *args, **kwargs):
S = self.solve(*args, **kwargs)
for i, n in S.N.items():
self.graph.N[i].selected = n.selected
@property
def cost(self):
return len(self.graph.active_nodes)
def solve(self, *args, **kwargs) -> Graph:
self.graph.deactivate()
G = self.graph.copy()
for i in range(len(G.N)):
n = self.choice(G)
G.select(n)
if len(G.queue) == 0:
assert len(G.N) == i + 1, "Unexpected behavior in remaining nodes and iterations"
break
return G
@abstractmethod
def choice(self, graph: Graph) -> Node:
pass
Primero creemos un algoritmo que elija aleatoriamente el siguiente nodo para incluirlo en nuestra solución.
import randomclass RandomChoice(BaseConstructive):
rng: random.Random
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None,
seed=None
):
super().__init__(edges, nodes)
self.rng = random.Random(seed)
def choice(self, graph: Graph) -> Node:
return self.rng.choice(graph.queue)
Ya se puede utilizar en nuestro procedimiento de solución y crea soluciones factibles que son conjuntos independientes máximos (no máximo). Sin embargo, su rendimiento varía según la secuencia aleatoria y podríamos ser vulnerables a malos resultados.
Codicioso adaptativo
Alternativamente, en cada paso, podríamos haber elegido el siguiente nodo que tenga el menor impacto en el “grupo” de elementos factibles del conjunto básico. Significaría elegir el siguiente elemento que en el subgrafo tenga el menor número de vecinos. En otras palabras, con el menor degree atributo. Este es el mismo enfoque adoptado por Feo et al. (1994).
Observe la degree de nuestros nodos pueden variar a medida que cambia la solución parcial y se eliminan elementos del subgrafo. Se puede definir por tanto como un codicioso adaptativo procedimiento.
Hay otras situaciones en las que el coste de la contribución de un elemento se ve afectado por las elecciones previas de elementos realizadas por el algoritmo. A estos los llamaremos algoritmos codiciosos adaptativos. (Resende y Ribeiro, 2016).
Implementemos entonces un algoritmo que elija como siguiente elemento el del subgrafo con el menor degree.
class GreedyChoice(BaseConstructive):def choice(self, graph: Graph) -> Node:
return min([n for n in graph.queue], key=lambda x: x.degree)
Aunque no proporciona pruebas de optimización, el enfoque adaptativo codicioso también puede ser una estrategia interesante para proporcionar resultados rápidos y de buena calidad a este problema. Pero intente ejecutar el enfoque aleatorio varias veces… En algunos casos, podría superar a la estrategia codiciosa (al menos en una o varias ejecuciones). ¿Por qué no implementar entonces un marco de múltiples inicios?
Inicios múltiples
En este enfoque, se realizan múltiples ejecuciones independientes y se mantiene un registro de la mejor solución. Al final, se devuelve la mejor solución.
class MultiRandom(RandomChoice):def solve(self, n_iter: int = 10) -> Graph:
best_sol = None
best_cost = 0
for _ in range(n_iter):
G = super().solve()
if len(G.N) > best_cost:
best_cost = len(G.N)
best_sol = G
return best_sol
En mi repositorio de GitHubencontrará un ejemplo de un gráfico de 32 nodos en el que codicioso adaptativo encontró un subconjunto de 5 vértices, pero un marco aleatorio con inicio múltiple encontró una solución con 6. El procedimiento de solución se representa a continuación.