Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

How to quickly choose numbers and weights in such a way as to obtain a specific weighted sum? – Artificial Intelligence

I have an unordered set of digits and a set of weights, I want to match the digits to the weights in such a way that the weighted sum is a given number. Now I do it so that I put these digits into some first arrangement and check the weighted sum, then I swap the first digit with the second, if the weighted sum is closer to the expected one, then I leave it, if I don’t undo it. Then I check all the numbers one by one.

How do you find these numbers faster? There are many such comparisons, and sometimes the weighted sum of numbers resulting from a given arrangement of digits differs by 1 from the expected one and to correct it you have to change places by more than 2 digits, so my algorithm does not work, then I draw a new arrangement of digits and do everything again , the problem is that here a lot depends on the draw, if the new initial setting is favorable, the number will be found quickly, and if not, there may be a lot of such draws.

Can me use artificial intelligence or a neural network or something?

Tags:

2

Answers


  1. 0

    I know you tagged your answer C#, but I did not feel like opening visual studio and python should help you grasp it just as well.

    I have simply done what I suggested in my comments: Run a brute-force algorithm:

    import itertools
def solve(given_weights, numbers, given_sum):
    all_combinations = [zip(x,given_weights) for x in itertools.permutations(numbers, len(given_weights))]
    for combination in all_combinations:
        tuplified = [tuple(x) for x in combination]
        if weighted_sum(tuplified) == given_sum:
            return tuplified
    return None

def weighted_sum(combination):
    return sum([x[0] * x[1] for x in combination])

    And when I run it with six weights, it is quick enough for me not having to wait:

    python
Python 3.7.3 (default, Mar 27 2019, 17:13:21) [MSC v.1915 64 bit (AMD64)] :: Anaconda, Inc. on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> given_weights = [1,2,3]
>>> numbers = [4,5,6]
>>> from tmp import *
>>> weighted_sum(zip(given_weights, numbers))
32
>>> solve(given_weights, numbers, 32)
[(4, 1), (5, 2), (6, 3)]

>>> weighted_sum(zip([1,2,3,6,5,4],[10,11,12,12,14,15]))
270
>>> solve([1,2,4,5,6,3], [15,14,12,12,11,10], 270)
[(12, 1), (12, 2), (11, 4), (14, 5), (15, 6), (10, 3)]

    So I say just stick with the simple approach of brute-forcing it.
    When I run it with nine numbers and nine weights, it takes about 2seconds though. So this approach really depends on the number of numbers you have.

    Login or Signup to reply.
  2. 0

    An approach to solve this problem is to use a hybrid solution of gradient descent and a genetic algorithm.

    Here I am starting with a ordered set of factors (double[][]) and filtering those so that I keep the best weights.Length. I then generate from those best solutions so far a set of mutations where I swap one element from each position with a randomly chosen position in the array. So if I start with a single double[] of length 24 then I end up with 24 double[] arrays of length 24 where each array differs by having two elements of each array swapped. This creates a larger number of guesses and I then loop doing this process until one solution is within a delta that is acceptably close to the answer.

    var weights = new [] { 0, 1, 2, 3, 3, 5, 6, 7, 7, 8, 8, 9, 10, 11, 12, 13, 13, 13, 14, 17, 17, 18, 19, 19 }.Select(x => (double)x).ToArray();
var factors = Enumerable.Range(1, weights.Length).Select(x => (double)x).ToArray();

var goal = 83.0833333333333;
var delta = 0.000001;

var rnd = new Random();

var pool = new [] { factors };

double[] swap(double[] array, int n, int m)
{
    var output = array.ToArray();
    var t = output[n];
    output[n] = output[m];
    output[m] = t;
    return output;
}

double score(double[] sample) => sample.Zip(weights, (x, w) => x * w).Sum() / weights.Length;

double[][] generate(double[][] current)
{
    var best = current.OrderBy(xs => Math.Abs(score(xs) - goal)).Take(weights.Length).ToArray();
    var guesses =
        best
            .SelectMany(xs => Enumerable.Range(0, weights.Length), (xs, n) => swap(xs, n, rnd.Next(weights.Length)))
            .ToArray();
    return guesses;
}

while (!pool.Where(xs => Math.Abs(score(xs) - goal) < delta).Any())
{
    pool = generate(pool);
}

var result = pool.Where(xs => Math.Abs(score(xs) - goal) < delta).First();

    The figure I’ve used for goal is the minimum possible weighted average. In this example the code effectively has to reverse the order of the original factors array. It does that in 0.019 seconds on my pc.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search