製造業向けワークショップ量子コンピュータ時代のDXセミナー～工場内搬送経路最適化の中身を覗いてみよう～（2022/08/24）

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 本日のAgenda 第一部 15:00-15:45 ⮚ はじめに ⮚ 会社紹介 ⮚ 組合せ最適化・イジングマシン及び製造業における事例の紹介 ⮚ Fixstars Amplifyの紹介第二部 15:50-17:00 ⮚ Amplify活用のワークショップ • 経路最適化編 Copyright © Fixstars Group 2

3.

4.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 本セミナーのゴール ⮚ 製造業に組合せ最適化問題がたくさんあることを知る ⮚ 組合せ最適化問題を解くためのフレームワークや、問題設定の考え方、目的関数や制約条件の定式化のポイントを理解する ⮚ 最適生産計画作成のサンプルコードを活用しながら、実際に量子アニーリング・イジングマシンを動かしてみることで、実問題への適用の足掛かりを得る課題の抽出、問題の数式化、プログラムの実装などお客様のステージやご要望に合わせて柔軟にお手伝いいたしますので、お気軽にお声がけください！ Copyright © Fixstars Group 4

5.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (1) • ご自身のPC (ブラウザ上) でPythonプログラミングを行います。Google colaboratoryを使うので、事前にログイン出来ることを確認をお願いします (Googleアカウントが必要です) • https://colab.research.google.com/ • Fixstars Amplify のトークンを取得済みか確認をお願いします。まだの人は Fixstars Amplifyホームページのサインアップよりユーザ登録の上、無料トークンの取得をお願いします (1分で終わります) • https://amplify.fixstars.com/ja/register Copyright © Fixstars Group 5

6.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (2) • お持ちのAmplifyのトークンを用いて、以下のURLにあるサンプルコードが動くか確認をお願いします。サンプルコードは閲覧のみ可能ですので、「ドライブにコピー」の上、ご自身のトークンを入力し、Shift+Enterで実行をしてください (警告が出る場合がありますが、「このまま実行」を選択下さい) • https://colab.research.google.com/drive/1evYBKqKfVrEzrQOa-SWwciROfvqjL8qm?usp=sharing この部分に、ご自身のトークン番号(32桁)を入力の上、Shift+Enterで実行下さい。ご自身のトークン番号は、Amplify HPよりご確認いただけます • ご自身のトークンを入力の上、以下の結果が出力されればOKです Copyright © Fixstars Group 6

https://colab.research.google.com/drive/1evYBKqKfVrEzrQOa-SWwciROfvqjL8qm?usp=sharing

7.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (3) • ワークショップで使うサンプルコードを以下のURLより取得して下さい • それぞれのサンプルコードにご自身のトークンを入力いただく必要があります。それぞれのサンプルコードを「ドライブにコピー」の上、トークンを入力し実行して下さい Step1 https://colab.research.google.com/drive/1nu_X8RufFbc4wzRlyxj8M5FlGorkcKIE?usp=sharing Step2 https://colab.research.google.com/drive/1ssgrvSQ7cZrLhGzmaLZUJRYu2JJeSOiv?usp=sharing Step3 https://colab.research.google.com/drive/1SlYCT_eS5abwzl_rldM-Vf9g2s-KihRp?usp=sharing 質問は随時ZoomのチャットかQ&Aでお願いします対応可能なメンバーが対応いたします Copyright © Fixstars Group 7

8.

9.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com フィックスターズの概要概要グループ体制株式会社フィックスターズ会社名株式会社フィックスターズ本社所在地東京都港区芝浦3-1-1 msb Tamachi 田町ステーションタワーN 28階設立 2002年8月上場区分 Fixstars Solutions, Inc. 当社完全子会社米国での営業及び開発株式会社Fixstars Autonomous Technologies 東証プライム（証券コード：3687）株式会社ネクスティエレクトロニクスとのJV 自動運転向けソフトウェア開発株式会社Fixstars Amplify 当社完全子会社量子コンピューティングのクラウド事業を運営代表取締役社長三木資本金 5億5,446万円（2021年9月現在）社員数（連結） 2021/10/1 設立聡株式会社Sider 当社完全子会社開発支援SaaS「Sider」を運営 258名（2021年9月現在）株式会社Smart Opinion キオクシア株式会社主なお客様株式会社ネクスティエレクトロニクス株式会社日立製作所キヤノン株式会社当社連結子会社乳がんAI画像診断支援事業を運営オスカーテクノロジー株式会社当社連結子会社ソフトウェア自動並列化サービスを提供 Copyright © Fixstars Group 9

