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

21-31. QUBOアニーリング実力テスト3(ジョブシーケンス問題)

やること

2024/09/07追記
試験問題の役割を終えたため解答の一例を公開しました。

「TYTAN」パッケージの開発・修正が進んでいます。

「qubomaster」認定試験用に実力テスト3を用意したので、腕に自信がある方は挑戦してみてください。認定試験として挑戦する場合は別途その指示に従ってください。

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.

筆者はチュートリアルコースを担当しています。

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

discordコミュニティもあるので気軽に質問できます。どなたでも参加できます → https://discord.gg/qT5etstPW8

チュートリアルを終えて試験に合格するとblueqat社が認定する「qubomaster」という資格が与えられます。qubomasterになると(blueqatサイト上で)認定バッジが付与され、有償業務の受託可能者リストに入ります。

blueqat club qubomaster認定試験に向けての各種ポイント | blueqat
blueqat clubというのがありまして、認定試験を受けて合格するとblueqat.com上でバッジがもらえます。現在量子コンピュータ業界は人材不足でして、かといって就職するほどの需要はないので、間をとってギグワークやパートタイム、単発仕事が多いです。 特に最初は初心者・初級者向けに量子コンピュータの説明...

おさらい

QUBOで設定できる条件式についてはこちらの記事にまとめてあります。暗記する必要はありませんが概要は把握しておくと良さそうです。

これまでのQUBOアニーリング系の記事はサイドバーの「カテゴリ一覧」→「量子コンピュータ」から絞れます。

量子コンピュータ
「量子コンピュータ」の記事一覧です。

実力テスト問題3

ポケモンセンターにはポケモンを回復させる「装置」が4台あります。装置には一度に一匹だけポケモンを入れることができ、1分毎にHPを1回復させます。

いま、ダメージを負ったポケモンが10匹搬送されてきました。彼らを4台の装置に適当に割り振って、できるだけ短い時間で全員を回復させたいです。全員が回復するまでにかかる最小の時間を求めてください。

▼各ポケモンのダメージ量(=回復すべきHP量)
17, 19, 25, 29, 30, 57, 60, 67, 97, 107

装置に入ったポケモンは全回復するまで取り出したり他の装置に移したりすることはできません。また、ポケモンの入れ替え時間はゼロとします。全員が回復するまでにかかる時間とは、一番遅いポケモンの回復が完了するまでの時間のことです。

(天の声)
「一番遅いポケモンの完了時間を最小にする」をそのまま定式化しようとするとけっこう難しいので、どうにかして言い換えることをおすすめします。

提出方法、注意事項など

解答は、そのまま実行するだけのpythonコードを「.py」または「.ipynb」のファイル形式で以下フォームから提出してください。すぐに自動返信メールが届きます。

メールアドレス(必須)

提出ファイル(必須)

Discordネームまたはニックネーム(必須)

※100KBまでの.py, .ipynbファイルのみ受け付けます
※受付完了メールが自動送信されます

▼注意事項

  • テキスト欄やコメントアウトにより最低限の説明や思考過程を含めてください
  • その際、チュートリアルの「おすすめコース」のどれと関連があるかにも触れてください
  • 説明のための図は必ずしも必要ありません
  • アニーリングのソルバーには必ずTYTANパッケージを使用してください
  • 必ずしも1回の実行で正解が得られる必要はなく、正解が得られることが期待できるコードであれば問題ありません

▼合格条件

  • QUBO条件式が妥当であること
  • 説明や思考過程が妥当であること
  • 十分な可読性のPythonコードであること
  • チュートリアル「おすすめコース」を把握していること

解答の一例(2024/09/07追記)

pip install tytan
from tytan import *
import numpy as np

#ダメージ
damage = [17, 19, 25, 29, 30, 57, 60, 67, 97, 107]

#量子ビット
q = symbols_list([10, 4], 'q{}_{}')
print(q)

#ワンホット
Hconst1 = 0
for i in range(10):
    Hconst1 += (sum(q[i, :]) - 1)**2

#各装置のかかる時間ができるだけ等しくなる(平均の127に近くなる、でもOK)
time1 = sum(damage * q[:, 0])
time2 = sum(damage * q[:, 1])
time3 = sum(damage * q[:, 2])
time4 = sum(damage * q[:, 3])

Hcost = 0
Hcost += (time1 - time2)**2
Hcost += (time2 - time3)**2
Hcost += (time3 - time4)**2
Hcost += (time4 - time1)**2

#解を絞るために最初のポケモンを装置1に固定
Hconst2 = (q[0, 0] - 1)**2

#合体
H = Hconst1 + Hconst2 + 0.0001*Hcost

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

#サンプラー選択
solver = sampler.ArminSampler()

#サンプリング
result = solver.run(qubo, shots=10000)

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

    #かかる時間
    print(sum(damage * arr[:, 0]), sum(damage * arr[:, 1]), sum(damage * arr[:, 2]), sum(damage * arr[:, 3]))

    if np.prod(np.sum(arr, axis=1)) != 1:
        print("WARNING: Not One-hot.")
[[q0_0 q0_1 q0_2 q0_3]
 [q1_0 q1_1 q1_2 q1_3]
 [q2_0 q2_1 q2_2 q2_3]
 [q3_0 q3_1 q3_2 q3_3]
 [q4_0 q4_1 q4_2 q4_3]
 [q5_0 q5_1 q5_2 q5_3]
 [q6_0 q6_1 q6_2 q6_3]
 [q7_0 q7_1 q7_2 q7_3]
 [q8_0 q8_1 q8_2 q8_3]
 [q9_0 q9_1 q9_2 q9_3]]
offset = 11.0
MODE: GPU
DEVICE: cuda:0
Energy -10.999600410461426, Occurrence 3
[[1 0 0 0]
 [0 0 1 0]
 [1 0 0 0]
 [1 0 0 0]
 [0 0 0 1]
 [1 0 0 0]
 [0 1 0 0]
 [0 1 0 0]
 [0 0 0 1]
 [0 0 1 0]]
128 127 126 127
Energy -10.99959945678711, Occurrence 5
[[1 0 0 0]
 [0 0 1 0]
 [1 0 0 0]
 [1 0 0 0]
 [0 1 0 0]
 [1 0 0 0]
 [0 0 0 1]
 [0 0 0 1]
 [0 1 0 0]
 [0 0 1 0]]
128 127 126 127
Energy -10.99940013885498, Occurrence 2
[[1 0 0 0]
 [0 1 0 0]
 [1 0 0 0]
 [1 0 0 0]
 [0 0 0 1]
 [1 0 0 0]
 [0 0 1 0]
 [0 0 1 0]
 [0 0 0 1]
 [0 1 0 0]]
128 126 127 127

かかる時間は [128, 127, 126, 127] より128分である。

<この問題のポイント>
いわゆるジョブシーケンス問題だが、素直にミニマックスを設定するのは難しいため、「4台にかかる時間ができるだけ等しくなる」と言い換えられるかがポイントである。また、制約条件とコストに十分な重み付けをしなければ正しい解が得られない。

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