Implement a genetic algorithm that can handle an arbitrary number of images

[ravicious]

Photo Layout with a Fast Evaluation Method and Genetic Algorithm by Jian Fan describes a genetic algorithm for making collage layouts which perfectly fits our needs.

However, in order to actually implement the algorithm, we need to take care of some other stuff first.

• Write a Wasm prototype that uses a genetic programming crate.
  • The crate will be probably either genevo or rsgenetic, probably best to evaluate them both.
  • Check if either of them works without any rayon-enabled features.
    • If it does then we can skip the next main point and go straight to writing the algorithm, adding parallelization later to make the algorithm faster.
  • We might need to use wasm-bindgen-rayon, because both of those crates depend on rayon, which doesn't work in Wasm OOTB.
• Implement randomized generation of layout tree (III.A).
• Implement the fast layout solver (III.B).
• Translate the random layout into an actual image.
  • I didn't think too much about it yet, but going from the tree to an actual bitmap will certainly require some thinking.
  • The first idea that came to my head was to treat each internal node as a separate canvas. We can calculate the size of each internal node. Going deeper in the tree is just going to shift the coordinates on the root canvas on which a particular internal node operates. So first we go to a bottom node and then make our way up.
• Implement the cost function (III.C).
  • We don't need to care about desired image size for now, all images will have the same weight.
• Implement the genetic operators (III.D)
  • This will probably be the most time consuming step, as far as the genetic algorithm is concerned, because it involves tree operations and I need to read more about that, never done that in Rust.
• Use the previous steps with a genetic programming crate to let the algorithm create a better layout.
• (Not needed for now) Rewrite the current code to use --target web rather than --target no-modules.
  • wasm-bindgen-rayon works only with --target web.
  • OTOH, Firefox doesn't support module workers yet, so in order for it to work with --target web and no bundler, we have to use module-workers-polyfill as described in wasm-bindgen-rayon readme.
• (Not needed for now) Add wasm-bindgen-rayon and increase population size.

III.B and III.C might need to be slightly changed. The original algorithm treats the resulting canvas size as the input, whereas we don't know the size upfront and just want to optimize for the biggest one. Perhaps the cost function will need to control the trade-off between canvas size and coverage of canvas area by images.

[ravicious]

• genevo works under Wasm after making a couple of changes.
  • This crate can run on wasm32 with a little modification. innoave/genevo#16 (comment)
• rsgenetic has a PR with Wasm support, but the last comment in that PR was made in September 2018.
  • seq WASM compatibility m-decoster/RsGenetic#33