cspy.PSOLGENT
Particle Swarm Optimization with combined Local and Global Expanding Neighborhood Topology (PSOLGENT) algorithm for the (resource) constrained shortest path problem (Marinakis et al 2017).
Note. Neighborhood expansion not implemented yet, so PSOLGNT.
Given the nature of our problem we have set the default parameters of the algorithm as suggested in the paper mentioned.
Code adapted from Solid.
Parameters
- Gobject
nx.Digraph()
must haven_res
graph attribute and all edges must haveres_cost
attribute.- max_reslist of floats
[M_1, M_2, ..., M_{n\_res}] upper bounds for resource usage.
- min_reslist of floats
[L_1, L_2, ..., L_{n\_res}] lower bounds for resource usage.
- preprocessbool, optional
enables preprocessing routine. Default : False.
- max_iterint, optional
Maximum number of iterations for algorithm. Default : 100.
- max_localiterint, optional
Maximum number of local search iterations. Default : 10.
- time_limitint, optional
time limit in seconds. Default: None
- thresholdfloat, optional
specify a threshold for a an acceptable resource feasible path with total cost <= threshold. Note this typically causes the search to terminate early. Default: None
- swarm_sizeint, optional
number of members in swarm. Default : 50.
- member_sizeint, optional
number of components per member vector. Default :
len(G.nodes())
.- neighbourhood_sizeint, optional
size of neighbourhood. Default : 10.
- lower_boundfloat, optional
lower bound of initial positions. Default : -1.
- upper_boundfloat, optional
upper bound of initial positions. Default : 1.
- c1float, optional
constant for 1st term in the velocity equation. Default : 1.35.
- c2float, optional
contsant for 2nd term in the velocity equation. Default : 1.35.
- c3float, optional
constant for 3rd term in the velocity equation. Default : 1.4.
- seedNone or int or numpy.random.RandomState instance, optional
seed for PSOLGENT class. Default : None (which gives a single value numpy.random.RandomState).
- REF_callbackREFCallback, optional
Custom resource extension callback. See REFs for more details. Default : None
Raises
- Exception
if no resource feasible path is found
Notes
The input graph must have a n_res
attribute.
The edges in the graph must all have a res_cost
attribute.
Also, we must have len(min_res)
= len(max_res)
.
See Using cspy.
This algorithm requires a consistent sorting of the nodes in the graph.
Please see comments and edit the function _sort_nodes
accordingly.
Example
>>> from cspy import PSOLGENT
>>> from networkx import DiGraph
>>> from numpy import zeros, ones, array
>>> G = DiGraph(directed=True, n_res=2)
>>> G.add_edge('Source', 'A', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('Source', 'B', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('Source', 'C', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('A', 'C', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('A', 'E', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('A', 'F', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('B', 'C', res_cost=array([2, 1]), weight=-1)
>>> G.add_edge('B', 'F', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('B', 'E', res_cost=array([10, 1]), weight=10)
>>> G.add_edge('C', 'D', res_cost=array([1, 1]), weight=-1)
>>> G.add_edge('D', 'E', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('D', 'F', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('D', 'Sink', res_cost=array([10, 10]), weight=10)
>>> G.add_edge('F', 'Sink', res_cost=array([10, 1]), weight=1)
>>> G.add_edge('E', 'Sink', res_cost=array([1, 1]), weight=1)
>>> n_nodes = len(G.nodes())
>>> psolgent = PSOLGENT(G, [5, 5], [0, 0],
max_iter=200,
swarm_size=50,
member_size=n_nodes,
neighbourhood_size=50)
>>> psolgent.run()
>>> print(psolgent.path)
['Source', 'A', 'C', 'D', 'E', 'Sink']