はじめに
本記事は全3回のシリーズ記事の第3回 です。
その1：JijZeptとは
その2：OpenJijとJijZeptSolver
その3：JijZept Solver の性能検証
本記事は、Pythonの数理最適化パッケージ群「JijZept SDK」とソルバー「JijZept Solver」を紹介し性能を比較検証する連載の第3回です。前回は OpenJij に含まれるソルバー2種と JijZept Solver で同じ最適化問題を解き、性能と傾向を比較しました。今回は、そのうちの openjij.SASampler（以下、SASampler） と JijZept Solver を対象に、同じ最適化問題を同じ時間で解くことで性能をより詳細に比較します。
実験：SASampler vs JijZept Solver
前回の実験で3種類のソルバーを比較した結果、3つの中では SASampler と JijZept Solver がより優れていることがわかりました。今回の実験ではこれら2つをより詳細に比較します。
前回の実験においてはソルバー同士で引数や条件が必ずしも揃っていませんでしたが、ここでは処理時間を揃えて解の精度を比較することとします。
対象問題
前回の実験と同様に以下の基本的な組合せ最適化問題を対象とします。
- 2次元平面上の点のクラスタリング
- ナップザック問題
- 巡回セールスマン問題（Touring Salesman Problem, TSP）
これらの最適化問題をランダムに生成し OMMX 形式とした上で、jijzept_solver および SASampler・SQASampler（のアダプター）に与えて解を比較します。
定式化も前回の実験と同様ですので、詳細は連載第2回の記事をご覧ください。
実行環境
前回の実験と同様です。連載第2回の記事をご覧ください。
実験条件
SASampler のパラメータ num_sweeps は 1000 とします。前回の実験と同じ複数の問題サイズに対して乱数シードを1～50として50個の問題を生成します。そして、次の手順で評価を進めます。
- SASampler で各問題を解き、解くのに要した時間を控える。
- 1で要した時間を time_limit_sec として JijZept Solver で同じ問題を解く。
- 両者の解の目的関数値を比較し、目的関数値の改善率を確認する。
import time
from ommx.v1 import Solution
import ommx_openjij_adapter as oj_ad
import jijzept_solver
# 前提：ommx_instance に問題が入っている
# SASampler で各問題を解き、解くのに要した時間を控える。
start = time.perf_counter()
solution: Solution = oj_ad.OMMXOpenJijSAAdapter.solve(instance, num_sweeps=num_sweeps)
process_time = time.perf_counter() - start
# SASampler が要した時間を引数に JijZept Solver で同じ問題を解く
solution_jijzept: Solution = jijzept_solver.solve(
instance,
time_limit_sec=min(process_time, 600), # 600秒が本記事における JijZept Solver 利用形態での上限値
)ここで改善率は、最小化の場合は ((目的関数値(SASampler))-(目的関数値(JijZept Solver)) / (目的関数値(SASampler))) * 100、最大化の場合は ((目的関数値(JijZept Solver))-(目的関数値(j)) / (目的関数値(SASampler))) * 100としました。それぞれ正の値である場合 JijZept Solver の解がより精度が高いと見做すことができます。
クラスタリング
評価結果を下表に示します。クラスタリングの定式化は目的関数の最小化でした。
| 点の数 | SASampler の処理時間 | 目的関数値（JijZept Solver） | 目的関数値（SASampler） | 改善率[%] |
|---|---|---|---|---|
| 50 | 0.2649 | -20.73 | -20.73 | ≃0 |
| 100 | 0.6032 | -41.42 | -41.42 | ≃0 |
| 200 | 7.5961 | -83.37 | -83.37 | ≃0 |
| 500 | 23.4778 | -206.58 | -206.58 | ≃0 |
| 1000 | 39.6464 | -413.40 | -413.40 | ≃0 |
ナップザック問題
評価結果を下表に示します。ナップザック問題の定式化は目的関数の最大化でした。
| 都市数 | SASampler の処理時間 | 目的関数値（JijZept Solver） | 目的関数値（SASampler） | 改善率[%] |
|---|---|---|---|---|
| 10 | 0.5959 | 0.3037 | 0.2893 | -5.0034 |
| 20 | 13.7946 | 0.2882 | 0.2707 | -6.4868 |
| 30 | 32.3606 | 0.2506 | 0.2662 | 5.8656 |
| 40 | 67.2699 | 0.2614 | 0.2638 | 0.9185 |
| 50 | 146.6790 | 0.2635 | 0.2657 | 0.8526 |
荷物の数が多くなるほど改善率が大きくなっていることが見て取れます。前回の実験(図4)で見たとおり SASampler は実行可能解を出せていても目的関数値が JijZept Solver に比べて低く、荷物の数が多くなるにしたがって差が生じていた結果とも合致します。
巡回セールスマン問題(TSP)
評価結果を下表に示します。TSPの定式化は目的関数の最小化でした。
| 荷物の数 | SASampler の処理時間 | 目的関数値（JijZept Solver） | 目的関数値（SASampler） | 改善率[%] |
|---|---|---|---|---|
| 20 | 0.1884 | 18.71 | 18.71 | 0.00 |
| 30 | 0.2688 | 31.12 | 31.12 | 0.00 |
| 50 | 0.6311 | 53.52 | 51.91 | 3.09 |
| 75 | 2.0294 | 82.89 | 76.85 | 7.87 |
| 100 | 7.1307 | 110.49 | 98.71 | 11.93 |
都市数が少ない条件では SASampler の方が解がよく、都市数が30以上の場合は JijZept Solver が勝る結果となった。
前回の実験(図6)でもこれら2つのソルバーの目的関数値が前後する結果が見られたため、ランダム性や実行環境にも依存するところがあると考えられます。
終わりに
本記事では、OpenJij に含まれるソルバー SASampler と JijZept Solver で同じ最適化問題を同じ時間で解き、目的関数値を比較することでその性能差を見ました。その結果、問題サイズが大きくなると JijZept Solver が優位となる結果となりました。問題サイズが小さなところでは SASampler が優位となるものも見受けられましたが、この差は問題を解くアルゴリズム中のランダム性や実行環境によるところもある考えられ、必ずしも毎回同じ結果になるとは限らない点に注意が必要です。
また、今回は解く問題を QUBO に限定しましたが、JijZept Solver は種々の最適化問題に対応できる点も忘れてはいけません。様々なクラスの問題に対応できる一方、問題設定による得意・不得意もあると考えられますので、実際に利用する際は得られた解をよく分析し定式化へフィードバックするなど、注意して利用しましょう。
ISP では、貨物の3次元積み付けシミュレータや小型宇宙機の軌道最適化ソフトウェアのような最適化を中核にしたシステムやアプリケーションを開発しております。今後も技ラボで発信していきますので、ぜひご覧ください。