Discussion :

[jurassic pork]

hello,
voici un petit exercice de répartition qui a été résolu en VBA, à voir si c'est "facilement faisable" en python.
A partir d'une liste de flottants, regrouper les flottants par groupes de telle façon que la somme des flottants de chaque groupe ait un écart minimal avec les autres groupes. Le nombre de groupes est fixe.
Exemple : il y a 19 valeurs de départ qui doivent être "dispatchées" en 6 groupes.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
          46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]

Voici une solution trouvée par le VBA avec une itération de 1000000 (trouvée en 8 secondes).





Sachant qu'en relançant le calcul dans la solution VBA on a pas tout à fait toujours le même résultat (même valeur moyenne par groupe mais Ecart Max différent). Et cela varie aussi avec le nombre d'itérations choisi.

Ami calmant, J.P

[jurassic pork]

Hello,
puisque personne n'a l'air de proposer quelque chose, j'ai essayé de traduire le code VBA en brut de fonderie python. Voici à ce que je suis arrivé (sans chercher à optimiser) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import time
from itertools import permutations
import random
start = time.time()
values = [56.94624,39.104,27.98432,26.9568,60.54048,48.8072,49.55808,31.85,50.752,55.3696,
          46.78128,34.80048,38.75508,55.13664,39.3354,37.37448,80.3374,19.24208,12.3786]
random.seed()
nbfois = 1000000
Ngpe = 6
ecartMax = float('inf')
t = values
sumGrpSol = [0]*Ngpe
#perm_iterator = permutations(t, len(t))
#for it in perm_iterator:
#    print(it)
grp = [0]*len(t)
# calcul du nombre d'éléments minimum par groupe
NparGpeMin = len(t) // Ngpe
# création de la liste des groupes
for i in range(0,(Ngpe * NparGpeMin)+1):
    grp[i] = 1 + (i  // NparGpeMin)
for i in range((Ngpe * NparGpeMin),len(t)):
    grp[i] = i - (Ngpe* NparGpeMin) + 1
for nbf in range(nbfois,-1,-1):
    #print(grp)
    # mélange des valeurs
    random.shuffle(t)
    max = 0
    min = float('inf')
    sumGrp = [0]*Ngpe
    # calcul de la somme des éléments pour chaque groupe
    for i in range(0,len(t)):
        sumGrp[grp[i] -1] =  sumGrp[grp[i] -1] + t[i]
    for i in range(0,len(sumGrp)):
        if sumGrp[i] < min: min = sumGrp[i]
        if sumGrp[i] > max: max = sumGrp[i]
    ecart = max - min
    if ecart < ecartMax:
        ecartMax = ecart
        tres = []
        #Mémorisation sous forme de tuple
        for i in range(0,len(t)):
            tres.append((t[i],grp[i]))
            sumGrpSol = sumGrp.copy()
end = time.time()
print('temps écoulé : ' + str(end - start) + " s")
print(tres)
print(ecartMax)
print(sumGrpSol)

Cela a l'air de donner un résultat cohérent :

temps écoulé : 9.891370058059692 s
[(34.80048, 1), (46.78128, 1), (12.3786, 1), (56.94624, 2), (38.75508, 2), (39.3354, 2), (55.13664, 3), (31.85, 3), (49.55808, 3), (26.9568, 4), (80.3374, 4), (27.98432, 4), (55.3696, 5), (19.24208, 5), (60.54048, 5), (37.37448, 6), (48.8072, 6), (50.752, 6), (39.104, 1)]
3.8693199999999877
[133.06436000000002, 135.03672, 136.54471999999998, 135.27852000000001, 135.15216, 136.93368]

Le principe est simple : on affecte à chaque élément de la liste des valeurs, un numéro de groupe puis on mélange les valeurs en regardant si à chaque itération on a un meilleur résultat. Plus
on a d'itérations plus on a de chance de trouver une meilleure solution. J'ai essayé de regarder pour balayer toutes les permutations possibles mais on arrive à 121645100408832000 cas possibles.
Pour l'instant ce code est moins rapide que le code VBA (10 s contre 7s en VBA) Les pistes possible d'optimisation : le calcul parallèle par cores. L'utilisation de np. L'utilisation d'expressions lambdas et sûrement d'autres astuces.
Ami calmant, J.P

[wiztricks]

Les pistes possible d'optimisation : le calcul parallèle par cores. L'utilisation de np. L'utilisation d'expressions lambdas et sûrement d'autres astuces.

Quelque soit le langage, la première piste sera de revoir l'algo.

- W

[jurassic pork]

Hello,

Quelque soit le langage, la première piste sera de revoir l'algo.

- W

J'ai posé le problème dans le forum d'Algorithmique

Ami calmant, J.P

[jurassic pork]

une solution ici

[wiztricks]

une solution ici

C'est une piste (celle donnée par User) à laquelle j'avais pensé mais je n'ai pas le temps (mental) de la valider. Si un algorithme se termine, il faut avoir une condition d'arrêt sur un optimum... si on prend quelque chose de pas trop mauvais on est dans l'heuristique.
Ca n'a pas l'air très différent mais ça peut changer pas mal de choses côté structures de données pour rendre compte du problème et du code qui va avec.
Sans non plus faire l'impasse sur des recherches sur Internet pour avoir une idée de l'état de l'art - ce qui a déjà été fait pour traiter des problèmes similaires.

- W

[jurassic pork]

Hello,
bon le problème est résolu dans la discussion ici grâce à l'intervention de User. J'ai réussi à intégrer le code python de la solution dans un classeur LibreOffice Calc :


Ami calmant, J.P