[PYTHON] Divide into teams by combinatorial optimization (simulated annealing method)
Introduction
In Previous article, I formulated the teaming problem as an average deviation minimization problem and introduced how to solve it exactly with Python + PuLP. In it, he mentioned that combinatorial optimization problems become difficult to solve exactly as the problem becomes large.
Therefore, this time, I will introduce an approximate solution method by simulated annealing using Python + simanneal.
What is simanneal
simanneal is a package for Simulated Annealing.
** Installation method **
pip install simanneal
** Basic usage **
- Create a subclass of the Annealer class.
- Override move () and implement search point move rules
- Override energy () and implement objective function
- Create a problem object by giving an initial solution to the constructor of the created class.
- Perform simulated annealing on the problem object .anneal ().
- Get the solution in the problem object .state.
The constraints of the optimization problem must be expressed in move () and energy ().
See also "Example: Optimization by Python + simanneal" below.
The problem you want to solve
We will deal with the same problem as last time. As for the background, refer to the previous article, and solve the following combinatorial optimization problem.
\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}
Last time, I removed the absolute value from here and made a transformation to make it a linear programming problem, but simulated annealing can be used as it is.
Example: Optimization by Python + simanneal
We will deal with the same example as last time.
- Divide 6 people into 3 teams.
- There are four types of communication skills.
grouping.py
from simanneal import Annealer
import random
class GroupingProblem(Annealer):
def __init__(self, init_state):
super(GroupingProblem, self).__init__(init_state) # important!
#Search point movement rules
def move(self):
#Move randomly selected member m1 from team t1 to team 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]
#Objective function
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__':
#example
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) #Number of teams
nmembers = len(members) #Number of members
nskills = len(skills) #Number of ability types
b = [sum(ai) for ai in scores] #Sum of skills of each member
#Initial allocation
init_state = [[0 for j in range(nteams)] for i in range(nmembers)]
for i in range(nmembers):
init_state[i][0] = 1 #At first, all belong to Team A
prob = GroupingProblem(init_state)
prob.steps = 100000
prob.copy_strategy = "deepcopy"
prob.anneal() #Annealing
for i,s in enumerate(prob.state):
print(members[i], teams[s.index(1)])
When you do this, you will see the progress of annealing.
I got the same solution as last time.
$ 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')
It supplements each item displayed by simanneal.
- Temperature: Temperature. The larger this value, the more severe the change of state.
- Energy: Energy. The value of the objective function.
- Accept: Transition probability. If this value is large, it will transition to a bad state (to escape from the local solution). This value depends on energy and temperature.
- Improve: The improvement rate of the objective function at the time of transition.
- Elapsed: Elapsed time.
- Remaining: Remaining time.
Eventually, Temperature and Improve become smaller and the solution converges.
in conclusion
I introduced how to solve combinatorial optimization problems with Python + simanneal. simanneal is a very convenient package that allows you to easily perform Simulated Annealing. Simanneal can also be run on pypy. If the operation for each iteration (the contents of move () and enargy ()) is simple, you can expect speedup by using pypy.
Note: Using numpy.array with pypy is slow. When using pypy, it is faster to turn the map or for statement in the list than to use the vector operation of numpy.array.
reference
- perrygeo/simanneal: Python module for Simulated Annealing optimization
- Simulated Annealing Method-Wikipedia (https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97 % E6% B3% 95)
- Multidimensional array calculation without Numpy
Recommended Posts