Brachistochrones - Jacob Slack
PHYS 210 PROJECTS --> here
My project is tentatively on determining various brachistochrone curves using a genetic algorithm. I say tentatively because the genetic algorithm I am developing is going to be very general, and I may have time to tackle other problems (see possible extensions)
brachistochrones
A brachistochrone means "shortest time". It is a curve that minimizes the travel time between two points for a point particle along it subject to certain forces (e.g. gravity). For a particle subject only to constant gravity in the vertical direction, the brachistochrone connecting two points is a portion of a cycloid. This can be shown precisely by solving the Euler-Lagrange equation. For more complex situations\ (e.g. with non-conservative forces), the solution cannot be easily obtained analytically and we must turn to numerical techniques.
Ooooh, I just thought of a neat application: as I'm sure you know, a straight tunnel between any two points on the surface of a uniform sphere (e.g. the Earth, approximately) will yield the same transit time to a frictionless capsule (e.g. train) without any added energy. For the Earth (treated as a uniform sphere) the transit time is 42 minutes (Doug Adams, are you listening?). The question is, can you do any better than a straight line? I.e. is there a faster path than a "chord" for such a tunnel train going between two points not on opposite sides of the Earth? I suspect not, but it would be cool to prove this. --- Jess 21:46, 18 October 2008 (PDT)
genetic algorithm
A genetic algorithm uses darwin's principle to optimize some function. As applied to brachistochrones, here are the steps:
- Generate initial population of candidate curves randomly (i.e. picking random connecting points and representing this curve by some encoding.This encoding is the curve's "DNA")
- Rank all of the functions according to some fitness value (for brachistochrones, the travel time along the curve). I will actually need to experiment with different forms of this fitness value. It may be necessary to, for instance, add penalties for certain qualities that wouldn't show up in a straight cost calculation (like false "convergence viruses" other types of false convergence) --S90584079 22:56, 22 October 2008 (PDT)
- Eliminate the weakest (i.e. longest travel time)
- Pick pairs of the surviving elite curves, and mate them (cross over sections of their DNA to produce two elite offspring with a mix of DNA from the two parents)
- mutate the offspring DNA (typically by a small amount just to make sure new genes are introduced and the gene pool doesn't stagnate)
- repeat steps 1-5 an arbitrary number of times.
details of implementation
This problem lends itself to a highly object oriented programming language. I chose java because of the portability and my familiarity with it. Here are steps I see myself completing the project in:
- Create general environment for the genetic algorithm
- Test genetic algorithm on a few base cases (e.g. try to recreate cycloid)
- Investigate other brachistochrones
- Possible Extensions.
progress
Into step 2. Compiling some benchmark data for very simple cases (like finding a straight line) and how the population dynamics respond to changes in various conditions (i.e. mutation rate, mating success rate, various forms of fitness expressions, inserting good and bad chromosomes, initial conditions, etc..). I will post some fancy graphs soon somewhere (maybe here isn't appropriate). Javadocs have also been updated --S90584079 22:49, 22 October 2008 (PDT)
I am in the thick of stage two, and my program generates better than optimal solutions! Tune in for more! --S90584079 19:57, 27 October 2008 (PDT)
I have discussed with Philip the possibility of using my genetic algorithm for calculating equilibrium configurations for his Dyson Spheres/Rings. This would be done by using a genetic algorithm to optimize gravitational potential.
