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 have n_res graph attribute and all edges must have res_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']