[PYTHON] Automatische Erstellung eines Arbeitsplans mithilfe der Tabusuche
zunaechst
In diesem Artikel erstellen wir eine 10-Tage-Schicht für 7 Mitarbeiter. In den Elementen der Prozession gibt es Variationen von 4 Stunden Arbeit, 8 Stunden Arbeit und 0 Stunden Arbeit (Urlaub). Nachdem Sie diesen Artikel gelesen haben, können Sie endlich den folgenden Arbeitsplan erstellen.
| Mond | Feuer | Wasser | Holz | Geld | Boden | Tag | Mond | Feuer | Wasser | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 8 | 8 | 8 | 4 | 0 | 8 | 8 | 8 | 4 |
| 1 | 4 | 8 | 4 | 4 | 4 | 8 | 0 | 8 | 4 | 4 |
| 2 | 0 | 8 | 4 | 0 | 0 | 4 | 8 | 4 | 4 | 8 |
| 3 | 4 | 0 | 8 | 0 | 0 | 4 | 4 | 8 | 4 | 8 |
| 4 | 8 | 0 | 4 | 4 | 4 | 0 | 0 | 8 | 4 | 8 |
| 5 | 4 | 4 | 4 | 0 | 4 | 8 | 0 | 8 | 8 | 8 |
| 6 | 0 | 8 | 4 | 8 | 4 | 8 | 0 | 4 | 4 | 0 |
Beginnen wir mit der Erklärung des Algorithmus.
Tabu-Suchalgorithmus
① Erstellung der ersten Lösung ② Erstellung einer Nachbarschaftslösung ③ Optimieren Sie mit einer Strafe, um die Randbedingungen zu erfüllen
Das war's auf den Punkt gebracht. Es ist ein Bild, das zufällig aus dem Array von [0, 4, 8] extrahiert und das Array füllt, um die Randbedingung zu erfüllen.
Eine erste Lösung erstellen
self.ns = np.zeros((person_num, days_num))
self.ns2 = np.zeros((person_num, days_num))
self.ns3 = np.zeros((person_num, days_num))
Wir erstellen eine Matrix mit allen 0 Elementen (Anzahl der Mitarbeiter x Anzahl der zu berechnenden Tage).
index_num = self.choice_index()
index_num2 = self.choice_index()
index_num3 = self.choice_index()
Wir haben jeweils 3 Indizes ausgewählt, um 3 Nachbarlösungen zu erstellen.
Einschränkungen
if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
penalty = penalty + 1
if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
penalty2 = penalty2 + 1
if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
penalty3 = penalty3 + 1
Wir definieren eine Einschränkung, dass die wöchentliche Arbeitszeit der drei Nachbarschaftslösungen innerhalb von 40 bis 64 Stunden liegt. Wenn die Einschränkungen nicht erfüllt sind, wird die Strafe um eins erhöht.
Das Herzstück der Tabusuche
Anhand der "Tabuliste", die die Übergänge aufzeichnet, die in eine schlechte Lösung geraten sind, werden wir andere als die einmal gesuchte untersuchen. Infolgedessen wird die Konvergenz schneller und es kann eine ungefähre Lösung erhalten werden.
Ganzer Code
%load_ext Cython
import numpy as np
import itertools
import matplotlib.pyplot as plt
import pandas as pd
class TabuSearch():
tabu_list = []
penalty_arr = []
def __init__(self, person_num = 7, days_num = 10, select_num = 3):
self.person_num = person_num
self.penalty_old = 7 * 2 + 10
self.days_num = 10
self.select_num = select_num
self.jikkou_num = 1
#Initialisierung der Näherungslösung
self.s_good = np.zeros((person_num, days_num))
self.index_list = list(itertools.product(range(0, person_num), range(0, days_num), repeat=1))
self.ns = np.zeros((person_num, days_num))
self.ns2 = np.zeros((person_num, days_num))
self.ns3 = np.zeros((person_num, days_num))
def choice_index(self):
return np.random.choice(list(range(0, self.person_num*self.days_num)), self.select_num, replace=False)
def generate_near(self):
#Erstellen einer Nachbarschaftslösung
#Da die Nachbarschaftslösung lokal transformiert wird, wählen Sie drei Elemente aus. (3 ist angemessen)
#Index zu ersetzen
index_num = self.choice_index()
index_num2 = self.choice_index()
index_num3 = self.choice_index()
penalty = 0
penalty2 = 0
penalty3 = 0
ns = np.zeros((self.person_num, self.days_num))
ns2 = np.zeros((self.person_num, self.days_num))
ns3 = np.zeros((self.person_num, self.days_num))
chg_flag = True
#Wert zu ändern
new_var = [np.random.choice([8,4,0]) for i in range(0, self.select_num)]
for j in range(0, len(self.tabu_list)):
# tabu_Siehe die ersten 7 Werte in der Liste
if j == 7:
break
for k in range(0, self.select_num):
if index_num[k] == TabuSearch.tabu_list[j][k]:
chg_flag = False
if index_num2[k] == TabuSearch.tabu_list[j][k]:
chg_flag = False
if index_num3[k] == TabuSearch.tabu_list[j][k]:
chg_flag = False
#Aktualisieren Sie den Wert nicht, wenn er in der Tabuliste enthalten ist
if chg_flag == True:
for i in range(0, len(index_num)):
self.ns[self.index_list[index_num[i]][0], self.index_list[index_num[i]][1]] = new_var[i]
self.ns2[self.index_list[index_num2[i]][0], self.index_list[index_num2[i]][1]] = new_var[i]
self.ns3[self.index_list[index_num3[i]][0], self.index_list[index_num3[i]][1]] = new_var[i]
for i in range(0, len(self.ns)):
if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
penalty = penalty + 1
if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
penalty2 = penalty2 + 1
if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
penalty3 = penalty3 + 1
if penalty < self.penalty_old and penalty <= penalty2 and penalty <= penalty3:
self.s_good = self.ns
#Strafe nur, wenn die Tabuliste keinen Wert enthält_Fügen Sie arr einen Wert hinzu
TabuSearch.penalty_arr.append(penalty)
for j in range(0, len(self.ns)):
print(f"{j+1}Gesamtwert der Zeile", str(sum(self.ns[j])))
self.jikkou_num = self.jikkou_num + 1
return penalty
elif penalty2 < self.penalty_old and penalty2 <= penalty3:
self.s_good = self.ns2
TabuSearch.penalty_arr.append(penalty2)
for j in range(0, len(self.ns)):
print(f"{j+1}Gesamtwert der Zeile", str(sum(self.ns2[j])))
self.jikkou_num = self.jikkou_num + 1
return penalty2
elif penalty3 < self.penalty_old:
self.s_good = self.ns3
TabuSearch.penalty_arr.append(penalty3)
for j in range(0, len(self.ns)):
print(f"{j+1}Gesamtwert der Zeile", str(sum(self.ns3[j])))
self.jikkou_num = self.jikkou_num + 1
return penalty3
else:
#Nehmen Sie schlechte Dinge auf und versuchen Sie, gute Richtungen zu optimieren
TabuSearch.tabu_list.insert(0, index_num)
TabuSearch.tabu_list.insert(0, index_num2)
TabuSearch.tabu_list.insert(0, index_num3)
return self.penalty_old
else:
self.jikkou_num = self.jikkou_num + 1
TabuSearch.penalty_arr.append(self.penalty_old)
return self.penalty_old
def execution(self, times=1000000):
#Code zum Beenden, wenn die Summe jeder Zeile innerhalb eines bestimmten Bereichs liegt
for i in range(0, times):
penalty = self.generate_near()
if penalty < self.penalty_old:
print(f"{self.jikkou_num}Zweite Ausführung")
print("Strafwert", penalty)
print("Gesamtstrafenwert", self.penalty_old)
self.penalty_old = penalty
if penalty == 0:
df = pd.DataFrame(self.s_good, columns=("Mond" , "Feuer", "Wasser", "Holz", "Geld", "Boden", "Tag", "Mond", "Feuer", "Wasser"))
print(df.to_markdown())
break
def plot_loss(self):
plt.plot(TabuSearch.penalty_arr)
def output_markdown(self):
df = pd.DataFrame(self.s_good, columns=("Mond" , "Feuer", "Wasser", "Holz", "Geld", "Boden", "Tag", "Mond", "Feuer", "Wasser"))
print(df.to_markdown())
Lauf
ts = TabuSearch()
ts.execution(100000)
Ein Teil der Ausgabe
Gesamtwert in der ersten Zeile 56.0
Gesamtwert in der zweiten Zeile 48.0
Gesamtwert in der dritten Zeile 40.0
Gesamtwert in der 4. Zeile 40.0
Gesamtwert in der 5. Zeile 40.0
Gesamtwert in Zeile 6 48.0
Gesamtwert in Zeile 7 40.0
232. Ausführung
Strafwert 0
Gesamtstrafenwert 1
| |Mond|Feuer|Wasser|Holz|Geld|Boden|Tag|Mond|Feuer|Wasser|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
| 0 | 0 | 8 | 8 | 8 | 4 | 0 | 8 | 8 | 8 | 4 |
| 1 | 4 | 8 | 4 | 4 | 4 | 8 | 0 | 8 | 4 | 4 |
| 2 | 0 | 8 | 4 | 0 | 0 | 4 | 8 | 4 | 4 | 8 |
| 3 | 4 | 0 | 8 | 0 | 0 | 4 | 4 | 8 | 4 | 8 |
| 4 | 8 | 0 | 4 | 4 | 4 | 0 | 0 | 8 | 4 | 8 |
| 5 | 4 | 4 | 4 | 0 | 4 | 8 | 0 | 8 | 8 | 8 |
| 6 | 0 | 8 | 4 | 8 | 4 | 8 | 0 | 4 | 4 | 0 |
Zeichnen Sie den Übergang des Strafwerts
ts.plot_loss()
Arbeitsplan mit Abschrift anzeigen
ts.output_markdown()
| |Mond|Feuer|Wasser|Holz|Geld|Boden|Tag|Mond|Feuer|Wasser|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
| 0 | 0 | 8 | 8 | 8 | 4 | 0 | 8 | 8 | 8 | 4 |
| 1 | 4 | 8 | 4 | 4 | 4 | 8 | 0 | 8 | 4 | 4 |
| 2 | 0 | 8 | 4 | 0 | 0 | 4 | 8 | 4 | 4 | 8 |
| 3 | 4 | 0 | 8 | 0 | 0 | 4 | 4 | 8 | 4 | 8 |
| 4 | 8 | 0 | 4 | 4 | 4 | 0 | 0 | 8 | 4 | 8 |
| 5 | 4 | 4 | 4 | 0 | 4 | 8 | 0 | 8 | 8 | 8 |
| 6 | 0 | 8 | 4 | 8 | 4 | 8 | 0 | 4 | 4 | 0 |
