# ################################################################### # # Program: sad_algorithme_genetique.py # Author: Jean-Michel Richer # Organisation: Computer Science Department, # University of Angers, # France # Email: jean-michel.richer@univ-angers.fr # Creation date: April, 2021 #  Modification: April, 2021 # # ################################################################### # # Aim: # # This program is an implementation of a genetic algorithm used # to find a solution to the knapsack problem. The method is based # on a population that evolves using a crossover operator, # mutations on children and replacement of parents if the best # child is better than is father or mother. # # Objectif : # # Ce programme repose sur l'utilisation d'un algorithme # génétique afin de résoudre le problème du sac à dos. La méthode # repose sur l'évolution d'une population grâce à un opérateur # de croisement, la mutation des enfants et le remplacement # de l'un des parent si un des enfants est meilleur que ses # parents. # # ################################################################### # # License # # This program is a free software you can modifiy it and # redistribute it for non profitable use. # # ################################################################### import random import sys import matplotlib.pyplot as plt import numpy as np import statistics as stats """ Les données de ce problème sont issues du site suivant : https://interstices.info/le-probleme-du-sac-a-dos/ La méthode de résolution utilisée est une méthode approchée qui se fonde sur l'utilisation des ratios p_i/w_i de chaque objet. Les objets sont triés suivant un ordre décroissant de ces ratios. """ # # Données du problème # Poids maximum autorisé et données de poids et profit # poids_maximum = 269 poids = [ 95, 4, 60, 32, 23, 72, 80, 62, 65, 46] profits = [ 55, 10, 47, 5, 4, 50, 8, 61, 85, 87 ] # =================================================================== # Classe qui permet de représenter les objets à mettre dans le sac # à dos. Un objet possède un poids, un profit # =================================================================== class Objet(object): """ class used to represent an object Attributes ---------- poids : int weight of the object profit : int profit of the object Methods ------- __str__() transform the object into a string """ def __init__(self, id, poids, profit): """ Constructor Parameters ---------- id : int object identifier from 1 to N poids : int weight of the object profit : int profit de l'objet """ self.id = id self.profit = profit self.poids = poids def __str__(self): """ Transform object into string """ return "(" + str(self.id) + ",p=" + str(self.poids) + ",w=" + str(self.profit) + ",r={0:.2f}".format(self.ratio) + ")" # =================================================================== # Classe qui permet de représenter un sac à dos composé d'une liste # de présence/absence d'objets, du poids et profit total qui # résulte de la présence/absence des objets # =================================================================== class Sac(object): """ Knapsack representation as a list of present/absent objects, the weight and the profit Attributes ---------- objets : list list of objects that can be put inside the knapsack liste : list list of 0 and 1, 1 means the object is present poids : int weight of the knapsack profit : int profit of the knapsack """ # ----------------------------------------------------- # Constructeur avec liste d'objets et liste # présence / absence des objets # ----------------------------------------------------- def __init__(self, objets, liste): """ Constructor """ self.objets = objets self.liste = liste self.poids = 0 self.profit = 0 for i in range(len(liste)): if liste[ i ] == 1: self.poids += objets[ i ].poids self.profit += objets[ i ].profit # ----------------------------------------------------- # ajouter un objet dans le sac à dos # ----------------------------------------------------- def ajoute_objet(self, n): """ Add object to knapsack """ if self.liste[ n ] == 1: return self.poids += self.objets[ n ].poids self.profit += self.objets[ n ].profit self.liste[ n ] = 1 # ----------------------------------------------------- # retirer un objet du sac à dos # ----------------------------------------------------- def supprime_objet(self, n): """ Delete object from knapsack """ if self.liste[ n ] == 0: return self.poids -= self.objets[ n ].poids self.profit -= self.objets[ n ].profit self.liste[ n ] = 0 # ----------------------------------------------------- # Convertion un sac à dos en chaine # ----------------------------------------------------- def __str__(self): """ Transform object into string """ return "(poids=" + str(self.poids) + ",profit=" + str(self.profit) + "," + str(self.liste) + ")" # ----------------------------------------------------- # Copie d'un sac à dos # ----------------------------------------------------- def copy(self): """ Create copy of the object """ sac = Sac(self.objets, self.liste.copy()) sac.poids = self.poids sac.profit = self.profit return sac # ----------------------------------------------------- # Mutation d'un objet # ----------------------------------------------------- def mutation(self, poids_maximum): """ Mutation of the knapsac which consists in removing objects if the weight of the knapsack is greater than the maximum weight or to add objects if the weight of the knapsack is smaller than the maximum weight Parameters ---------- poids_maximum : int maximum weight allowed """ if self.poids == poids_maximum: return # on définit un ordre aléatoire de prise en compte # des objets ordre = [ x for x in range(len(self.liste)) ] random.shuffle(ordre) # si le poids de l'objet est supérieur au poids maximum if self.poids > poids_maximum: # on supprime des objets en suivant l'ordre @@@...@@@ # si le poids de l'objet est inférieur au poids maximum else: # on ajoute des objets en suivant l'ordre @@@...@@@ # ----------------------------------------------------- # Fonction qui indique si un objet est meilleur qu'un autre. # L'objet courant est meilleur qu'un autre objet si lorsque # son profit est supérieur à celui de l'autre objet, sa # distance au poids maximum est inférieure à celle de l'autre # objet # ----------------------------------------------------- def est_meilleur(self, autre, poids_maximum): """ Comparison of two knapsacks based on profit and weight Parameters ---------- autre : Sac other knapsack for comparison poids_maximum : int maximum weight allowed """ @@@...@@@ # =================================================================== # Classe représentant un solveur de type algorithme génétique # =================================================================== class SAD(object): """ This class is a solver based on a Genetic Algorithm """ def __init__(self, poids_maximum, poids, profits): """ Constructor given maximum weight of knapsack, weights and profits of objects that can be put in the knaspsack. Objects are created in this class and are provided to the Sac class """ self.poids_maximum = poids_maximum self.profits = profits self.poids = poids self.nbr_objets = len(poids) # # création des objets # self.objets = [] for i in range(len(profits)): objet = Objet(i, poids[i], profits[i]) self.objets.append( objet ) self.verbose = False # données stockées concernant l'évolution # de la population afin d'afficher des # graphiques self.copie_population_initiale = [] self.liste_evolution_score_minimum = [] self.liste_evolution_score_maximum = [] self.liste_evolution_score_moyen = [] # ----------------------------------------------------- # croisement entre deux individus # ----------------------------------------------------- def croisement(self, pere, mere): """ Crossover operation given two parents. The list of present/absent objects is considered as a chromosome and is cut at a certain point Parameters ---------- pere : Sac father mere : Sac mother """ # enfants générés enfant1 = None enfant2 = None # point de coupure du chromosome point_de_coupure = @@@...@@@ l_enfant1 = @@@...@@@ l_enfant2 = @@@...@@@ enfant1 = Sac( self.objets, l_enfant1 ) enfant2 = Sac( self.objets, l_enfant2 ) if self.verbose: print("cut=",point_de_coupure) print(pere) print(mere) print(enfant1) print(enfant2) return enfant1, enfant2 # ----------------------------------------------------- # Modification de la population en fonction du fait # que les enfants sont meilleurs que le père et la # mère # ----------------------------------------------------- def remplacement(self, pere, mere, enfant1, enfant2): """ Modification of the population : we keep the best child which replaces the mother or the father if he is better than one of them """ if self.verbose: print( "enfant1 muté : ", enfant1 ) print( "enfant2 muté : ", enfant2 ) # choisir le meilleur enfant if enfant1.est_meilleur( enfant2, self.poids_maximum ): enfant = enfant1 else: enfant = enfant2 # remplacer le pere remplacement = False if enfant.est_meilleur(pere, self.poids_maximum): self.population.remove( pere ) self.population.append( enfant ) remplacement = True if enfant.est_meilleur(mere, self.poids_maximum) and remplacement == False: self.population.remove( mere ) self.population.append( enfant ) # ----------------------------------------------------- # Enregistre les données pour créer les graphiques # ----------------------------------------------------- def enregistre_donnees(self): """ Record data to display graphics """ # enregistre les données de l'évolution de la population minimum = min(self.population, key=lambda x: x.profit) maximum = max(self.population, key=lambda x: x.profit) somme = 0 for individu in self.population: somme += individu.profit moyenne = somme / len(self.population) self.liste_evolution_score_minimum.append( minimum.profit ) self.liste_evolution_score_maximum.append( maximum.profit ) self.liste_evolution_score_moyen.append( moyenne ) # ----------------------------------------------------- # Méthode de résolution basée sur un algorithme # génétique # ----------------------------------------------------- def algorithme_genetique(self, taille_population, nombre_de_generations): """ Genetic algorithm to solve the problem. Parameters ---------- taille_population : int population size nombre_de_generations : int maximum number of generations """ self.nombre_de_generations = nombre_de_generations # # Générer la population initiale de manière aléatoire # self.population = [ ] for i in range(taille_population): objets_selectionnes = [] while len(objets_selectionnes) != len(self.objets): x = random.randint(0, 1) objets_selectionnes.append(x) self.population.append( Sac( self.objets, objets_selectionnes ) ) # enregistrement de la population initiale pour affichage graphique self.population_initiale = self.population.copy() self.enregistre_donnees() # # Trier la population suivant le poids # @@@...@@@ # # Algorithme génétique # generation = 1 while generation <= nombre_de_generations: print("==== GENERATION ", generation, "====") # choix aléatoire de deux parents p = @@@...@@@ m = @@@...@@@ @@@...@@@ if self.verbose: print("pere indice =", p) print("mere indice =", m) pere = self.population[ p ] mere = self.population[ m ] # génération des enfant par croisement enfant1, enfant2 = self.croisement( pere, mere ) if self.verbose: print("===========================") print("pere : ", pere) print("mere : ", mere) print("enfant1 : ", enfant1) print("enfant2 : ", enfant2) # mutation des enfants enfant1.mutation( self.poids_maximum ) enfant2.mutation( self.poids_maximum ) # remplacement de la population self.remplacement(pere, mere, enfant1, enfant2) self.enregistre_donnees() generation += 1 # tri des sac finaux suivant le poids self.population.sort(key=lambda x : x.poids) self.population_finale = self.population.copy() candidats = [ individu for individu in self.population if individu.poids <= self.poids_maximum ] return candidats # ----------------------------------------------------- # Affiche deux graphiques # - le premier concerne l'évolution des scores (profit) # minimum, moyen et maximum de la populationen en # fonction du nombre de génération # - second affiche les populations initiales et finales # en fonction du poids et du profit ainsi que les #  solutions potentielles de la population finale # ----------------------------------------------------- def graphique(self): """ Display two graphics: - the first one is the evolution of the profit of the population, we show the minimum, average and maximum values over the generations - the second one displays the initial and final populations in function of the weight and profit as well as the possible solutions """ # une génération en plus la première, génération 0 x = range( self.nombre_de_generations + 1) plt.grid() plt.plot( x, self.liste_evolution_score_minimum, label='minimum' ) plt.plot( x, self.liste_evolution_score_maximum, label='maximum' ) plt.plot( x, self.liste_evolution_score_moyen, label='moyenne' ) plt.hlines( self.poids_maximum, 0, self.nombre_de_generations, color='#aaa',label="poids maximum") plt.xlabel('itérations') plt.legend() plt.title('Algorithme génétique - Evolution du score des populations') plt.show() initial_poids = [individu.poids for individu in self.population_initiale] initial_profits = [individu.profit for individu in self.population_initiale] final_poids = [individu.poids for individu in self.population_finale] final_profits = [individu.profit for individu in self.population_finale] possible_poids = [individu.poids for individu in self.population_finale if individu.poids <= self.poids_maximum] possible_profits = [individu.profit for individu in self.population_finale if individu.poids <= self.poids_maximum] fig, ax = plt.subplots() plt.scatter(initial_poids, initial_profits, s=100.0, color='#A0A0A0', label='conf. initiales') unique_confs = {} for individu in self.population: poids_profit = str( individu.poids ) + ',' + str( individu.profit ) if unique_confs.get( poids_profit ) == None: unique_confs[ poids_profit ] = 1 else: unique_confs[ poids_profit ] += 1 print("-------------------------------------") print(" Nombre d'occurrences de chaque ") print("configuration de la population finale") print(" (diversité de la population) ") print("-------------------------------------") print("poids maximum = ", self.poids_maximum) print("-------------------------------------") print(" poids,profit : occurrences") print("-------------------------------------") for poids_profit, n_occ in unique_confs.items(): poids, profit = poids_profit.split(',') poids = int(poids) if poids <= self.poids_maximum: solution = " solution " else: solution = " " print( "{0:7s} : {1:3d} {2:s}".format( poids_profit, n_occ, solution ) ) print("-------------------------------------") print("Note : les solutions sont les configurations") print("de la population finale en dessous de la ") print("limite de poids autorisée") x = [] y = [] z = [] for v in unique_confs: poids, profit = v.split(',') xc = int(poids) yc = int(profit) zc = unique_confs.get( v ) * 20 x.append( xc ) y.append( yc ) z.append( zc ) plt.scatter(x, y, s=z, c='#CC6900', alpha=1.0, label='conf. finales') plt.scatter(possible_poids, possible_profits, color='#007CFF', marker='x',label='solutions') plt.xlabel("poids") plt.ylabel("profit") plt.vlines(self.poids_maximum,0,400,color='#aaa',label="poids maximum") plt.title('Algorithme génétique - Evolution de la population') ax.legend(loc=2) plt.show() # =================================================================== # Programme principal # =================================================================== HELP_MESSAGE = """ Program arguments are: -h or --help to get this message -q or --quiet to remove verbose mode and avoid to display graphics """ sad = SAD(poids_maximum, poids, profits) taille_population = 30 nombre_de_generations = 200 # gestion des arguments du programme if len(sys.argv) >= 1: try: i = 1 while i < len(sys.argv): arg = sys.argv[i] if arg == "-h" or arg == "--help": print( HELP_MESSAGE ) elif arg == "-q" or arg == "--quiet": sad.verbose = False elif arg == "-p": i += 1 taille_population = int(sys.argv[i]) elif arg.startswith("--population="): taille_population = int(arg.split('=')[1]) elif arg == "-g": i += 1 nombre_de_generations = int(sys.argv[i]) elif arg.startswith("--generations="): nombre_de_generations = int(arg.split('=')[1]) else: raise ValueError("Unexpected argument") i += 1 except: print("="*40) print(sys.exc_info()[1]) print("="*40) print( HELP_MESSAGE ) sys.exit(1) population = sad.algorithme_genetique(taille_population, nombre_de_generations) for individu in population: print(individu) sad.graphique()