[PYTHON] Lösung des Planungsproblems der Krankenschwester (Schichtoptimierung) mit einem genetischen Algorithmus

Dieser Beitrag

• Als ich das Optimierungsproblem, das als Krankenschwester-Planungsproblem bezeichnet wird, mit einem genetischen Algorithmus löste, war es ziemlich genau, es ist also eine Aufzeichnung.
• Ich verwende eine Bibliothek namens deap in Python

Annahme

Krankenschwester Planungsproblem

• Es liegt ein [Nurse Scheduling Problem] vor (http://www.msi.co.jp/nuopt/glossary/term_9ad8057bc9aa1325cae9843e345fd8c9034ef119.html).

Dies ist ein Problem, das den Arbeitsplan von Krankenschwestern bestimmt, die in medizinischen Einrichtungen wie Krankenhäusern arbeiten, und ein typisches Beispiel für das Schichtplanungsproblem ist. Aufgrund der komplizierten Schichtarbeit wie Tagschicht, Abendschicht, Nachtschicht und verschiedener Einschränkungen ist es schwierig, den Zeitplan tatsächlich zu finden.

• Kurz gesagt, es plant automatisch die Schichtarbeit optimal.
• Es gibt verschiedene Einschränkungen, von grundlegenden Dingen, die die erforderliche Anzahl von Personen, Fairness, wesentliche Qualifikationen / Rollen erfüllen, diese beiden Personen (weil sie nicht nahe beieinander sind?) Können nicht zusammengefügt werden usw. Es fühlt sich wie ein Problem an und es ist schwierig, eine perfekte Antwort zu finden. Es scheint also ein Bereich zu sein, der nach einer ungefähren Lösung sucht.

Genetischen Algorithmus

• Es scheint verschiedene Möglichkeiten zu geben, das obige Problem zu lösen, aber [Genetischer Algorithmus](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) scheint eine relativ wichtige Methode zu sein.
• Der genetische Algorithmus wird im Allgemeinen durch die folgende Methode optimiert.
• Erstellen Sie viele "Individuen", die Daten enthalten (normalerweise eindimensionale Sequenzen oder Taples wie Gene).
• Die Daten der zu Beginn erstellten Person sind zufällig
• Fördern Sie die Generation, während Sie das Individuum verändern, indem Sie zwei Individuen kombinieren (Kreuzung), zufällig mutieren (Mutation) usw.
• Bewerten Sie eine Person basierend darauf, wie gut die Daten der Person die vordefinierten Einschränkungen erfüllen
• Passen Sie es so an, dass Personen mit hervorragenden Ergebnissen auch im Verlauf der Generation überleben
• Nach einer bestimmten Generation wird die Person mit der höchsten Gesamtpunktzahl als ungefähre Lösung erhalten.
• Diese Methode kann für die allgemeine Kombinationsoptimierung verwendet werden, um auch bei der Optimierung diskrete Lösungen zu finden.
• Für Details ist es leicht zu verstehen, dass es [hier] ist (http://algoful.com/Archive/Algorithm/ga).
• Das "OneMax-Problem", das mit zunehmender Anzahl von Einsen eine hohe Punktzahl aufweist, ist insbesondere einfacher und am einfachsten zu verstehen.

Also, wie man sich bewirbt

• Wie kann der oben genannte genetische Algorithmus angewendet werden, um das Planungsproblem der Krankenschwester zu lösen? Es ist jedoch ein Bild, dass die dem Individuum gegebenen Daten als Verschiebungsrahmen verwendet werden.
• Beispiel) Angenommen, Sie versuchen, eine Schicht von 3 Personen wie folgt zu verschieben (1 ist der zuzuweisende Rahmen).

• Hier werden die einzelnen Daten erhalten, indem Nullen von Mitarbeiter 0 zu Mitarbeiter 2 in einem Array verbunden werden.
• Mit anderen Worten, im obigen Fall werden die folgenden eindimensionalen Array-Daten bereitgestellt.

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

• Erstellen Sie eine geeignete Bewertungslogik, um zu berechnen, inwieweit diese Person verschiedene Einschränkungen erfüllt, und treiben Sie die Generierung gemäß den Regeln des genetischen Algorithmus voran.
• Dann bleibt ein besseres Individuum (= es wird eine optimalere Kombination erhalten).

Implementiert in Python / deap

Fahren wir konkret mit der Implementierung fort.

Verwendung von Deap

• Implementierung implementiert Python, das stark im maschinellen Lernen ist
• Umfangreiche Bibliothek genetischer Algorithmen namens deap
• Normalerweise mit Pip installieren (Details weggelassen)

pip install deap

• Die Verwendung des OneMax-Problems in [hier] ist leicht zu verstehen (http://testpy.hatenablog.com/entry/2017/01/09/213846).

Beispielspezifikationen

Die Spezifikationen dieses Beispiels sind wie folgt.

Mitarbeiter und Schichtwünsche

• Die Anzahl der Mitarbeiter beträgt 10, und die folgenden Schichtanfragen werden gestellt.

• Die erforderliche Anzahl von Mitarbeitern ist die Anzahl der für dieses Stück erforderlichen Mitarbeiter.

Zwang

Stellen Sie sicher, dass Ihre Punktzahl hoch genug ist, um die folgenden Einschränkungen zu erfüllen. Die Zahlen in Klammern sind Gewichte und stellen die Priorität der Einschränkung dar.

• Die erforderliche Anzahl von Mitarbeitern und die Anzahl der zugewiesenen Mitarbeiter müssen übereinstimmen (10)
• Nicht Frames zuweisen, die der Mitarbeiter nicht möchte (100)
• Weisen Sie mindestens die Hälfte der von jedem Mitarbeiter gewünschten Anzahl von Frames zu (1)
• Da er es angefordert hat, möchte ich es so weit wie möglich aufnehmen.
• Achten Sie darauf, einen Administrator zuzuweisen (100)
• Administratoren sind Mitarbeiter 3, 5, 9
• Dem gleichen Mitarbeiter sollten bis zu 2 Frames pro Tag zugewiesen werden (10).

Codeübersicht

• Das gesamte Programm ist hier
• Ich habe ziemlich oft auf den Code von This OneMax problem verwiesen (≒ copy).

Punkt

• Ich werde nur die Punkte erklären, die gegenüber dem obigen OneMax-Problem für das Krankenschwester-Planungsproblem geändert wurden.

Mitarbeiterdefinition

• Zunächst wird die Mitarbeiterklasse objektorientiert definiert.

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

    #Wille ist der Tag_Zeitzone. 1 ist Morgen, 2 ist Mittag, 3 ist Nacht.
    #Beispiel) mon_1 ist Montagmorgen
    self.wills = wills
...

• Der Ort, an dem die Instanz erstellt wird, ist wie folgt

#Nur am Morgen
e0 = Employee(0, "Yamada", 40, False, ['mon_1', 'tue_1', 'wed_1', 'thu_1', 'fri_1', 'sat_1', 'sun_1'])

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

#Nur an Wochenenden
e2 = Employee(2, "Sato", 18, False, ['sat_1', 'sat_2', 'sat_3', 'sun_1', 'sun_2', 'sun_3'])

#OK überall
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]

Definition der Verschiebung (Rahmen)

• Definiert eine Schichtklasse oder eine Reihe von Frames
• Der "Listen" -Tapel dieser Klasse ist das "Individuum" des genetischen Algorithmus.

#Klasse, die Verschiebung darstellt
#Intern 3(Morgen, Tag und Nacht) *Der 7 ..*10 Personen=Besteht aus 210-dimensionalen Taples
class Shift(object):
  #Definition von top
  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']

  #Geschätzte Anzahl von Personen in jedem Frame
  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 = []

  #Zufällige Daten generieren
  def make_sample(self):
    sample_list = []
    for num in range(210):
      sample_list.append(random.randint(0, 1))
    self.list = tuple(sample_list)
...

• Wie oben erwähnt, machen wir zuerst Personen mit zufälligen Daten
• Die Shift-Klasse ist länger, aber es ist nur eine Datenmanipulationsmethode, mit der die Frames und Benutzer, die die Bedingungen erfüllen, endlos abgerufen werden.

Wertung und Gewichtung

• Die Einzelwertung wird mit der Deap-Funktion gewichtet

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

  #Unterschied zwischen der erwarteten Anzahl von Personen und der zugewiesenen Anzahl von Personen
  people_count_sub_sum = sum(s.abs_people_between_need_and_actual()) / 210.0
  #Anzahl der Zuordnungen zu Zeiten, in denen Sie sich nicht bewerben
  not_applicated_count = s.not_applicated_assign() / 210.0
  #Anzahl der Mitarbeiter mit weniger als der Hälfte der Anzahl der Aufgaben
  few_work_user = len(s.few_work_user()) / 10.0
  #Anzahl der Frames ohne Administrator
  no_manager_box = len(s.no_manager_box()) / 21.0
  #Zugewiesen an alle Morgen, Mittag und Nacht
  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, less_work_user, no_manager_box, three_box_per_day)` weight = (-10.0, -100.0, -1.0, -100.0, -10.0) `` ` (In der angegebenen Reihenfolge angeben)
