[PYTHON] Sternumfrage mit Kombinationsoptimierung

Was ist das

• Untersuchen Sie 1000 Sterne hintereinander mit einer Photonenrakete.
• Lass uns herausfinden, ob es Außerirdische gibt. Es können jedoch nicht alle Sterne untersucht werden.
• Die Vermessungszeit variiert von Stern zu Stern. Die gesamte Vermessungszeit der zu vermessenden Sterne sollte innerhalb von 10.000 Tagen liegen.
• Die Entdeckungswahrscheinlichkeit wird für jeden Stern geschätzt. Maximieren Sie die Summe der Entdeckungswahrscheinlichkeiten der untersuchten Sterne.

Versuche es zu lösen

Es kann als [Rucksackproblem] angesehen werden (http://qiita.com/SaitoTsutomu/items/d3c07494e7ba992bf19d). Lösen wir es mit Python. Informationen zur mathematischen Optimierung mit Python finden Sie unter dem Referenzlink.

python3

import numpy as np
from pulp import *
np.random.seed(1)
Anzahl der Sterne= 1000
Umfragezeit= np.random.randint(10,100,Anzahl der Sterne)
Entdeckungswahrscheinlichkeit= np.random.random(Anzahl der Sterne)/100000
m = LpProblem(sense=LpMaximize)
x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(Anzahl der Sterne)]
m += lpDot(Entdeckungswahrscheinlichkeit,x)
m += lpDot(Umfragezeit,x) <= 10000
m.solve()
print(value(m.objective)) #Summe der Entdeckungswahrscheinlichkeiten
>>>
0.0022822674119170536

In der Tat haben Raketen eine maximale Reichweite. Hier ist die maximale Anzahl von Sprüngen + 1 mx, nicht nur die Entfernung. Mal sehen, was mit der Zielfunktion passiert, wenn wir mx ändern. Die horizontale Achse ist mx und die vertikale Achse ist die Zielfunktion.

python3

r = []
for mx in range(4,17):
    m = LpProblem(sense=LpMaximize)
    x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(Anzahl der Sterne)]
    m += lpDot(Entdeckungswahrscheinlichkeit,x)
    m += lpDot(Umfragezeit,x) <= 10000
    for i in range(Anzahl der Sterne-mx+1):
        m += lpSum(x[i:i+mx]) >= 1 #Untersuchen Sie mindestens einen Ort innerhalb von mx
    m.solve()
    r.append(value(m.objective))

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16);

Versuchen Sie zu vergrößern.

python3

plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16)
plt.xlim((9,16))
plt.ylim((0.00227,0.0023));

Mit dem Standard-Free-Solver-CBC verbessern die strengeren Einschränkungen aufgrund von Fehlern die Lösung.

Der kommerzielle Löser wurde genauer gelöst.

Referenzlink

• Python in Optimierung - Qiita

das ist alles