🎄

一般化割当問題に対する重み付き局所探索法の実装

に公開

はじめに

「制約付き」の組合せ最適化問題に対するメタヒューリスティクスの実装を解説します。
今回は、一般化割当問題(Generalized Assignment Problem; GAP)に対する重み付き局所探索法(Weighting Local Search; WLS)を紹介します。

問題設定と定式化

与えられたn個の仕事をm個のエージェントに割り当てるとき、割り当てにともなうコストの合計を最小化する問題です。ここで、仕事jをエージェントiに割り当てたときのコストc[i,j]と資源a[i,j]、各エージェントiの利用可能資源量b[i]が与えられます。

一般化割当問題の例

エージェントiに仕事jを割り当てるときにx[i,j]=1(それ以外は0)を取る変数を考えると、一般化割当問題は以下の通りに定式化できます。

\begin{array}{lll} \textnormal{min.} & \displaystyle\sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij}\\ \textnormal{s.t.} & \displaystyle\sum_{j \in J} a_{ij} x_{ij} \le b_i, & i \in I,\\ & \displaystyle\sum_{i \in I} x_{ij} = 1, & j \in J,\\ & x_{ij} \in \{ 0, 1 \}, & i \in I, j \in J. \end{array}

一般化割当問題は、NP困難な組合せ最適化問題であることはもちろん、制約条件を満たす実行可能解の有無を判定する決定問題がNP完全で、実行可能解を一つ求めることすら容易ではありません。

制約付き最適化問題に対するペナルティ関数法

制約付き最適化問題では、制約条件に対する違反量の重み付き和を目的関数に足し合わせて得られる評価関数を最小化するペナルティ関数法が良く使われます。今回は、エージェントiに対する容量制約の違反度に重みw[i]をかけた値をペナルティとして目的関数に加えて得られる評価関数z(\bm{x})を最小化する解を探索します。

\begin{array}{lll} \textnormal{min.} & z(\bm{x}) = \displaystyle\sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij} + \sum_{i \in I} w_i \; \max \left\{ \sum_{j \in J} a_{ij} x_{ij} - b_i, 0 \right\} \\ \textnormal{s.t.} & \displaystyle\sum_{i \in I} x_{ij} = 1, \quad j \in J,\\ & x_{ij} \in \{ 0, 1 \}, \quad i \in I, j \in J. \end{array}

ペナルティ重みw[i]の調整は容易ではなく、適当な値に設定して局所探索法を1回適用しただけでは質の高い実行可能解は得られません。そこで、ペナルティ重みw[i]を更新しては局所探索法を適用する手続きを繰り返す重み付き局所探索法(WLS)を用います。

局所探索法の実装

重み付き局所探索法(WLS)の基本となる局所探索法(Local Search; LS)を実装します。
局所探索法は、適当な初期解\bm{x}から始めて、現在の解\bm{x}の近傍に改善解\bm{x}^\primeがあれば移動する手続きを繰り返します。
局所探索法

# 初期解の生成
for j in range(num_job):
    sol[j] = random.randrange(0,num_agenet)
# 局所探索法
best = sol[:]
while True
    # シフト近傍走査
    shift_nb_search(best,sol)
    # スワップ近傍走査
    if swap_nb_search(best,sol): continue
    break

一般化割当問題に対する局所探索法の手続きは以下の通りです。ランダムな初期解から始めて、シフト近傍走査とスワップ近傍走査を交互に繰り返し適用して改善解を探索します。
一般化割当問題に対する局所探索法の手続き

今回の局所探索法では、解を1次元配列solに格納します。sol[j]=iは仕事jをエージェントiに割り当てることを表します。シフト近傍では、仕事jの割り当て先をエージェントi1からi2に変更します。これはsol[j]=i1をsol[j]=i2と書き換える操作になります。
シフト近傍

スワップ近傍では、仕事j1とj2の割り当て先のエージェントi1とi2を交換します。これはsol[j1]=i1, sol[j2]=i2をsol[j1]=i2, sol[j2]=i1と書き換える操作になります。
スワップ近傍

シフト近傍走査の実装