• Übrigens scheint es, dass je kleiner die Punktzahl, desto besser, also muss das Gewicht ein negativer Wert sein.

Geben Sie die Anzahl der Entwicklungen usw. an.

• Wie unten gezeigt, berechnen wir bis zu 500 Generationen mit 300 Personen.

    pop = toolbox.population(n=300)
    CXPB, MUTPB, NGEN = 0.6, 0.5, 500 #Kreuzungswahrscheinlichkeit, Mutationswahrscheinlichkeit, Anzahl der Schleifen in der Evolutionsberechnung

Lauf

• Bei Ausführung wird der Lernprozess wie unten gezeigt ausgegeben.

$ python nurse_scheduling_by_ga.py 
Die Evolution begann
Bewerten Sie 300 Personen
--0 Generation--
Bewerten Sie 245 Personen
*Parameter 1
  Min 0.242857142857
  Max 0.242857142857
  Avg 0.242857142857
  Std 2.2660056242e-08
*Parameter 2
  Min 0.247619047619
  Max 0.247619047619
  Avg 0.247619047619
  Std 9.49766396283e-09
*Parameter 3
  Min 0.0
  Max 0.0
  Avg 0.0
  Std 0.0
*Parameter 4
  Min 0.142857142857
  Max 0.142857142857
  Avg 0.142857142857
  Std 1.66600046866e-08