10.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ソフトウェア高速化サービス (概要) • お客様にソースコードをご提供いただき、 • 最適化やアルゴリズムの改良を施して高速化してお返ししますオリジナルソースコードのご提供当社高速化したソースコードコンサルティング高速化お客様サポート性能評価アルゴリズムの改良・開発レポートやコードへのQ&A ボトルネックの特定ハードウェアへの最適化実製品への組込み支援レポート作成 Copyright © Fixstars Group 10

11.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com フィックスターズの強みフィックスターズは、コンピュータの性能を最大限に引き出し大量データの高速処理を実現する、高速化のエキスパート集団です。低レイヤソフトウェア技術アルゴリズム実装力 Copyright © Fixstars Group 各産業・研究分野の知見 11

12.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com フィックスターズの量子技術への取り組み次世代技術を先取りし今ある課題の解決を目指す 2018年 NEDOのプロジェクトに採択「イジングマシン共通ソフトウェア基盤の研究開発」 2019年 SIPの研究開発に参画「光・量子を活用した Society 5.0実現化技術：光電子情報処理」 2021年 • 2月：量子アニーリングクラウドサービス「Fixstars Amplify」提供開始 • 10月：子会社Fixstars Amplifyを設立 • 11月：Q-STAR 量子技術による新産業創出協議会に特別会員として加入 2017年日本で初めて D-Wave Systems 社と提携 Copyright © Fixstars Group 12

13.

14.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 量子アニーリング・イジングマシンと組合せ最適化問題量子アニーリング・イジングマシン ⇒ 組合せ最適化問題を解くための専用マシン膨大な選択肢から、制約条件を満たし、ベストな選択肢を探索する（組合せ最適化問題）スケジューリング配送計画スマートシティー集積回路設計参考: 慶應義塾大学田中宗准教授「量子コンピュータ最前線とイジングマシンの可能性」 Copyright © Fixstars Group 14

15.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 組合せ最適化問題は統一的なフレームワークで解くことができる問題設定膨大な解候補（組合せ）から最適解を選ぶ組合せ最適化問題の例・解候補一つ一つの計算は可能・候補数が膨大ですべての解候補を計算できないバイキングで最も安く必要な栄養が取れる組合せは？ (1 0g単位) 定式化解を取得タンパク質脂質金額目的関数: これを最小化（最大化）する解が最適 8g 1g 1g 10円制約条件: 解が必ず満たすべき条件パン 7g 1g 2g 12円ハンバーグ 1g 5g 4g 50円焼き魚 1g 8g 1g 35円数式で表現実装炭水化物ごはん目的関数: 合計金額（最小化）数式をPythonのプログラムで記述 Amplifyが最適解を探索 Copyright © Fixstars Group 制約条件: 炭水化物：300g以上タンパク質：150g以上脂質：50g以上最適メニューごはん：380g 焼き魚：140g 金額：870円 15

16.

17.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 組合せ最適化の取り組み事例シフト作成自動化生産計画最適化経路指示リアルタイム制御人の直観で時間をかけて行っていた生産ラインや物流倉庫の業務シフト作成を、スキルや勤務時間などの条件をもとに最適化します製造工場の設備の利用割り当て (ジョブショップスケジューリング) を、納期や段取り時間などを考慮して最適化します倉庫を走行する多数の搬送ロボット (AGV) が効率よく動作するよう、最適経路だけでなく迂回や交差点での待機などリアルタイムに指示します 9/22, 10/20のセミナーのテーマ 1/26, 2/16のセミナーのテーマ 11/17, 12/15のセミナーのテーマ Copyright © Fixstars Group 17

