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

　これまで、量子アニーリングを利用して種々の組合せ最適化問題を学んできた。一般にエネルギー関数（目的関数、あるいはコスト関数とも呼ぶ）と制約条件をイジングマシンに与えて解く。この時、エネルギー関数と制約条件を単に合体させるのではなく、制約条件にある係数をかけてその強さを調整することが重要であることが分かった。だが、適度な係数値を決める方法は自明ではない。ここでは、「最適生産計画作成」を例に、その係数の値が最適化にどのように影響するかを観察する。

■例題：生産計画最適化
　以下に公開されているFixstars Amplifyのセミナー・トレーニング「生産計画最適化」を利用させていただいた。
　https://amplify.fixstars.com/ja/news/seminar
　3台の製造装置で3品種、合計45個を生産する。各品種毎の生産台数、生産時間、及び、生産する品種を切り替えるための段取り時間が定められている。全ての製品の生産にかかる総所要時間が少なく、総段取り時間も少ない、最適な生産計画を作成する。（詳細仕様は上記URLを参照願いたい。）

　制約１：各装置は同時には１品種のみを製造
　制約２：各品種の生産数は規定通りにする
　目的１：製造総所要時間（これを最小化する）
　目的２：総段取り時間（これを最小化する）

イジングマシンに与えるmodelを以下のようにする。ここで、係数kは制約条件の強さを意味する：
　model ← （目的1と目的2の併合）と（ k* (制約1と制約2の併合)）を合体

■制約条件の強さを表す係数kのアニーリングへの影響
　このmodelを、係数kの値を変えて実行した結果、表１のように目的関数値（=製造総所要時間と総段取り時間の和）を得た。利用したイジングマシン（Fixstars Amplify AEとHiroshima Univ. /NTT DATA ABS）によって多少異なるが、目的関数の値が最小となる、係数kの値の最小値は20〜50位であることが分かった。また、係数kはかなり大きな値で良いらしい。上記セミナー資料では（算出法の明記は無いが） k=35となっていた。さすがである。

　もちろん、ここで得たkの値はこの問題に特有なものだろう。しかし、上記の表からkの値の広がり具合が何となく掴める。この漠然とした感触が別の新たな問題に取り組む時に拠り所になりそうに思うのである。

■制約条件の強さを表す係数kの値の見積もり
　係数kの適切な値は、コスト関数に依存すると考えられる。これらの見積もり方法はいくつか提案されているが、ヒューリスティックか、機械学習によるもののようだ。以下の２つの説明は、上記の実行結果からも納得が行くと感じた。

説明１：
以下のオンラインデモ&チュートリアル「巡回セールスマン問題」の説明：
　https://amplify.fixstars.com/ja/demo
「ここで制約条件の強さに注意を要する必要があります。適切な制約条件の強さはコスト関数に依存し、十分に大きな値にする必要があるからです。しかし一方で、制約の強さを可能な限り小さくすることで、イジングマシンが出力する結果が改善する傾向にもあります。」

説明２：
インタフェース誌 2022年6月号の記事pp.129-131にある説明の要点：
実行可能解を制約条件を全て満たす解、そして実行不可能解を制約条件が満たされていない解と定義する。

• 係数kが小さい場合、実行不可能解のエネルギーが小さくなり、そこへ到達する可能性が生ずる。
• 係数kが十分大きい場合、実行不可能解のエネルギーが大きくなるため、よりコスト関数値の小さな実行可能解へ移動する傾向となる。
• 係数kが大きすぎる場合、実行不可能解のエネルギーがあまりにも大きいため、ある実行可能解に達しても、さらに別の実行可能解への移動がしにくくなり、結果として最適解に到達しにくい。

（何となく補足）
　最近、「量子コンピュータによるAI」というのを見かけることがあります。ちょっと違和感ありますね。従来不可能だった何を解きたいのか、何に応用したいのか、それを示唆する簡潔な表現が欲しいですね。そうでないと、「量子コンピュータ」という言葉に流された空疎なアナウンスにしか聞こえない。小生の場合、ゲートウェイ型であれアニーリング型であれ、量子コンピューティングでどんな問題が解けるのかを、基本的な例題にひとつづつ当たって丹念に調べるという段階にあります。今回の記事もその一環のつもり。