search

caigaoub / PhysarumOptimization

Physarum solver; Acceleration Strategies;
4 stars 0 forks source link

Information regarding the Python implementations #2

Open co-ord opened 3 years ago

co-ord commented 3 years ago

Dear @caigaoub ,

Thank you for providing an access to your work, this is extremely helpful and instructive.

A few questions:

Screenshot 2020-11-19 114043

Increasing the food amount to -2.2 (on line 37 and 39 of your script) somehow made possible to extend the paths but it is still impossible to distinguish which one is the shortest path, even when applying the corresponding width to the edges.

Screenshot 2020-11-19 124305

caigaoub commented 3 years ago

Hi there, Sorry to ask, may I know who I am talking to? thanks. Q1. well, i only have the matlab version of fast physarum solver. But you should be able to modify the python code (which is for classic physarum solver) i put there with reference to the matlab code.  Q2. The implementation of the paper you mentioned can be found in APS folder and is only in Matlab. Q3. According to my experience, there is no need to fine-tune the classic physarum solver. Maybe you should check the stopping criteria in physarum_solver.py, i.e., change the number of iterations and make it 1000, or inf, or remove it. But fast physarum solver should solve your problem significantly faster than the classic one. Q4. i am not sure but i think the answer is quite positive.

Let me know if you have any questions. Cai

co-ord commented 3 years ago

Thank you for the swift reply.

I'm a creative coding hobbyist, located in France, just trying to replicate the "Tokyo Railway Network" experiment for fun and knowledge. (I can provide you with my contact details by email if necessary). English is not my first language so please let me know if there was something off with the way I formulated my question.

1/ I will do my best to so, even though I'm no expert in vectorized computation with Numpy and have no experience with MATLAB.

2/ I'm a little bit surprised to hear that physarum_solver.py is an implementation of the classical physarum solver since it doesn't seem to follow the exact routine described in the original paper by Tero Atsuhi + some references seem to be missing or changed (gamma value, IO).

3/ Even with 2000+ iterations, the output data remains unchanged displaying a variety of starting paths unable to connect. I would tend to think that increasing the iteration count wouldn't solve the problem but, of course, I can be wrong.

4/ Really looking forward to test that out.

Thank you for your willingness to help, it means a lot !

caigaoub commented 3 years ago

Hi,

thank you for your interest. Your questions are very clear to me.

the python is not totally same as the paper. Definitely you can modify it but i don’t think it would make a big difference.

did you try small size network ? say 10*10 ? does it work ?

On Thu, Nov 19, 2020 at 08:51 solub notifications@github.com wrote:

Thank you for the swift reply.

I'm a creative coding hobbyist, located in France, just trying to replicate the "Tokyo Railway Network" experiment for fun and knowledge. (I can provide you with my contact details by email if necessary). English is not my first language so please let me know if there was something off with the way I formulated my question.

1/ I will do my best to so, even though I'm no expert in vectorized computation with Numpy and have no experience with MATLAB.

2/ I'm a little bit surprised to hear that physarum_solver.py is an implementation of the classical physarum solver since it doesn't seem to follow the exact routine described in the original paper by Tero Atsuhi + some references seem to be missing or changed (gamma value, IO).

3/ Even with 2000+ iterations, the output data remains unchanged displaying a variety of starting paths unable to connect. I would tend to think that increasing the iteration count wouldn't solve the problem but, of course, I can be wrong.

4/ Really looking forward to test that out.

Thank you for your willingness to help, it means a lot !

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/caigaoub/PhysarumOptimization/issues/2#issuecomment-730389313, or unsubscribe https://github.com/notifications/unsubscribe-auth/AH2SXBQSLDNHNWKXR6H3BT3SQUPGPANCNFSM4T3JLMFA .

--

Operations Research, University at Buffalo, SUNY

co-ord commented 3 years ago

On a 40*40 grid, I tried to increase the number of iterations but even after 20000 passes nothing changes.

Screenshot 2020-11-20 201939

On a 10*10 grid, the algorithm stops automatically at 328 iterations with the following result:

Screenshot 2020-11-20 202430

Paths are connecting but branches are still apparent and no shortest path can be found.

