Résolution du problème d'horaire des infirmières (optimisation des équipes) avec un algorithme génétique

Cet article

supposition

Problème de planification de l'infirmière

Il s'agit d'un problème qui détermine l'horaire de travail des infirmières travaillant dans des établissements médicaux tels que les hôpitaux, et c'est un exemple typique du problème d'horaire des équipes. En raison du travail par quarts compliqué comme le quart de jour, le quart de soir, le quart de nuit et la prise en compte de diverses restrictions, c'est une tâche difficile qui nécessite du travail manuel pour obtenir un horaire ...

Algorithme génétique

Alors comment postuler

journée Mois Mois Mois Feu Feu Feu eau eau eau bois bois bois Argent Argent Argent sol sol sol journée journée journée
Fuseau horaire Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit
Employé 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0
Employé 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Employé 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0
[0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,
 1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0]

Implémenté en Python / deap

Procédons concrètement à la mise en œuvre.

Utilisation de deap

pip install deap

Spécifications de l'échantillon

Les spécifications de cet exemple sont les suivantes.

Employés et souhaits de quart

journée Mois Mois Mois Feu Feu Feu eau eau eau bois bois bois Argent Argent Argent sol sol sol journée journée journée
Fuseau horaire Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit
Nombre de personnes requis 2 3 3 2 3 3 2 3 3 1 2 2 2 3 3 2 4 4 2 4 4
Employé 0
Employé 1
Employé 2
Employé 3
Employé 4
Employé 5
Employé 6
Employé 7
Employé 8
Employé 9

Contrainte

Assurez-vous que votre score augmente suffisamment pour répondre aux contraintes suivantes. Les nombres entre parenthèses sont des poids et représentent la priorité de la contrainte.

Aperçu du code

point

Définition de l'employé

class Employee(object):
  def __init__(self, no, name, age, manager, wills):
    self.no = no
    self.name = name
    self.age = age
    self.manager = manager

    #la volonté est le jour_Fuseau horaire. 1 est le matin, 2 est midi, 3 est la nuit.
    #Exemple) mon_1 est le lundi matin
    self.wills = wills
...
#Seulement le matin
e0 = Employee(0, "Yamada", 40, False, ['mon_1', 'tue_1', 'wed_1', 'thu_1', 'fri_1', 'sat_1', 'sun_1'])

#Lun / mer / ven
e1 = Employee(1, "Suzuki", 21, False, ['mon_1', 'mon_2', 'mon_3', 'wed_1', 'wed_2', 'wed_3','fri_1', 'fri_2', 'fri_3'])

#Uniquement le week-end
e2 = Employee(2, "Sato", 18, False, ['sat_1', 'sat_2', 'sat_3', 'sun_1', 'sun_2', 'sun_3'])

#OK n'importe où
e3 = Employee(3, "Tanaka", 35, True, ['mon_1', 'mon_2', 'mon_3',
                                     'tue_1', 'tue_2', 'tue_3',
                                     'wed_1', 'wed_2', 'wed_3',
                                     'thu_1', 'thu_2', 'thu_3',
                                     'fri_1', 'fri_2', 'fri_3',
                                     'sat_1', 'sat_2', 'sat_3',
                                     'sun_1', 'sun_2', 'sun_3'
                                    ])

...

employees = [e0, e1, e2, e3, e4, e5, e6, e7, e8, e9]

Définition du décalage (frame)

#Classe représentant le décalage
#En interne 3(Matin, jour et nuit) *Le 7*10 personnes=Se compose de taples de 210 dimensions
class Shift(object):
  #Définition de haut
  SHIFT_BOXES = [
    'mon_1', 'mon_2', 'mon_3',
    'tue_1', 'tue_2', 'tue_3',
    'wed_1', 'wed_2', 'wed_3',
    'thu_1', 'thu_2', 'thu_3',
    'fri_1', 'fri_2', 'fri_3',
    'sat_1', 'sat_2', 'sat_3',
    'sun_1', 'sun_2', 'sun_3']

  #Nombre estimé de personnes dans chaque cadre
  NEED_PEOPLE = [
    2,3,3,
    2,3,3,
    2,3,3,
    1,2,2,
    2,3,3,
    2,4,4,
    2,4,4]

  def __init__(self, list):
    if list == None:
      self.make_sample()
    else:
      self.list = list
    self.employees = []

  #Générer des données aléatoires
  def make_sample(self):
    sample_list = []
    for num in range(210):
      sample_list.append(random.randint(0, 1))
    self.list = tuple(sample_list)
...

Notation et pondération

creator.create("FitnessPeopleCount", base.Fitness, weights=(-10.0, -100.0, -1.0, -100.0, -10.0))
creator.create("Individual", list, fitness=creator.FitnessPeopleCount)

...

def evalShift(individual):
  s = Shift(individual)
  s.employees = employees

  #Différence entre le nombre prévu de personnes et le nombre attribué de personnes
  people_count_sub_sum = sum(s.abs_people_between_need_and_actual()) / 210.0
  #Nombre d'affectations à des moments où vous ne postulez pas
  not_applicated_count = s.not_applicated_assign() / 210.0
  #Nombre d'employés avec moins de la moitié du nombre d'affectations
  few_work_user = len(s.few_work_user()) / 10.0
  #Nombre de cadres sans administrateur
  no_manager_box = len(s.no_manager_box()) / 21.0
  #Assigné à tous les matins, midi et soirs
  three_box_per_day = len(s.three_box_per_day()) / 70.0
  return (not_applicated_count, people_count_sub_sum, few_work_user, no_manager_box, three_box_per_day)

