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

1. Download the binary if available for your platform. If not, go to the Build section.
2. Execute from a terminal / command prompt. Use the -h flag to display the help
3. Set the RUST_LOG environment variable to info to display the iterations as they happen, or to debug 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

1. 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.