2 questions:

Ideally, I would like to have the algorithm (this one or another version) running on a grid no smaller than 30*30 so I can fit and differentiate between all the major train stations in the area of Tokyo.

An example based on a modified Urquhart graph for clarity:

Screenshot 2020-11-20 204532

caigaoub commented 3 years ago

Hi,

Sorry for the late reply. From the 10*10 graph, the paths that the algorithm finds are those shortest paths, right? One thing you probably realize is that physarum solver can find all shortest path by assigning equal flow to each of them. Say, there are 10 shortest (optimal) paths, the flow for each is total input flow /10.

the figures above are beautiful. If you don't mind, can you send me the code of generating these graphs (i guess it is python) so i can work on my end when i have time. my email is caigao@buffalo.edu

thanks

Cai

On Fri, Nov 20, 2020 at 2:48 PM solub notifications@github.com wrote:

On a 40*40 grid, I tried to increase the number of iterations but even after 20000 passes nothing changes.

[image: Screenshot 2020-11-20 201939] https://user-images.githubusercontent.com/28729303/99840979-c31fc180-2b6d-11eb-93c3-eafe89cdffd8.png

On a 10*10 grid, the algorithm stops automatically at 328 iterations with the following result:

[image: Screenshot 2020-11-20 202430] https://user-images.githubusercontent.com/28729303/99841404-6a045d80-2b6e-11eb-9fe4-bc1498ea19e3.png

Paths are connecting but branches are still apparent and no shortest path can be found.

2 questions:

-

Have you ever tried this algorithm on grids/networks composed of more than 100 nodes ?

If the grid size has an impact on the ability for nodes to connect, shouldn't it mean that some of the parameters should be changed accordingly ? (ex: larger grid size -> more food)

Ideally, I would like to have the algorithm (this one or another version) running on a grid no smaller than 30*30 so I can fit and differentiate between all the major train stations in the area of Tokyo.

An example based on a modified Urquhart graph for clarity:

[image: Screenshot 2020-11-20 204532] https://user-images.githubusercontent.com/28729303/99843231-835ad900-2b71-11eb-949b-550653c4545c.png

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/caigaoub/PhysarumOptimization/issues/2#issuecomment-731373729, or unsubscribe https://github.com/notifications/unsubscribe-auth/AH2SXBUSJGJTTLQQZ3VE2R3SQ3BXVANCNFSM4T3JLMFA .

--

Operations Research, University at Buffalo, SUNY

co-ord commented 3 years ago

My apologies for the late reply, I just sent you the files via email although I'm not sure they will be of interest to you as they require Processing to be installed on your machine to be run.

One question: What would you change to physarum_solver.py in order to compute, not the shortest path between 2 nodes, but the most efficient network between a whole series of nodes ?

I tried to pick a random pair of source-sink nodes at each iteration but the final results are impossible to interpret for 2 main reasons:

caigaoub commented 3 years ago

Hi,

Thanks for sending me those files. I will work on that.

To design the "most" efficient network, you can go check the paper of my friend Xiaoge Zhang: https://www.nature.com/articles/srep10794 . I am sure you will get some insights of how to simulate the Tokyo railway network using physarum. Let me work on the physarum_solve.py code and get back to you soon.

Thanks

Cai

On Fri, Nov 27, 2020 at 9:27 AM solub notifications@github.com wrote:

My apologies for the late reply, I just sent you the files via email although I'm not sure they will be of interest to you as they require Processing https://processing.org/ to be installed on your machine to be run.

One question: What would you change to physarum_solver.py in order to compute, not the shortest path between 2 nodes, but the most efficient network between a whole series of nodes ?

I tried to pick a random pair of source-sink nodes at each iteration but the final results are impossible to interpret for 2 main reasons:

  • multiple branches not connecting (no apparent paths)
  • no consistent outputs (totally different at each run)

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/caigaoub/PhysarumOptimization/issues/2#issuecomment-734860210, or unsubscribe https://github.com/notifications/unsubscribe-auth/AH2SXBUYPBDTL4JSWLEXTQDSR6ZMBANCNFSM4T3JLMFA .

--

Operations Research, University at Buffalo, SUNY