Pour étudier l'algorithme, j'ai essayé de résoudre le problème de planification des équipes. Le sujet le plus brûlant en mai 2020, lorsque j'écrivais cet article, était le COVID-19, et compte tenu de la façon dont cela affecterait la vie de mon bétail, j'aimerais venir travailler (demandes des employés, jusqu'à l'année dernière). Je pense que c'est une bonne idée de satisfaire à la fois la demande de l'entreprise d'aller au travail et le télétravail (demande de l'entreprise. Jusqu'à l'année dernière, la demande de télétravail de l'employé). Ouais, c'est un soi-disant problème de planification des équipes.
Tout d'abord, essayons le modèle Zing, qui est également utilisé dans la méthode de recuit quantique de D-Wave. Cependant, la méthode de cuisson quantique ne peut pas être exécutée sur un ordinateur ordinaire, c'est pourquoi la méthode de cuisson ordinaire est utilisée. C'est de la même manière que le Digital Annealer de Fujitsu.
Cependant, il était difficile de créer un processus pour résoudre le modèle Zing par la méthode de recuit, donc [D-Wave's neal](https://docs.ocean.dwavesys.com/projects/neal/en/latest/index. J'ai utilisé du html). De plus, il est assez difficile de faire un modèle ascendant à la main (ou plutôt, ma capacité mathématique est trop faible pour comprendre les pièces), donc la génération du modèle ascendant était [PyQUBO of Recruit Communications](https: //) J'ai utilisé pyqubo.readthedocs.io/en/latest/).
Ainsi, le code pour résoudre le problème en utilisant neal et PyQUBO ressemble à ceci.
import numpy as np
from funcy import *
from neal import SimulatedAnnealingSampler
from pyqubo import Array, Constraint, Placeholder, Sum
M = 5 # Nombre d'employés
D = 10 # jours
BETA_RANGE = (5, 100) # L'inverse de la température du recuit. Plus la solution est volumineuse, plus la solution est stable, mais plus elle est susceptible de tomber dans une solution locale.
NUM_READS = 10 # Nombre de tannages. NUM_READS solutions sont générées. Plus vous en avez, plus vous avez de chances d'obtenir une meilleure solution.
NUM_SWEEPS = 100000 # Nombre de fois où effectuer l'étape de bronzage. Le nombre d'itérations pour générer une seule solution. Plus la valeur est élevée, plus il est probable qu'une meilleure solution sera obtenue.
BETA_SCHEDULE_TYPE = 'linear' # Comment changer la température de bronzage. S'il est linéaire, il changera linéairement
# Animer le modèle Ising à l'aide de neal et renvoyer la solution
def solve(hs, js):
response = SimulatedAnnealingSampler().sample_ising(hs, js, beta_range=BETA_RANGE, num_reads=NUM_READS, num_sweeps=NUM_SWEEPS, beta_schedule_type=BETA_SCHEDULE_TYPE, seed=1)
# NUM_READS Renvoie la meilleure solution sur
return tuple(response.record.sample[np.argmin(response.record.energy)])
# Définissez les variables qui composent QUBO
xs = Array.create('x', shape=(M, D), vartype='BINARY')
# Définir des variables pour le réglage
a = Placeholder('A')
b = Placeholder('B')
# Définissez QUBO. d'ici……
h = 0
# Ajoutez une contrainte de 2 personnes ou plus par jour et le moins possible. Des pénalités seront encourues pour plus ou moins de 2 personnes
for d in range(D):
h + = a * Contrainte ((Sum (0, M, lambda m: xs [m] [d]) --2) ** 2, f'day- {d} ') # 2 est négative si au moins , S'il y en a beaucoup, ce sera un nombre positif, mais mettez-le au carré pour en faire une valeur positive
# Ajoutez une contrainte que vous ne viendrez pas travailler avec la même personne un autre jour
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
h + = b * xs [m1] [d1] * xs [m2] [d1] * xs [m1] [d2] * xs [m2] [d2] # xs vaut 1 ou 0, donc si vous voulez multiplier Ce ne sera 1 que si tous sont 1.
# Compiler pour créer un modèle
model = h.compile()
# ……Jusque là. Définir QUBO
# Valeur des variables pour le réglage
feed_dict = {'A': 2.0, 'B': 1.0}
# Générez un modèle ascendant et résolvez avec neal
hs, js, _ = model.to_ising(feed_dict=feed_dict)
answer, broken, energy = model.decode_solution(dict(enumerate(solve(hs, js))), vartype='SPIN', feed_dict=feed_dict)
# Sortir le résultat
print (f'breaké: \ t {len (cassé)} ') # Si la contrainte est violée, cassé sera rempli.
print (f'energy: \ t {energy} ') # L'énergie de QUBO. Dans ce modèle, il sera égal à 0 si toutes les contraintes sont satisfaites.
# Sorties les employés qui viennent travailler au quotidien
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if answer['x'][m][d] == 1 else False, range(M))))
Ainsi, le résultat de l'exécution de ce programme ressemble à ceci.
broken: 0
energy: 0.0
('D', 'E')
('A', 'D')
('B', 'C')
('A', 'C')
('B', 'D')
('B', 'E')
('C', 'E')
('A', 'E')
('A', 'B')
('C', 'D')
Oui c'est vrai. Deux personnes viennent travailler chaque jour, et il n'y a pas la même combinaison. Au fait, le temps d'exécution sur mon ordinateur était de 0,734 seconde. Depuis que 10 solutions ont été créées, 0,073 seconde par solution. neal est vraiment rapide!
[Page de modèle Ising Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%82%B8%E3%83%B3%E3%82%B0%E6%A8% Si vous lisez A1% E5% 9E% 8B), vous pouvez comprendre qu'il s'agit d'un modèle de treillis composé de points de treillis qui prennent deux états de coordination et ne considère l'interaction que des points de treillis adjacents. ne pas. Hamiltonien est un terme physique, mais est-ce délicieux? Dois-je étudier la physique à partir de maintenant?
Soyez assuré. Ce sont les gens qui fabriquent le matériel qui utilise le modèle Zing, pas nous les programmeurs, qui devons étudier la physique. De plus, le modèle Zing est une histoire assez simple en termes de logiciel.
Laissez-moi vous expliquer avec un exemple concret. Tout d'abord, ignorez le mot grille (qui semble être vertical et horizontal dans l'image) (important pour les quincailleries physiques, mais pas pour nous en tant que programmeurs). Alors, considérez les deux états de coordination comme des variables spéciales qui ne peuvent être attribuées que -1 ou 1. Il est difficile d'obtenir une image de 1 ou -1, alors considérons le cas où trois personnes votent pour ou contre une proposition. Si vous êtes d'accord, ce sera 1, et si vous n'êtes pas d'accord, ce sera -1. Il existe une relation délicate entre ces trois personnes, et cela fait du bien que M. a et M. b agissent de la même manière, et cela fait du bien que M. c et M. b prennent des mesures différentes pour une cause passée. Je vais. Maintenant, comment faire en sorte que chacun se sente le plus à l'aise possible dans ces conditions?
Les ordinateurs ne peuvent gérer que des nombres, ils doivent donc être exprimés numériquement. Puisque a, b et c ne peuvent prendre que 1 ou -1, les expressions qui ont des nombres * plus petits * lorsque tout le monde se sent à l'aise peuvent être exprimées avec ce code.
-1 * a * b + 1 * b * c
Regardons de plus près. Le résultat de la multiplication de la combinaison de 1 et -1 est le suivant.
| Valeur 1 | Valeur 2 | résultat |
|---|---|---|
| 1 | 1 | 1 |
| 1 | -1 | -1 |
| -1 | 1 | -1 |
| -1 | -1 | 1 |
Si la valeur est la même ou différente, elle sera confortablement divisée en 1 et -1, donc si vous multipliez ce résultat par -1, ce sera une petite valeur de -1 si elle est la même, et une grande valeur de 1 si elle est différente. Vous voyez, vous pourriez bien l'exprimer avec la formule ci-dessus, non?
Cependant, ce n'est pas pratique car il n'est pas polyvalent tel quel, alors rendons-le polyvalent. Les valeurs du tableau ci-dessous sont ajoutées aux résultats de multiplication de toutes les variables (cependant, a * a est le même à chaque fois, donc il n'a pas de sens, alors laissez ce champ vide. Comme a * b et b * a sont la même valeur, entrez la valeur dans une seule) Je vais l'accrocher.
| a | b | c | |
| a | -1 | 0 | |
| b | 1 | ||
| c | |||
Vous pouvez le définir sur 0 là où cela n'a pas d'importance. Ainsi, lorsque j'écris le code à calculer à l'aide de cette table, cela ressemble à ceci. Imaginez que a, b et c sont dans un tableau appelé «xs» et que les valeurs du tableau ci-dessus sont dans une variable appelée «js».
def energy():
result = 0
for i in range(1, len(xs)):
for j in range(i + 1, len(xs)):
result += js[i][j] * xs[i] * xs[j]
return result
Maintenant, même si la relation change en raison de la réconciliation entre M. b et M. c, elle peut être exprimée avec le même code (en fait, pour le rendre plus général («a» et «). Une autre variable (pour profiter du fait que bouc est égal à 1 ou -1) (utilisez également le hs` dans le code recuit en utilisant le modèle Zing)). Et ce modèle polyvalent et merveilleux est le modèle Rising.
À ce stade, il est facile de voir si c'est meilleur ou pire en retournant l'élément approprié de xs et en comparant les résultats dans le code ci-dessus. Il peut être résolu par la méthode dite d'alpinisme. Cependant, quand je l'ai recherché, l'explication de la méthode d'alpinisme disait qu'il était facile de tomber dans une solution locale, donc j'étais un peu inquiet, donc même si le résultat du code ci-dessus est un peu pire au début, je vais permettre le mouvement, le dernier est le degré Contournons ce problème en réduisant et en allant dans le sens de l'amélioration. C'est ce qu'on appelle la méthode de bronzage car elle ressemble au bronzage dans le monde réel, et le degré de pardon même si le résultat est mauvais s'appelle la température, après le bronzage dans le monde réel. De plus, comme c'est l'énergie qui correspond au résultat du code ci-dessus dans le monde réel, le résultat du code ci-dessus est appelé énergie. C'est pourquoi c'est une expression comme trouver une combinaison qui minimise l'énergie tout en abaissant la température. Le neal de D-Wave le fait très efficacement.
Donc, si vous essayez de le graver, le résultat devrait être a = 1, b = 1, c = -1 ou a = -1, b = -1, c = 1. Dans les deux cas, l'énergie est au minimum -2, donc tout le monde se sent bien.
Il ne vous reste plus qu'à créer les valeurs dans le tableau ci-dessus en fonction des contraintes évoquées au début de cet article ... mais c'est assez difficile. Je ne sais pas quoi faire lorsque plusieurs variables sont impliquées, comme dans les contraintes de cet article (il semble qu'une variable soit ajoutée en coulisse et définie par rapport à la variable ajoutée). Utilisons donc PyQUBO de Recruit Communications. Avec PyQUBO, l'expression de la formule est convertie en un modèle Zing polyvalent. De plus, comme il est difficile de penser à 1 et -1, il peut également être défini sous la forme de QUBO en utilisant 1 et 0 (je ne pouvais pas comprendre, mais il semble que le modèle Zing et QUBO puissent être convertis l'un à l'autre). Je vais.
Exprimons-le concrètement. Si vous considérez «xs» comme un tableau bidimensionnel de «M» × «D» et que vous le définissez sur 1 si vous allez au travail et 0 si vous ne vous rendez pas au travail, le nombre d'employés qui viennent travailler le premier jour peut être calculé comme suit.
result = 0
for m in range(M):
result += xs[m][0]
return result
Donc, plus ce résultat est proche de 2, mieux c'est, et peu importe si c'est plus ou moins. Donc je veux soustraire 2 et ʻabs pour trouver la valeur absolue ... mais malheureusement je ne peux pas utiliser une fonction comme ʻabs. Alors, ce qu'il faut faire est de le concilier. Je ne suis pas bon en mathématiques, donc je ne suis pas sûr, mais il semble que multiplier moins par moins donnera un plus. De plus, PyQUBO fournit une fonction pour calculer la somme appelée «Sum», donc le code est le suivant.
h += (Sum(0, M, lambda m: xs[m][0]) - 2) ** 2
Or, lorsque le nombre de personnes qui viennent travailler est de 2, l'énergie est la plus petite, et quand il y en a plus ou moins de 2, l'énergie est plus élevée.
Pour le reste des différentes paires d'employés, ce n'est pas grave si vous n'avez pas la même combinaison à des jours différents. Par souci de simplicité, si vous réfléchissez un peu plus en détail, par exemple, «l'employé 0 et l'employé 1 seront pénalisés si les 2e et 3e jours sont identiques», cela peut être exprimé par le code suivant.
h += xs[0][2] * xs[1][2] * xs[0][3] * xs[1][3]
Puisqu'il s'agit de QUBO, la valeur de l'élément de xs est 1 ou 0, elle sera donc 0 à moins que l'employé 0 et l'employé 1 ne viennent travailler le jour 0 et le jour 1, c'est-à-dire tous les 1. .. Tous les 1 sont la même combinaison, donc si cela devient 1 dans ce cas, c'est très pratique comme pénalité. Il ne vous reste plus qu'à écrire une quadruple boucle pour couvrir les combinaisons des autres employés et les combinaisons des autres jours.
De plus, la plupart des choses ont des priorités, et il est difficile d'ajouter différentes choses ensemble (je ne pense pas que les systèmes d'unités des deux formules bien faites cette fois-ci sont les mêmes: "démanger" et "ça" N'est-il pas difficile de calculer le "désagrément" en ajoutant le "bruit"?). Donc, multiplions les coefficients appropriés, ʻaetb, afin que ces valeurs puissent être spécifiées au moment du réglage (démangeaisons x ʻa + bruyant x b = désagréable et provisoire Ensuite, ajustez les valeurs de «a» et «b» comme il convient). «Placeholder» est pratique dans un tel cas. Cette fois, j'ai essayé diverses choses et mis ʻa = 1.0etb = 0.5. Si vous définissez QUBO avec PyQUBO comme ceci, il sera converti en un modèle montant avec model.to_ising ()` en un seul coup, et si vous le résolvez avec neal, la réponse sera retournée. De plus, il est possible d'utiliser D-Wave au lieu de neal. Vous pouvez également le résoudre avec un recuit numérique et comparer le temps d'exécution et la précision avec neal. Eh bien, c'est devenu pratique dans le monde.
Continuons et faisons-le avec un algorithme génétique qui rend le nom romantique.
Comme d'habitude, il était fastidieux de créer un processus d'algorithmes génétiques, j'ai donc utilisé une bibliothèque open source appelée DEAP. Le code ressemble à ceci.
from deap import algorithms, base, creator, tools
from functools import reduce
from funcy import *
from random import randint, random, seed
M = 5 # Nombre d'employés
D = 10 # jours
# Fonction d'évaluation
def evaluate(individual):
# Ajoutez une contrainte de 2 personnes ou plus par jour et le moins possible. Des pénalités seront encourues pour plus ou moins de 2 personnes
def member_size():
result = 0
for d in range(D):
result + = abs (reduction (lambda acc, m: acc + individual [m * D + d], range (M), 0) --2) # Puisque la valeur elle-même est utilisée, abs peut également être utilisé.
return result
# Ajoutez une contrainte que vous ne viendrez pas travailler avec la même personne un autre jour
def different_member():
result = 0
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
result += individual[m1 * D + d1] * individual[m2 * D + d1] * individual[m1 * D + d2] * individual[m2 * D + d2]
return result
# Renvoie plusieurs points de vue d'évaluation sous forme de taple avec les résultats d'évaluation de chaque point de vue en tant qu'élément.
return (member_size(), different_member())
# DEAP définit comment l'algorithme génétique
creator.create ('Fitness', base.Fitness, weights = (-1.0, -0.5)) Plus le résultat de # evaluer () est petit, mieux c'est, alors ajoutez un moins au poids.
creator.create('Individual', list, fitness=creator.Fitness)
toolbox = base.Toolbox()
toolbox.register('attribute', randint, 0, 1)
toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.attribute, n=M * D)
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutFlipBit, indpb=0.05)
toolbox.register('select', tools.selTournament, tournsize=3)
toolbox.register('evaluate', evaluate)
# Correction de graines aléatoires pour la reproductibilité
seed(1)
# Résolvez le problème avec un algorithme génétique
population, _ = algorithms.eaSimple(toolbox.population(n=100), toolbox, 0.5, 0.2, 300, verbose=False)
# Obtenez la meilleure solution
individual = tools.selBest(population, 1)[0]
# Sortir le résultat
print(f'fitness:\t{individual.fitness.values}')
# Sorties les employés qui viennent travailler au quotidien
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if individual[m * D + d] else False, range(M))))
Et le résultat est comme ça.
fitness: (0.0, 0.0)
('B', 'E')
('A', 'D')
('B', 'C')
('C', 'E')
('D', 'E')
('C', 'D')
('A', 'C')
('A', 'E')
('B', 'D')
('A', 'B')
Oui. C'est la bonne solution. Le temps d'exécution sur mon ordinateur était de 4,595 secondes. Si vous pensez qu'il est trop lent à utiliser, veuillez lire les "explications simples" suivantes jusqu'à la fin.
Les enfants nés de parents sympas sont très cool. Et je suis né d'un parent qui n'était pas ...
Comme pour la méthode de cuisson précédente, la méthode de création d'une nouvelle solution est importante dans la méthode de recherche d'une meilleure solution en créant une nouvelle solution. Par exemple, si vous créez une nouvelle solution au hasard, la situation s'aggravera probablement et vous ne trouverez pas de solution que vous pouvez attendre. Par conséquent, la méthode d'alpinisme utilise une solution proche de la solution actuelle, ce qui est une légère modification de la solution actuelle. Je pense que c'est probablement bon parce que cela ressemble à une bonne solution. Ainsi, dans l'algorithme génétique, la solution est exprimée comme un gène, une nouvelle solution est créée par l'accouplement et un enfant est né ou muté, et une meilleure solution est créée avec un sentiment de sélection naturelle. Je vais le chercher. Pour l'accouplement et la sélection naturelle, nous avons plusieurs solutions au lieu d'une. Les enfants de parents sympas sont plutôt cool, alors j'ai l'impression que je peux survivre sans être éliminé du marché matrimonial.
Donc, la chose la plus importante dans l'algorithme génétique est "comment exprimer la solution avec les chromosomes". Comme cette fois, si vous venez travailler et ne venez pas travailler, vous pouvez l'exprimer avec une liste de 0. N'importe quel ensemble de nombres peut être utilisé (ndarray, Set, Dictionary, arborescence de NumPy, etc. peuvent également être utilisés), donc par exemple, s'il s'agit d'un problème de voyageur de commerce, une liste de numéros de ville en déplacement est acceptable. Lorsque vous conduisez une voiture, la force avec laquelle vous appuyez sur l'accélérateur ou le frein peut être exprimée en points flottants. Le DEAP possède une multitude de fonctions qui permettent l'expression de divers gènes et chromosomes. Par exemple, si le numéro de la ville à visiter par le voyageur de commerce est un gène, Création de types de documentation DEAP La permutation est utile (vous n'avez plus à utiliser de techniques fastidieuses comme la représentation ordinale!).
En outre, il existe en fait diverses méthodes telles que l'accouplement (appelé croisement dans les algorithmes génétiques), la mutation et la sélection naturelle, mais elles en implémentent beaucoup. Et cela fournit également une bonne manière de les combiner dans le paquet ʻalgorithms`.
Cependant, DEAP a une petite bizarrerie dans la façon de l'utiliser ... Nous réutiliserons les fonctions fournies par DEAP pour créer les outils nécessaires pour résoudre le problème, mais nous devons le faire avec les fonctions de DEAP au lieu de la synthèse de fonctions ordinaire. Par exemple, pour définir une classe individuelle (correspondant à l'une des solutions) ʻIndividual, vous devez le faire avec l'API DEAP comme creator.create ('Invididual', ...) . Hmm. Ainsi, créer des méthodes qui se croisent est comme toolbox.register ('mate', tools.cxTwoPoint). Il est facile de générer une méthode qui coupe deux points avec cela seul, mais si possible, je voulais l'écrire comme un partiel` normal ...
Eh bien, c'est un problème de luxe, alors faisons un programme rapidement. Puisque vous devez écrire la fonction pour évaluer l'individu par vous-même, il est pratique d'utiliser ʻabsdans le cas de l'algorithme génétique, en se référant au code écrit au moment de la cuisson en utilisant le modèle Zing. En réfléchissant, j'ai créé la fonction ʻevaluate (). Après cela, créez une classe Fitness qui évalue la qualité de la solution, une classe Individuelle qui exprime un individu, créez une méthode ʻattribute () qui crée les attributs du chromosome de l'individu et utilisez-la pour créer un individu. Créez une méthode ʻindividual () qui crée une méthodepopulation ()qui l'utilise pour générer une population. Après cela, la méthode d'intersection mate () requise pour l'algorithme génétique, la méthode de mutation mutation (), la méthode de sélection naturelle select () et la première fonction créée ʻevalute () Générez une méthode ʻevalute ()à appeler.
Donc, cette fois, j'ai essayé d'exécuter la forme la plus simple d'algorithme génétique avec ʻalgorithms.eaSimple () `. Même si vous le laissez complètement à la bibliothèque, si vous faites un algorithme génétique sur 300 générations avec 100 individus, vous obtiendrez la bonne réponse.
À propos, les bons points de l'algorithme génétique, qui était plus lent que la méthode de cuisson utilisant le modèle Zing, sont qu'il existe de nombreux problèmes applicables car l'expression de la solution est plus flexible que le modèle Zing, et il y a beaucoup de place pour le réglage car il existe de nombreuses méthodes. est. Je ne l'ai pas réglé dans cet article, mais si vous rendez l'expression des chromosomes plus efficace, changez le moyen de croisement et changez la probabilité de mutations pour qu'elle soit agréable, ce sera plus que la méthode de recuit utilisant le modèle Zing. Il peut être possible de dériver une solution très précise à grande vitesse. Le réglage est amusant car vous pouvez voir l'effet immédiatement.
Eh bien, pour ce faire, je dois étudier diverses méthodes d'algorithmes génétiques, mais si j'étudie en essayant réellement avec DEAP, je pense que je peux le maîtriser immédiatement.
Quand je me suis demandé s'il y avait autre chose, j'ai remarqué la méthode de programmation entière. C'est une version qui rend la programmation linéaire encore plus difficile en la limitant aux entiers.
La méthode de programmation linéaire est une expression linéaire (une expression dans laquelle une seule variable est multipliée et reliée par addition et soustraction. 3 * x + y est une expression linéaire et 3 * a * a + b semble être une expression quadratique). C'est une méthode pour exprimer une fonction objective ou une fonction de contrainte et la résoudre mathématiquement rapidement. La fonction objectif est une expression qui exprime la bonté de la solution comme si elle avait été réalisée par la méthode de cuisson en utilisant le modèle Zing ou l'algorithme génétique, et sélectionne la solution la plus grande ou la plus petite possible. Ainsi, la fonction de contrainte est une expression conditionnelle qui exprime la contrainte de la solution.
e? Savez-vous ce que vous dites?
Je ne sais pas du tout alors ne demande pas ... Cependant, si vous utilisez PuLP, vous pouvez effectuer rapidement la méthode de planification par nombres entiers (et bien sûr la méthode de planification linéaire). Le code ressemble à ceci.
from functools import reduce
from funcy import *
from pulp import *
M = 5 # Nombre d'employés
D = 10 # jours
# Définir les variables utilisées dans le problème
xs = LpVariable.dicts('x', (range(M), range(D)), 0, 1, 'Binary')
# Définir le problème. d'ici……
problem = LpProblem('shift-scheduling-problem', LpMinimize)
# Ajouter une contrainte de 2 personnes ou plus par jour
for d in range(D):
problem += reduce(lambda acc, m: acc + xs[m][d], range(M), 0) >= 2
# Ajoutez une contrainte que vous ne viendrez pas travailler avec la même personne un autre jour
for m1 in range(M):
for m2 in range(m1 + 1, M):
for d1 in range(D):
for d2 in range(d1 + 1, D):
problem + = xs [m1] [d1] + xs [m2] [d1] + xs [m1] [d2] + xs [m2] [d2] <= 3 # L'inégalité (<) n'a pas pu être utilisée, donc < = 3
problem.writeLP('shift-scheduling-problem')
# ……Jusque là. Définir le problème
# Résolvez le problème avec la programmation d'entiers
status = problem.solve()
# Sortir le résultat
print(LpStatus[status])
# Sorties les employés qui viennent travailler au quotidien
for d in range(D):
print(tuple(keep(lambda m: 'ABCDE'[m] if xs[m][d].value() else False, range(M))))
Et le résultat est comme ça.
Optimal
('D', 'E')
('C', 'D')
('A', 'E')
('C', 'E')
('B', 'D')
('B', 'C')
('A', 'C')
('A', 'D')
('B', 'E')
('A', 'B')
C'est une solution optimale. Le temps d'exécution est de 0,132 seconde, ce qui est très rapide!
Les variables dans PuLP sont créées avec LpVariable. Cette fois, j'avais besoin de beaucoup de variables, donc j'en ai généré beaucoup avec LpVariable.dicts () à la fois. Aussi, cette fois, il n'y a pas de supériorité ou d'infériorité dans la solution qui satisfait la contrainte (si vous essayez de respecter au maximum la contrainte de différents couples d'employés, le nombre de personnes qui viennent travailler diminuera), donc seule la contrainte est définie.
La manière d'écrire des contraintes dans PuLP est une expression conditionnelle. 1 Le résultat du calcul du nombre de personnes à Hinode avec réduire () est comme > = 2. Ajoutez cette expression conditionnelle au problème créé en tant que LpProblem avec + =. Avec la restriction que vous ne venez pas travailler avec la même personne un autre jour, si vous faites xs [] * xs [] * xs [] * xs [] comme avant, ce sera une expression quaternaire, alors additionnez (dans ce cas) À la suite de (expression linéaire), j'ai créé une contrainte sous la forme de <= 3.
Tout ce que vous avez à faire est de «résoudre ()» ceci. Si la contrainte peut être satisfaite, la solution optimale avec la plus petite fonction objectif parmi la contrainte peut être résolue par la magie des mathématiques et renvoyée (En passant, vous pouvez vérifier si la contrainte est satisfaite par LpStatus [status]. Masu). Je ne sais pas quel genre de magie mathématique j'utilise, mais ce n'est pas grave si j'utilise juste PuLP.
Ouais, je ne sais pas ce qu'il y a dedans, mais PuLP est incroyable de trouver la solution optimale en si peu de temps ... Bien sûr, c'est incroyable, mais malheureusement, la programmation en entier n'est pas parfaite. Si c'est aussi simple que celui-ci, vous obtiendrez une réponse tout de suite, mais si c'est une question difficile, trouver une solution peut prendre beaucoup de temps. La méthode de cuisson utilisant un algorithme génétique ou un modèle d'ingénierie est une méthode qui produit une solution qui semble être raisonnablement bonne, bien qu'elle puisse ne pas être optimale, de sorte que même les problèmes difficiles peuvent être résolus d'une manière ou d'une autre. S'il s'agit d'un problème difficile, il peut ne pas être possible de l'exprimer avec une expression linéaire. Bien sûr, si la solution n'est pas absolument optimale, ou si le problème n'est pas très compliqué, la méthode de programmation entière (méthode de programmation linéaire) est meilleure.
Mais ça? Si vous vous calmez, je pense que vous pouvez le résoudre en moins de temps avec un programme plus simple. Voyez, en pensant en combinaison, ça ressemble à ça …….
from itertools import combinations, cycle
# Générez une combinaison unique de deux employés
membres = cycle (combinaisons ('ABCDE', 2)) # Vous n'êtes pas obligé de faire du vélo pendant 10 jours, mais juste au cas où
# Sortie pendant 10 jours
for _ in range(10):
print(next(members))
Si vous l'essayez ...
('A', 'B')
('A', 'C')
('A', 'D')
('A', 'E')
('B', 'C')
('B', 'D')
('B', 'E')
('C', 'D')
('C', 'E')
('D', 'E')
Ouais, c'est correct de voir. Le temps d'exécution était de 0,028 seconde ...
En fait, le processus de choix de différentes paires est très facile si vous pouvez l'exprimer par programme. Comme ça.
def getPairs(xs):
for i in range(len(xs)):
for j in range(i + 1, len(xs)):
yield xs[i], xs[j]
Je viens de commencer la plage de la boucle j avec ʻi + 1` pour que la même chose ne soit pas choisie et que la combinaison d'ordre inverse ne soit pas choisie. C'est la même technique que j'ai utilisée dans le code de la méthode de torréfaction utilisant le modèle Zing, où je ne suis pas venu travailler avec la même personne un autre jour. Donc, quand j'ai compté les résultats retournés par cette fonction, c'était 10, donc le problème cette fois était que si c'était bien fait, je pourrais obtenir une réponse qui répond à toutes les contraintes.
Donc, le nombre de combinaisons à choisir 2 sur 5 est de 10, j'ai l'impression d'avoir appris quelque part dans le passé ... Quand je l'ai recherché, [Wikipedia combinaison mathématique](https://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E6%95%B0%E5 C'est exactement la formule de combinaison qui ne permet pas la répétition de% AD% A6). 5! / (2! * (5-2)!) = 10.
Et, comme il s'agit d'un processus célèbre comme celui-ci, les combinaisons sont transformées en une bibliothèque dans la plupart des langages de programmation. Pour le Python utilisé dans cet article, c'est ʻitertools.combinarions`. Il était normal d'appliquer simplement le résultat de «combinaisons» à «cycle», qui répète l'ensemble pour créer un ensemble infini et afficher le nombre de jours depuis le début.
Donc, c'est l'Ochi cette fois (je suis désolé pour ceux qui ont remarqué Ochi en raison des restrictions. De plus, le terme problème de planification des équipes est la pêche. Je suis vraiment désolé pour ceux qui ont sérieusement des problèmes d'horaire des équipes). Mais ce que je veux dire dans cet article ne concerne pas la maîtrise des combinaisons. Cet article soutient que les méthodes d'animation utilisant le modèle d'Ising, les algorithmes génétiques, la programmation d'entiers et les combinaisons peuvent être facilement implémentées à l'aide de bibliothèques modernes. Chaque méthode a ses avantages et ses inconvénients, de sorte que le problème dépend de la méthode appropriée. Ensuite, lorsqu'on me demande quoi faire, je pense que je devrais essayer différentes choses pour le moment. Parce que c'est si facile à mettre en œuvre.