[PYTHON] Versuchsplanungsmethode und Kombinationsoptimierung

Dies ist der Artikel zum dritten Tag von Algorithm Advent Calendar 2015.

Einführung

Wir werden eine kurze Einführung in die experimentelle Planungsmethode und einen Ansatz durch Kombinationsoptimierung als deren Entwicklung einführen.

Hintergrund

• Angenommen, Sie möchten eine Analyse anhand der Sensorinformationen durchführen. ――Es gibt Sensoren für 10.000 Yen und 30.000 Yen, und es gibt Zeiten, in denen Sie sie nicht einsetzen. Daher gibt es drei Arten von Auswahlmöglichkeiten.
• Es gibt 20 Kandidaten für den Installationsort des Sensors. ――Die Gesamtkosten für den Kauf aller Sensoren müssen unter 50.000 Yen liegen. ――Wenn Sie wissen möchten, wo und wie viele Sensoren für eine effiziente Überprüfung platziert werden sollen.

Als Beispiel für den Fall "Ein Sensor von 10.000 Yen wird an den Punkten A und B platziert, und ein Sensor von 30.000 Yen wird an Punkt C platziert".

der Begriff

Verwenden Sie die folgenden Begriffe.

—— Faktor: Das zu untersuchende Thema, für das Sie das Niveau bestimmen möchten. Dieses Mal ist es ein Kandidat für die Sensorplatzierung. --Level: Möglicher Wert des Faktors. Dieses Mal gibt es drei Arten von Sensorkosten: 0,000 Yen, 10.000 Yen und 30.000 Yen.

• Interaktion: Die Wirkung eines Faktors hängt von der Höhe eines anderen Faktors ab.
• Lateinisches Quadrat: Eine Zahlenmatrix, deren Zeilen oder Spalten nicht dieselben Zahlen enthalten.
• Experimentelle Planungsmethode: Eine Methode zur Durchführung effizienter Experimente. Hier wollen wir die Anzahl der Fälle reduzieren.

Diesmal wird davon ausgegangen, dass keine Interaktion stattfindet.

So ermitteln Sie die Anzahl der Fälle mithilfe der experimentellen Planungsmethode.

Abgesehen von der Hintergrundgeschichte werde ich als allgemeine Theorie ein Beispiel mit 3 Arten von Faktoren und 3 Arten von Ebenen zeigen. Einfach ausgedrückt, Sie benötigen $ 3 ^ 3 = 27 $ so viele Fälle.

Bei der experimentellen Planungsmethode kann die Anzahl der Fälle basierend auf dem lateinischen Quadrat (siehe unten) erstellt werden.

Wenn Sie das lateinische Quadrat verwenden, können Sie es in 9 Fällen wie folgt effizient ausführen. Diese 9 Fälle umfassen alle Kombinationen von Faktoren und Ebenen, und die Anzahl aller Faktoren und Ebenen ist gleich.

9 Fälle ausgewählt (Stufe für jeden Faktor)

• 1,1,1
• 1,2,2
• 1,3,3
• 2,1,2
• 2,2,3
• 2,3,1
• 3,1,3
• 3,2,1
• 3,3,2

Da jedes der 9 Quadrate im lateinischen Quadrat dem Fall entspricht, betrachten Sie die Zeilennummer als Faktor 1, die Spaltennummer als Faktor 2 und die Quadratnummer als Faktor 3.

Nachteile der Versuchsplanung

Die experimentelle Planungsmethode weist die folgenden Nachteile auf.

• Es kann nur eine bestimmte Anzahl von Faktoren und Ebenen verwendet werden.
• Es können keine zusätzlichen Bedingungen berücksichtigt werden.

Denken durch Kombinationsoptimierung

Bei der experimentellen Planungsmethode wurde nach Sicherstellung einer bestimmten Anzahl von Faktoren / Ebenen die Anzahl der Fälle so gering wie möglich gewählt. Sie können sich dasselbe als Optimierungsproblem vorstellen. Geben Sie insbesondere die Mindestanzahl von Fällen an, die jede Ebene jedes Faktors enthalten, und ermitteln Sie die Methode zur Auswahl von Fällen durch gemischte Ganzzahloptimierung.

Formulierung

$ C_ {ij} $ repräsentiert die $ j $ -te Ebene im $ i $ -ten Fall, und $ N $ repräsentiert die Mindestanzahl.

Mit Python kann es wie folgt berechnet werden. (Es wird angenommen, dass die variablen Fälle die Gesamtzahl der Fälle mit Anschaffungskosten von 50.000 Yen oder weniger enthalten.)

python

from pulp import *
r = [0, 1, 3] #Niveau
for N in [20, 40, 60, 120]: #Mindestanzahl
    m = LpProblem()
    v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cases))]
    m += lpSum(v)
    for j in range(len(cases[0])):
        for k in r:
            m += lpSum(v[i] for i in range(len(cases)) if cases[i][j] == k) >= N
    m.solve()
    print(N, LpStatus[m.status], value(m.objective)) #Mindestanzahl, Status, Anzahl der Fälle

Ergebnis

Vergleichen wir es mit dem Fall der Zufallsstichprobe. Die minimale Anzahl von Zufallsstichproben ist ein ungefährer Wert, der in der Simulation erhalten wird. Sie können sehen, dass der Fall mithilfe der Kombinationsoptimierung effizient ausgewählt werden kann.