18.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 最も効率的な作業員のシフトは？問題設定定式化チーム編成とタスク割り当て目的関数：業務要求の満足度最適化・スキルや業務時間平滑化、個人の希望などの考慮実装解を取得制約条件：チーム人数や一人1タスクなどの制約・従来、ホワイトボードを使い、朝・夕30分程度ずつかけて作成・Amplifyが10秒で推薦配置を提示 Copyright © Fixstars Group 18

19.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 最も効率的な生産スケジュールは？問題設定定式化製品製造工程順序の最適化目的関数：製造完了時間（最小化）・段取り時間、納期、稼動率などを考慮実装解を取得制約条件：機械数や製造可能な製品の制約・従来技術だと数時間かかることも・Amplifyがより高速に妥当な解を提示 Copyright © Fixstars Group 19

20.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 電気機器製造メーカー A社様複数の製品事業部から様々なプリント基板の注文を受け、生産を行う部門段取り時間課題生産する基板に応じて製造装置の部品や材料を交換する「段取り時間」が必要。段取り時間を考慮した効率的な生産スケジュールを作成したい従来は、専任者が、一日数回・毎回数十分かけて経験に基づいてスケジュールを作成。更なる生産性向上やノウハウ継承のため、生産スケジュール作成の自動化に着手装置1 A A 装置2 B B B B B 段取り時間装置x C E B 段取り時間 E D 生産スケジュール作成の時間・コストの大幅な削減！効果 (一日あたり数時間 → 数分) 段取りのための製造装置の停止回数の削減！ (10%以上削減) 最適化未経験のご担当者様1人がプログラム試作開始から約1～2ヵ月間取り組んでこの効果を実現現在は試作段階で、実運用に向けてモデルを改良中！次期フェーズでは、Amplify の活用領域の拡大を検討中！ Copyright © Fixstars Group 20

21.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 最も効率的な部材や製品の搬送方法は？問題設定定式化実装解を取得 AGV（無人搬送車）の待ち時間を最小化するリアルタイム経路選択目的関数：各AGVの次の一定時間の待ち時間（最小化）制約条件：各AGVが衝突しない、など・Amplifyが他のAGVの行動を考慮し、次の最適動作をリアルタイムに指示・最短経路だけでなく、迂回・交差点制御なども実現 Copyright © Fixstars Group 21

22.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Fixstars Amplify: メディア掲載 https://amplify.fixstars.com/ja/news/media Software Design 「はじめての量子プログラミング体験」 Interface 「Pythonで体験！量子コンピュータ」（2021年6月号～2022年1月号まで連載）（2022年6月号） Copyright © Fixstars Group 22

https://amplify.fixstars.com/ja/news/media

23.

24.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 量子コンピュータとその周辺 2. ン 1. 量子コンピュータ量子ゲート方式古典汎用コンピュータの上位互換。量子力学の重ね合わせ状態を制御する量子ゲートを操作し、特定の問題を汎用的かつ高速に処理する。イジングマシ二値二次多項式模型 1 2 量子コンピュータイジングマシン IBM/Google/Rigetti/IonQ 富士通/日立/東芝/Fixstars 3 二次の多変数多項式で表される目的関数の最適化問題 (QUBO) を扱う専用マシン。変数は0,1または±1。統計物理学におけるイジング模型 (磁性体の性質を表す模型) に由来。様々な実装により実現されている。量子アニーリング D-Wave/NEC 3. 式量子アニーリング方量子焼きなまし法イジングマシンの一種であり、量子焼きなまし法の原理に基づいて動作する。量子イジング模型を物理的に搭載したプロセッサで実現する。自然計算により低エネルギー状態が出力される。 Copyright © Fixstars Group Amplify AE 24

