[PYTHON] Diviser en équipes par optimisation de combinaison (méthode de cuisson)

introduction

Dans l'article précédent (http://qiita.com/matsulib/items/898873b73d584c7dcb8b), j'ai formulé le problème d'association comme un problème de minimisation de l'écart moyen et présenté comment le résoudre exactement avec Python + PuLP. Dans ce document, il a mentionné que le problème d'optimisation de combinaison devient difficile à résoudre exactement à mesure que le problème devient grand.

Par conséquent, cette fois, je vais introduire une méthode de solution approximative par la méthode de cuisson en utilisant Python + simannal.

Qu'est-ce que simanneal

simanneal est un package pour la méthode de bronzage.

** Méthode d'installation **

pip install simanneal

** Utilisation de base **

Les contraintes du problème d'optimisation doivent être exprimées en move () et energy ().

Voir aussi "Exemple: Optimisation par Python + simanneal" ci-dessous.

Le problème que vous souhaitez résoudre

Il traite du même problème que la dernière fois. En ce qui concerne l'arrière-plan, reportez-vous à l'article précédent et résolvez le problème d'optimisation de combinaison suivant.

\begin{align}
\text{minimize} \quad &\sum_{j=1}^m \Bigl(\sum_{k=1}^l \Bigl|\sum_{i=1}^n a_{i,k} x_{i,j} - \mu_j \Bigr|\Bigr) + 1.5\sum_{j=1}^m\Bigl|\sum_{i=1}^n b_i x_{i,j} -\nu\Bigr| \tag{2.1}\\
\text{subject to} \quad &\mu_j = \frac{1}{l}\sum_{k=1}^l\sum_{i=1}^n a_{i,k}x_{i,j} &j=1,\ldots,m \tag{2.2}\\
& \nu = \frac{1}{m} \sum_{j=1}^m \sum_{i=1}^n b_i x_{i,j} \tag{2.3}\\
&\sum_{j=1}^m x_{i,j} = 1 &i=1,\ldots,n \tag{2.4}\\
& x_{i,j} \in \{0,1\} &i=1,\ldots,n;\, j=1,\ldots,m \tag{2.5}\\
\end{align}

La dernière fois, j'ai supprimé la valeur absolue d'ici et effectué une transformation pour en faire un problème de planification linéaire, mais avec la méthode de cuisson, tout va bien tel quel.

Exemple: optimisation par Python + simanneal

Nous traiterons du même exemple que la dernière fois.

grouping.py


from simanneal import Annealer
import random

class GroupingProblem(Annealer):
    
    def __init__(self, init_state):
        super(GroupingProblem, self).__init__(init_state)  # important!

    #Règles de déplacement des points de recherche
    def move(self):
        #Déplacer le membre m1 sélectionné au hasard de l'équipe t1 vers l'équipe t2
        m1 = random.choice(list(range(nmembers)))
        t1 = self.state[m1].index(1)
        t2 = random.choice(list(range(nteams)))
        self.state[m1][t1], self.state[m1][t2] = self.state[m1][t2], self.state[m1][t1]

    #Fonction objective
    def energy(self):
        v = 0
        nu = sum(sum(b[i] * self.state[i][j] for i in range(nmembers)) for j in range(nteams)) / nteams
        for j in range(nteams):
            mu_j = sum(sum(scores[i][k] * self.state[i][j] for i in range(nmembers)) for k in range(nskills)) / nskills
            for k in range(nskills):
                v += abs(sum(scores[i][k] * self.state[i][j] for i in range(nmembers)) - mu_j)
            v += 1.5 * abs(sum(b[i] * self.state[i][j] for i in range(nmembers)) - nu)
        return v


if __name__ == '__main__':
    #exemple
    teams = ['A', 'B', 'C']
    members = ['P', 'Q', 'R', 'S', 'T', 'U']
    skills = ['Controller', 'Promoter', 'Supporter', 'Analyzer']
    scores = [[6, 0, 1, 3],
              [2, -1, 3, 5],
              [2, 4, 0, 0],
              [3, 4, 5, 0],
              [0, 2, 1, 4],
              [2, 3, -1, 1]]

    nteams = len(teams)  #Nombre d'équipes
    nmembers = len(members)  #Nombre de membres
    nskills = len(skills)  #Nombre de types de capacités
    b = [sum(ai) for ai in scores]  #Somme des compétences de chaque membre

    #Allocation initiale
    init_state = [[0 for j in range(nteams)] for i in range(nmembers)]
    for i in range(nmembers):
        init_state[i][0] = 1  #Au début, tous appartiennent à l'équipe A
    
    prob = GroupingProblem(init_state)
    prob.steps = 100000
    prob.copy_strategy = "deepcopy"
    prob.anneal()  #Exécution brûlante

    for i,s in enumerate(prob.state):
        print(members[i], teams[s.index(1)])

Lorsque vous faites cela, vous verrez la progression du bronzage. 3.gif

J'ai eu la même solution que la dernière fois.

$ pypy grouping.py
 Temperature        Energy    Accept   Improve     Elapsed   Remaining
     2.50000         23.50    35.60%     0.70%     0:00:04     0:00:00
('P', 'A')
('Q', 'C')
('R', 'C')
('S', 'B')
('T', 'A')
('U', 'B')

Il complète chaque élément affiché par simanneal.

Finalement, la température et l'amélioration deviennent plus petites et la solution converge.

en conclusion

J'ai présenté comment résoudre le problème d'optimisation des combinaisons avec Python + simanneal. simanneal est un emballage très pratique qui vous permet d'effectuer facilement la méthode de bronzage. Simanneal peut également être exécuté sur pypy. Si l'opération pour chaque itération (le contenu de move () et enargy ()) est simple, on peut s'attendre à une accélération en utilisant pypy.

Remarque: l'utilisation de numpy.array avec pypy est lente. Lorsque vous utilisez pypy, il est plus rapide de tourner la carte ou l'instruction for dans la liste que d'utiliser l'opération vectorielle de numpy.array.

référence

Recommended Posts

Diviser en équipes par optimisation de combinaison (méthode de cuisson)
Divisez en équipes par optimisation de combinaison
Diviser en équipes par optimisation de combinaison (minimiser l'écart moyen)
Méthode gagnante des courses de chevaux par optimisation des combinaisons
Optimisation combinée avec recuit quantique
Résolution de "cubes en cubes" avec optimisation des combinaisons
Déterminer le programme enregistré par optimisation de combinaison
Optimisation SVM par la méthode de l'ensemble actif
Penser les menus par l'optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Minimisez le nombre de polissages en optimisant la combinaison
[Python] Divisez les albums de Switch en dossiers par jeu