search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

PSOLGENT fails when Source directly connected to Sink #79

Closed dvbuntu closed 2 years ago

dvbuntu commented 3 years ago

PSOLGENT has a check for prospective paths that demands they involve at least 3 nodes. This misses the edge case where the Source has an edge connecting directly to the Sink. Is this just a typo, and len(path) >= 2 was intended? Strictly speaking, even length 1 shouldn't throw an error, since one could access both path[0] and path[-1], though obviously they can't both match.

https://github.com/torressa/cspy/blob/083f25c22d61ec2b5b2b1455839eb1e0a33f1e90/src/python/algorithms/psolgent.py#L333

dvbuntu commented 3 years ago

Looking through psolgent.py some more, would you mind if I put together a PR for this and other minor things (way nodes are sorted could break if ZZ is a node name, making position of source and sink node always "on", etc)?

torressa commented 3 years ago

Hey @dvbuntu Thanks for checking! Great spot, that is a mistake. Of course I'd be happy for a PR :)

dvbuntu commented 3 years ago

Hmm, is the setting of the lower and upper bound on the position values correct? This is really only used during initialization, but the code now forces these to be U(0,1). While the sig values are bounded this way, the actual positions are arbitrary reals. Obviously there needs to be some reasonable bounds for initialization, but the PSOLGENT paper doesn't seem to describe what they used.

Maybe changing this to +-2 to make it symmetric and clear that the values are not necessarily bounded by 1 would be preferable?

https://github.com/torressa/cspy/blob/083f25c22d61ec2b5b2b1455839eb1e0a33f1e90/src/python/algorithms/psolgent.py#L138

torressa commented 3 years ago

The paper does specify for example the rand coefficients to be U(0,1), and the initialisation for the velocity to be zeros. Other than that I can't seem to find any info on the bounds. I think I just used what I saw in a test in Solid (repo linked at the top of the file, test here) so as to avoid specifying lower/upper bounds for each problem.

My suspicion is that it will be may vary from problem to problem but I don't really understand what the implications/limitations.
Maybe we could have some default values (low=[0,..,0], up=[1,..,1]), but also let the user set them too.

dvbuntu commented 3 years ago

Default values with optional arguments sound good. And I wrote to Dr. Marinakis from the PSOLGENT paper to see if he'll weigh in on what they used.

My understanding of PSO (and really most metaheuristics) is that ideally one covers the search space more or less uniformly with the initialization. In the case of PSOLGENT, our search space is R^n for the positions (which when put the sigmoid become values in (0,1)). We can't cover the whole thing uniformly, but I think an interval symmetric about zero is a good default. Not a big deal either way since it will be specifiable.

torressa commented 3 years ago

Ahh that's a good shout!! Didn't think to do that... That makes sense! I think the velocity was U(-1,1)

dvbuntu commented 3 years ago

I like the way you have the velocities set with U(lower-upper, upper-lower), but the PSOLGENT paper I'm seeing initializes them to zero (last sentence of first paragraph of section 4), unless you mean for generic PSO. Honestly probably doesn't make a big difference, and they don't necessarily describe why they choose these values anyway. Do you think it's worth adding another parameter to enable zero initial velocity? My inclination is no, but it's easy to add.