25.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com クラウドサービス：Fixstars Amplify 様々な量子コンピュータ・イジングマシンに対応したアプリケーションを開発出来る、クラウドプラットフォームです。量子コンピューティング時代を見据え、シンプルで効率的な開発環境の提供を目指しています。サービス概要主な特長様々なマシンに対応各社が提供する量子アニーリング・イジングマシンを Fixstars Amplifyから利用することが出来ます。シンプルで効率的なアプリ開発複雑で専門性の高いプロセスを自動化し、効率的にマシンを使うための学習コストを、圧倒的に低くします。 PoCから実問題まで対応大規模問題の入力と高速実行が可能で、PoCや実問題を視野に入れたアプリケーション開発が行えます。すぐに開発を開始可能適用分野 (一例) ・・・金融物流開発環境と実行環境がセットで提供されるため、すぐに開発を開始することが出来ます。ライフサイエンス Copyright © Fixstars Group 25

26.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 二次計画問題 • 最適化問題の分類 • 組合せ最適化問題 • 決定変数が離散値 (整数など) • • • 整数計画問題 (決定変数が整数) 0-1整数計画問題 (決定変数が二値) 連続最適化問題 • • • 量子アニーリング・イジングマシン Quadratic 二次形式 Unconstrained 制約条件なし Binary Optimization 0-1整数 (二値) 計画決定変数が連続値 (実数など) QUBO模型 (0-1整数二次計画問題) 𝑓 = ෍ 𝑄𝑖𝑗 𝑞𝑖 𝑞𝑗 + ෍ 𝑄𝑖𝑖 𝑞𝑖 𝑖<𝑗 𝑖 評価値 (目的関数) 𝑞𝑖 ∈ 0,1 or 𝑞𝑖 ∈ ±1 決定変数 (出力・変数) 問題設定 (入力・定数) Copyright © Fixstars Group 26

27.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com イジングマシンの実行手順 1. 数理モデル検討解きたい課題の「目的関数」「決定変数」「制約条件」を検討する 2. QUBO定式化「 2値決定変数+二次形式」で「目的関数」と「決定変数」を記述 (変換) する「制約条件」は直接扱えないので「ペナルティ関数」で表現する (論理) 3. QUBO定式化 (物理) 各マシンの仕様や制限に準拠した形式にQUBO模型を変換する (例: 二次項に制約がある場合は「グラフマイナー埋め込み」問題を解く) SWによる支援と自動化 4. 入力データの準備各マシンのSDKやAPI仕様に合わせてQUBO模型 (物理) をデータ化する 5. マシンの実行マシンを実行して出力の変数値やエネルギー値(コスト値)を解析する上記の逆の手順を辿り解きたい課題の「決定変数」を解釈する Copyright © Fixstars Group 27

28.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Fixstars Amplify の特長 – いつでも開発環境と実行環境がセットのためすぐにプログラミングと実行が出来る – 誰でもハードウェアや専門的な知識が不要無料で開発がスタート可能 – 高速に 26万ビットクラスの大規模問題の高速処理と高速実行が可能 – あらゆる一般に公開されている全てのイジングマシンを利用可能 Copyright © Fixstars Group 28

29.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Fixstars Amplify クラウドの構成アプリケーション組合せ最適化問題を含むアプリケーションは Amplify SDK を用いることで効率的かつ簡便に組合せ最適化の定式化が可能研究・開発ではAmplifyクラウドは無償提供されるため直ぐに開発をスタートできる Amplify SDK 組合せ最適化問題の定式化やマシンを高度に操るための最先端の技術や知見をライブラリ化したシンプルなインターフェースを提供専門知識が不要で量子アニーリングイジングマシンを用いた最適化エンジンの開発に取り組める量子アニーリング・イジングマシン (Amplify AE) Amplify クラウドが量子アニーリングマシン・イジングマシンの大規模実行環境を提供 Amplify SDK で書かれた最適化エンジンは他社製も含め全ての商用イジングマシンで実行可能 Copyright © Fixstars Group 29

30.