toolbox.register("evaluate", evalShift)

Précisez le nombre d'évolutions, etc.

    pop = toolbox.population(n=300)
    CXPB, MUTPB, NGEN = 0.6, 0.5, 500 #Probabilité de croisement, probabilité de mutation, nombre de boucles dans le calcul de l'évolution

Courir

$ python nurse_scheduling_by_ga.py 
L'évolution a commencé
Évaluer 300 personnes
--0 génération--
Évaluer 245 personnes
*Paramètre 1
  Min 0.242857142857
  Max 0.242857142857
  Avg 0.242857142857
  Std 2.2660056242e-08
*Paramètre 2
  Min 0.247619047619
  Max 0.247619047619
  Avg 0.247619047619
  Std 9.49766396283e-09
*Paramètre 3
  Min 0.0
  Max 0.0
  Avg 0.0
  Std 0.0
*Paramètre 4
  Min 0.142857142857
  Max 0.142857142857
  Avg 0.142857142857
  Std 1.66600046866e-08
*Paramètre 5
  Min 0.114285714286
  Max 0.114285714286
  Avg 0.114285714286
  Std 1.19267483008e-08
--1 génération--
Évaluer 235 personnes
*Paramètre 1
  Min 0.238095238095
  Max 0.238095238095
  Avg 0.238095238095
  Std 2.45699769971e-08
*Paramètre 2
  Min 0.228571428571
  Max 0.228571428571
  Avg 0.228571428571
  Std 2.38534966016e-08
*Paramètre 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Paramètre 4
  Min 0.047619047619
  Max 0.047619047619
  Avg 0.047619047619
  Std 4.46646616171e-09
*Paramètre 5
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08

(snip)

--499 générations--
Évaluer 219 personnes
*Paramètre 1
  Min 0.0333333333333
  Max 0.0333333333333
  Avg 0.0333333333333
  Std 2.98168707519e-09
*Paramètre 2
  Min 0.0714285714286
  Max 0.0714285714286
  Avg 0.0714285714286
  Std 8.33000234328e-09
*Paramètre 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Paramètre 4
  Min 0.0952380952381
  Max 0.0952380952381
  Avg 0.0952380952381
  Std 8.93293232343e-09
*Paramètre 5
  Min 0.0428571428571
  Max 0.0428571428571
  Avg 0.0428571428571
  Std 4.56253018749e-09
--Fin d'évolution--
Le meilleur individu: [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1], (0.0, 0.0, 0.2, 0.047619047619047616, 0.1)
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0
0,1,0,0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1
1,0,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1
0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0
1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1
0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,1
0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	1	0	0
0	1	0	0	0	0	1	1	0	0	0	0	1	1	1	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
1	0	1	0	1	1	0	0	1	0	1	0	1	0	1	0	1	1
0	0	0	0	0	1	0	0	1	0	0	1	0	0	1	0	0	0
1	1	1	1	1	1	1	1	1	0	0	1	0	1	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	1
0	1	0	0	1	0	0	1	0	0	1	0	0	0	0	0	1	0
0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	1	1

résultat

journée Mois Mois Mois Feu Feu Feu eau eau eau bois bois bois Argent Argent Argent sol sol sol journée journée journée Nombre de missions Numéro souhaité Taux d'affectation
Fuseau horaire Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit Matin Le midi Nuit
Nombre de personnes requis 2 3 3 2 3 3 2 3 3 1 2 2 2 3 3 2 4 4 2 4 4
Numéro approuvé 2 3 3 2 3 3 2 3 3 1 2 2 2 3 3 2 4 4 2 4 4
Différence 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Employé 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 5 7 71.4%
Employé 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 6 9 66.7%
Employé 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 4 6 66.7%
[tube]Employé 3 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 7 21 33.3%
Employé 4 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 5 7 71.4%
[tube]Employé 5 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 8 15 53.3%
Employé 6 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 5 9 55.6%
Employé 7 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 6 7 85.7%
Employé 8 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 4 7 57.1%
[tube]Employé 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 7 12 58.3%
Nombre d'administrateurs 1 1 1 1 2 1 1 1 0 1 1 2 1 1 1 0 1 1 1 2 1

À la fin

Recommended Posts

Résolution du problème d'horaire des infirmières (optimisation des équipes) avec un algorithme génétique
Trouver une solution au problème N-Queen avec un algorithme génétique (2)
Trouver une solution au problème N-Queen avec un algorithme génétique (1)
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (code Python)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 2)
Résolvez le problème de minimisation parabolique avec OpenMDAO
Rechercher le labyrinthe avec l'algorithme python A *
Comment réparer la population initiale avec un algorithme génétique utilisant DEAP
Résolution du problème de l'iris avec scikit-learn ver1.0 (régression logistique)
[Python] Essayez d'optimiser les paramètres de systole FX avec un algorithme génétique
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
Une histoire sur la façon de traiter le problème CORS
Un mémo qui a résolu le problème du sac à dos par la méthode gourmande
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Résolution du labyrinthe avec Python-Supplément au chapitre 6 de la référence rapide de l'algorithme-
Je voulais résoudre le problème ABC164 A ~ D avec Python
Erreur avec pip: un problème est survenu lors de la confirmation du certificat SSL
Résolvez le problème du sac à dos Python avec la méthode de branche et liée
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée
J'ai essayé de résoudre le problème de planification des équipes par diverses méthodes
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 1)
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Paver la route avec l'optimisation des combinaisons
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python