Um den Algorithmus zu studieren, habe ich versucht, das Schichtplanungsproblem zu lösen. Das heißeste Thema im Mai 2020, als ich diesen Artikel schrieb, war COVID-19, und angesichts der Auswirkungen auf mein Viehleben würde ich gerne zur Arbeit kommen (Anfragen von Mitarbeitern bis letztes Jahr). Ich denke, es ist eine gute Idee, sowohl die Anfrage des Unternehmens zur Arbeit als auch die Telearbeit zu erfüllen (Anfrage des Unternehmens. Bis zum letzten Jahr die Anfrage des Mitarbeiters nach Telearbeit). Ja, es ist ein sogenanntes Schichtplanungsproblem.
Versuchen wir zunächst das Zing-Modell, das auch in der Quantenglühmethode von D-Wave verwendet wird. Das Quantenbackverfahren kann jedoch nicht auf einem gewöhnlichen Computer ausgeführt werden, so dass das gewöhnliche Backverfahren verwendet wird. Es ist genauso wie Fujitsus Digital Annealer.
Es war jedoch mühsam, einen Prozess zum Lösen des Zing-Modells durch die Glühmethode zu erstellen, also D-Wave's Neal. Ich habe HTML verwendet). Es ist auch ziemlich schwierig, ein aufsteigendes Modell von Hand zu erstellen (oder besser gesagt, meine mathematischen Fähigkeiten sind zu gering, um die Teile zu verstehen), daher war die Erzeugung des aufsteigenden Modells [PyQUBO of Recruit Communications](https: //). Ich habe pyqubo.readthedocs.io/en/latest/) verwendet.
Der Code zur Lösung des Problems mit neal und PyQUBO sieht also so aus.
import numpy as np
from funcy import *
from neal import SimulatedAnnealingSampler
from pyqubo import Array, Constraint, Placeholder, Sum
M = 5 # Anzahl der Mitarbeiter
D = 10 # Tage
BETA_RANGE = (5, 100) # Die Umkehrung der Temperatur des geglühten. Je größer die Lösung ist, desto stabiler ist die Lösung, aber desto wahrscheinlicher ist es, dass sie in eine lokale Lösung fällt.
NUM_READS = 10 # Anzahl der Gerbungen. NUM_READS-Lösungen werden generiert. Je mehr Sie haben, desto wahrscheinlicher ist es, dass Sie eine bessere Lösung finden.
NUM_SWEEPS = 100000 # Häufigkeit, mit der der Bräunungsschritt ausgeführt wird. Die Anzahl der Iterationen, um eine einzelne Lösung zu generieren. Je größer der Wert ist, desto wahrscheinlicher ist es, dass eine bessere Lösung erhalten wird.
BETA_SCHEDULE_TYPE = 'linear' # So ändern Sie die Bräunungstemperatur. Wenn es linear ist, ändert es sich linear
# Animieren Sie das Ising-Modell mit neal und geben Sie die Lösung zurück
def solve(hs, js):
response = SimulatedAnnealingSampler().sample_ising(hs, js, beta_range=BETA_RANGE, num_reads=NUM_READS, num_sweeps=NUM_SWEEPS, beta_schedule_type=BETA_SCHEDULE_TYPE, seed=1)
# NUM_READS Gibt die beste Lösung aus zurück
return tuple(response.record.sample[np.argmin(response.record.energy)])
# Definieren Sie die Variablen, aus denen QUBO besteht
xs = Array.create('x', shape=(M, D), vartype='BINARY')
# Definieren Sie Variablen für die Optimierung
a = Placeholder('A')
b = Placeholder('B')
# Definieren Sie QUBO. von hier……
h = 0
# Fügen Sie eine Einschränkung von 2 oder mehr Personen pro Tag und so wenig wie möglich hinzu. Für mehr oder weniger als 2 Personen fallen jetzt Strafen an
for d in range(D):
h + = a * Einschränkung ((Summe (0, M, Lambda m: xs [m] [d]) - 2) ** 2, f'day- {d} ') # 2 ist zumindest negativ Wenn es viele gibt, ist es eine positive Zahl, aber quadrieren Sie sie, um einen positiven Wert zu erhalten
# Fügen Sie eine Einschränkung hinzu, dass Sie an einem anderen Tag nicht mit derselben Person arbeiten werden
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
h + = b * xs [m1] [d1] * xs [m2] [d1] * xs [m1] [d2] * xs [m2] [d2] # xs ist 1 oder 0, also beim Multiplizieren Es wird nur 1 sein, wenn alle 1 sind.
# Kompilieren Sie, um ein Modell zu erstellen
model = h.compile()
# ……Bisher. Definieren Sie QUBO
# Wert der Variablen für die Abstimmung
feed_dict = {'A': 2.0, 'B': 1.0}
# Generiere ein steigendes Modell und löse mit neal
hs, js, _ = model.to_ising(feed_dict=feed_dict)
answer, broken, energy = model.decode_solution(dict(enumerate(solve(hs, js))), vartype='SPIN', feed_dict=feed_dict)
# Das Ergebnis ausgeben
print (f'broken: \ t {len (gebrochen)} ') # Wenn die Einschränkung verletzt wird, wird defekt ausgefüllt.
print (f'energy: \ t {energy} ') # QUBOs Energie. In diesem Modell ist es 0, wenn alle Einschränkungen erfüllt sind.
# Gibt Mitarbeiter aus, die täglich zur Arbeit kommen
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if answer['x'][m][d] == 1 else False, range(M))))
Das Ergebnis der Ausführung dieses Programms sieht also so aus.
broken: 0
energy: 0.0
('D', 'E')
('A', 'D')
('B', 'C')
('A', 'C')
('B', 'D')
('B', 'E')
('C', 'E')
('A', 'E')
('A', 'B')
('C', 'D')
Ja das ist richtig. Jeden Tag kommen zwei Leute zur Arbeit, und es gibt keine gleiche Kombination. Die Ausführungszeit auf meinem Computer betrug übrigens 0,734 Sekunden. Da 10 Lösungen erstellt wurden, 0,073 Sekunden pro Lösung. Neal ist sehr schnell!
[Ising-Modellseite von Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%82%B8%E3%83%B3%E3%82%B0%E6%A8% Wenn Sie A1% E5% 9E% 8B) lesen, können Sie verstehen, dass es sich um ein Gittermodell handelt, das aus Gitterpunkten besteht, die zwei Koordinationszustände annehmen und die Interaktion nur der benachbarten Gitterpunkte berücksichtigen. nicht. Hamiltonian ist ein physikalischer Begriff, aber ist er köstlich? Muss ich von nun an Physik studieren?
Seien Sie versichert. Es sind die Leute, die die Hardware herstellen, die das Zing-Modell verwendet, nicht wir Programmierer, die Physik studieren müssen. Darüber hinaus ist das Zing-Modell in Bezug auf Software eine ziemlich einfache Geschichte.
Lassen Sie mich anhand eines konkreten Beispiels erklären. Ignorieren Sie zunächst das Wortraster (das im Bild vertikal und horizontal zu sein scheint) (wichtig für physische Baumärkte, aber nicht für uns als Programmierer). Stellen Sie sich die beiden Koordinationszustände als spezielle Variablen vor, denen nur -1 oder 1 zugewiesen werden kann. Es ist schwierig, ein Bild von 1 oder -1 zu erhalten. Betrachten wir also den Fall, in dem drei Personen für oder gegen einen Vorschlag stimmen. Wenn Sie zustimmen, ist es 1, und wenn Sie nicht einverstanden sind, ist es -1. Es gibt eine heikle Beziehung zwischen diesen drei Personen, und es fühlt sich gut an, wenn Herr a und Herr b die gleichen Maßnahmen ergreifen, und es fühlt sich gut an, wenn Herr c und Herr b aufgrund einer früheren Ursache unterschiedliche Maßnahmen ergreifen. Ich werde. Wie können wir nun dafür sorgen, dass sich alle unter diesen Bedingungen so wohl wie möglich fühlen?
Computer können nur mit Zahlen umgehen, daher müssen sie irgendwie numerisch ausgedrückt werden. Da a, b und c nur 1 oder -1 annehmen können, können Ausdrücke mit * kleineren * Zahlen, wenn sich jeder wohl fühlt, mit diesem Code ausgedrückt werden.
-1 * a * b + 1 * b * c
Lass uns genauer hinschauen. Das Ergebnis der Multiplikation der Kombination von 1 und -1 ist wie folgt.
| Wert 1 | Wert 2 | Ergebnis |
|---|---|---|
| 1 | 1 | 1 |
| 1 | -1 | -1 |
| -1 | 1 | -1 |
| -1 | -1 | 1 |
Wenn die Werte gleich und unterschiedlich sind, wird sie bequem in 1 und -1 unterteilt. Wenn Sie also dieses Ergebnis mit -1 multiplizieren, ist es ein kleiner Wert von -1, wenn es gleich ist, und ein großer Wert von 1, wenn es unterschiedlich ist. Sie sehen, Sie könnten es mit der obigen Formel gut ausdrücken, richtig?
Es ist jedoch unpraktisch, weil es nicht so vielseitig ist, wie es ist. Machen wir es also vielseitig. Die Werte in der folgenden Tabelle werden zu den Multiplikationsergebnissen aller Variablen hinzugefügt (a * a ist jedoch jedes Mal gleich, daher ist es bedeutungslos. Lassen Sie es leer. Da a * b und b * a der gleiche Wert sind, geben Sie den Wert nur in einem ein.) Ich werde es aufhängen.
| a | b | c | |
| a | -1 | 0 | |
| b | 1 | ||
| c | |||
Sie können es auf 0 setzen, wo es keine Rolle spielt. Wenn ich also den Code zur Berechnung anhand dieser Tabelle schreibe, sieht es so aus. Stellen Sie sich vor, a, b und c befinden sich in einem Array mit dem Namen "xs" und die Werte in der obigen Tabelle in einer Variablen mit dem Namen "js".
def energy():
result = 0
for i in range(1, len(xs)):
for j in range(i + 1, len(xs)):
result += js[i][j] * xs[i] * xs[j]
return result
Selbst wenn sich die Beziehung aufgrund der Versöhnung von Herrn b und Herrn c ändert, kann sie mit demselben Code ausgedrückt werden (eigentlich, um sie allgemeiner zu machen ("a" und "). Eine andere Variable (um auszunutzen, ob boderc 1 oder -1 ist) (verwenden Sie auch das hs` im getemperten Code unter Verwendung des Zing-Modells)). Und dieses vielseitige und wundervolle Modell ist Rising.
An diesem Punkt ist es leicht zu erkennen, ob es besser oder schlechter ist, indem Sie die entsprechenden Elemente von "xs" umdrehen und die Ergebnisse im obigen Code vergleichen. Es kann durch die sogenannte Bergsteigermethode gelöst werden. Als ich es jedoch nachschlug, sagte die Erklärung der Bergsteigermethode, dass es leicht war, in eine lokale Lösung zu fallen, und ich war ein wenig besorgt. Selbst wenn das Ergebnis des obigen Codes am Anfang etwas schlechter ist, werde ich Bewegung zulassen, der letzte ist der Grad Lassen Sie uns dieses Problem umgehen, indem wir es reduzieren und in Richtung Verbesserung bewegen. Dies wird als Bräunungsmethode bezeichnet, da es dem Bräunen in der realen Welt ähnelt, und der Grad der Vergebung, selbst wenn das Ergebnis schlecht ist, wird als Temperatur bezeichnet, die dem Bräunen in der realen Welt folgt. Da es Energie ist, die dem Ergebnis des obigen Codes in der realen Welt entspricht, wird das Ergebnis des obigen Codes Energie genannt. Deshalb ist es ein Ausdruck wie das Finden einer Kombination, die die Energie minimiert und gleichzeitig die Temperatur senkt. D-Waves Neal erledigt dies sehr effizient.
Wenn Sie also versuchen, es zu brennen, sollte das Ergebnis a = 1, b = 1, c = -1 oder a = -1, b = -1, c = 1 sein. In beiden Fällen ist die Energie das Minimum -2, so dass sich jeder gut fühlt.
Dann müssen Sie nur noch die Werte in der obigen Tabelle gemäß den am Anfang dieses Artikels genannten Einschränkungen erstellen ... aber das ist ziemlich schwierig. Ich weiß nicht, was ich tun soll, wenn mehrere Variablen beteiligt sind, wie in den Einschränkungen dieses Artikels (es scheint, dass eine Variable hinter den Kulissen hinzugefügt und in Bezug auf die hinzugefügte Variable definiert wird). Verwenden wir also PyQUBO von Recruit Communications. Mit PyQUBO wird der Ausdruck in der Formel in ein vielseitiges Zing-Modell umgewandelt. Da es schwierig ist, an 1 und -1 zu denken, kann es auch in Form von QUBO mit 1 und 0 definiert werden (ich konnte es nicht verstehen, aber es scheint, dass das Zing-Modell und QUBO ineinander konvertiert werden können). Ich werde.
Lassen Sie es uns konkret ausdrücken. Wenn Sie sich "xs" als zweidimensionales Array von "M" × "D" vorstellen und es auf 1 setzen, wenn Sie zur Arbeit gehen, und auf 0, wenn Sie nicht zur Arbeit gehen, kann die Anzahl der Mitarbeiter, die am ersten Tag zur Arbeit kommen, wie folgt berechnet werden.
result = 0
for m in range(M):
result += xs[m][0]
return result
Je näher dieses Ergebnis an 2 liegt, desto besser und es spielt keine Rolle, ob es mehr oder weniger ist. Also möchte ich 2 und abs subtrahieren, um den absoluten Wert zu finden ... aber leider kann ich eine Funktion wie abs nicht verwenden. Was zu tun ist, ist es zu quadrieren. Ich bin nicht gut in Mathematik, daher bin ich mir nicht sicher, aber es scheint, dass das Multiplizieren von Minus mit Minus ein Plus ergibt. Außerdem bietet PyQUBO eine Funktion zum Berechnen der Summe, die als "Summe" bezeichnet wird. Der Code lautet also wie folgt.
h += (Sum(0, M, lambda m: xs[m][0]) - 2) ** 2
Wenn nun 2 Menschen zur Arbeit kommen, ist die Energie am geringsten und die Energie größer oder kleiner als 2.
Für den Rest der verschiedenen Mitarbeiterpaare ist es in Ordnung, wenn Sie an verschiedenen Tagen nicht dieselbe Kombination haben. Wenn Sie der Einfachheit halber etwas genauer überlegen, z. B. "Mitarbeiter 0 und Mitarbeiter 1 werden bestraft, wenn der 2. und 3. Tag gleich sind", kann dies durch den folgenden Code ausgedrückt werden.
h += xs[0][2] * xs[1][2] * xs[0][3] * xs[1][3]
Da es sich um QUBO handelt, ist der Wert des Elements von xs entweder 1 oder 0, daher ist er 0, es sei denn, Mitarbeiter 0 und Mitarbeiter 1 kommen sowohl an Tag 0 als auch an Tag 1 zur Arbeit, dh an allen Einsen. .. Da alle Einsen die gleiche Kombination sind, ist es als Strafe sehr praktisch, wenn es in diesem Fall 1 wird. Alles, was Sie tun müssen, ist eine Vierfachschleife zu schreiben, um die Kombinationen anderer Mitarbeiter und die Kombinationen anderer Tage abzudecken.
Außerdem haben die meisten Dinge Prioritäten und es ist schwierig, verschiedene Dinge zusammenzufügen (ich denke nicht, dass die Einheitensysteme der beiden gut gemachten Formeln diesmal gleich sind: "Juckreiz" und "es" Ist es nicht schwierig, "Unangenehmkeit" durch Hinzufügen von "Rauschen" zu berechnen?). Multiplizieren wir also die entsprechenden Koeffizienten "a" und "b", damit diese Werte zum Zeitpunkt der Abstimmung angegeben werden können (Juckreiz x "a" + Rauschen x "b" = unangenehm und vorläufig Passen Sie dann die Werte von "a" und "b" entsprechend an. "Platzhalter" ist in einem solchen Fall praktisch. Dieses Mal habe ich verschiedene Dinge ausprobiert und "a = 1.0" und "b = 0.5" gesetzt. Wenn Sie QUBO mit PyQUBO wie folgt definieren, wird es auf einmal in ein steigendes Modell mit model.to_ising () konvertiert, und wenn Sie es mit neal lösen, wird die Antwort zurückgegeben. Es ist auch möglich, D-Wave anstelle von Neal zu verwenden. Sie können es auch mit einem digitalen Annealer lösen und die Ausführungszeit und Genauigkeit mit neal vergleichen. Nun, es ist in der Welt bequem geworden.
Machen wir weiter und machen es mit einem genetischen Algorithmus, der den Namen romantisch erscheinen lässt.
Wie üblich war es mühsam, einen Prozess für genetische Algorithmen zu erstellen, daher verwendete ich eine Open-Source-Bibliothek namens DEAP. Der Code sieht so aus.
from deap import algorithms, base, creator, tools
from functools import reduce
from funcy import *
from random import randint, random, seed
M = 5 # Anzahl der Mitarbeiter
D = 10 # Tage
# Bewertungsfunktion
def evaluate(individual):
# Fügen Sie eine Einschränkung von 2 oder mehr Personen pro Tag und so wenig wie möglich hinzu. Für mehr oder weniger als 2 Personen fallen jetzt Strafen an
def member_size():
result = 0
for d in range(D):
Ergebnis + = abs (reduzieren (Lambda acc, m: acc + Individuum [m * D + d], Bereich (M), 0) - 2) # Da der Wert selbst verwendet wird, kann auch abs verwendet werden.
return result
# Fügen Sie eine Einschränkung hinzu, dass Sie an einem anderen Tag nicht mit derselben Person arbeiten werden
def different_member():
result = 0
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
result += individual[m1 * D + d1] * individual[m2 * D + d1] * individual[m1 * D + d2] * individual[m2 * D + d2]
return result
# Gibt mehrere Bewertungsansichtspunkte als Taple mit den Bewertungsergebnissen von jedem Ansichtspunkt als Element zurück.
return (member_size(), different_member())
# DEAP definiert den genetischen Algorithmus
creator.create ('Fitness', base.Fitness, weight = (-1.0, -0.5)) Je kleiner das Ergebnis von # evalu () ist, desto besser. Fügen Sie dem Gewicht also ein Minus hinzu.
creator.create('Individual', list, fitness=creator.Fitness)
toolbox = base.Toolbox()
toolbox.register('attribute', randint, 0, 1)
toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.attribute, n=M * D)
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutFlipBit, indpb=0.05)
toolbox.register('select', tools.selTournament, tournsize=3)
toolbox.register('evaluate', evaluate)
# Fix zufällige Samen für die Reproduzierbarkeit
seed(1)
# Lösen Sie das Problem mit einem genetischen Algorithmus
population, _ = algorithms.eaSimple(toolbox.population(n=100), toolbox, 0.5, 0.2, 300, verbose=False)
# Holen Sie sich die beste Lösung
individual = tools.selBest(population, 1)[0]
# Das Ergebnis ausgeben
print(f'fitness:\t{individual.fitness.values}')
# Gibt Mitarbeiter aus, die täglich zur Arbeit kommen
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if individual[m * D + d] else False, range(M))))
Und das Ergebnis ist so.
fitness: (0.0, 0.0)
('B', 'E')
('A', 'D')
('B', 'C')
('C', 'E')
('D', 'E')
('C', 'D')
('A', 'C')
('A', 'E')
('B', 'D')
('A', 'B')
Ja. Das ist die richtige Lösung. Die Laufzeit auf meinem Computer betrug 4,595 Sekunden. Wenn Sie der Meinung sind, dass die Verwendung zu langsam ist, lesen Sie bitte die folgende "Einfache Erklärung" bis zum Ende.
Kinder, die von coolen Eltern geboren wurden, sind sehr cool. Und ich wurde von einem Elternteil geboren, der nicht ...
Wie bei der vorherigen Backmethode ist die Methode zum Erstellen einer neuen Lösung wichtig für die Suche nach einer besseren Lösung durch Erstellen einer neuen Lösung. Wenn Sie beispielsweise zufällig eine neue Lösung erstellen, wird diese wahrscheinlich schlechter und Sie finden keine Lösung, auf die Sie warten können. Daher verwendet die Bergsteigermethode eine Lösung in der Nähe der aktuellen Lösung, die eine geringfügige Modifikation der aktuellen Lösung darstellt. Ich denke, es ist wahrscheinlich gut, weil es einer guten Lösung ähnelt. Im genetischen Algorithmus wird die Lösung also wie ein Gen exprimiert, eine neue Lösung wird durch Paarung erstellt und ein Kind wird geboren oder mutiert, und eine bessere Lösung wird mit einem Gefühl natürlicher Selektion erstellt. Ich werde es suchen. Für die Paarung und natürliche Selektion haben wir mehrere Lösungen anstelle einer. Die Kinder cooler Eltern sind ziemlich cool, daher habe ich das Gefühl, dass ich überleben kann, ohne auf dem Heiratsmarkt ausgeschieden zu sein.
Das Wichtigste im genetischen Algorithmus ist also, "wie man die Lösung mit Chromosomen ausdrückt". Wenn Sie wie dieses Mal zur Arbeit kommen und nicht zur Arbeit kommen, können Sie dies mit einer Liste von 0 ausdrücken. Es können beliebige Zahlen verwendet werden (NumPys ndarray, Set, Dictionary, Baumstruktur usw. können ebenfalls verwendet werden). Wenn es sich beispielsweise um ein Problem mit reisenden Verkäufern handelt, ist eine Liste mit reisenden Städtenummern in Ordnung. Beim Autofahren kann die Kraft, mit der Sie auf das Gaspedal oder die Bremse treten, in Gleitkomma ausgedrückt werden. DEAP verfügt über eine Vielzahl von Funktionen, die die Expression verschiedener Gene und Chromosomen ermöglichen. Wenn beispielsweise die Nummer der Stadt, die vom reisenden Verkäufer besucht werden soll, ein Gen ist, Erstellen von Arten von DEAP-Dokumentation Permutation ist nützlich (jetzt müssen Sie keine langwierigen Techniken wie die ordinale Darstellung mehr anwenden!).
Es gibt auch verschiedene Methoden wie Paarung (in genetischen Algorithmen als Kreuzung bezeichnet), Mutation und natürliche Selektion, aber sie implementieren viele davon. Und es bietet auch eine gute Möglichkeit, diese im Paket "Algorithmen" zu kombinieren.
DEAP hat jedoch eine kleine Eigenart in der Verwendung ... Wir werden die von DEAP bereitgestellten Funktionen wiederverwenden, um die zur Lösung des Problems erforderlichen Werkzeuge zu erstellen, aber wir müssen dies mit den Funktionen von DEAP anstelle der normalen Funktionssynthese tun. Um beispielsweise eine "Individual" -Klasse zu definieren, die eine Einzelperson ist (die einer der Lösungen entspricht), müssen Sie dies mit der DEAP-API wie "creator.create (" Invididual ", ...)" tun. Hmm. Das Erstellen sich überschneidender Methoden ist also wie "toolbox.register" ("mate", tools.cxTwoPoint) ". Es ist einfach, eine Methode zu generieren, die allein damit zwei Punkte schneidet, aber wenn möglich wollte ich sie wie ein normales "Teil" schreiben ...
Nun, das ist ein Luxusproblem, also lassen Sie uns schnell ein Programm erstellen. Da Sie die Funktion schreiben müssen, um das Individuum selbst zu bewerten, ist es zweckmäßig, im Fall des genetischen Algorithmus "abs" zu verwenden, wobei auf den Code verwiesen wird, der zum Zeitpunkt des Backens unter Verwendung des Zing-Modells geschrieben wurde. Während ich darüber nachdachte, erstellte ich die Funktion evalu (). Erstellen Sie anschließend eine "Fitness" -Klasse, die die Güte der Lösung bewertet, eine "Individual" -Klasse, die das Individuum ausdrückt, erstellen Sie eine "attribute ()" - Methode, die die Attribute des Chromosoms des Individuums erstellt, und verwenden Sie sie, um das Individuum zu erstellen. Erstellen Sie eine "individual ()" -Methode, die eine "populations ()" - Methode erstellt, mit der eine Population generiert wird. Danach die für den genetischen Algorithmus erforderliche Schnittstellenmethode "mate ()", die Mutationsmethode "mutations ()", die natürliche Auswahlmethode "select ()" und die zuerst erstellte Funktion "evalute ()" Generieren Sie eine aufzurufende evalute () -Methode.
Also habe ich dieses Mal versucht, die einfachste Form des genetischen Algorithmus mit "algorithm.eaSimple ()" auszuführen. Selbst wenn Sie es vollständig der Bibliothek überlassen, erhalten Sie die richtige Antwort, wenn Sie einen genetischen Algorithmus für 300 Generationen mit 100 Personen ausführen.
Übrigens sind die guten Punkte des genetischen Algorithmus, der langsamer war als die Backmethode unter Verwendung des Zing-Modells, dass es viele anwendbare Probleme gibt, weil der Ausdruck der Lösung flexibler ist als das Zing-Modell, und es gibt viel Raum für die Abstimmung, weil es viele Methoden gibt. ist. Ich habe es in diesem Artikel nicht eingestellt, aber wenn Sie die Expression der Chromosomen effizienter gestalten, die Art der Kreuzung ändern und die Wahrscheinlichkeit ändern, dass Mutationen schön sind, ist dies mehr als die Backmethode mit dem Zing-Modell. Es kann möglich sein, eine hochgenaue Lösung mit hoher Geschwindigkeit abzuleiten. Das Stimmen macht Spaß, weil Sie den Effekt sofort sehen können.
Nun, um das zu tun, muss ich verschiedene Methoden genetischer Algorithmen studieren, aber wenn ich studiere, während ich es tatsächlich mit DEAP versuche, denke ich, dass ich es sofort beherrschen kann.
Als ich mich fragte, ob es noch etwas gab, bemerkte ich die ganzzahlige Programmiermethode. Es ist eine Version, die die lineare Programmierung noch schwieriger macht, indem sie auf ganze Zahlen beschränkt wird.
Die lineare Programmiermethode ist ein linearer Ausdruck (ein Ausdruck, bei dem nur eine Variable multipliziert und durch Addition und Subtraktion verbunden wird. 3 * x + y ist ein linearer Ausdruck und 3 * a * a + b scheint ein quadratischer Ausdruck zu sein). Es ist eine Methode, um eine Zielfunktion oder eine Beschränkungsfunktion auszudrücken und mathematisch schnell zu lösen. Die Zielfunktion ist ein Ausdruck, der die Güte der Lösung ausdrückt, als ob sie durch die Backmethode unter Verwendung des Zing-Modells oder des genetischen Algorithmus durchgeführt worden wäre, und die Lösung auswählt, die so groß oder klein wie möglich ist. Die Einschränkungsfunktion ist also ein bedingter Ausdruck, der die Einschränkung der Lösung ausdrückt.
e? Weißt du was du sagst?
Ich weiß es überhaupt nicht, also frag nicht ... Wenn Sie jedoch PuLP verwenden, können Sie die ganzzahlige Planungsmethode (und natürlich die lineare Planungsmethode) schnell ausführen. Der Code sieht so aus.
from functools import reduce
from funcy import *
from pulp import *
M = 5 # Anzahl der Mitarbeiter
D = 10 # Tage
# Definieren Sie die im Problem verwendeten Variablen
xs = LpVariable.dicts('x', (range(M), range(D)), 0, 1, 'Binary')
# Definiere das Problem. von hier……
problem = LpProblem('shift-scheduling-problem', LpMinimize)
# Fügen Sie eine Einschränkung von 2 oder mehr Personen pro Tag hinzu
for d in range(D):
problem += reduce(lambda acc, m: acc + xs[m][d], range(M), 0) >= 2
# Fügen Sie eine Einschränkung hinzu, dass Sie an einem anderen Tag nicht mit derselben Person arbeiten werden
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
Problem + = xs [m1] [d1] + xs [m2] [d1] + xs [m1] [d2] + xs [m2] [d2] <= 3 # Die Ungleichung (<) konnte nicht verwendet werden, also < = 3
problem.writeLP('shift-scheduling-problem')
# ……Bisher. Definiere das Problem
# Lösen Sie das Problem mit der Ganzzahlprogrammierung
status = problem.solve()
# Das Ergebnis ausgeben
print(LpStatus[status])
# Gibt Mitarbeiter aus, die täglich zur Arbeit kommen
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if xs[m][d].value() else False, range(M))))
Und das Ergebnis ist so.
Optimal
('D', 'E')
('C', 'D')
('A', 'E')
('C', 'E')
('B', 'D')
('B', 'C')
('A', 'C')
('A', 'D')
('B', 'E')
('A', 'B')
Es ist eine optimale Lösung. Die Ausführungszeit beträgt 0,132 Sekunden, was sehr schnell ist!
Variablen in PuLP werden mit LpVariable erstellt. Dieses Mal brauchte ich viele Variablen, also habe ich mit "LpVariable.dicts ()" viel auf einmal generiert. Auch diesmal gibt es keine Überlegenheit oder Unterlegenheit in der Lösung, die die Einschränkung erfüllt (wenn Sie versuchen, die Einschränkung verschiedener Mitarbeiterpaare so weit wie möglich zu erfüllen, verringert sich die Anzahl der Personen, die zur Arbeit kommen), sodass nur die Einschränkung definiert wird.
Das Schreiben von Einschränkungen in PuLP ist ein bedingter Ausdruck. 1 Das Ergebnis der Berechnung der Anzahl der Personen in Hinode mit "redu ()" lautet "> = 2". Fügen Sie diesen bedingten Ausdruck zu dem Problem hinzu, das als LpProblem mit + = erstellt wurde. Mit der Einschränkung, dass Sie an einem anderen Tag nicht mit derselben Person arbeiten, ist es ein quaternärer Ausdruck, wenn Sie wie zuvor "xs [] * xs [] * xs [] * xs []" ausführen. Addieren Sie also (in diesem Fall) Als Ergebnis von (linearer Ausdruck) habe ich eine Einschränkung in Form von "<= 3" vorgenommen.
Alles was Sie tun müssen, ist dies zu lösen. Wenn die Bedingung erfüllt werden kann, kann die optimale Lösung mit der kleinsten Zielfunktion unter der Bedingung durch die Magie der Mathematik gelöst und zurückgegeben werden (Übrigens können Sie überprüfen, ob die Bedingung durch "LpStatus [Status]" erfüllt wird. Masu). Ich weiß nicht, welche Art von mathematischer Magie ich benutze, aber es ist in Ordnung, wenn ich nur PuLP "benutze".
Ja, ich weiß nicht, was drin ist, aber PuLP ist erstaunlich, um in so kurzer Zeit die optimale Lösung zu finden ... Natürlich ist es erstaunlich, aber leider ist die Ganzzahlprogrammierung nicht perfekt. Wenn es so einfach ist wie dieses, erhalten Sie sofort eine Antwort. Wenn es jedoch schwierig ist, kann es sehr lange dauern, eine Lösung zu finden. Die Backmethode unter Verwendung eines genetischen Algorithmus oder eines Ing-Modells ist eine Methode, die eine Lösung liefert, die einigermaßen gut zu sein scheint, obwohl sie möglicherweise nicht optimal ist, so dass selbst schwierige Probleme auf irgendeine Weise gelöst werden können. Wenn es ein schwieriges Problem ist, ist es möglicherweise nicht möglich, es mit einem linearen Ausdruck auszudrücken. Wenn die Lösung nicht absolut optimal ist oder wenn das Problem nicht sehr kompliziert ist, ist natürlich die ganzzahlige Programmiermethode (lineare Programmiermethode) besser.
Aber das? Wenn Sie sich beruhigen, können Sie es mit einem einfacheren Programm in kürzerer Zeit lösen. Sehen Sie, wenn Sie in Kombination denken, sieht es so aus …….
from itertools import combinations, cycle
# Generieren Sie eine einzigartige Kombination von zwei Mitarbeitern
Mitglieder = Zyklus (Kombinationen ('ABCDE', 2)) # Sie müssen nicht 10 Tage lang fahren, sondern nur für den Fall
# Ausgabe für 10 Tage
for _ in range(10):
print(next(members))
Wenn Sie es versuchen ...
('A', 'B')
('A', 'C')
('A', 'D')
('A', 'E')
('B', 'C')
('B', 'D')
('B', 'E')
('C', 'D')
('C', 'E')
('D', 'E')
Ja, es ist richtig zu sehen. Die Ausführungszeit betrug 0,028 Sekunden ....
Tatsächlich ist die Auswahl verschiedener Paare sehr einfach, wenn Sie sie programmgesteuert ausdrücken können. So was.
def getPairs(xs):
for i in range(len(xs)):
for j in range(i + 1, len(xs)):
yield xs[i], xs[j]
Ich habe gerade den "Bereich" der "j" -Schleife mit "i + 1" gestartet, damit nicht dasselbe gewählt wird und die Kombination in umgekehrter Reihenfolge nicht gewählt wird. Es ist dieselbe Technik, die ich im Code der Röstmethode unter Verwendung des Zing-Modells verwendet habe, bei der ich an einem anderen Tag nicht mit derselben Person gearbeitet habe. Als ich die von dieser Funktion zurückgegebenen Ergebnisse gezählt habe, war es 10, und das Problem war diesmal, dass ich bei guter Leistung eine Antwort erhalten konnte, die alle Einschränkungen erfüllt.
Also, die Anzahl der Kombinationen, um 2 von 5 zu wählen, ist 10. Ich habe das Gefühl, irgendwo in der Vergangenheit gelernt zu haben ... Als ich es nachgeschlagen habe, [Wikipedia-Kombinationsmathematik](https://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E6%95%B0%E5 Dies ist genau die Kombinationsformel, die die Wiederholung von% AD% A6 nicht zulässt. 5! / (2! * (5-2)!) = 10.
Und weil es ein berühmter Prozess wie dieser ist, werden die Kombinationen in den meisten Programmiersprachen zu einer Bibliothek gemacht. Für den in diesem Artikel verwendeten Python ist das "itertools.combinarions". Es war in Ordnung, nur das Ergebnis von "Kombinationen" auf "Zyklus" anzuwenden, das die Menge wiederholt, um eine unendliche Menge zu erstellen, und die Anzahl der Tage von Anfang an anzuzeigen.
Diesmal ist dies also der Ochi (es tut mir leid für diejenigen, die Ochi aufgrund von Einschränkungen bemerkt haben. Außerdem ist der Begriff Schichtplanungsproblem Angeln. Es tut mir wirklich leid für diejenigen, die ernsthafte Schichtplanungsprobleme haben). Aber was ich in diesem Artikel sagen möchte, ist nicht das Beherrschen von Kombinationen. In diesem Artikel wird argumentiert, dass Animationsmethoden unter Verwendung des Ising-Modells, genetischer Algorithmen, ganzzahliger Programmierung und Kombinationen mithilfe moderner Bibliotheken leicht implementiert werden können. Jede Methode hat ihre Vor- und Nachteile, daher hängt das Problem davon ab, welche Methode geeignet ist. Wenn ich dann gefragt werde, was ich tun soll, denke ich, ich sollte vorerst verschiedene Dinge ausprobieren. Weil es so einfach zu implementieren ist.
Recommended Posts