31.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Fixstars Amplifyによる課題解決 ■ イジングマシンのための革新的な開発環境簡単多くのマシンに対応始めやすい ✔SDKをインストールするだけですぐに使える (pip install amplify) ✔進化の早いマシンの発展に追従すべての量子アニーリング/ イジングマシンに対応 ✔研究・開発用途には開発環境と実行環境が無償で利用可能 ✔ハードウェアの専門知識不要でアプリケーションが開発できる ✔26万ビット級のアニーリングマシン実行環境が利用可能 ✔多くのチュートリアル、サンプルコードを整備・拡充多くの人が始めやすい開発プラットフォームを無料で提供 https://amplify.fixstars.com Copyright © Fixstars Group 31

https://amplify.fixstars.com

32.

33.

34.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Amplify SDKによるシンプルプログラミング数独を解くサンプルアプリ SDKなし最適化しても 200行以上富士通・デジタルアニーラの設定用コード SDKあり 30行程度 SDKなし 59行 SDKあり 1行日立CMOSアニーリングマシンの設定用コード SDKなし 183行 SDKあり 1行出典: Wikipdia Copyright © Fixstars Group 34

35.

36.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Amplify Annealing Engine • NVIDIA GPU V100/A100 で動作 • 独自の並列化シミュレーテッドアニーリングアルゴリズム • WEB経由で計算機能を提供 • Amplify SDK の実装を直ぐに実行可能 • 社会課題への取り組み・PoC・検証が加速 • 商用マシンでは最大規模かつ最高速レベル • 128Kビット (全結合) / 256Kビット超 (疎結合) Amplify Cloud Copyright © Fixstars Group 36

37.

38.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com Amplify 標準提供マシン最先端の並列化技術最先端の量子技術出典:https://www.nvidia.com/ja-jp/data-center/dgx-2/ NVIDIA A100/V100 最大26万ビット以上 D-Wave Advantage 5000量子ビット Copyright © Fixstars Group 38

39.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 料金のご案内 https://amplify.fixstars.com/ja/pricing Amplifyクラウド利用料開発支援サービス(個別見積り) New 利用料金無料 / 1ユーザー月額10万円 / 1ユーザーコンサル・システム開発等計算環境スモールミディアムサポートベーシックスタンダード研究・開発フェーズでの利用実運用フェーズでの利用数百万円～数千万円ラージ月額利用料定式化や実装を百万円～手厚く支援します！ Copyright © Fixstars Group 39

https://amplify.fixstars.com/ja/pricing

40.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com セミナー・トレーニングのご案内 https://amplify.fixstars.com/ja/news/seminar お客様の実際に課題解決をご支援するために、無料セミナーや有償トレーニングを提供しています無料セミナー・ワークショップビジネス向け、エンジニア向けに分けて毎月開催しています！本日企業向けプライベートトレーニングお客様が抱える実際の課題やデータを使ったカスタムメイドのトレーニングです！ Copyright © Fixstars Group 40

https://amplify.fixstars.com/ja/news/seminar

41.

42.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (1) • ご自身のPC (ブラウザ上) でPythonプログラミングを行います。Google colaboratoryを使うので、事前にログイン出来ることを確認をお願いします (Googleアカウントが必要です) • https://colab.research.google.com/ • Fixstars Amplify のトークンを取得済みか確認をお願いします。まだの人は Fixstars Amplifyホームページのサインアップよりユーザ登録の上、無料トークンの取得をお願いします (1分で終わります) • https://amplify.fixstars.com/ja/register Copyright © Fixstars Group 42

43.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (2) • お持ちのAmplifyのトークンを用いて、以下のURLにあるサンプルコードが動くか確認をお願いします。サンプルコードは閲覧のみ可能ですので、「ドライブにコピー」の上、ご自身のトークンを入力し、Shift+Enterで実行をしてください (警告が出る場合がありますが、「このまま実行」を選択下さい) • https://colab.research.google.com/drive/1evYBKqKfVrEzrQOa-SWwciROfvqjL8qm?usp=sharing この部分に、ご自身のトークン番号(32桁)を入力の上、Shift+Enterで実行下さい。ご自身のトークン番号は、Amplify HPよりご確認いただけます • ご自身のトークンを入力の上、以下の結果が出力されればOKです Copyright © Fixstars Group 43