シフト近傍走査の詳細は以下の通りです。
まず、仕事jとエージェントiの組に対してシフト操作を適用した際の目的関数とペナルティ関数の差分値をcalc_diffで計算します。
次に、暫定解\bm{x}^{\ast}を更新します。ここで、暫定解\bm{x}^{\ast}≠現在の解\bm{x}であることに注意して下さい。最初の実行可能解が求まるまではペナルティ関数の値が最小となる解を暫定解とします。暫定解が実行不能(制約を満たしていない)であればペナルティ関数の値を、実行可能(制約を満たしている)であれば目的関数の値を比較します。
最後に、現在の解\bm{x}を更新します。目的関数とペナルティ関数の値を足し合わせた評価関数の値を比較し、候補解が改善解であればupdate_solで現在の解を更新します。

restart = True
while restart:
    restart = False
    nbhd = ((j,i)
            for j in range(num_job)
            for i in range(num_agent) if i != sol[j])
    for j,i in nbhd:
        # 差分値の計算
        delta_obj, delta_plt = calc_diff(sol,j,i)
        # 暫定解の更新
        if(plt + delta_plt < EPSILON and (best_plt > EPSILON or obj + delta_obj < best_obj - EPSILON)):
            best = sol[:]
            update_sol(best,j,i)
        # 現在の解の更新
        if delta_obj + delta_plt < -EPSILON:
            update_sol(sol,j,i)
            restart = True
            break

目的関数とペナルティ関数の差分値を計算するcalc_diffの詳細は以下の通りです。
ここで、ペナルティ関数の値を愚直に計算しないように注意して下さい。サンプルコードでは、現在の解\bm{x}(暫定解\bm{x}^{\ast})におけるエージェントiの資源利用量を1次元配列used[i]に記憶することで、少ない計算手間でペナルティ関数の差分値を計算しています。

シフト近傍の操作

def calc_diff(sol,j,i):
    i1,i2 = sol[j],i
    delta_obj = cost[i2][j] - cost[i1][j]
    plt = max(0, used[i1] - cap[i1])
    new_plt = max(0, used[i1] - res[i1][j] - cap[i1])
    delta_plt = wt[i1] * (new_plt - plt)
    plt = max(0, used[i2] - cap[i2])
    new_plt = max(0, used[i2] + res[i2][j] - cap[i2])
    delta_plt += wt[i2] * (new_plt - plt)
    return delta_obj, delta_plt

解を更新するupdate_solの詳細は以下の通りです。
現在の解の更新と同時にused[i]も更新します。下記のコードは紛らわしいですが、実際には、暫定解bestと現在の解solのそれぞれに異なる1次元配列used[i]を用意する必要があることに注意して下さい。

def update_sol(sol,j,i,flag):
    i1,i2 = sol[j],i
    sol[j] = i2
    used[i1] -= res[i1][j]
    used[i2] += res[i2][j]
    obj += cost[i2][j] - cost[i1][j]
    plt = 0.0
    for i in range(num_agent):
        plt += wt[i] * max(0, used[i] - cap[i])

スワップ近傍走査の実装

スワップ近傍走査の詳細は以下の通りです。
シフト近傍走査とほとんど変わりませんので説明は省きます。

restart = True
while restart:
    restart = False
    nbhd = ((j1,j2)
            for j1 in range(num_job)
            for j2 in range(j1+1,num_job) if sol[j2] != sol[j1])
    for j1,j2 in nbhd:
        # 差分値の計算
        delta_obj, delta_plt = calc_diff(sol,j1,j2)
        # 暫定解の更新
        if(plt + delta_plt < EPSILON and (best_plt > EPSILON or obj + delta_obj < best_obj - EPSILON)):
            best = sol[:]
            update_sol(best,j1,j2)
        # 現在の解の更新
        if delta_obj + delta_plt < -EPSILON:
            update_sol(sol,j1,j2)
            restart = True
            break

スワップ近傍の操作

