Measuring Fitness in Genetic Programming Functionology

I recently begun working on a genetic algorithm to solve for patterns in data. More specifically, it solves for functions given a sample of ins and outs. So a possible solution would be X+2 = Y. The problem is scoring.

I began by trying to use the distance between the result and the expected result as a way of measuring fitness. The problem is the difference is not a reflection of the distance from a correct solution.

So the question: Given a random set of values, is it possible to measure how many operations(+,-,/,*) it would take to get to an certain number without using brute force. And of course, if so how?

EDIT The random set will always contain {0,1,2}.

I don't know how to solve your original problem, but I can describe how to solve a simpler version of it. Given numbers $a_1,\dots,a_n$ and a target $y$, if you only allow operations +,-, you can count how many operations it will take to reach $y$.

In particular, this amounts to asking for integers $x_1,\dots,x_n$ such that

$$a_1 x_1 + \dots + a_n x_n = y,$$

while minimizing $|x_1| + \dots + |x_n|$.

This can be solved using integer linear programming. Introduce variables $w_1,\dots,w_n$ and the constraints $w_i \ge 0$ and $-w_i \le x_i \le w_i$ as well as

$$a_1 x_1 + \dots + a_n x_n = y,$$

and then minimize the objective function $w_1 + \dots + w_n$.

While integer linear programming is NP-hard in the worst case, when the numbers aren't too large, I expect that this will yield an efficient solution.

Introducing the *,/ operators makes your problem much harder.

To deal with your full problem, you might consider using the A* algorithm. For instance, you might build a heuristic function that estimates the distance to the target by using integer linear programming to get an overestimate of the distance to the target (you know that the distance using +,-,*,/ operators will be at most the distance using +,- operators, and the latter you can compute efficiently using ILP). I don't know for sure whether this will work well or not, but it's something you could try.

• Thank you, I your presentation of the problem for subtraction and addition enabled me to find a solution for that case. I haven't looked at the A* algorithm yet. Will do so soon. Forgot to mention that 0,1, and 2 will always be available if that changes anything. – BlueCow Oct 7 '16 at 2:27