https://colab.research.google.com/drive/1evYBKqKfVrEzrQOa-SWwciROfvqjL8qm?usp=sharing

44.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップの準備 (3) • ワークショップで使うサンプルコードを以下のURLより取得して下さい • それぞれのサンプルコードにご自身のトークンを入力いただく必要があります。それぞれのサンプルコードを「ドライブにコピー」の上、トークンを入力し実行して下さい Step1 https://colab.research.google.com/drive/1nu_X8RufFbc4wzRlyxj8M5FlGorkcKIE?usp=sharing Step2 https://colab.research.google.com/drive/1ssgrvSQ7cZrLhGzmaLZUJRYu2JJeSOiv?usp=sharing Step3 https://colab.research.google.com/drive/1SlYCT_eS5abwzl_rldM-Vf9g2s-KihRp?usp=sharing 質問は随時ZoomのチャットかQ&Aでお願いします対応可能なメンバーが対応いたします Copyright © Fixstars Group 44

45.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 搬送経路最適化一言に「経路最適化」と言っても、搬送ロボット (AGV) が運用されている環境や要件などは様々で、それぞれに対する問題設定や定式化は異なります状況や要件の例 • AGVが通過できる経路が定められている • AGVごとに稼働時間に制限がある • AGVごとに積載量に制約がある • 配達地ごとに要求される到着時間がある • AVGの衝突回避の制御が必要 • 運ぶ材料や部品によって各配達地で作業時間が異なる Copyright © Fixstars Group 45

46.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 搬送経路最適化【問題】工場内の4台のAGVを用いて、AGVの充電ステーションから20か所の搬送先に部品を届けるときの各搬送ロボットの走行距離の合計が最短になるような経路を求めます。尚、搬送ロボットをできるだけ平均的に利用したいため各AGVの搬送先は5か所とします充電ステーション Copyright © Fixstars Group 46

47.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com 搬送経路最適化【問題】工場内の4台のAGVを用いて、AGVの充電ステーションから20か所の搬送先に部品を届けるときの各搬送ロボットの走行距離の合計が最短になるような経路を求めます。尚、搬送ロボットをできるだけ平均的に利用したいため各AGVの搬送先は5か所とします全てを一度にやるのは難しいので、3つのステップに分けてアルゴリズムを作成します Step1 Step2 Step3 AGVを1台とし、制約を守るだけのアルゴリズムを作ります制約➀: 各順番で回れる訪問先 (充電ステーション+各搬送先) は1か所制約②: 各訪問先を回るのは1回のみ解の候補多数あり Step1に「総距離の最小化」という目的を追加し、複数の解の候補から目的を実現する解を求めるアルゴリズムを作ります AGVを4台に増やします。具体的には、Step2に対して以下の2つの変更を加えます変更➀: 決定変数の一部を0/1で固定変更➁: 制約条件の対象範囲を微調整 Copyright © Fixstars Group 47

48.

Fixstars Fixstars Corporation Corporation Step1 www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります Step1のサンプルコードのレビュー (尚、本ワークショップでは、最適化のコードにフォーカスするため、可視化のコードの詳細は割愛します) Copyright © Fixstars Group 48

49.

50.

Fixstars Fixstars Corporation Corporation Step1 www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります決定変数を準備計算して得られる解の例イジングマシンで最適な(0,1)の組合せを探す実装 BinaryPoly型 (21×21) = 441 [qbit] 1は訪問する、0はしないことを示す Copyright © Fixstars Group 充電ステーションから出発を示す充電ステーションの次は、訪問先 (20) に行くことを示す 50

