1 unstable release
0.1.3 | Feb 11, 2020 |
---|
#470 in Science
160KB
1K
SLoC
GRACO
Generalized Rust Ant Colony Optimization
Warning: This is a probabilistic algorithm for exploring graphs. The parameters of the run are very important, and choosing different parameters may not lead to the same solution. Even running the same parameters twice might not lead to the same solution!
Usage
- Download the binary if available for your platform. If not, go to the Build section.
- Execute from a terminal / command prompt. Use the
-h
flag to display the help - Set the
RUST_LOG
environment variable toinfo
to display the iterations as they happen, or todebug
if debugging.
Please refer to the help for details on each parameter.
Defining the graph
The graph must be defined with the following structure: NODE_1 NODE_2 EDGE_WEIGHT
, where the nodes are strings of characters without any space and the edge weight is a floating point value. Each item is separated by exactly one space.
Although that weight may be negative, it is important to note that the ACO will minimize the total weight of the edges.
Examples
Using the seed
parameter
In order to help the reproducibility of results, it is possible to specify a seed for the pseudo random number generator.
However, if the tool runs on several CPUs, there is no guarantee that this reproducibility will work the same way each time because the order in which threads are spawned cannot be guaranteed. [link] This code tries to help the operating system to order these threads, but it will depend on what the computer is doing at any given time.
In an example case, using the same parameters and seed for three subsequent runs returned the optimal path of 8.1. But running six more with the --cpus
flag set to 7 (on an 8 core machine) returned once a bad path (8.9), one two suboptimal ones (8.2) and three the optimal one.
Useful run
chris@linux-fgdx ~/Workspace/rbin/graco issue-3 ●✚ RUST_LOG=graco=info cargo run -- -v complete_graph.txt --wander 0.15 --ants 10 -i 100 --seed 4580147489518812583 --cpus 1
Finished dev [unoptimized + debuginfo] target(s) in 0.09s
Running `target/debug/graco -v complete_graph.txt --wander 0.15 --ants 10 -i 100 --seed 4580147489518812583 --cpus 1`
[2019-05-21T22:24:16Z INFO graco::io] Loaded graph from `"complete_graph.txt"`
[2019-05-21T22:24:16Z INFO graco::colony] Seed: 4580147489518812583
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 1
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 2
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 3
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 4
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 5
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 6
[2019-05-21T22:24:16Z INFO graco::colony] Completed iteration 7
[2019-05-21T22:24:16Z INFO graco::colony] Stagnation reached
iterations: 8
weight: 8.1
path: ["S", "A", "D", "B", "C"]
chris@linux-fgdx ~/Workspace/rbin/graco issue-3 ●✚
Problems with probabilities
Here, we run the same program three times in a row with the exact same parameters, yet we find three different solutions!
In the following, we let 10 ants wander with a probability of 0.15 for 100 iterations, setting an evaporation rate of 0.2.
chris@linux-fgdx ~/Workspace/rbin/graco master ● RUST_LOG=graco=info cargo run -- -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2
Finished dev [unoptimized + debuginfo] target(s) in 0.07s
Running `target/debug/graco -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2`
[2019-05-20T21:57:49Z INFO graco] Running on 8 CPUs
[2019-05-20T21:57:49Z INFO graco::io] Loaded graph from `"complete_graph.txt"`
[2019-05-20T21:57:49Z INFO graco::colony] Completed iteration 1
[2019-05-20T21:57:49Z INFO graco::colony] Completed iteration 2
[2019-05-20T21:57:49Z INFO graco::colony] Completed iteration 3
[2019-05-20T21:57:49Z INFO graco::colony] Stagnation reached
iterations: 4
weight: 9.8
path: ["S", "C", "A", "B", "D"]
chris@linux-fgdx ~/Workspace/rbin/graco master ● RUST_LOG=graco=info cargo run -- -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2
Finished dev [unoptimized + debuginfo] target(s) in 0.08s
Running `target/debug/graco -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2`
[2019-05-20T21:57:53Z INFO graco] Running on 8 CPUs
[2019-05-20T21:57:53Z INFO graco::io] Loaded graph from `"complete_graph.txt"`
[2019-05-20T21:57:53Z INFO graco::colony] Completed iteration 1
[2019-05-20T21:57:53Z INFO graco::colony] Completed iteration 2
[2019-05-20T21:57:53Z INFO graco::colony] Completed iteration 3
[2019-05-20T21:57:53Z INFO graco::colony] Stagnation reached
iterations: 4
weight: 9.7
path: ["S", "B", "A", "C", "D"]
chris@linux-fgdx ~/Workspace/rbin/graco master ● RUST_LOG=graco=info cargo run -- -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2
Finished dev [unoptimized + debuginfo] target(s) in 0.09s
Running `target/debug/graco -v complete_graph.txt --wander 0.15 --ants 10 --density 3 -i 100 -e 0.2`
[2019-05-20T21:57:54Z INFO graco] Running on 8 CPUs
[2019-05-20T21:57:54Z INFO graco::io] Loaded graph from `"complete_graph.txt"`
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 1
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 2
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 3
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 4
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 5
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 6
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 7
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 8
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 9
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 10
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 11
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 12
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 13
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 14
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 15
[2019-05-20T21:57:54Z INFO graco::colony] Completed iteration 16
[2019-05-20T21:57:54Z INFO graco::colony] Stagnation reached
iterations: 17
weight: 8.1
path: ["S", "A", "D", "B", "C"]
chris@linux-fgdx ~/Workspace/rbin/graco master ●
Build
- Install Rust: https://www.rust-lang.org/learn/get-started
Dot graphs
When running in verbose mode, the pheromone graph will be output as a .dot
file, which can be converted to an image by graphviz.
Dependencies
~7–15MB
~181K SLoC