brachystochrone problem


To practice with implementations of GAs I’ve decided to use a classical problem posed by the great mathematician Jakob Bernoulli in 1696. The brachystochrone problem. The objective is to find an optimal planar curve between a higher starting point (x0, y0) and a lower destination point (xk, yk) in such a way that the time a movable object needs to travel along the track becomes minimal. The problem assumes a point mass which moves frictionless (maybe later we can extend the problem to several friction patterns and see how adapts the algorithm) by means of its own gravity and has zero velocity in the beginning.

A candidate curve is approximated by a polygon defined by a set of k+1 succesive track-points (xi, yi). For simplicity, we assume a constant horizontal distance Δx among the track-points, so that only the k-1 y-positions of the inner track-points (x1, y1), …, (xk-1, yk-1) are subject to optimisation.

Hows does the GA encode these heights y1, …, yk-1 into a chromosome? The chromosome C in the GA is usually a binary encoded string s0, …, sN, with the bit si ∈ {0,1}. The first parameter y1 can acquire one out of 2^N possible discrete, equidistant values in the interval [ymin, ymax] encoded by the first n bits s0, …, sn-1:

y1 = ymin + ( (ymax – ymin) / (2n -1) ) * sum (from i = 0 to y = n-1) (si * 2i)

The remaining parameters are encoded in a similar fashion by the remaining sn, …, sN of the string. It is important to choose n large enough such that the discretisation provides a sufficient resolution which enables the GA to adjust the parameters yi to a desired level of accuracy.

The quality of the track is evaluated by a fitness function that computes the time a point mass needs to slide from the start to the end point. The overall time:

T = sum (i=0 to i=k-1) (ti)

the sum of times ti that pass while the point mass travels the straight line from (xi,yi) to (xi+1, yi+1) The initial velocity vi can be computed from the conservation of energy:

(1) (m * vi2)/2 = m * g * (y0 – yi)
(2) vi = sqrt (2 * g * (y0 – yi))

assuming that the velocity v0 at the start is zero. The acceleration ai along the track segment is constant and given by:

(3) ai = (g * dyi) / sqrt (dxi2 + dyi2)

where dxi = xi+1 – xi and dyi = dyi+1 – yi.

From the equations of the motion the distance of the straight line equals the acceleration and the velocity term:

(4) sqrt (dx2 + dy2) = (ai * ti2)/2 + vi * ti

and substituting (2)(3) into (4) we obtain the travel time T(Ci)

The scalar fitness function f(Ci) (Ci is chromosome i) evaluates the quality of the solution. We want to minimise the travel time. That is the fitness function will be the inverse of travel time. The individuals that reach the end-point faster receive larger fitness.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s