51.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります Step1 制約の定式化制約1: 各順番で回れる訪問先は1つ → one_hot制約 20 ෍ 𝑞𝑛,𝑖 = 1 訪問先 (i) 順番(n) 𝑛 ∈ 0,1, ⋯ , 20 𝑖=0 制約2: 各訪問先を回るのは1回のみ → one_hot制約 0 1 2 ・・・ 20 0 1 0 0 ・・・ 0 one_hot 1 0 0 0 ・・・ 1 one_hot 0 0 one_hot 2 0 1 ・・・・・・・・・・・・・・・ 20 0 0 1 ・・・ 0 one_hot 20 ෍ 𝑞𝑛,𝑖 = 1 𝑖 ∈ 0,1, ⋯ , 20 one_hot one_hot one_hot one_hot 𝑛=0 Copyright © Fixstars Group 51

52.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります Step1 実装制約の定式化制約1:各順番で回れる訪問先は1つ → one_hot制約 20 ෍ 𝑞𝑛,𝑖 = 1 𝑛 ∈ 0,1, ⋯ , 20 𝑖=0 制約2: 各訪問先を回るのは1回のみ → one_hot制約 20 ෍ 𝑞𝑛,𝑖 = 1 𝑖 ∈ 0,1, ⋯ , 20 𝑛=0 Copyright © Fixstars Group 52

53.

Fixstars Fixstars Corporation Corporation Step1 www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります求解 Amplify AE • 先ほど作った constraints (制約) をmodelに格納してマシンに投げます • 制約条件だけを与えた場合、制約条件を満たす解を探してきてくれます無料版は1ジョブ10秒まで設定可。有料版では1分まで設定可能 Copyright © Fixstars Group 53

54.

Fixstars Fixstars Corporation Corporation Step1 www.fixstars.com www.fixstars.com AGVを1台とし、制約を守るだけのアルゴリズムを作ります結果の取得可視化充電ステーション各順番で回れる訪問先は1つ、各訪問先を回るのは1回のみ、という二つの制約を満たす経路を求めることができました。解の候補がたくさんある状況ですので、次のStepでは、目的を追加して解を絞ります Copyright © Fixstars Group 54

55.

56.

Fixstars Fixstars Corporation Corporation Step2 www.fixstars.com www.fixstars.com Step1に「総距離の最小化」という目的を追加し、複数の解の候補から目的を実現する解を求めるアルゴリズムを作ります目的関数の定式化 20 20 20 総距離の最小化 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = ෍ ෍ ෍ 𝑑𝑖,𝑗 ∙ 𝑞𝑛,𝑖 ∙ 𝑞𝑛+1,𝑗 𝑛=0 𝑖=0 𝑗=0 決定変数 x 決定変数 (2次) 計算のイメージ n=1のときi=20が1、n=2のときj=1が1なので、𝑑20,1 である1.17がdistanceに加算される各訪問先間の距離行列 (𝑑𝑖,𝑗 ) 決定変数 (𝑞𝑛,𝑖 , 𝑞𝑛+1,𝑗 ) 訪問先 (i) 順番(n) 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = Copyright © Fixstars Group 0 1 2 ・・・ 20 0 1 0 0 ・・・ 0 1 0 0 0 ・・・ 1 2 0 1 0 ・・・・・・・・・・・・・・・ 20 0 0 1 ・・・ 0 0 56

57.

Fixstars Fixstars Corporation Corporation Step2 www.fixstars.com www.fixstars.com Step1に「総距離の最小化」という目的を追加し、複数の解の候補から目的を実現する解を求めるアルゴリズムを作ります実装 : 追加 or 変更部分剰余を使って、最後の訪問先の次は0番目に戻るようにしていますイジングマシンは、制約を満たす中で、この distance (目的) を最小にする組合せを探します・・・【補足】制約条件には、目的関数の値を考慮して適切な値の重みを設定する必要があります。制約条件の取り扱いに関する詳細は、こちらのチュートリアルも合わせてご参照下さい https://amplify.fixstars.com/ja/demo Copyright © Fixstars Group 57

https://amplify.fixstars.com/ja/demo

58.

