[PYTHON] Sehen Sie sich Wale mit Kombinationsoptimierung an

Was ist das

In den Sommerferien werden Sie Wale sehen. Verwenden Sie Kombinationsoptimierung, um zu überlegen, welcher der acht Punkte ausgewählt werden soll.

Punktinformationen mit Python anzeigen


import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addbinvars
n = 8 #Punkte
np.random.seed(639)
df = pd.DataFrame(np.random.rand(n,2).round(2)*[0.2,100], columns=['Prob','Time'])
df.insert(0,'Place', [chr(i+65) for i in range(n)])
print(df)
Place Prob Time
0 A 0.082 57.0
1 B 0.182 93.0
2 C 0.184 89.0
3 D 0.108 51.0
4 E 0.104 5.0
5 F 0.152 83.0
6 G 0.178 83.0
7 H 0.156 16.0

Ort repräsentiert den ** Namen ** des Punktes, Prob repräsentiert die ** Wahrscheinlichkeit **, den Wal zu sehen, und Zeit repräsentiert die ** Zeit ** (Minuten), die benötigt wird, um sich zu bewegen und den Punkt zu beobachten.

Problem 1

Maximieren Sie die Summe der ** Wahrscheinlichkeiten ** innerhalb der Gesamtzeit ** 140 Minuten **

Antwort 1

Rucksackproblem, also lösen wir es schnell.

python


m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += lpDot(df.Prob,df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

Ergebnis


Optimal found. Ave prob. = 0.450, Any prob. = 0.381
  Place   Prob  Time    Var  Val
0     A  0.082  57.0  v0001  1.0
3     D  0.108  51.0  v0004  1.0
4     E  0.104   5.0  v0005  1.0
7     H  0.156  16.0  v0008  1.0

Die erwartete Häufigkeit, Wale zu sehen, beträgt 0,45. Die Wahrscheinlichkeit, es mehr als einmal zu sehen, beträgt jedoch 0,381.

Problem Nr. 2

Maximieren Sie die Wahrscheinlichkeit, innerhalb der Gesamtzeit mehr als einmal zu sehen ** 140 Minuten **

Antwort 2

Die Wahrscheinlichkeit, dass Sie es nie sehen werden, ist $ \ prod_i {(1-Prob_i)} $. So wie es ist, ist es nicht linear, aber linearisieren wir es mit $ \ log $ (was eine monotone Funktion ist).

python


m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += -lpDot(np.log(1-df.Prob),df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

Ergebnis


Optimal found. Ave prob. = 0.444, Any prob. = 0.383
  Place   Prob  Time    Var  Val
2     C  0.184  89.0  v0011  1.0
4     E  0.104   5.0  v0013  1.0
7     H  0.156  16.0  v0016  1.0

Die Wahrscheinlichkeit, es mehr als einmal zu sehen, ist leicht von 0,381 auf 0,383 gestiegen.

das ist alles

Recommended Posts

Sehen Sie sich Wale mit Kombinationsoptimierung an
Gruppieren von Spielen mit Kombinationsoptimierung
Kombinationsoptimierung mit Quantenglühen
Maximieren Sie den Restaurantverkauf durch kombinierte Optimierung
Bereiten Sie die Straße mit Kombinationsoptimierung
Spieltheorie mit Kombinationsoptimierung lösen
Lassen Sie uns Bücher mit Kombinationsoptimierung flach stapeln
Lösen von Planungsproblemen für Krankenschwestern mit Kombinationsoptimierung
Python mit Go
Verwenden Sie die Kombinationsoptimierung
Erstellen Sie ein akademisches Programm mit Kombinationsoptimierung
Lösen von Problemen bei der Organisation von Schulbezirken durch Kombinationsoptimierung
Lösen des N Queen-Problems mit kontinuierlicher / kombinierter Optimierung
Lösen des N Queen-Problems mit Kombinationsoptimierung
Straßeninstallation durch Optimierung
Gruppierung nach Kombinationsoptimierung
Einführung in die Optimierung
Versuchen Sie die Funktionsoptimierung mit Optuna
Betreiben Sie den Db2-Container mit Go
Erste Schritte mit Go Assembly
Sternumfrage mit Kombinationsoptimierung
Vollbit-Suche mit Go
Stellen Sie mit GO eine Verbindung zu Postgresql her
Stellen Sie unzusammenhängende Fotos mit Optimierung wieder her!
Globale Allzweckoptimierung mit Z3
Versuchen Sie, Parfüm mit Go zu implementieren
Passen Sie die Hyperparameter mit der Bayes'schen Optimierung an
Lösen von Rucksackproblemen mit den OP-Tools von Google - Üben der Grundlagen von Kombinationsoptimierungsproblemen