Cet article

Quand j'ai résolu le problème d'optimisation appelé le problème de planification des infirmières avec un algorithme génétique, c'était assez précis, donc c'est un enregistrement.
J'utilise une bibliothèque appelée deap en python

supposition

Problème de planification de l'infirmière

Il existe un problème de planification des infirmières

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 ...

En bref, il planifie automatiquement le travail par quarts de manière optimale.
Il existe diverses restrictions, allant des choses de base qui correspondent au nombre de personnes requis, l'équité, les qualifications / rôles essentiels, ces deux personnes (parce qu'elles ne sont pas proches?) Ne peuvent pas être réunies, etc. Cela ressemble à un problème, et il est difficile de faire une réponse parfaite, donc cela semble être un domaine qui cherche une solution approximative.

Algorithme génétique

Il semble y avoir différentes manières de résoudre le problème ci-dessus, mais [Algorithme génétique](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84 % E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) semble être une méthode relativement importante.
L'algorithme génétique s'optimise généralement par la méthode suivante.
Créez de nombreux "individus" contenant des données (généralement des séquences unidimensionnelles ou des taples comme des gènes)
Les données de l'individu créées au début sont aléatoires
Faire avancer la génération en changeant l'individu en combinant deux individus (croisement), mutant aléatoirement (mutation), etc.
Noter un individu en fonction de la mesure dans laquelle les données de l'individu répondent aux contraintes prédéfinies
Ajustez pour que les individus avec d'excellents scores survivent même au fur et à mesure que la génération progresse
Après une certaine génération, l'individu avec le score le plus élevé dans son ensemble est obtenu comme solution approximative.
C'est une méthode qui peut être utilisée pour l'optimisation générale des combinaisons afin de trouver des solutions discrètes même en optimisation.
Pour plus de détails, il est facile de comprendre que c'est ici.
En particulier, le plus simple et le plus facile à comprendre est le "problème OneMax", qui a un score élevé lorsque le nombre de 1 augmente.

Alors comment postuler

Comment l'algorithme génétique ci-dessus peut-il être appliqué pour résoudre le problème d'horaire des infirmières? Cependant, c'est une image que les données fournies à l'individu sont utilisées comme cadre de décalage.
Exemple) Par exemple, supposons que vous essayez d'effectuer un quart de travail de 3 personnes comme suit (1 est le cadre à attribuer)

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

Ici, les données individuelles sont obtenues en connectant les zéros de l'employé 0 à l'employé 2 dans un seul tableau.
En d'autres termes, dans le cas ci-dessus, les données de tableau à 1 dimension suivantes sont fournies.

[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]

Nous allons construire correctement une logique de notation pour calculer à quel point cet individu répond à diverses contraintes, et faire avancer la génération selon les règles de l'algorithme génétique.
Ensuite, un meilleur individu restera (= une combinaison plus optimale sera obtenue).

Implémenté en Python / deap

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

Utilisation de deap

La mise en œuvre a utilisé python, ce qui est fort dans l'apprentissage automatique
Bibliothèque étendue d'algorithmes génétiques appelée deap
Installer avec pip normalement (détails omis)

pip install deap

Comment utiliser est facile à comprendre l'exemple du problème OneMax dans ici

Spécifications de l'échantillon

Les spécifications de cet exemple sont les suivantes.

Employés et souhaits de quart

Le nombre d'employés est de 10 et les demandes de quart suivantes sont faites.

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										○	○	○	○	○	○	○	○	○	○	○	○

Le nombre d'employés requis est le nombre d'employés requis pour cette pièce.

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.

Le nombre d'employés requis et le nombre d'employés affectés doivent correspondre (10)
Ne pas attribuer aux cadres que l'employé ne veut pas (100)
Attribuer au moins 1/2 du nombre de cadres souhaité par chaque employé (1)
Puisqu'il l'a demandé, j'aimerais l'inclure autant que possible.
Assurez-vous d'attribuer un administrateur (100)
Les administrateurs sont des employés 3, 5, 9
Le même employé doit se voir attribuer jusqu'à 2 cadres par jour (10)

Aperçu du code

L'ensemble du programme est ici
J'ai fait référence au code de Ce problème OneMax un peu (quite copie).

point

Je n'expliquerai que les points modifiés à partir du problème OneMax ci-dessus pour le problème de planification des infirmières.

Définition de l'employé

Premièrement, la classe d'employés est définie de manière orientée objet.

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
...

L'endroit où l'instance est créée est le suivant

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

Définit une classe de décalages ou un ensemble de cadres
Le taple "liste" de cette classe est "l'individu" de l'algorithme génétique.

#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)
...

Comme mentionné ci-dessus, nous créons d'abord des individus avec des données aléatoires
La classe Shift est plus longue, mais ce n'est qu'une méthode de manipulation de données qui obtient les cadres et les utilisateurs qui remplissent les conditions à l'infini.

Notation et pondération

La notation individuelle est pondérée à l'aide de la fonction deap

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)

Return (not_applicated_count, people_count_sub_sum, few_work_user, no_manager_box, three_box_per_day) poids = (-10.0, -100.0, -1.0, -100.0, -10.0) (Précisez dans l'ordre)
Au fait, il semble que plus le score est petit, mieux c'est, donc le poids doit être une valeur négative.

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

Comme indiqué ci-dessous, calculons jusqu'à environ 500 générations avec 300 individus.

    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

Une fois exécuté, le processus d'apprentissage sera généré comme indiqué ci-dessous.

$ 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

C'est une spécification de découpe que le résultat est sorti en standard au format tableau, format CSV, format TSV.
Traitez-le correctement et collez-le sur Excel pour l'utiliser.
Au fait, le temps d'exécution était inférieur à 2 minutes

résultat

Donc, j'ai essayé d'une manière ou d'une autre et le résultat était le suivant
(Les données sont différentes du résultat de l'implémentation ci-dessus, mais ne vous inquiétez pas)

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

Les caractères gras correspondent aux conditions non remplies
Cela fonctionne principalement pour les conditions assez compliquées

À la fin

Si vous pouvez le faire jusqu'à présent, il semble que vous puissiez effectuer un changement immédiatement en effectuant des ajustements précis manuellement.
Cependant, je pensais que moins de 2 minutes prendraient trop de temps.
J'ai essayé d'accélérer certaines choses en le distribuant avec scoop, mais cela a fini par devenir un goulot d'étranglement du processeur et cela n'a pas été beaucoup plus rapide.
Cela peut être plus rapide si vous utilisez un GPU comme le Deep Learning
Il est apparu dans Niveau papier, mais aucune implémentation n'a été trouvée. .. Il est difficile de créer le vôtre avec cuda. ..
Au fait, moi, ma sœur est infirmière, et elle semble regarder l'horaire pendant environ une semaine pour faire des quarts de travail, alors j'ai pensé que ce serait très utile si je créais sérieusement des contraintes.

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