Fixstars Fixstars Corporation Corporation Step2 www.fixstars.com www.fixstars.com Step1に「総距離の最小化」という目的を追加し、複数の解の候補から目的を実現する解を求めるアルゴリズムを作ります充電ステーション 2つの制約を満たした上で、総距離を最小化する経路が求められるようになりました。次のStepでは、 AGVを4台に増やします Copyright © Fixstars Group 58

59.

Fixstars Fixstars Corporation Corporation Step3 www.fixstars.com www.fixstars.com AGVを4台に増やします。Step2に対して以下の2つの変更を加えます変更➀: 決定変数の一部を0/1で固定変更➁: 制約条件の対象範囲を微調整 Step3のサンプルコードのレビュー Copyright © Fixstars Group 59

60.

Fixstars Fixstars Corporation Corporation Step3 www.fixstars.com www.fixstars.com AGVを4台に増やします変更➀: 決定変数の一部を0/1で固定します。これにより、各AGVの搬送先を5か所に固定しています充電ステーションには、0番目、6番目、 12番目、18番目に訪問します (計4回訪問) 決定変数実装 : 追加 or 変更部分これらの中で合計が最短となる経路を探します・・・・・・・・・・・・・・・ Copyright © Fixstars Group 60

61.

Fixstars Fixstars Corporation Corporation Step3 www.fixstars.com www.fixstars.com AGVを4台に増やします変更➁: 制約条件の対象範囲を微調整します。訪問先 (0) である充電ステーションを、one_hot制約の対象から外します決定変数 one_hot制約対象外実装 Copyright © Fixstars Group : 追加 or 変更部分 61

62.

63.

Fixstars Fixstars Corporation Corporation www.fixstars.com www.fixstars.com ワークショップ: おさらい AGV1台の制約のみから始めて、目的を追加し、最終的には、4台のAGVそれぞれが5か所ずつ搬送し総走行距離が最短になるような経路を求めることができました！充電ステーション充電ステーション Copyright © Fixstars Group 63

64.

https://amplify.fixstars.com/ja/demo

65.

66.

製造業向けワークショップ量子コンピュータ時代のDXセミナー～工場内搬送経路最適化の中身を覗いてみよう～（2022/08/24）

株式会社フィックスターズ

関連スライド

Kaggleスコアアップセミナー～画像系コンペ入門[前編]（2023/08/02）

いまさら聞けない ARM を使ったNEONの基礎と活用事例（2021/08/05）

Kaggleスコアアップセミナー～画像系コンペ入門[後編]（2023/09/26）

いまさら聞けない！CUDA高速化入門～プログラミングモデルとアーキテクチャの解説、高速化の実践～（2021/10/29）

ROS2自律走行実現に向けて 2 ～次世代ロボット開発フレームワークROS2のビルドシステム徹底理解～（2022/11/30）

CUDA高速化セミナー vol.2 ～CUDAアーキテクチャの進化～（2022/06/23）

各ページのテキスト

製造業向けワークショップ 量子コンピュータ時代のDXセミナー ～工場内搬送経路最適化の中身を覗いてみよう～（2022/08/24）

株式会社フィックスターズ

関連スライド

Kaggleスコアアップセミナー～画像系コンペ入門[前編]（2023/08/02）

いまさら聞けない ARM を使ったNEONの基礎と活用事例（2021/08/05）

Kaggleスコアアップセミナー～画像系コンペ入門[後編]（2023/09/26）

いまさら聞けない！CUDA高速化入門 ～プログラミングモデルとアーキテクチャの解説、高速化の実践～（2021/10/29）

ROS2自律走行実現に向けて 2 ～次世代ロボット開発フレームワークROS2のビルドシステム徹底理解～（2022/11/30）

CUDA高速化セミナー vol.2 ～CUDAアーキテクチャの進化～（2022/06/23）

各ページのテキスト

製造業向けワークショップ量子コンピュータ時代のDXセミナー～工場内搬送経路最適化の中身を覗いてみよう～（2022/08/24）

いまさら聞けない！CUDA高速化入門～プログラミングモデルとアーキテクチャの解説、高速化の実践～（2021/10/29）