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 22:00]
martindm [Initial Tests]
mind:atlas-evolutionary-investigation-1 [2016/05/02 22:27] (current)
martindm [Conclusions]
Line 22: Line 22:
 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. 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?100]]+[{{mind:​ga_001.png|30 initial points}}] 
 +[{{mind:​ga_002.png|50 initial points}}]
  
-{{:mind:ga_001.png?​nolink&​100|}}+== 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.1462248000.txt.gz · Last modified: 2016/05/02 22:00 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