[PYTHON] Durch Kombinationsoptimierung (Backmethode) in Teams aufteilen
Einführung
Daher werde ich dieses Mal eine ungefähre Lösungsmethode für die Backmethode mit Python + simannal vorstellen.
Was ist simanneal
simanneal ist ein Paket für die Bräunungsmethode.
** Installationsmethode **
pip install simanneal
** Grundlegende Verwendung **
- Erstellen Sie eine Unterklasse der Annealer-Klasse.
- Überschreiben Sie move () und implementieren Sie Bewegungsregeln für Suchpunkte
- Überschreiben Sie Energie () und implementieren Sie die Zielfunktion
- Erstellen Sie ein Problemobjekt, indem Sie dem Konstruktor der erstellten Klasse eine erste Lösung geben.
- Führen Sie die Glühmethode für das Problemobjekt .anneal () aus.
- Holen Sie sich die Lösung im Problemobjekt .state.
Die Einschränkungen des Optimierungsproblems müssen in move () und energy () ausgedrückt werden.
Siehe auch "Beispiel: Optimierung durch Python + Simanneal" weiter unten.
Das Problem, das Sie lösen möchten
Es befasst sich mit dem gleichen Problem wie beim letzten Mal. Informationen zum Hintergrund finden Sie im vorherigen Artikel. Lösen Sie das folgende Problem bei der Kombinationsoptimierung.
\begin{align}
\text{minimize} \quad &\sum_{j=1}^m \Bigl(\sum_{k=1}^l \Bigl|\sum_{i=1}^n a_{i,k} x_{i,j} - \mu_j \Bigr|\Bigr) + 1.5\sum_{j=1}^m\Bigl|\sum_{i=1}^n b_i x_{i,j} -\nu\Bigr| \tag{2.1}\\
\text{subject to} \quad &\mu_j = \frac{1}{l}\sum_{k=1}^l\sum_{i=1}^n a_{i,k}x_{i,j} &j=1,\ldots,m \tag{2.2}\\
& \nu = \frac{1}{m} \sum_{j=1}^m \sum_{i=1}^n b_i x_{i,j} \tag{2.3}\\
&\sum_{j=1}^m x_{i,j} = 1 &i=1,\ldots,n \tag{2.4}\\
& x_{i,j} \in \{0,1\} &i=1,\ldots,n;\, j=1,\ldots,m \tag{2.5}\\
\end{align}
Beim letzten Mal habe ich den absoluten Wert von hier entfernt und eine Transformation vorgenommen, um daraus ein lineares Planungsproblem zu machen, aber mit der Backmethode ist es in Ordnung, wie es ist.
Beispiel: Optimierung durch Python + Simanneal
Wir werden uns mit dem gleichen Beispiel wie beim letzten Mal befassen.
- Teilen Sie 6 Personen in 3 Teams.
- Es gibt vier Arten von Kommunikationsfähigkeiten.
grouping.py
from simanneal import Annealer
import random
class GroupingProblem(Annealer):
def __init__(self, init_state):
super(GroupingProblem, self).__init__(init_state) # important!
#Suchpunktbewegungsregeln
def move(self):
#Verschiebe das zufällig ausgewählte Mitglied m1 von Team t1 zu Team t2
m1 = random.choice(list(range(nmembers)))
t1 = self.state[m1].index(1)
t2 = random.choice(list(range(nteams)))
self.state[m1][t1], self.state[m1][t2] = self.state[m1][t2], self.state[m1][t1]
#Zielfunktion
def energy(self):
v = 0
nu = sum(sum(b[i] * self.state[i][j] for i in range(nmembers)) for j in range(nteams)) / nteams
for j in range(nteams):
mu_j = sum(sum(scores[i][k] * self.state[i][j] for i in range(nmembers)) for k in range(nskills)) / nskills
for k in range(nskills):
v += abs(sum(scores[i][k] * self.state[i][j] for i in range(nmembers)) - mu_j)
v += 1.5 * abs(sum(b[i] * self.state[i][j] for i in range(nmembers)) - nu)
return v
if __name__ == '__main__':
#Beispiel
teams = ['A', 'B', 'C']
members = ['P', 'Q', 'R', 'S', 'T', 'U']
skills = ['Controller', 'Promoter', 'Supporter', 'Analyzer']
scores = [[6, 0, 1, 3],
[2, -1, 3, 5],
[2, 4, 0, 0],
[3, 4, 5, 0],
[0, 2, 1, 4],
[2, 3, -1, 1]]
nteams = len(teams) #Anzahl der Teams
nmembers = len(members) #Anzahl der Mitglieder
nskills = len(skills) #Anzahl der Fähigkeitstypen
b = [sum(ai) for ai in scores] #Summe der Fähigkeiten jedes Mitglieds
#Erstzuteilung
init_state = [[0 for j in range(nteams)] for i in range(nmembers)]
for i in range(nmembers):
init_state[i][0] = 1 #Zunächst gehören alle zu Team A.
prob = GroupingProblem(init_state)
prob.steps = 100000
prob.copy_strategy = "deepcopy"
prob.anneal() #Brennende Ausführung
for i,s in enumerate(prob.state):
print(members[i], teams[s.index(1)])
Wenn Sie dies tun, sehen Sie den Fortschritt des Bräunens.
$ pypy grouping.py
Temperature Energy Accept Improve Elapsed Remaining
2.50000 23.50 35.60% 0.70% 0:00:04 0:00:00
('P', 'A')
('Q', 'C')
('R', 'C')
('S', 'B')
('T', 'A')
('U', 'B')
Es ergänzt jeden von simanneal angezeigten Artikel.
- Temperatur: Temperatur. Je größer dieser Wert ist, desto schwerwiegender ist die Zustandsänderung.
- Energie: Energie. Der Wert der Zielfunktion.
- Akzeptieren: Übergangswahrscheinlichkeit. Wenn dieser Wert groß ist, wechselt er in einen schlechten Zustand (um der lokalen Lösung zu entkommen). Dieser Wert hängt von Energie und Temperatur ab.
- Verbessern: Die Verbesserungsrate der Zielfunktion zum Zeitpunkt des Übergangs.
- Verstrichen: Verstrichene Zeit.
- Verbleibende: Verbleibende Zeit.
Schließlich werden Temperatur und Verbesserung kleiner und die Lösung konvergiert.
abschließend
Ich habe vorgestellt, wie das Problem der Kombinationsoptimierung mit Python + simanneal gelöst werden kann. simanneal ist ein sehr praktisches Paket, mit dem Sie die Bräunungsmethode einfach durchführen können. Simanneal kann auch auf Pypy ausgeführt werden. Wenn die Operation für jede Iteration (der Inhalt von move () und enargy ()) einfach ist, kann eine Beschleunigung durch Verwendung von pypy erwartet werden.
Hinweis: Die Verwendung von numpy.array mit pypy ist langsam. Bei Verwendung von pypy ist es schneller, die Map oder for-Anweisung in der Liste zu drehen, als die Vektoroperation von numpy.array zu verwenden.
Referenz
- perrygeo/simanneal: Python module for Simulated Annealing optimization
- [Gebackene Methode-Wikipedia](https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97 % E6% B3% 95)
- Mehrdimensionale Array-Berechnung ohne Numpy
Recommended Posts