Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
mind:atlas-evolutionary-investigation-1 [2016/05/02 21:50]
martindm [Problems with GAs]
mind:atlas-evolutionary-investigation-1 [2016/05/02 22:27] (current)
martindm [Conclusions]
Line 17: Line 17:
 * GAs generally are slow to converge for large problems spaces: Tile-based level design is indeed a large problem space (trillions or quadrillions of raw variations). * GAs generally are slow to converge for large problems spaces: Tile-based level design is indeed a large problem space (trillions or quadrillions of raw variations).
 ** We seek to mitigate this in Atlas by using very deliberate, intentional mutations (rather than random), and very deliberate, intentional selection of which components to mutate (rather than a fixed proportion or random selection). For example, when trying to space nodes of a flowMap evenly, Atlas might only mutate offending nodes (nodes that are too close), rather than picking them at random. This should achieve much faster convergence. ** We seek to mitigate this in Atlas by using very deliberate, intentional mutations (rather than random), and very deliberate, intentional selection of which components to mutate (rather than a fixed proportion or random selection). For example, when trying to space nodes of a flowMap evenly, Atlas might only mutate offending nodes (nodes that are too close), rather than picking them at random. This should achieve much faster convergence.
 +
 +== Initial Tests ==
 +
 +To quickly test some of these methods, I wrote a brief genetic algorithm that simply places nodes of a flow-map on the screen (no connections between them), and tried to space them out so that no two were adjacent. This was straightforward,​ but a pure-random mutation and crossover resulted in a long convergence time (dozens or hundreds of generations). I then compared this with very deliberate mutations (only selecting offending nodes that were too close, and only nudging them one space in a random direction). The latter method achieves convergence in 5-6 generations.
 +
 +[{{mind:​ga_001.png|30 initial points}}]
 +[{{mind:​ga_002.png|50 initial points}}]
 +
 +== Something Trickier ==
 +
 +Now how hard would it be to increase the complexity of the criteria? Instead of preserving space between nodes, let's try aligning all nodes horizontally and vertically with one another. In this test, the goal was to get nodes which keep exactly 1 tile between themselves and their neighbors, and want to be vertically or horizontally aligned.
 +
 +Using smart mutations (rather than random), and selecting only offending nodes to mutate, this was accomplished in less than 50 generations:​
 +
 +[{{mind:​ga_003.png|Alignment task}}]
 +
 +== Conclusions ==
 +
 +Using deliberate domain-specific mutations, we can achieve extremely efficient exploration of a space on simple tasks. If we can break down flow generation into a series of these simple tasks, then we can do flow generation quite cheaply.
 +
 +I need to do experiments on a full flowMap involving global properties such as branching factor, connections,​ segment length, angle, etc. One of the tricky parts of evolutionary algorithms is selecting a fitness function that is reasonably cheap to compute. Global fitness functions tend to be quite expensive on complex domains. However, I think I can mitigate this by using global properties which can be computed on-line (that is, they don't need to be re-evaluated from scratch. Each small change can incrementally update the properties listed above).
mind/atlas-evolutionary-investigation-1.1462247424.txt.gz ยท Last modified: 2016/05/02 21:50 by martindm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0