Topology¶
The classes of this submodule are all instances of the same base class used to define the migration paths in the PyGMO.archipelago. When a new PyGMO.island is pushed back into the PyGMO.archipelago the various connections are rewired as to respect the topological properties defined by these classes.
The user will mainly use these classes in the following way:
from PyGMO import *
prob = problem.lennard_jones(5)
algo = algorithm.bee_colony(gen = 10) #instantiates artificial bee colony setting 10 generations for each algorithmic call
topo = topology.ring() #defines an empty ring topology
archi = archipelago(algo,prob,8,20,topology=topo) #connects 8 islands in a ring topology
archi.topology.draw() #requires networkx to be installed
Migration Probability¶
When defining the migration paths (edges of the DAG in the topology), one of the parameters is the migration probability, by default equal to 1. It is possible to change it globally for all edges:
from PyGMO import *
topo = topology.fully_connected(5) # Defines a 5-vertex ring topology
topo.set_weight(0.5) # Changing the migration probability to 0.5 for all edges
specify a custom migration probability for all out-going edges of a node:
from PyGMO import *
topo = topology.fully_connected(3) # Defines a 5-vertex ring topology
topo.set_weight(0.5) # Change the migration probability to 0.5 for all edges
topo.set_weight(0, 0.1) # Probability 0.1 for all out-going edges from island 0
topo.set_weight(2, 0.0) # Probability 0.0 for all out-going edges from island 2 (effectively invalidating the migration path)
or specify a custom migration probability for individual edges:
from PyGMO import *
topo = topology.one_way_ring(5) # Defines a 5-vertex ring topology
topo.set_weight(1, 2, 0.5) # Changing the migration probability to 0.5 for edge 1 -> 2
topo.set_weight(2, 3, 0.2) # Changing the migration probability to 0.2 for edge 2 -> 3
topo.set_weight(3, 4, 0.1) # Changing the migration probability to 0.1 for edge 3 -> 4
topo.set_weight(4, 0, 0.05) # Changing the migration probability to 0.05 for edge 4 -> 0
The Classes¶
- class PyGMO.topology.base¶
Methods of the topology base class, shared by all topology objects.
- set_weight((float)w)¶
Sets the weight for each edge in the topology.
- set_weight((int)id, (float)w)
Sets the weight for each edge outgoing from the vertex id
- set_weight((int)id1, (int)id2, (float)w)
Sets the weight for the edge between the vertices id1 and id2
- class PyGMO.topology.unconnected¶
Unconnected topology (this corresponds to do parallel independent runs of the algorithms)
- unconnected.__init__(nodes=0)¶
Constructs an unconnected topology
USAGE: topology.unconnected(nodes = 0)
- nodes: number of nodes
- unconnected.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.unconnected(nodes=100) topo.draw(layout='spring', n_size=15, e_arrows=False)
- class PyGMO.topology.ring¶
Ring topology (links go in both directions)
- ring.__init__(nodes=0)¶
Constructs a ring topology
USAGE: topology.ring(nodes = 0)
- nodes: number of nodes
- ring.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.ring(nodes=30) topo.draw(layout='circular', n_size=30, e_arrows=True, e_alpha=0.5)
- class PyGMO.topology.one_way_ring¶
Ring topology (links go only in one direction)
- one_way_ring.__init__(nodes=0)¶
Constructs a one_way_ring topology:
USAGE: topology.one_way_ring(nodes = 0)
- nodes: number of nodes
- one_way_ring.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.one_way_ring(nodes=30) topo.draw(layout='circular', n_size=30, e_arrows=True, e_alpha=0.5)
- class PyGMO.topology.fully_connected¶
Fully connected topology (i.e. all islands are connected bi-directionally)
- fully_connected.__init__(nodes=0)¶
Constructs a fully connected topology:
USAGE: topology.fully_connected(nodes = 0)
- nodes: number of nodes
- fully_connected.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.fully_connected(nodes=30) topo.draw(layout='circular', n_size=30, e_arrows=True, e_alpha=0.1)
- class PyGMO.topology.pan¶
Islands are connected in a ring, except the island with id 0 that is connected to the ring only receiving migrants. This topology was first conceived to have global optimization happening on the outer ring while using a local optimizer in the island 0 to refine the solution (also seen as a memetic approach)
- pan.__init__(nodes=0)¶
Constructs a pan topology: this is, essentially, a ring with a sink node. This topology was ‘invented’ to support a local optimization algorithm in the sink node
USAGE: topology.pan(nodes = 0)
- nodes: number of nodes
- pan.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
from PyGMO import * topo = topology.pan(nodes=10) topo.draw(layout='spring', n_size=30, e_arrows = True)
- class PyGMO.topology.rim¶
Islands are connected in a ring and they all are also connected to the No.0 island.
- rim.__init__(nodes=0)¶
Constructs a rim topology: this is, essentially, a ring + one node that connects all ring nodes bi-directionally
USAGE: topology.rim(nodes = 0)
- nodes: number of nodes
- rim.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
from PyGMO import * topo = topology.rim(nodes=90) topo.draw(layout='circular', n_size=30)
- class PyGMO.topology.hypercube¶
Hypercube topology
- hypercube.__init__(nodes=0)¶
Constructs a hypercube topology:
USAGE: topology.hypercube(nodes = 0)
- nodes: number of nodes
- hypercube.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
from PyGMO import * topo = topology.hypercube(nodes=32) topo.draw(layout='spring', n_size=90)
- class PyGMO.topology.watts_strogatz¶
The Watts-Strogatz topology is a ring lattice network in which forward edges are rewired with random probability. Such a network has small-world properties, including short average path lengths and high clustering. When the push_back method is used all the connections are rewired (all links are bidirectional).
Watts-Strogatz topology in wikipedia
- watts_strogatz.__init__(k=10, p=0.1, nodes=0)¶
Constructs Watts-Strogatz Topology:
USAGE: topology.watts-strogatz(k = 10, p = 0.1, nodes=0)
- k: number of neighbours
- p: rewiring probability [0,1]
- nodes: number of nodes
- watts_strogatz.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.watts_strogatz(nodes=100, p=0.1) topo.draw(layout='circular', n_size=3, scale_by_degree=True)
- class PyGMO.topology.erdos_renyi¶
A random graph (all links are bidirectional)
- erdos_renyi.__init__(p=0.1, nodes=0)¶
Constructs an Erdos-Renyi (random) topology:
USAGE: topology.erdos_renyi(p = 0.1, nodes=0)
- p: wiring probability [0,1]
- nodes: number of nodes
- erdos_renyi.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.erdos_renyi(nodes=100, p=0.03) topo.draw(layout='spring', n_size=5, scale_by_degree=True)
- class PyGMO.topology.barabasi_albert¶
Topology based on the Barabási-Albert (BA) model. (all links are bidirectional)
The network is grown in two phases:
- The first m0 elements added to the network constitute a kernel of nodes connected to each other with high probability;
- After the kernel is built, the next elements added to the network are connected randomly to m of the existing nodes; the probability of connection is biased linearly towards the most connected nodes.
- barabasi_albert.__init__(m0=3, m=3, nodes=0)¶
Constructs an Barabasi-Albert topology:
USAGE: topology.barabasi_albert(m0 = 3, m = 3, nodes = 0)
- m0: kernel size
- m: number of random connections to be established when a new node is added.
- nodes: number of nodes
- barabasi_albert.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.barabasi_albert(m0=3, m=3, nodes=1000) topo.draw(layout='spring', n_size=1, scale_by_degree=True,e_alpha=0.03)
- class PyGMO.topology.clustered_ba¶
Topology based on the Clustered Barabási-Albert (BA) model. (all links are bidirectional)
The network is grown in two phases:
- The first m0 elements added to the network constitute a kernel of nodes connected to each other with high probability;
- After the kernel is built, the next elements added to the network are connected randomly to m of the existing nodes; the probability of connection is biased linearly towards the most connected nodes. A link is established also between the m nodes with probability p
- clustered_ba.__init__(m0=3, m=3, p=0.5, nodes=0)¶
Constructs a Clustered Barabasi-Albert topology:
USAGE: topology.clustered_ba(mm0 = 3, m=3, p=0.5, nodes = 0)
- m0: kernel size
- m: nnumber of random connections to be established when a new node is added
- p: probability that a connection is established between two nodes that are adjacent to a new node
- nodes: number of nodes
- clustered_ba.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.clustered_ba(m0=3, m=3, p=0.5,nodes=1000) topo.draw(layout='spring', n_size=1, scale_by_degree=True,e_alpha=0.03)
- class PyGMO.topology.ageing_clustered_ba¶
Topology based on the Ageing Clustered Barabási-Albert (BA) model. (all links are bidirectional)
The network is grown in two phases:
- The first m0 elements added to the network constitute a kernel of nodes connected to each other with high probability;
- After the kernel is built, the next elements added to the network are connected randomly to m of the existing nodes not older than a; the probability of connection is biased linearly towards the most connected nodes. A link is established also between the m nodes with probability p
- ageing_clustered_ba.__init__(m0=3, m=3, p=0.5, a=1000, nodes=0)¶
Constructs a Clustered Barabási-Albert with Ageing vertices graph topology.:
USAGE: topology.clustered_ba(m0 = 3, m=3, p=0.5, a=1000, nodes = 0)
- m0: kernel size
- m: number of random connections to be established when a new node is added
- p: probability that a connection is established between two nodes that are adjacent to a new node
- a: ‘age’ at which a node ceases to make new connections.
- nodes: number of nodes
- ageing_clustered_ba.draw()¶
Draw topology using the draw() command from networkx.
USAGE: topology.draw(layout = “spring”, n_size = 15, scale_by_degree = False, n_color = ‘blue’, n_alpha = 0.5, e_alpha = 0.1, e_arrows=False)
- layout: Network layout. Can be ‘spring’ or ‘circular’.
- n_size: The size of nodes. Becomes scaling factor when scale_by_degree=True.
- scale_by_degree: When True, nodes will be sized proportional to their degree.
- n_color: Node color.
- n_alpha: Transparency of nodes. Takes value between 0 and 1.
- e_elpha: Transparency of edges. Takes value between 0 and 1.
- e_arrows: Plots arrows on the edges for directed graphs
- scale_by_degree: When True, nodes will be sized proportional to their degree.
The above image is produced by the code:
from PyGMO import * topo = topology.ageing_clustered_ba(m0=3, m=3, p=0.5,a=150,nodes=1000) topo.draw(layout='spring', n_size=1, scale_by_degree=True,e_alpha=0.03)
- class PyGMO.topology.custom¶
A custom topology. Allows for the construction of any topology via its unique methods.
- push_back()¶
Adds a vertex
- add_edge((int)id1, (int)id2, (float)w)¶
Adds a directed adge from vertex id1 to vertex id2, with an optional weight ‘w’ between id1 and id2 (by default 1.0)
- remove_edge((int)id1, (int)id2)¶
Removes the directed adge from vertex id1 to vertex id2
- remove_all_edges()¶
Removes all_edges
- draw()¶
Uses Python networx module to draw the topology in a graphic window
Example:
from PyGMO import * prob = problem.lennard_jones(5) algo = algorithm.de(gen = 10) #instantiates artificial bee colony with default params and 10 generations topo = topology.custom() #builds a custom topology for i in range(30): topo.push_back() #Now we have an unconnected topology of 30 vertices topo.add_edge(1,2) .... topo.add_edge(22,0) archi = archipelago(algo,prob,30,20) #constructs an archipelago (we cannot assign here directly topo #to the kwarg topology as the archipelago constructor only takes empty topologies archi.topology = topo #sets the topology to the customly constructed one archi.topology.draw() #Draws the topology (this requires networkx to be installed)