Algorithme AFDO pour la résolution du Bin Packing Problem

1 pièce(s) jointe(s)

Bonjour,

Je suis actuellement en train de travailler sur un programme en python de Adaptive Fitness-Dependent Optimizer qui me permettrait de trouver la solution optimale du 1D Bin Packing Problem (https://www.degruyter.com/document/d...7/html?lang=en). Cependant je n'arrive pas à simuler le mouvement pour s'approcher de la solution idéale (pace, équation 2 du document) et je suis donc bloqué, je vous met mon code en pièce jointe au cas où ça peut servir.
Pourriez-vous me guider dans les démarches car je suis un peu perdu, n'étant pas très à l'aise avec le code de base. Merci pour votre aide!

Salut,

De l'aide côté algo. c'est du côté du forum algorithme qu'il faut aller la chercher... Quand à la traduction de l'algo. en Python, il serait bon de décrire ce que vous chercher à faire en français et montrer comment vous avez essayé de le retranscrire.
Là vous montrez du code: ça veut dire qu'il faut comprendre l'algo. puis lire le code pour voir comment vous l'avez traduit puis... ce qui est un travail conséquent et sans rapport avec le langage Python: pas grand monde va s'y atteler mais vous pouvez toujours espérer (comme un brin d'herbe).

- W

Hello,
cela devient inquiétant car avec l'IA maintenant vous posez une question : elle vous répond et en plus génère du code dans le langage que vous avez désigné. Bientôt il n'y aura plus besoin de programmeur :aie:.

Voici ce qu'elle m'a répondu concernant l'AFDO bin packing:

Citation:

L'algorithme AFDO (Approximate First Fit Decreasing Order) est un algorithme de bin packing, également connu sous le nom d'algorithme de remplissage de conteneurs, qui consiste à emballer un certain nombre d'objets de tailles différentes dans un nombre limité de conteneurs de capacité donnée. Voici la traduction en français de l'algorithme AFDO :

Trier les objets par ordre décroissant de taille.

Placer le premier objet dans le premier conteneur.

Pour chaque objet restant, parcourir tous les conteneurs déjà utilisés dans l'ordre où ils ont été remplis. Si l'objet peut être placé dans l'un des conteneurs sans dépasser sa capacité, le placer dans ce conteneur et passer à l'objet suivant. Sinon, ouvrir un nouveau conteneur et y placer l'objet.

Le nombre de conteneurs utilisés est le résultat de l'algorithme.

Cet algorithme est appelé "approximatif" car il ne garantit pas une solution optimale, mais il est connu pour être efficace et relativement simple à implémenter.

Et pour le code voici ce qu'elle m'a répondu :
Voici un exemple de code Python pour l'Adaptive Fitness-Dependent Optimizer appliqué au problème de Bin Packing:

Code:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import random
 
 
def bin_packing(items, bin_size):
    population_size = 20
    max_iterations = 1000
    mutation_rate = 0.1
    crossover_rate = 0.5
 
 
    def generate_individual():
        individual = []
        for item in items:
            if random.random() > 0.5:
                individual.append(1)
            else:
                individual.append(0)
        return individual
 
 
    def evaluate_fitness(individual):
        bins = []
        for i in range(len(individual)):
            if individual[i] == 1:
                item_size = items[i]
                added = False
                for j in range(len(bins)):
                    if bins[j] + item_size <= bin_size:
                        bins[j] += item_size
                        added = True
                        break
                if not added:
                    bins.append(item_size)
        return len(bins)
 
 
    def tournament_selection(population, tournament_size):
        tournament = random.sample(population, tournament_size)
        tournament.sort(key=lambda x: x[1])
        return tournament[0]
 
 
    def crossover(parent1, parent2):
        child1 = []
        child2 = []
        for i in range(len(parent1)):
            if random.random() < crossover_rate:
                child1.append(parent2[i])
                child2.append(parent1[i])
            else:
                child1.append(parent1[i])
                child2.append(parent2[i])
        return child1, child2
 
 
    def mutate(individual):
        for i in range(len(individual)):
            if random.random() < mutation_rate:
                individual[i] = 1 - individual[i]
        return individual
 
 
    # initialisation
    population = []
    for i in range(population_size):
        individual = generate_individual()
        fitness = evaluate_fitness(individual)
        population.append((individual, fitness))
 
 
    best_solution = population[0]
    iteration = 0
    while iteration < max_iterations:
        # adaptation des paramètres
        fitness_values = [x[1] for x in population]
        average_fitness = sum(fitness_values) / population_size
        best_fitness = min(fitness_values)
        worst_fitness = max(fitness_values)
        mutation_rate = mutation_rate * (1 - (best_fitness / worst_fitness))
        population_size = int(population_size * (best_fitness / average_fitness))
 
 
        # mise à jour de la population
        new_population = []
        for i in range(population_size):
            parent1 = tournament_selection(population, 3)
            parent2 = tournament_selection(population, 3)
            child1, child2 = crossover(parent1[0], parent2[0])
            child1 = mutate(child1)
            child2 = mutate(child2)
            fitness1 = evaluate_fitness(child1)
            fitness2 = evaluate_fitness(child2)
            new_population.append((child1, fitness1))
            new_population.append((child2, fitness2))
 
 
        population = new_population
 
 
        # mise à jour de la meilleure solution
        best_solution = min(population, key=lambda x: x[1])
 
 
        iteration += 1
 
 
    return best_solution[0]

A voir si le code tient la route !

Ami calmant, J.P