[Problème de sac à dos (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83 % E3% 82% AF% E5% 95% 8F% E9% A1% 8C) Méthode de limitation de branche (Wikipedia) % 9E% 9D% E9% 99% 90% E5% AE% 9A% E6% B3% 95). L'autre jour, j'ai résolu le problème du sac à dos avec une méthode gourmande. Résolution du problème du sac à dos Python avec l'algorithme glouton
La méthode gourmande n'était pas une méthode pour trouver une solution exacte, mais une méthode pour trouver une solution qui avait l'air bien. Cette fois, nous allons implémenter la méthode de limitation de branche pour trouver la solution exacte.
(À propos de la méthode de limitation de branchement de Wikipedia)
Méthode de limitation de branchement (Bunshigen Teiho, anglais: branch and bound,BB)
Il s'agit d'un algorithme polyvalent permettant de trouver des solutions optimales à divers problèmes d'optimisation (en particulier l'optimisation discrète et l'optimisation combinée).
Branch operation (anglais:branching operation) et un fonctionnement limité (anglais:Opération de délimitation).
Il répertorie systématiquement toutes les solutions candidates, en utilisant une estimation de limite supérieure et inférieure optimisée.
Les candidats non optimaux sont jetés «en vrac».
Vérifier tous les candidats serait trop nombreux, il est donc possible d'utiliser un problème d'atténuation (la solution de x est 0 ou 1, mais trouvez la solution avec 0 <= x <= 1). S'il n'y en a pas, j'ai l'impression que je vais le couper des candidats. Si la solution du problème d'atténuation est inférieure à la solution de la solution provisoire, elle sera supprimée des candidats.
Nous vous serions reconnaissants si vous pouviez nous faire savoir s'il y a des lacunes ou des suggestions d'amélioration concernant le code.
2*x1 + 3*x2 + 5*x3 + 6*x4 <= 9
xi = 0 or 1 (i = 1, 2, 3, 4)
Dans les conditions ci-dessus
4*x1 + 5*x2 + 12*x3 + 14*x4
Pour maximiser( x1, x2, x3, x4 )Utilisez la méthode de limitation de branche.
import numpy as np
from pandas import DataFrame
import copy
class BranchAndBound:
def __init__(self, weights, values, max_weight, answer_val):
self.weights = np.array(weights)
self.values = np.array(values)
self.max_weight = max_weight
self.answer_val = answer_val
self.evaluates = self.values/self.weights
self.index_list = []
for index in range(1, len(weights) + 1):
self.index_list.append('x' + str(index))
self.target_df = DataFrame(np.c_[self.evaluates, self.weights, self.values, np.array(self.answer_val)], index=self.index_list, columns=["evaluate", "weight", "value", "ans"])
self.target_df = self.target_df.sort_values('evaluate', ascending=False)
self.answer_val = list(self.target_df['ans']) # answer_Changement de val à un trié par ordre décroissant de valeur d'évaluation
del self.target_df['ans'] #Colonne "ans" supprimée car elle n'est plus nécessaire pour DataFrame
self.target_ans = np.dot(np.array(answer_val), values)
self.index_list = self.target_df.index #Modifier l'ordre des index
def __judgeValue(self, fixed_list): # fixed_Résolvez le problème d'atténuation à la valeur fixe de x passée dans la liste et jugez la continuation de la branche. De plus, si une meilleure solution est trouvée, la solution provisoire sera échangée.
sum_weight = 0 #Le poids total du x adopté
evaluate_list = [] #Décision d'acceptation des magasins
evaluate_list.extend(fixed_list)
for index, val in enumerate(fixed_list):
sum_weight += self.target_df.ix[self.index_list[index]]['weight']*val # fixed_Le poids total des valeurs x passées dans la liste
for index in range(len(fixed_list), len(self.index_list)):
if sum_weight > self.max_weight: #max_Si le poids est dépassé, la branche se termine
return False #Fin de branche
elif sum_weight == self.max_weight: #max_Le poids étant atteint, l'autre x vaut 0
evaluate_list.append(0)
continue
else:
if sum_weight + self.target_df.ix[self.index_list[index]]['weight'] < self.max_weight: # x=Même si c'est 1, max_Lorsque le poids n'est pas atteint
sum_weight += self.target_df.ix[self.index_list[index]]['weight']
evaluate_list.append(1)
else: # 0 < x <=Quand il devient 1
evaluate_list.append((self.max_weight - sum_weight)/self.target_df.ix[self.index_list[index]]['weight'])
sum_weight = self.max_weight
if (self.max_weight - sum_weight) == self.target_df.ix[self.index_list[index]]['weight']: # x=Lorsque 1, remplacez la solution provisoire
evaluate_list_count = len(evaluate_list)
for i in range(evaluate_list_count, len(self.index_list)): #Entrez 0 pour tous les x qui n'ont pas été décidés
evaluate_list.append(0)
self.target_ans = np.dot(np.array(evaluate_list), np.array(self.target_df.value)) #Cible de la solution provisoire_Remplacement d'ans
self.answer_val = evaluate_list #Réponse provisoire_Remplacement de val
return False #Fin de branche
if len(fixed_list) == len(self.index_list): #Comparaison avec la solution provisoire lorsque toutes les valeurs x sont fixes
if (sum_weight <= self.max_weight) and (np.dot(np.array(fixed_list), np.array(self.target_df.value)) > self.target_ans): #Comparaison avec la solution provisoire
self.target_ans = np.dot(np.array(fixed_list), np.array(self.target_df.value)) #Cible de la solution provisoire_Remplacement d'ans
self.answer_val = fixed_list #Réponse provisoire_Remplacement de val
return False
if np.dot(np.array(evaluate_list), np.array(self.target_df.value)) > self.target_ans: #Lorsque la solution du problème d'atténuation dépasse la solution provisoire
return True #Continuation de la succursale
else: #Lorsque la solution provisoire n'est pas dépassée
return False #Fin de branche
def breadthFirstSearch(self): #Recherche de priorité de largeur
search_lists = [[0], [1]] #élément[0]、[1]Mettre en premier
while len(search_lists) != 0: # search_Continuer jusqu'à ce que les listes soient vides
first_list = search_lists[0] #Pensez dans la file d'attente, obtenez-en un du haut
search_lists.pop(0) #Supprimer l'élément acquis
if self.__judgeValue(first_list): #Si la recherche continue
new_list_cp = copy.deepcopy(first_list) #Copie profonde pour ajouter "1" à l'élément suivant
new_list_cp.append(0) #Ajouter 0 à la fin
search_lists.append(new_list_cp) #Rechercher de nouveaux éléments_Stocker à la fin des listes
new_list_cp = copy.deepcopy(first_list) #Copie profonde pour ajouter "0" à l'élément suivant
new_list_cp.append(1) #Ajouter 1 à la fin
search_lists.append(new_list_cp) #Rechercher de nouveaux éléments_Stocker à la fin des listes
print("-----Recherche de priorité de largeur-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
def depthFirstSearch(self): #Recherche de priorité de profondeur
search_lists = [[0], [1]] #élément[0]、[1]Mettre en premier
while len(search_lists) != 0: # search_Continuer jusqu'à ce que les listes soient vides
first_list = search_lists[0] #Pensez avec Stach, obtenez-en un du haut
search_lists.pop(0) #Supprimer l'élément acquis
if self.__judgeValue(first_list): #Si la recherche continue
new_list_cp = copy.deepcopy(first_list) #Copie profonde pour ajouter "1" à l'élément suivant
new_list_cp.append(1) #Ajouter 1 à la fin
search_lists.insert(0, new_list_cp) #Rechercher de nouveaux éléments_Stocker au début des listes
new_list_cp = copy.deepcopy(first_list) #Copie profonde pour ajouter "0" à l'élément suivant
new_list_cp.append(0) #Ajouter 0 à la fin
search_lists.insert(0, new_list_cp) #Rechercher de nouveaux éléments_Stocker au début des listes
print("-----Recherche de priorité de profondeur-----")
for index, val in enumerate(self.index_list):
print(val + ": " + str(self.answer_val[index]))
print("ans: " + str(self.target_ans))
# BranchAndBound(weight_list(a1, a2, a3, a4), value_list(c1, c2, c3, c4), max_weight(a_max), first_values(x1, x2, x3, x4))
# first_les valeurs peuvent être n'importe quoi, mais ici gourmand-La solution obtenue par algorithme est donnée comme valeur initiale.
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.breadthFirstSearch()
bb = BranchAndBound([2, 3, 5, 6], [4, 5, 12, 14], 9, [1, 0, 0, 1] )
bb.depthFirstSearch()
Dans la méthode de limitation de branche, il semble y avoir une recherche de priorité de profondeur et une recherche de priorité de largeur, donc j'ai essayé l'une ou l'autre méthode.
Il semble que la quantité de code puisse être réduite un peu plus. ..
-----Recherche de priorité de largeur-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
-----Recherche de priorité de profondeur-----
x3: 0
x4: 1
x1: 0
x2: 1
ans: 19.0
Donc, ( x1, x2, x3, x4 ) = ( 0, 1, 0, 1 )
Recommended Posts