2
$\begingroup$

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}.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BlueCow Oct 7 '16 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.