Взвешенная упаковка для бин / оптимизация ранцев

Question

Я изо всех сил пытаюсь классифицировать проблему, над которой я работаю, а это означает, что я не смог выяснить, есть ли какие-либо установленные эвристические решения. Как вы думаете, что это за проблема, и как бы вы посоветовали мне ее решить?

У меня есть серия ведер A, B, C, D. Каждый из них может содержать определенное количество предметов. Общий размер ведер соответствует размеру населения. Предметы в популяции имеют оценку A, B, C, D.

Я хочу отсортировать элементы по группам так, чтобы общий счет для соответствующих групп был максимизирован; то есть баллы A для всех предметов в корзине A, баллы B для всех предметов в корзине B и так далее. Из этого следует, что в идеале предмет может находиться в ведре B, даже если его оценка A выше, поскольку может быть много предметов с высокими баллами A и немногие с высокими баллами B.

Answer 1

Это похоже на проблему максимального потока с минимальными затратами. Это на самом деле максимальная стоимость, но это можно изменить, просто уменьшив вес.

Рассмотрим следующую сеть. Есть источник, sи раковина, t,

Каждый предмет i представлен вершиной u_iс ребром s -> u_i с емкостью 1 и стоимостью 0.

Каждое ведро также представлено вершиной: v_Av_B, и так далее. Есть преимущество v_A -> t с мощностью, равной размеру группы A и стоимостью 0, и аналогичными ребрами для других групп.

И, наконец, есть края u_i -> v_G которые имеют емкость 1 и стоимость, равную (минус счет сдачи предмета i в группе G).

Обратите внимание, что любой максимальный поток в этой сети соответствует разбиению элементов на группы, так что каждая группа имеет заданный размер.

Обратите внимание, что максимальный поток с минимальными затратами в этой сети является разделом, в котором максимальный общий балл раздела.

Это хорошо масштабируется с количеством предметов и количеством групп. Кроме того, это легко распространяется на случай, когда размер групп может варьироваться до определенного предела, но каждый элемент должен по-прежнему принадлежать к одной группе.

Answer 2

Для достаточно малых размеров метаэвристика (например, локальный поиск) может работать хорошо.

public class WeightedKnapsackProblem {

private int numberOfBins = 0;
private int numberOfItems = 0;

private int[][] scoreMatrix;
private int[] maxItemsPerBin;

public WeightedKnapsackProblem(int[][] score, int[] maxItemsPerBin){
    this.numberOfItems = score.length;
    this.numberOfBins = score[0].length;
    this.scoreMatrix = score;
    this.maxItemsPerBin = maxItemsPerBin;
}

public int score(int[] assignment){
    int s = 0;
    for(int i=0;i<numberOfItems;i++){
        int item = i;
        int bin = assignment[item];
        s += scoreMatrix[item][bin];
    }
    return s;
}

public int cost(int[] assignment){
    int c = 0;
    int[] tmp = new int[numberOfBins];
    for(int i=0;i<numberOfItems;i++){
        tmp[assignment[i]]++;
    }
    for(int i=0;i<numberOfBins;i++){
        if(tmp[i] > maxItemsPerBin[i])
            c++;
    }
    return c;
}

private java.util.Random RANDOM = new java.util.Random(System.currentTimeMillis());

private int[] mutate(int[] orig){
    int[] out = new int[orig.length];
    for(int i=0;i<orig.length;i++)
        out[i] = orig[i];
    out[RANDOM.nextInt(out.length)] = RANDOM.nextInt(numberOfBins);
    return out;
}

public int[] localSearch(){
    // initial assignment
    int[] a0 = new int[numberOfItems];
    for(int i=0;i<numberOfItems;i++)
        a0[i] = RANDOM.nextInt(numberOfBins);

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    // local search
    int[] a1 = mutate(a0);
    int c0 = score(a0) - cost(a0) * max * max;
    int c1 = score(a1) - cost(a1) * max * max;
    for(int i=0;i<1000;i++){
        if(c1 > c0){
            a0 = a1;
            c0 = c1;
        }
        a1 = mutate(a0);
        c1 = score(a1) - cost(a1) * max;
    }

    // return
    return a0;
}

public int[] repeatedLocalSearch(int k){

    // max score for any item
    int max = scoreMatrix[0][0];
    for(int i=0;i<scoreMatrix.length;i++)
        for(int j=0;j<scoreMatrix[i].length;j++)
            max = java.lang.Math.max(max, scoreMatrix[i][j]);

    int[] a0 = localSearch();
    int c0 = score(a0) - cost(a0) * max * max;

    for(int i=0;i<k;i++){
        int[] a1 = localSearch();
        int c1 = score(a1) - cost(a1) * max * max;

        if(c1 > c0){
            c0 = c1;
            a0 = a1;
        }
    }

    return a0;
}
}

Эта программа, по сути, генерирует случайное назначение элементов для корзин и итеративно пытается улучшить эту начальную ситуацию.

Поскольку с помощью этой техники вы можете легко попасть в локальные оптимумы, имеет смысл повторить это пару раз с различными (случайными) начальными конфигурациями.

Следующая программа использует класс WeightedKnapsackProblem для генерации возможного решения:

    int[][] score = {   {9,5,2,3},
                        {8,9,2,1},
                        {3,2,1,4},
                        {1,2,1,2},
                        {7,8,9,2},
                        {0,1,2,3}
                    };
    int[] maxItemsPerBin = {2,1,2,1};

    WeightedKnapsackProblem wkp = new WeightedKnapsackProblem(score, maxItemsPerBin);
    int[] assignment =  wkp.repeatedLocalSearch(10);

    System.out.println(wkp.score(assignment));
    System.out.println(wkp.cost(assignment));
    System.out.println(Arrays.toString(assignment));

Это распечатывает:

34
0
[0, 1, 0, 3, 2, 2]

Другими словами, демонстрационная задача может быть решена за максимальный балл 34.
Количество неуместных элементов (которые могут превысить емкость бункера) равно 0.

И назначение:

• первый элемент в первом бункере
• второй предмет во втором бункере
• третий элемент в первом бункере
• четвертый пункт в четвертом мусорном ведре
• пятый и шестой предмет в третьем мусорном ведре