evolution of a Brachystochrone

The goal is to optimize the track between a start- and an endpoint in such a way that the time a moveable point sliding down the track needs to reach the end of the track becomes minimal. The point moves frictionless by means of his own gravity.

evolving a Brachystochrone using evolution strategy

  • ES - interface help
  • Evolution Strategy Theory should be an applet here

    evolving a Brachystochrone using genetic algorithms

  • GA - interface help
  • Genetic Algorithms Theory should be an applet here

    Evolution of a Brachystochrone - Problem Info

    The goal is to optimize the track between a start- and an endpoint in such a way, that the time a moveable point sliding down the track needs to reach the end of the track becomes minimal. The point moves frictionless by means of his own gravity and its velocity is 0 at the startpoint.

    chromosome (genotype representation)

    The track is modelled by lines through successive trackpoints.

  • evolution strategy
    The brachystochrone was encoded using 2 double values per trackpoint: the position (x,y) of the trackpoint. Thus each chromosome consists of 2*n double values, if n is the number of track points. 

      // 10 trackpieces => 9 inner trackpoints
  double object_parameters[]= {10,10, 20,20, 30,30, 40,40, 50,50, 
                               60,60, 70,70, 80,80, 90,90, 100,100, 110,110 };
  double strategy_parameters[] = {0,0, 0,1, 0,1, 0,1, 0,1,     
                                  0,1, 0,1, 0,1, 0,1, 0,1, 0,0 }; 
    
 As we want to optimize the height of the tracks inner points all but the y-positions
 of the inner track points have a strategy parameter of 0.
  • genetic algorithms (bitvector)
    Only the y-positions of the inner tack points are encoded in the chromsome. 
       // 10 trackpieces => 9 inner trackpoints => 9*10 bit gray-encoded bit-vector
   [ [010011110],[011000110],[110100001],[010111011],[101111001], 
     [101011001],[010011101],[011000011],[001111001] ]

    • drawing the chromsome (phenotype representation)

  • evolution strategy and gentic algorithms
    draw a polygon through track-points

    • quality function

    The time a moveable point P needs, to slide frictionless on a track from a startpoint to an endpoint, driven by means of his own gravity shall become minimal, by optimizing the track between start and end.

    ti is the time needed to slide down the track from (xi,yi) to (xi+1,yi+1);
    ti is calculated by integrating the acceleration:

    If the point on track-piece i is accelerated by ai we get its position, after being accelerated for a time t, if we have its initial velocity vi and its initial position xi.
    By inserting ai and li,j we get:
    and we solve this for t, to get ti;

    applet parameters