[PYTHON] Illustration der Ergebnisse des Rucksackproblems
Einführung
Als Lösung für das Rucksackproblem in "Kombinationsoptimierung verwenden", "[Gierige Methode](https: //ja.wikipedia. org / wiki /% E8% B2% AA% E6% AC% B2% E6% B3% 95) ist ein guter Weg, nicht optimal. "
Eigentlich habe ich mich gefragt, was es war, also werde ich es überprüfen.
Löse zufällige Probleme mit Python
- Die Anzahl der Artikel beträgt 100.
- Die Größe des Artikels sollte eine einheitliche Zufallszahl von (0,1, 1,0) sein.
- Der Wert eines Elements wird durch Multiplizieren seiner Größe mit einer logarithmischen regulären Zufallszahl erstellt.
- Ändern Sie die Kapazität des Rucksacks in Schritten von 0,1 und lösen Sie ihn wiederholt.
- Das Ergebnis wird durch matplotlib veranschaulicht.
Datenaufbereitung
python
%matplotlib inline
import math, numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(1)
n = 100 #Stückzahl
siz = np.random.uniform(0.1, 1.0, n)
prf = siz * np.random.lognormal(1, 0.1, n)
eff = prf / siz
siz, prf, eff = np.array([siz, prf, eff]).T[eff.argsort()].T
r1, r2, p1, p2 = [], [], [], []
Ergebnis der Näherungslösung (Giermethode)
Bei der gierigen Methode werden wir die Reihenfolge der Effizienz (Wert / Größe) untersuchen und so eingeben, dass die Kapazität nicht überschritten wird.
python
for sz in range(math.ceil(sum(siz)*10)):
v, r, rm = 0, [], sz / 10
for i in range(len(siz)-1, -1, -1):
r.append(int(rm < siz[i]))
if r[-1] == 0:
rm -= siz[i]
v += prf[i]
r1.append(list(reversed(r)))
p1.append(v)
plt.imshow(np.array(r1).T, cmap='gray')
――Es dauerte einige Millisekunden, um 538 Mal zu lösen. ――Vertikalisch entspricht den Elementen in der Reihenfolge ihrer Effizienz. Die Seite entspricht der Kapazität des Rucksacks x 10.
- Schwarz steht für das ausgewählte Element und Weiß für das nicht ausgewählte Element. ――Die gierige Methode ist in der Reihenfolge ihrer Effizienz gepackt, sodass die Grenzen relativ klar sind.
Ergebnis der exakten Lösung
Lösen wir es als gemischtes ganzzahliges Optimierungsproblem mit Zellstoff.
python
m = LpProblem(sense=LpMaximize)
v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(siz))]
m += lpDot(prf, v)
e = lpDot(siz, v) <= 1
m += e
r = []
for sz in range(math.ceil(sum(siz)*10)):
e.changeRHS(sz / 10)
m.solve()
r2.append([1 - int(value(x)) for x in v])
p2.append(value(m.objective))
plt.imshow(np.array(r2).T, cmap='gray')
- 538 Mal in 16 Sekunden mit Gurobi 6.5.1 und 58 Sekunden mit dem Standard-CBC gelöst. ――Die Mischung aus Schwarz und Weiß in der Nähe der Grenze zeigt an, dass es am besten ist, eine ineffiziente als Ganzes zu wählen.
Genauigkeit der Giermethode
Stellen Sie den gierigen Lösungswert dividiert durch den genauen Lösungswert grafisch dar. Die Vertikale ist das Verhältnis und die Horizontale ist die Kapazität des Rucksacks x 10.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p1[2:]) / np.array(p2[2:]))
Wenn die Kapazität gering ist und die Anzahl der Elemente, die eingegeben werden können, gering ist, treten einige Fehler auf. Wenn jedoch eine bestimmte Anzahl von Elementen vorhanden ist, können Sie feststellen, dass die Genauigkeit recht gut ist.
Postscript (geizige Methode)
Es war in H22.Math.Prog.No.9.pdf Ich habe die 吝嗇-Methode ausprobiert.
python
r3,p3 = [],[]
for sz in range(math.ceil(sum(siz)*10)):
v, r, ca, rm = 0, [], sz / 10, sum(siz)
for i in range(len(siz)):
r.append(int(not(0 < rm-siz[i] <= ca and siz[i] <= ca)))
rm -= siz[i]
if r[-1] == 0:
ca -= siz[i]
v += prf[i]
r3.append(r)
p3.append(v)
plt.imshow(np.array(r3).T, cmap='gray');
Sie können sehen, dass die gierige Methode über der Grenze hervorstand, aber die Brüllmethode unter der Grenze fehlte. Wenn man die Leistung betrachtet, fühlt es sich schlimmer an als die gierige Methode.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p3[2:]) / np.array(p2[2:]));
das ist alles
Recommended Posts