Fitness

We want to apply the technique of genetic programming to finding Lyapunov functions, where the tree structures represent potential Lyapunov functions. The population will evolve (we hope) until a Lyapunov function is produced (assuming the system is stable). But like most optimization methods, the hard part of genetic programming is not the genetic programming itself, but the evaluation of the objective function, i.e., the fitness.

The fitness of a potential Lyapunov function is a measure of its ``Lyapunovness,'' that is, how well the function satisfies the criteria for a Lyapunov function. A continuously differentiable, real-valued function $V(x)$, where $x \in\Re^n$, is is a Lyapunov function of a system $\dot x=f(x)$ that is stable at the origin if the following criteria hold for some domain $D$ containing the origin:

1. $V(0)=0$
2. $V(x) > 0 \quad\forall\; x \in D-\{0\}$
3. $\dot V(x) \leq 0 \quad\forall\; x \in D$

Should $V(0)$ be defined but not equal zero, it is easy enough to define a function $\hat V(x) = V(x)-V(0)$ that does satisfy the first criterion. (If $V(0)$ is not defined, then $V(x)$ is not a Lyapunov function and not likely to be close. The fitness of such a function is zero.) Henceforth we assume, when evaluating the other two criteria, that $V(x)$ has been corrected by subtracting $V(0)$.

Criteria 2 and 3 are applicable to the entire domain. A function may satisfy one or both of these criteria in some places, but not others. This suggests a possible measure of fitness: the percentage of the domain $D$ where these criteria hold. More specifically, the fitness could be the percentage of the domain satisfying Criterion 2 plus the percentage of the domain satisfying Criterion 3.

Unfortunately, determining this measure of fitness exactly is not easy for a computer to do. The most obvious way to approximate the fitness is numerically: evaluate $V(x)$ and $\dot V(x)$ at many points, and take the ratio of points satisfying the criteria as an approximation to the fitness. The many points could be a grid of points covering the domain $D$. Or, the points could be randomly chosen.

For this paper, I have implemented this fitness approximation using random points.