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:02]
martindm [Initial Tests]
mind:atlas-evolutionary-investigation-1 [2016/05/02 22:27]
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|ProfGoodrich ​and Joseph working on a UAV}}]+[{{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.txt · Last modified: 2016/05/02 22:27 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