Illustration des résultats du problème du sac à dos
Introduction
Comme solution au problème du sac à dos dans "Utiliser l'optimisation des combinaisons", "[Greedy method](https: //ja.wikipedia. org / wiki /% E8% B2% AA% E6% AC% B2% E6% B3% 95) est un bon moyen, pas optimal. "
En fait, je me demandais ce que c'était, alors je vais le vérifier.
Résoudre des problèmes aléatoires avec Python
- Le nombre d'articles est de 100.
- La taille de l'élément doit être un nombre aléatoire uniforme de (0,1, 1,0). --La valeur d'un élément est créée en multipliant sa taille par un nombre aléatoire régulier logarithmique.
- Changez la capacité du sac à dos par incréments de 0,1 et résolvez-le à plusieurs reprises.
- Le résultat est illustré par matplotlib.
Préparation des données
python
%matplotlib inline
import math, numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(1)
n = 100 #Nombre d'éléments
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 = [], [], [], []
Résultat de la solution approximative (méthode de la cupidité)
Dans la méthode gourmande, nous allons rechercher par ordre d'efficacité (valeur / taille) et mettre en place de manière à ne pas dépasser la capacité.
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')
――Il a fallu quelques millisecondes pour résoudre 538 fois. ――Vertical correspond aux éléments par ordre d'efficacité. Le côté correspond à la capacité du sac à dos x 10.
- Le noir représente l'élément sélectionné et le blanc représente l'élément non sélectionné. ――La méthode gourmande est classée par ordre d'efficacité, les limites sont donc relativement claires.
Résultat de la solution exacte
Résolvons-le comme un problème d'optimisation d'entiers mixtes avec pulp.
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')
- Résolution 538 fois en 16 secondes avec Gurobi 6.5.1 et 58 secondes avec le CBC par défaut. ――Le mélange de noir et de blanc près de la frontière indique qu'il est préférable d'en choisir un inefficace dans son ensemble.
Précision de la méthode de cupidité
Représentez graphiquement la valeur de la solution gourmande divisée par la valeur exacte de la solution. La verticale est le rapport et l'horizontale est la capacité du sac à dos x 10.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p1[2:]) / np.array(p2[2:]))
Si la capacité est petite et le nombre d'éléments qui peuvent être saisis est petit, il y aura des erreurs, mais s'il y a un certain nombre d'éléments, vous pouvez voir que la précision est assez bonne.
Postscript (méthode avare)
C'était dans H22.Math.Prog.No.9.pdf J'ai essayé la méthode 吝嗇.
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');
Vous pouvez voir que la méthode gourmande dépassait la limite, mais la méthode rugissante manquait en dessous de la limite. En regardant la performance, c'est pire que la méthode gourmande.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p3[2:]) / np.array(p2[2:]));
c'est tout