12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡

21-37. QUBOアニーリング「TYTAN」に高速GPUサンプラーが追加

やること

QUBOアニーリングでお世話になっている「TYTAN」パッケージに、なんとGPUサンプラーが追加されました。バージョン0.0.22からです。

その名も「ArminSampler」

待ってください。TYTANのサンプラーには巨人の名前が付けられる慣習のはず。まるでアルミンが巨人になるかのようなネーミングじゃないか。え?(←アニメ1期しか見てない)

アルミンサンプラーの使い方は?どれくらい速いの?彼女はいる?結婚してる?

調べてみた結果、公開されていませんでした。いかがでしたか?

比較してみました。

TYTANについて

「TYTAN」はOSSのアニーリングSDKです。

GitHub - tytansdk/tytan: Python SDK for large QUBO problems
Python SDK for large QUBO problems. Contribute to tytansdk/tytan development by creating an account on GitHub.

チュートリアル教材はこちら。また、毎週木曜日22時にオンライン勉強会もやっています(2024年2月現在)。

GitHub - tytansdk/tytan_tutorial
Contribute to tytansdk/tytan_tutorial development by creating an account on GitHub.

discordコミュニティもあるので気軽に質問できます。

https://discord.gg/qT5etstPW8

ベンチマーク問題

180量子ビットの生産計画最適化問題(ジョブスケジューリング問題)を用意しました。

5台の機械(単位時間あたりの処理能力1, 1, 2, 2, 3)と36個のタスク(処理時間1, 2, …, 35, 36)があり、最短ですべてのタスクを終わらせる割り振りを見つける問題です。

import time
import numpy as np
from tytan import *

# 機械数
M = 5

# 単位時間あたりの処理能力
machine_power = np.array([1, 1, 2, 2, 3])
print(machine_power)

# タスク数
T = 36

# 各タスクの必要処理量
task = np.arange(1, T + 1)
print(task)
[1 1 2 2 3]
[ 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 25 26 27 28 29 30 31 32 33 34 35 36]

この問題の最適解(大域解)は74時間で、複数パターンあります。

実行マシン

CPU:Ryzen 5 5600G

GPU:RTX 2070(※ColabのTesla T4より性能は高い)

SASamplerで求解(CPU)

サンプリングが10秒程度で終わるようにパラメータを調整しています。デフォルトの shots=100, T_num=2000 から shots=1000, T_num=4000 に上げています。

#量子ビットを用意
q = symbols_list([M, T], 'q{}_{}')

#制約条件(ワンホット)
H = 0
for i in range(T):
    H += 100 * (sum(q[:, i]) - 1)**2

#コスト(処理時間が74に近い)
for i in range(M):
    H += (sum(task*q[i]) / machine_power[i] - 74)**2

#コンパイル
qubo, offset = Compile(H).get_qubo()
print(f'offset={offset}')

#サンプラー選択
solver = sampler.SASampler(seed=None)

#サンプリング
s = time.time()
result = solver.run(qubo, shots=1000, T_num=4000)
e = time.time()
print(round(e - s, 3), 's')

#結果(上位1件)
for r in result[:1]:
    print(f'Energy={r[1]}, Occurrence={r[2]}')
    arr, subs = Auto_array(r[0]).get_ndarray('q{}_{}')
    print(arr)

    #ワンホット確認
    print(np.sum(arr, axis=0))

    #割り振りを確認
    for i in range(M):
        task_select = task[np.where(arr[i]==1)[0]]
        t = np.sum(task_select) / machine_power[i]
        print(f'機械{i} タスク {task_select} 時間 {t}')
offset=30980.0
11.128 s
Energy=-30977.88888888889, Occurrence=1
[[0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0]
 [0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
 [0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0]
 [0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0]
 [1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [ 2  8 31 34] 時間 75.0
機械1 タスク [ 4 10 11 17 32] 時間 74.0
機械2 タスク [ 3 14 15 18 19 20 26 33] 時間 74.0
機械3 タスク [ 5  6  7 21 23 25 29 30] 時間 73.0
機械4 タスク [ 1  9 12 13 16 22 24 27 28 35 36] 時間 74.33333333333333

10回中もっとも良かった結果を載せました。最良解のエネルギーは理想値+2.1でした。

ArminSamplerのCPU版で求解

ArminSamplerにはCPUモードとGPUモードがありますが、いずれもpytorchのインストールが必須で、ない場合はこのような警告が出ます。pytorchはTYTANパッケージの標準装備ではないため、別途適当にインストールしてください。

=======================
= A T T E N T I O N ! =
=======================
ArminSampler requires PyTorch installation.
Use "pip install torch" (or others) and ensure
-------
import torch
torch.cuda.is_available()
#torch.backends.mps.is_available() #if Mac
-------
outputs True to set up the environment.

こちらもサンプリングが10秒程度で終わるようにパラメータを調整しています。ArminSampler() はデフォルトで mode=’GPU’ です。shots=2000, T_num=4000 に上げています。

#サンプラー選択
solver = sampler.ArminSampler(seed=None, mode='CPU')

#サンプリング
result = solver.run(qubo, shots=2000, T_num=4000, show=True)
offset=30980.0
MODE: CPU
DEVICE: cpu
11.716 s
Energy=-30977.890625, Occurrence=1
[[0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1]
 [0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
 [1 1 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [ 3  6 19 20 27] 時間 75.0
機械1 タスク [ 8 11 23 32] 時間 74.0
機械2 タスク [12 17 24 26 31 36] 時間 73.0
機械3 タスク [ 4  7 13 18 21 22 28 35] 時間 74.0
機械4 タスク [ 1  2  5  9 10 14 15 16 25 29 30 33 34] 時間 74.33333333333333

10回中もっとも良かった結果を載せました。こちらも最良解のエネルギーは理想値+2.1程度でした。

ArminSamplerのGPU版で求解

こちらもサンプリングが10秒程度で終わるようにパラメータを調整しています。ArminSampler() のGPUモードではサンプリング数を増やしても計算時間があまり伸びません。shots=15000まで上げました。

#サンプラー選択
solver = sampler.ArminSampler(seed=None, mode='GPU')

#サンプリング
result = solver.run(qubo, shots=15000, T_num=8000, show=True)
offset=30980.0
MODE: GPU
DEVICE: cuda:0
11.03 s
Energy=-30980.0, Occurrence=1
[[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1]
 [0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0]
 [0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0]]
[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
機械0 タスク [13 16 18 27] 時間 74.0
機械1 タスク [ 1  2 10 12 21 28] 時間 74.0
機械2 タスク [ 4  8 20 23 25 32 36] 時間 74.0
機械3 タスク [ 5 19 26 31 33 34] 時間 74.0
機械4 タスク [ 3  6  7  9 11 14 15 17 22 24 29 30 35] 時間 74.0

10回中1回だけ大域解が見つかりました。(え)

スコア比較

各10回実行した最良解のエネルギーをグラフにまとめました。いずれもサンプリングの実行時間を10秒程度で揃えています。-30980が大域解です。

GPU版の威力と安定感がよく分かります!

おわりに

こうなると良いGPUが欲しくなりますね。ご乱のスポンサーをお待ちしています!

タイトルとURLをコピーしました