*Parameter 5
  Min 0.114285714286
  Max 0.114285714286
  Avg 0.114285714286
  Std 1.19267483008e-08
--1 Generation--
Bewerten Sie 235 Personen
*Parameter 1
  Min 0.238095238095
  Max 0.238095238095
  Avg 0.238095238095
  Std 2.45699769971e-08
*Parameter 2
  Min 0.228571428571
  Max 0.228571428571
  Avg 0.228571428571
  Std 2.38534966016e-08
*Parameter 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Parameter 4
  Min 0.047619047619
  Max 0.047619047619
  Avg 0.047619047619
  Std 4.46646616171e-09
*Parameter 5
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08

(snip)

--499 Generationen--
Bewerten Sie 219 Personen
*Parameter 1
  Min 0.0333333333333
  Max 0.0333333333333
  Avg 0.0333333333333
  Std 2.98168707519e-09
*Parameter 2
  Min 0.0714285714286
  Max 0.0714285714286
  Avg 0.0714285714286
  Std 8.33000234328e-09
*Parameter 3
  Min 0.1
  Max 0.1
  Avg 0.1
  Std 1.31048702444e-08
*Parameter 4
  Min 0.0952380952381
  Max 0.0952380952381
  Avg 0.0952380952381
  Std 8.93293232343e-09
*Parameter 5
  Min 0.0428571428571
  Max 0.0428571428571
  Avg 0.0428571428571
  Std 4.56253018749e-09
--Ende der Evolution--
Die beste Person: [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

• Es ist eine Ausschnittsspezifikation, dass das Ergebnis standardmäßig im Array-Format, CSV-Format und TSV-Format ausgegeben wird.
• Verarbeiten Sie es entsprechend und fügen Sie es zur Verwendung in Excel ein.
• Die Ausführungszeit betrug übrigens weniger als 2 Minuten

Ergebnis

• Also habe ich es irgendwie versucht und das Ergebnis war wie folgt
• (Die Daten unterscheiden sich vom Ergebnis der obigen Implementierung, aber keine Sorge)

• Fett ist, wenn die Bedingungen nicht erfüllt wurden
• Es funktioniert hauptsächlich unter ziemlich komplizierten Bedingungen

Am Ende

• Wenn Sie dies bisher tun können, können Sie anscheinend sofort eine Verschiebung vornehmen, indem Sie die Feineinstellungen manuell vornehmen.
• Ich dachte jedoch, dass weniger als 2 Minuten zu viel Zeit in Anspruch nehmen würden.
• Ich habe versucht, einige Dinge zu beschleunigen, indem ich sie mit scoop verteilte, aber es wurde zu einem CPU-Engpass und es wurde nicht viel schneller.
• Es kann schneller sein, wenn Sie eine GPU wie Deep Learning verwenden
• Es erschien in Papierstufe, aber es wurde keine Implementierung gefunden. .. Es ist schwer, mit Cuda eigene zu machen. ..
• Übrigens, meine Schwester ist eine Krankenschwester, und es scheint, dass sie ungefähr eine Woche lang auf den Zeitplan starrt, um Schichten zu machen, also dachte ich, dass es ziemlich nützlich wäre, wenn ich ernsthaft Einschränkungen schaffen würde.