조합 최적화로 팀 나누기(야키나마시법)

소개

마지막 기사 에서 팀 분할 문제를 평균 편차 최소화 문제로 공식화하고 Python+PuLP로 엄격하게 해결하는 방법을 소개했습니다. 그 중 조합 최적화 문제는 문제가 대규모가 되면 엄격하게 풀기가 어려워진다고 말했습니다.

그래서 이번에는 Python+simanneal을 사용한 어닐링법에 의한 근사해법을 소개합니다.

simanneal이란?

simanneal은 어닐링 방법을위한 패키지입니다.

설치 방법

pip install simanneal

기본 사용법

Annealer 클래스의 서브 클래스를 작성합니다.

move ()를 재정의하고 탐색 지점 이동 규칙을 구현합니다.

energy ()를 재정의하고 목적 함수 구현

작성한 클래스의 생성자에 초기 해를 주어 문제 오브젝트를 작성한다.

문제 객체 .anneal()에서 어닐링 방법을 실행한다.

문제 객체 .state에서 솔루션을 가져옵니다.

최적화 문제의 제약은 move()와 energy() 속에서 표현할 필요가 있습니다.

아래의 "예제 : Python + simanneal에 의한 최적화"도 참조하십시오.

풀고 싶은 문제

이전과 같은 문제를 다룹니다.
배경은 이전 기사를 참조하도록 하여 다음과 같은 조합 최적화 문제를 해결합니다.

\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}

전회는 여기에서 절대치를 제외해 선형 계획 문제로 하는 것 같은 변형을 실시했습니다만, 어닐링법에서는 그대로로 괜찮습니다.

예제: Python+simanneal에 의한 최적화

이전과 같은 예제를 다룹니다.

6명을 3팀으로 나눕니다.

커뮤니케이션 능력의 종류는 4종류입니다.

grouping.py

from simanneal import Annealer
import random

class GroupingProblem(Annealer):

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

    # 探索点の移動ルール
    def move(self):
        # ランダムに選択したメンバーm1をチームt1からチーム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]

    # 目的関数
    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__':
    # 例題
    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)  # チーム数
    nmembers = len(members)  # メンバー数
    nskills = len(skills)  # 能力種別数
    b = [sum(ai) for ai in scores]  # 各メンバーのスキルの総和

    # 初期割当て
    init_state = [[0 for j in range(nteams)] for i in range(nmembers)]
    for i in range(nmembers):
        init_state[i][0] = 1  # 最初は全員Aチームに所属

    prob = GroupingProblem(init_state)
    prob.steps = 100000
    prob.copy_strategy = "deepcopy"
    prob.anneal()  # 焼きなまし実行

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

이렇게하면 어닐링의 경과가 표시됩니다.


전회와 같은 해를 얻었습니다.

$ 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')

simanneal이 표시하는 각 항목에 대해 보충합니다.

Temperature: 온도. 이 값이 클수록 상태 변화가 심해집니다.

Energy: 에너지. 목적 함수의 값.

Accept: 전이 확률. 이 값이 크면 나쁜 상태로도 천이한다(국소해로부터 탈출하기 위해). 이 값은 에너지와 온도에 따라 다릅니다.

Improve : 전환시 목적 함수 개선율.

Elapsed: 경과 시간.

Remaining: 남은 시간.

결국 Temperature와 Improve가 작아지고 해가 수렴합니다.

결론

조합 최적화 문제를 Python+simanneal로 해결하는 방법을 소개했습니다.
simanneal은 쉽게 구운 방법을 수행 할 수있는 매우 편리한 패키지입니다.
또한 simanneal은 pypy에서도 실행할 수 있습니다. 반복마다의 조작(move()이나 enargy()의 내용)이 단순한 것이라면 pypy를 이용하는 것으로 고속화를 전망할 수 있습니다.

참고 : pypy에서 numpy.array를 사용하면 느려집니다. pypy를 사용하는 경우는 numpy.array의 벡터 연산을 사용하는 것보다 목록에서 map이나 for문을 돌리는 것이 빠릅니다.

참고

perrygeo/simanneal: Python module for Simulated Annealing optimization

야키나마시법 - Wikipedia

Numpy를 사용하지 않는 다차원 배열 계산