2022年6月12日日曜日

量子アニーリングにおける制約条件の強さの扱い(続)

 前回に引き続き、エネルギー関数と制約条件を合体させる場合に、制約条件に掛ける係数の影響を観察する。また、今回の例題では目的関数が2種類あり、それぞれをどの程度重視するかを決める係数についても見る。

例題:シフト最適化
 以下に公開されているFixstars Amplifyのセミナー・トレーニング「シフト最適化」を利用させていただいた。
 https://amplify.fixstars.com/ja/news/seminar
 3つの生産ラインへ15名の従業員を5名づつ割り当てる。各従業員はそれぞれのラインに対するスキル値を持つ。全ラインのスキル値の合計をできるだけ大きくしたい。同時、各ラインのスキル値のばらつき(分散)を小さくしたい。そこで、目的関数と制約条件を図1のようにする。(より詳細は上記URLを参照されたい。)

 目的関数が2つあるので、それぞれをどの程度重視するかを決める係数γを設定する。また、前回と同様に、制約条件も2つあり、目的関数に対するそれらの制約条件の強さを示す係数δを設定する。

制約条件の強さを表す係数δのアニーリングへの影響
 このmodel(イジング模型)を、係数δの値を変えて実行した結果は表1のようになった。係数δの値が、0.2〜10.0の広い範囲で、目的関数の一つである全ラインのスキル値合計を高くできている。(ただし、その値は係数γの値により異なる。)実際には、係数δに従業員のスキル値の最大値を掛けている。すなわち、大雑把に言って、制約条件に掛ける重みの係数は、従業員のスキル値の最大値付近(数分の1から数倍程度)が良いようである。

 一方、もう一つの目的関数である各ラインのスキル値の分散を小さくすることは、係数γの値の調整で可能であることが確認できた。すなわち、あくまで合計スキル値を最高にすることにこだわるのか(γ=0.6)、それとも、ライン毎のスキル値の分散を限りなく小さくすることに固執するのか(γ=0.4)を選択できる。

 今回の観察結果から、種々の問題における係数δの決め方の一般的な方法が得られたわけではない。しかし、このような観察を多数のイジング模型の解法で実施することは、経験的に良い値を設定することに繋がるだろう。

0 件のコメント:

コメントを投稿