Création automatique d'horaire de travail à l'aide de la recherche tabou

en premier

Dans cet article, nous allons créer un quart de travail de 10 jours pour 7 employés. Il existe des variations de 4 heures de travail, 8 heures de travail et 0 heure de travail (vacances) dans les éléments de la procession. Après avoir lu cet article, vous pourrez enfin créer le planning de travail suivant.

Commençons par l'explication de l'algorithme.

Algorithme de recherche tabou

① Création de la solution initiale ② Création de solution de quartier ③ Optimiser à l'aide d'une pénalité pour répondre aux conditions de contrainte

C'est tout en un mot. C'est une image qui extrait aléatoirement du tableau de [0, 4, 8] et remplit le tableau de manière à satisfaire la condition de contrainte.

Créer une première solution

self.ns = np.zeros((person_num, days_num))
self.ns2 = np.zeros((person_num, days_num))
self.ns3 = np.zeros((person_num, days_num))

Nous créons une matrice avec tous les 0 éléments (nombre d'employés x nombre de jours à calculer).

index_num = self.choice_index()
index_num2 = self.choice_index()
index_num3 = self.choice_index()

Nous avons sélectionné 3 index chacun à modifier pour créer 3 solutions voisines.

Contraintes

if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
    penalty = penalty + 1
if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
    penalty2 = penalty2 + 1
if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
    penalty3 = penalty3 + 1

Nous définissons une contrainte selon laquelle les heures de travail hebdomadaires des trois solutions de quartier se situent entre 40 et 64 heures. Si les contraintes ne sont pas respectées, la pénalité sera augmentée de un.

Le cœur de la recherche taboue

En utilisant la "liste tabou" qui enregistre les transitions qui sont tombées dans une mauvaise solution, nous étudierons autre chose que celle recherchée une fois. En conséquence, la convergence devient plus rapide et une solution approximative peut être obtenue.

Code entier

%load_ext Cython

import numpy as np
import itertools
import matplotlib.pyplot as plt
import pandas as pd

class TabuSearch():
  tabu_list = []
  penalty_arr = []

  def __init__(self, person_num = 7, days_num = 10, select_num = 3):
    self.person_num = person_num
    self.penalty_old = 7 * 2 + 10
    self.days_num = 10
    self.select_num = select_num
    self.jikkou_num = 1
    #Initialisation de la solution approximative
    self.s_good = np.zeros((person_num, days_num))
    self.index_list = list(itertools.product(range(0, person_num), range(0, days_num), repeat=1))
    self.ns = np.zeros((person_num, days_num))
    self.ns2 = np.zeros((person_num, days_num))
    self.ns3 = np.zeros((person_num, days_num))

  def choice_index(self):
    return np.random.choice(list(range(0, self.person_num*self.days_num)), self.select_num, replace=False)

  def generate_near(self):
    #Créer une solution de quartier
    #Puisque la solution de voisinage est transformée localement, sélectionnez trois éléments. (3 est approprié)
    #Index à remplacer
    index_num = self.choice_index()
    index_num2 = self.choice_index()
    index_num3 = self.choice_index()

    penalty = 0
    penalty2 = 0
    penalty3 = 0

    ns = np.zeros((self.person_num, self.days_num))
    ns2 = np.zeros((self.person_num, self.days_num))
    ns3 = np.zeros((self.person_num, self.days_num))

    chg_flag = True
    #Valeur à changer
    new_var = [np.random.choice([8,4,0]) for i in range(0, self.select_num)]
    
    for j in range(0, len(self.tabu_list)):
      # tabu_Voir les 7 premières valeurs de la liste
      if j == 7:
        break
      for k in range(0, self.select_num):
        if index_num[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False
        if index_num2[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False
        if index_num3[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False

    #Ne mettez pas à jour la valeur si elle figure dans la liste des tabous
    if chg_flag == True:
      for i in range(0, len(index_num)):
        self.ns[self.index_list[index_num[i]][0], self.index_list[index_num[i]][1]] = new_var[i]
        self.ns2[self.index_list[index_num2[i]][0], self.index_list[index_num2[i]][1]] = new_var[i]
        self.ns3[self.index_list[index_num3[i]][0], self.index_list[index_num3[i]][1]] = new_var[i]
      for i in range(0, len(self.ns)):
        if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
          penalty = penalty + 1
        if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
          penalty2 = penalty2 + 1
        if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
          penalty3 = penalty3 + 1
      if penalty < self.penalty_old and penalty <= penalty2 and penalty <= penalty3:
        self.s_good = self.ns
        #Pénalité uniquement lorsqu'il n'y a aucune valeur dans la liste des tabous_Ajouter une valeur à arr
        TabuSearch.penalty_arr.append(penalty)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Valeur totale de la ligne", str(sum(self.ns[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty
      elif penalty2 < self.penalty_old and penalty2 <= penalty3:
        self.s_good = self.ns2
        TabuSearch.penalty_arr.append(penalty2)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Valeur totale de la ligne", str(sum(self.ns2[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty2
      elif penalty3 < self.penalty_old:
        self.s_good = self.ns3
        TabuSearch.penalty_arr.append(penalty3)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Valeur totale de la ligne", str(sum(self.ns3[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty3
      else:
        #Enregistrez les mauvaises choses et essayez d'optimiser les bonnes directions
        TabuSearch.tabu_list.insert(0, index_num)
        TabuSearch.tabu_list.insert(0, index_num2)
        TabuSearch.tabu_list.insert(0, index_num3)
        return self.penalty_old
    else:
      self.jikkou_num = self.jikkou_num + 1
      TabuSearch.penalty_arr.append(self.penalty_old)
      return self.penalty_old

  def execution(self, times=1000000):
    #Code pour terminer si la somme de chaque ligne est dans une certaine plage
    for i in range(0, times):
      penalty = self.generate_near()
      if penalty < self.penalty_old:
        print(f"{self.jikkou_num}Deuxième exécution")
        print("Valeur de la pénalité", penalty)
        print("Valeur de pénalité globale", self.penalty_old)
        self.penalty_old = penalty
      if penalty == 0:
        df = pd.DataFrame(self.s_good, columns=("Mois" , "Feu", "eau", "bois", "Argent", "sol", "journée", "Mois", "Feu", "eau"))
        print(df.to_markdown())
        break
  def plot_loss(self):
    plt.plot(TabuSearch.penalty_arr)

  def output_markdown(self):
    df = pd.DataFrame(self.s_good, columns=("Mois" , "Feu", "eau", "bois", "Argent", "sol", "journée", "Mois", "Feu", "eau"))
    print(df.to_markdown())

Courir

ts = TabuSearch()
ts.execution(100000)

Une partie de la sortie

Valeur totale sur la première ligne 56.0
Valeur totale sur la deuxième ligne 48.0
Valeur totale sur la troisième ligne 40.0
Valeur totale sur la 4ème ligne 40.0
Valeur totale sur la 5ème ligne 40.0
Valeur totale à la ligne 6 48.0
Valeur totale à la ligne 7 40.0
232e exécution
Valeur de pénalité 0
Valeur de pénalité globale 1
|    |Mois|Feu|eau|bois|Argent|sol|journée|Mois|Feu|eau|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
|  0 |    0 |    8 |    8 |    8 |    4 |    0 |    8 |    8 |    8 |    4 |
|  1 |    4 |    8 |    4 |    4 |    4 |    8 |    0 |    8 |    4 |    4 |
|  2 |    0 |    8 |    4 |    0 |    0 |    4 |    8 |    4 |    4 |    8 |
|  3 |    4 |    0 |    8 |    0 |    0 |    4 |    4 |    8 |    4 |    8 |
|  4 |    8 |    0 |    4 |    4 |    4 |    0 |    0 |    8 |    4 |    8 |
|  5 |    4 |    4 |    4 |    0 |    4 |    8 |    0 |    8 |    8 |    8 |
|  6 |    0 |    8 |    4 |    8 |    4 |    8 |    0 |    4 |    4 |    0 |

Tracez la transition de la valeur de pénalité

ts.plot_loss()

Afficher l'horaire de travail avec démarque

ts.output_markdown()

|    |Mois|Feu|eau|bois|Argent|sol|journée|Mois|Feu|eau|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
|  0 |    0 |    8 |    8 |    8 |    4 |    0 |    8 |    8 |    8 |    4 |
|  1 |    4 |    8 |    4 |    4 |    4 |    8 |    0 |    8 |    4 |    4 |
|  2 |    0 |    8 |    4 |    0 |    0 |    4 |    8 |    4 |    4 |    8 |
|  3 |    4 |    0 |    8 |    0 |    0 |    4 |    4 |    8 |    4 |    8 |
|  4 |    8 |    0 |    4 |    4 |    4 |    0 |    0 |    8 |    4 |    8 |
|  5 |    4 |    4 |    4 |    0 |    4 |    8 |    0 |    8 |    8 |    8 |
|  6 |    0 |    8 |    4 |    8 |    4 |    8 |    0 |    4 |    4 |    0 |

Livre de référence

Métahuristique et calcul naturel