def calc_diff(sol,j1,j2):
    i1,i2 = sol[j1],sol[j2]
    delta_obj = cost[i2][j1] + cost[i1][j2] - cost[i1][j1] - cost[i2][j2]
    plt = max(0, used[i1] - cap[i1])
    new_plt = max(0, used[i1] - res[i1][j1] + res[i1][j2] - cap[i1])
    delta_plt = wt[i1] * (new_plt - plt)
    plt = max(0, used[i2] - cap[i2])
    new_plt = max(0, used[i2] - res[i2][j2] + res[i2][j1] - cap[i2])
    delta_plt += wt[i2] * (new_plt - plt)
    return delta_obj, delta_plt
def update_sol(sol,j1,j2,flag):
    i1,i2 = sol[j1],sol[j2]
    sol[j1],sol[j2] = i2,i1
    used[i1] += res[i1][j2] - res[i1][j1]
    used[i2] += res[i2][j1] - res[i2][j2]
    obj += cost[i2][j1] + cost[i1][j2] - cost[i1][j1] - cost[i2][j2]
    plt = 0.0
    for i in range(num_agent):
        plt += wt[i] * max(0, used[i] - cap[i])

重み付き局所探索法

重み付き局所探索法は(WLS)は局所探索法とペナルティ重みw[i]の更新を交互に繰り返し適用します。エージェントiにおける資源容量制約の違反量をp_i(\bm{x}) = \max\left\{ \sum_{j \in J} a_{ij} x_{ij} - b_i, 0 \right\}とします。評価関数z(\bm{x})の値が暫定解の目的関数の値より小さければ、以下の更新式にしたがってペナルティ重みw[i]を増加し、そうでなければ、一律に\alpha(0 < \alpha < 1)倍して減少します。

w_i = w_i \left( 1 + \delta \frac{p_i(\bm{x})}{\displaystyle \max_{h \in I} p_h(\bm{x})} \right)

重み付き局所探索法の詳細は以下の通りです。
探索開始直後は、まず実行可能解を一つ求めることを優先するため、ペナルティ重みw[i]は十分に大きな値に初期化します。ここでは、w_i = \max_{j \in J} c_{ij}に初期化しています。

# ペナルティ重みの初期化
init_weight(wt)
# 重み付き局所探索法
best = sol[:]
st_time = time.time()
while time.time() - st_time < TIME_LIMIT:
    # 局所探索法
    local_search(best, sol)
    # ペナルティ重みの更新
    update_weight(wt)
def init_weight(wt):
    # ペナルティ重みの初期化
    for i in range(num_agent):
        wt[i] = -float('inf')
        for j range(num_job):
            if cost[i][j] > wt[i]: wt[i] = cost[i][j]
    # ペナルティ関数の再計算
    plt = 0.0
    for i in range(num_agent):
        plt += wt[i] * max(0, used[i] - cap[i])
def update_weight(wt,th):
    if obj + plt > best_obj - EPSILON:
        # ペナルティ重みを減少
        for i in range(num_agent):
            wt[i] = max(WT_MIN, ALPHA * wt[i])
    else:
        # ペナルティ重みを増加
        max_plt = 0.0
        for i in range(num_agent):
            max_plt = max(max_plt, used[i] - cap[i])
        for i in range(num_agent):
            wt[i] *= 1.0 + DELTA * max(0, used[i] - cap[i]) / max_plt
    # ペナルティ関数の再計算
    plt = 0.0
    for i in range(num_agent):
        plt += wt[i] * max(0, used[i] - cap[i])

おわりに

この記事でご紹介した重み付き局所探索法のサンプルコードをこちらで公開しています。
一般化割当問題のサンプルコード

理由は良く分からないのですが、なぜか、「制約付き」の組合せ最適化問題に対するメタヒューリスティクスを検討した論文をあまり見かけません。これは、組合せ最適化問題のさまざまな制約をペナルティ関数法などの典型的な手法で簡単にあしらえるからではなく、実際には、高性能なメタヒューリスティクスを実装するためには問題毎に多くの試行錯誤を要することが少なくありません。そこで、今回は「制約付き」の組合せ最適化問題に対するメタヒューリスティクスの汎用的なアプローチを紹介しました。この記事が少しでも皆さんのお役に立てば幸いです。

Discussion