Hi mates from tbs,
A few days ago a friend came to me, saying he has a problem. The problem is that in his work, he works with balance and accounting stuff, and sometimes some balances dont match. When that happens, he must get a lot of things and start adding them to see which of them gives that different between balances. So he asked me to write a lil algorithm (he cant program, he doesnt know how to) to do this task :
(Very similar to TBS Story III from programming):
Given a certain number, lets say 10, you get a lot of numbers and you must say which of them added together returns the number you are seeking (in this case 10).
So, 10 is the number we are looking for, and the other numbers are 3,3,2,1,3
The solution in this case would be 3+3+1+3=10, no other combination is possible to form a 10.
This is what I need to do for him, and when you start writing the code, you'll note it is more difficult than it looks .....

He manages numbers like 1.389.846.364 and then he has about 30 or maybe more accounts, so he needs to know which of those accounts added together returns that huge number.
Did you get the idea? Sorry for my bad english, im really tired right now.
Any reply will be very apreciated

See you guys

hess

PS: If you do the algorithm in a "combinatory" way, it wont work, could take years to find the right combinations(thats if we are talking about 500 accounts, that might happen too , and dont forget you can get bigger numbers than the one you are looking for, because you can also receive negative numbers.... )

Hai there Hessiann!

The first thing that came to my mind when I read this is a genetic algorithm approach. I think that could give you a fast answer. I'm going to run a test right now, see what I get!

Back with results!

I'm having kind of nice results using a genetic algorithm and a bit of local search. In just some seconds I get a result for 500 account balances, but I see a problem: none of them use the same accounts that the provided solution uses to get the balance, but the balance matches. That means that, as expected, there may be more than one solution to this problem.

So maybe a genetic algorithm is not what you want, because you might want to be able to get all solutions, am I right?

Wow, you are a doing an incredible work there....Thx a lot!
Well it would be nice to have all the results...but you see, those numbers are quite different from eachother.....they are not low values, they are all values like 2582, 460000, -460000....etc, and they form a huge number, also with decimals, so my friend thinks that there are very low probabilities of getting more than one solution, but once again, those are numbers, it could happen.
Btw, what is a genetic algorithm? Im not familiar with the term, and what language are you using to test it?

Thx again for your time and effort

You're welcome!

Well I've just tried with random positive integers, but I see no problem for it to work for random positive/negative floats aswell.

A genetic algorithm is a type of iterative improvement algorithm which mimics the process of natural evolution (definition almost shamelessly copied from wikipedia, much more info there). The most simple version goes like this:

generate random population of individuals
while the best of them is not good enough do:
    choose some of them as "parents" of the next generation (usually among the best)
    create new individuals from those parents
    mutate some of those new individuals (random changes)
    kill some individuals of the population

So in my implementation, the individuals are arrays of booleans, which indicate if the given account is used to compute that individual's balance. The "fitness" function (which evaluates how good that individual is, and generally affects its survivability) is the difference between its balance and the target balance (the closer, the better).

In each iteration of my algorithm (by definition called a "generation"), two parents are chosen, creating 2 new individuals, mutating them a little and finally killing the two worst individuals in the population. That goes on until the target balance is reached.

The local search I talked about is performed for each new individual in the population. It tries to exclude one account and include another to see if it gets the individual closer to the target balance. That way you don't have to wait for that miraculous mutation that would make your individuals perfect.

Given the random nature of the algorithm, it is usually a good practice to run it several times and choose the best result among all of them.

I usually use Java when I think I can get an answer fast enough, or when I have to make a quick test. Used Java with this because it fits both criteria If you are interested in the code itself, tell me and I will send it to you!

Hope to have helped

[EDIT] Made a little modification and the result is now almost instantaneous for 500 accounts. The local search is now what you would call God in this algorithm

Excellent! Of course I am interested in having the code, if thats no problem for you!
You can contact me at mhpetringa@gmail.com
We can chat in there and you can show me how it works.
Thank you for your effort and help!

hess