Optimisation de l'emballage des bacs pondérés/du sac à dos

Question

J'ai du mal à catégoriser un problème sur lequel je travaille, ce qui signifie que je n'ai pas pu déterminer s'il existe des solutions heuristiques établies. À votre avis, de quel type de problème s'agit-il et comment me recommandez-vous de le résoudre ?

J'ai une série de bacs A, B, C, D. Chacun d'eux peut contenir un certain nombre d'éléments. nombre d'éléments. La taille totale des seaux correspond à la taille de la population. population. Les éléments de la population ont chacun un score pour A, B, C, D.

Je veux trier les éléments dans les godets de sorte que le score total de l'ensemble des éléments qui correspondent est maximisé, c'est-à-dire que les notes A de tous les éléments sont les suivantes pour tous les éléments du panier A, les scores B pour tous les éléments du panier B et ainsi de suite. Le site Il s'ensuit qu'un élément peut idéalement se trouver dans le seau B même si son score A est plus élevé, car il peut y avoir de nombreux éléments avec des élevés et peu d'éléments avec des scores B élevés.

Answer 1

Cela ressemble à coût minimal débit maximal problème. C'est un problème de coût maximum, en fait, mais cela peut être modifié en annulant simplement les poids.

Considérons le réseau suivant. Il y a une source, s et un évier, t .

Chaque élément i est représenté par un sommet u_i avec un bord s -> u_i avec une capacité de 1 et un coût de 0.

Chaque godet est également représenté par un sommet : v_A v_B et ainsi de suite. Il existe une arête v_A -> t avec la capacité étant la taille du groupe A et le coût 0, et des bords similaires pour les autres groupes.

Et enfin, il y a les bords u_i -> v_G qui ont une capacité de 1 et un coût égal à (moins le score de mise en place de l'élément i en groupe G ).

Observez que tout flux maximal dans ce réseau correspond à une partition des articles en groupes de sorte que chaque groupe ait la taille donnée.

Observez que le flux maximal à coût minimal dans ce réseau est une partition où le score total de la partition est maximisé.

Cela s'adapte bien au nombre d'éléments et au nombre de groupes. En outre, elle s'étend facilement au cas où la taille des groupes peut varier jusqu'à une certaine limite, mais où chaque élément doit toujours appartenir à un groupe.

Answer 2

Pour des tailles suffisamment petites, une méta heuristique (comme la recherche locale) pourrait fonctionner correctement.

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

Ce programme génère essentiellement une affectation aléatoire des articles aux bacs, et tente itérativement d'améliorer cette situation initiale.

Comme cette technique permet de se piéger facilement dans des optimums locaux, il est judicieux de la répéter plusieurs fois, avec des configurations de départ différentes (aléatoires).

Le programme suivant utilise la classe WeightedKnapsackProblem pour générer une solution possible :

    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));

Cela s'imprime :

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

En d'autres termes, le problème de démonstration peut être résolu pour un score maximal de 34.
Le nombre d'articles mal placés (qui dépasseraient la capacité de la poubelle) est de 0.

Et la mission est :

• premier article dans le premier bac
• deuxième article dans le deuxième bac
• troisième article dans le premier bac
• quatrième article dans le quatrième bac
• cinquième et sixième articles dans le troisième bac