# 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! !["cabaran" is licensed under CC0 1.0](./logo-cc.png "cabaran is licensed under CC0 1.0 ") ## Usage 1. Download the binary if available for your platform. If not, go to the [Build](./#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]](https://doc.rust-lang.org/book/ch16-01-threads.html#creating-a-new-thread-with-spawn) 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. ![Initial graph](pheromones_it_0.dot.png) ![Final graph](pheromones_it_16.dot.png)