Solving the Brachistochrone Problem with Genetic Programming

摘要

The brachistochrone problem seeks the path in a uniform gravitational field through which a weighted particle falls most quickly from one point to another. The optimal path has long been known to be a segment of a cycloid, the curve traced by a point on a rolling circle. Genetic programming seeks to automatically evolve a program that solves a target problem. It maintains a population of representations of candidate programs and manipulates them with operators inspired by the mechanisms of biological evolution. A genetic programming approach to the brachistochrone problem uses the four arithmetic operations in functions that describe curves between two points. These functions' fitnesses are the times a particle requires to fall along the curves they describe, with a penalty added if they miss the destination point. Given a starting point and a destination, this approach yields a close approximation of the optimal cycloid.