108 Views
November 29, 21
スライド概要
製造業における組合せ問題最適化問題の事例やFixstars Amplifyを活用したソリューションのデモを紹介する無料のセミナーを開催します。
Fixstars Amplifyについてはウェブサイトをご覧ください。
https://amplify.fixstars.com/ja/
フィックスターズは、コンピュータの性能を最大限に引き出すソフトウェア開発のスペシャリストです。車載、産業機器、金融、医療など、幅広い分野での開発経験があります。また、ディープラーニングや機械学習などの最先端技術にも力を入れています。 並列化や最適化技術を駆使して、マルチコアCPU、GPU、FPGA、量子アニーリングマシンなど、さまざまなハードウェアでソフトウェアを高速化するサービスを提供しています。さらに、長年の経験から培ったハードウェアの知識と最適化ノウハウを活かし、高精度で高性能なアルゴリズムの開発も行っています。 ・開催セミナー一覧:https://www.fixstars.com/ja/seminar ・技術ブログ :https://proc-cpuinfo.fixstars.com/
Fixstars Corporation www.fixstars.com 製造業向け量子コンピュータ時代のDXセミナー Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 本日のゴール 製造業に組合せ最適化問題がたくさんあることを知る 組合せ最適化問題を解くためには、問題を数式化する必要があることを理解する 中でも、最適化(最大化 or 最小化)したい対象を特定することが出発点であることを理解 する 皆様の身近な課題を、組合せ最適化問題として捉えることができるか考えてみる → 課題の抽出、問題の数式化など 私どもでお手伝いいたしますので お気軽にお声がけください! 2 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 本日のAgenda •会社紹介(5分) •組合せ最適化・イジングマシンの紹介(5分) •Fixstars Amplifyの紹介(10分) •問題分類及び最適化問題検討のフレームワークについて(10分) •製造業における組合せ最適問題の事例の紹介(10分) •製造業におけるAmplify活用デモ(15分) a. ロットまとめ b. シフト割付 ご質問がある場合は、その都度聞いて下さい! Copyright © Fixstars Group 3
Fixstars Corporation www.fixstars.com 会社紹介 Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com フィックスターズの概要 概要 グループ体制 株式会社フィックスターズ 会社名 株式会社フィックスターズ 本社所在地 東京都港区芝浦 3-1-1 msb Tamachi 田町ステーションタワー N 28階 設立 2002年8月 上場区分 Fixstars Solutions, Inc. 当社完全子会社 米国での営業及び開発を担当 株式会社Fixstars Autonomous Technologies 株式会社ネクスティ エレクトロニクスとの JV 自動運転向けソフトウェア開発に特化 東証一部(証券コード: 3687) 株式会社Fixstars Amplify 代表取締役社長 三木 聡 資本金 5億5,341万円(2020年9月現在) 社員数(連結) 2021/11/1~ 当社完全子会社 量子コンピューティング関連のサービス事業を担当 株式会社Sider 当社完全子会社 SaaS事業 ”Sider”を担当 253名(2020年9月現在) 株式会社Smart Opinion キオクシア株式会社 主なお客様 株式会社ネクスティ エレクトロニクス 株式会社日立製作所 プロディジーメディカル株式会社との JV 乳がん AI画像診断支援事業を担当 オスカーテクノロジー株式会社 キヤノン株式会社 連結子会社 ソフトウェア自動並列化サービスを提供 Copyright © Fixstars Group 5
Fixstars Corporation www.fixstars.com フィックスターズの強み フィックスターズは、コンピュータの性能を最大限に引き出し大量データの高速処理を実現する、 高速化のエキスパート集団です。 低レイヤ ソフトウェア技術 アルゴリズム 実装力 各産業・研究 分野の知見 6 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 量子アニーリング・イジングマシンと組 合せ最適化問題 Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 量子アニーリング・イジングマシンと組合せ最適化問題 量子アニーリング・イジングマシン ⇒ 組合せ最適化問題を解くための専用マシン 膨大な選択肢から、制約条件を満たし、ベストな選択肢を探索する(組合せ最適化問題) スケジューリング 配送計画 スマートシティー 参考: 慶應義塾大学 田中宗 准教授 「量子コンピュータ最前線とイジングマシンの可能性」 Copyright © Fixstars Group 集積回路設計 8
Fixstars Corporation www.fixstars.com 組合せ最適化問題は統一的なフレームワークで解くことができる 問題設定 膨大な解候補(組合せ)から最適解を選ぶ ・解候補一つ一つの計算は可能 ・候補数が膨大ですべての解候補を計算できない 組合せ最適化問題の例 バイキングで最も安く 必要な栄養が取れる組合せは? 目的関数: これを最小化(最大化)する解が最適 定式化 制約条件: 解が必ず満たすべき条件 決定変数: 解が必ず満たすべき条件 目的関数: 合計金額(最小化) 数式で表現 実装 解を取得 数式をPythonのプログラムで記述 制約条件: 炭水化物:300g以上 タンパク質:150g以上 脂質:50g以上 最適メニュー Amplifyが最適解を探索 ごはん:380g 焼き魚:140g 金 額:870円 9 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 製造業における品質管理の4M Man 本日の事例やデ モの対象 4Mとは Machine Method Material 10 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 最も効率的な生産スケジュールは? 問題設定 定式化 製品製造工程順序の最適化 目的関数:製造完了時間(最小化) ・段取り時間、納期、稼動率などを考慮 実装 解を取得 デモパートで 詳しくご紹介 制約条件:機械数や製造可能な製品の制約 ・従来技術だと数時間かかることも ・Amplifyがより高速に妥当な解を提示 11 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 最も効率的な作業員のシフトは? 問題設定 チーム編成とタスク割り当て 目的関数:業務要求の満足度最適化 定式化 実装 解を取得 ・スキルや業務時間平滑化、個人の希望などの考慮 デモパートで 詳しくご紹介 制約条件:チーム人数や一人1タスクなどの制約 ・従来、ホワイトボードを使い、朝・夕30分程度ずつかけて作成 ・Amplifyが10秒で推薦配置を提示 12 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 最も効率的な部材や製品の搬送方法は? 問題設定 定式化 AGV(無人搬送車)の待ち時間を最小化するリアルタイム経路選択 目的関数:各AGVの次の一定時間の 待ち時間(最小化) 制約条件:各AGVが衝突しない、など 実装 解を取得 ・Amplifyが他のAGVの行動を考慮し、次の最適動作をリアルタイムに指示 ・最短経路だけでなく、迂回・交差点制御なども実現 13 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Fixstars Amplify のご紹介 Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 量子コンピュータとその周辺 1. 量子コンピュータ 2. イジングマシン 量子ゲート方式 二値二次多項式模型 古典汎用コンピュータの上位互換。 量子力学の重ね合わせ状態を制御 する量子ゲートを操作し、特定の問 題を汎用的かつ高速に処理する。 二次の多変数多項式で表される目的 関数の最適化問題 (QUBO) を扱う 専用マシン。変数は0,1または±1。 統計物理学におけるイジング模型 (磁性体の性質を表す模型) に由来。 様々な実装により実現されている。 1 2 量子コンピュータ イジングマシン IBM/Google/Rigetti/IonQ 富士通/日立/東芝/Fixstars 3 量子 アニーリング D-Wave/NEC 3. 式 量子アニーリング方 量子焼きなまし法 イジングマシンの一種であり、量子焼き なまし法の原理に基づいて動作する。 量子イジング模型を物理的に搭載した プロセッサで実現する。 自然計算により低エネルギー状態が Copyright © Fixstars Group 出力される。 Amplify AE 15
Fixstars Corporation www.fixstars.com クラウドサービス :Fixstars Amplify 様々な量子コンピュータ・イジングマシンに対応したアプリケーションを開発出来る、クラウドプラットフォームです。 量子コンピューティング時代を見据え、シンプルで効率的な開発環境の提供を目指しています。 サービス概要 主な特長 様々なマシンに対応 各社が提供する量子アニーリング・イジングマシンをFixstars Amplifyから利用することが出来ます。 シンプルで効率的なアプリ開発 複雑で専門性の高いプロセスを自動化し、効率的にマシンを 使うための学習コストを、圧倒的に低くします。 PoCから実問題まで対応 大規模問題の入力と高速実行が可能で、PoCや実問題を視野 に入れたアプリケーション開発が行えます。 すぐに開発を開始可能 適用分野 (一例) ・・・ 金融 物流 開発環境と実行環境がセットで提供されるため、すぐに開発を 開始することが出来ます。 ライフサイエンス 16 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 二次計画問題 • 最適化問題の分類 • 組合せ最適化問題 • 決定変数が離散値 (整数など) • • • 0-1整数計画問題 (決定変数が二値) 連続最適化問題 • • • 整数計画問題 (決定変数が整数) 決定変数が連続値 (実数など) 量子アニーリング・イジングマシン QUBO模型 (0-1整数二次計画問題) Q uadratic 二次形式 Unconstrained 制約条件なし Binary 0-1整数 (二値) Optimization 計画 決定変数 (出力・変数) 評価値 (目的関数) 問題設定 (入力・定数) Copyright © Fixstars Group 17
Fixstars Corporation www.fixstars.com イジングマシンの実行手順 1. 数理モデル検討 解きたい課題の「 目的関数」「決定変数」「制約条件」を検討する 2. QUBO定式化 「 2値決定変数+二次形式」で「目的関数」と「決定変数」を記述 (変換) する 「制約条件」は直接扱えないので「ペナルティ関数」で表現する (論理) 3. QUBO定式化 (物理) 各マシンの仕様や制限に準拠した形式にQUBO模型を変換する (例: 二次項に制約がある場合は「グラフマイナー埋め込み」問題を解く) 4. 入力データの準備 各マシンのSDKやAPI仕様に合わせてQUBO模型 (物理) をデータ化する 5. マシンの実行 マシンを実行して出力の変数値やエネルギー値(コスト値)を解析する 上記の逆の手順を辿り解きたい課題の「 決定変数」を解釈する SWによる 支援と自動化 18 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Fixstars Amplify の特長 – いつでも 開発環境と実行環境がセットのため すぐにプログラミングと実行が出来る – 誰でも ハードウェアや専門的な知識が不要 無料で開発がスタート可能 – 高速に 10万ビットクラスの大規模問題の 高速処理と高速実行が可能 – あらゆる 一般に公開されている全てのイジング マシンを利用可能 19 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Fixstars Amplify クラウドの構成 アプリケーション 組合せ最適化問題を含むアプリケーションは Amplify SDK を 用いることで効率的かつ簡便に組合せ最適化の定式化が可能 研究・開発ではAmplifyクラウドは無償提供されるため直ぐに開 発をスタートできる Amplify SDK 組合せ最適化問題の定式化やマシンを高度に操るため の最先端の技術や知見をライブラリ化したシンプルなイン ターフェースを提供 専門知識が不要で量子アニーリングイジングマシンを用 いた最適化エンジンの開発に取り組める 量子アニーリング・ イジングマシン (Amplify AE) Amplify クラウドが量子アニーリングマシン・イジングマシ ンの大規模実行環境を提供 Amplify SDK で書かれた最適化エンジンは 他社製も含め全ての商用イジングマシンで実行可能 20 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify の対応マシン 21 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Fixstars Amplifyによる課題解決 ■ イジングマシンのための革新的な開発環境 簡単 多くのマシンに対応 ✔ SDKをインストールするだけです ぐに使える (pip install amplify) ✔ ハードウェアの専門知識不要で アプリケーションが開発できる ✔ 進化の早いマシンの発展に追従 すべての量子アニーリング/イジ ングマシンに対応 ✔ 10万ビット級のアニーリングマシ ン実行環境が利用可能 始めやすい ✔ 研究・開発用途には開発環境と 実行環境が無償で利用可能 ✔ 多くのチュートリアル、サンプル コードを整備・拡充 多くの人が始めやすい開発プラットフォームを無料で提供 https://amplify.fixstars.com Copyright © Fixstars Group 22
Fixstars Corporation www.fixstars.com Fixstars Amplify の技術 Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify SDKのワークフロー ■ 従来のプログラミングワークフローとの比較 実行方法 24 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify SDKによるシンプルプログラミング 数独を解くサンプルアプリ SDKなし 最適化しても 200行以上 富士通・デジタルアニーラの設定用コード SDKあり 30行程度 SDKなし 59行 SDKあり 1行 日立CMOSアニーリングマシンの設定用コード SDKなし 183行 SDKあり 1行 25 出典: Wikipdia Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify による巡回セールスマン問題の実装例 26 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify Annealing Engine • NVIDIA GPU V100/A100 で動作 • 独自の並列化シミュレーテッドアニーリングアルゴリズム • WEB経由で計算機能を提供 • Amplify SDK の実装を直ぐに実行可能 • 社会課題への取り組み・PoC・検証が加速 • 商用マシンでは最大規模かつ最高速レベル • 64Kビット (全結合) / 100Kビット超 (疎結合) Amplify Cloud 27 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify Annealing Engine ■ 実問題やPoCを視野に入れたアプリケーション開発にも対応 キンググラフ 28 研究・開発利用において無償提供 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Amplify 標準提供マシン 最先端の並列化技術 最先端の量子技術 出典:https://www.nvidia.com/ja-jp/data-center/dgx-2/ NVIDIA A100/V100 最大10万ビット以上 D-Wave Advantage 5000量子ビット 29 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 製造業におけるAmplify活用デモ ・ロットまとめ ・シフト割付 Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com ロットまとめ問題 【問題】10台の製造装置を使い4種の製品を合計100ロット作りたい。製造する品種を変更するには、部品 の交換するための段取り時間が必要。全ロットの生産が完了するまでの時間を最短にするには、どの製 品を、どの製造装置で、どういう順番で製造するのが最適か 装置0 製造装置 装置1 A B A B A B A 装置9 B 段取り 時間 段取り 時間 C D A 製品:4品種 100個 品種 ロット数 処理時間 (時間/ロット) A 30 2時間 B 10 3時間 C 40 1時間 D 20 1時間 B 10台 段取り 時間 1020通りの組合せ! 段取り時間 A→A 0時間 B→A 2時間 C→A 1時間 D→A 2時間 同種のロットをできるだけまとめて生産したら良さそ うだけど、段取り時間もあるし、どうするのが一番い いんだろう・・・ Copyright © Fixstars Group 31
Fixstars Corporation www.fixstars.com ロットまとめ問題 問題設定 定式化 段取り時間を含めた総生産時間を最小化する 目的関数: 制約条件: 実装 生産時間と段取りの総生産時間の最小化 ① 各装置が同時に作れるのは1品種のみ ② 各品種の合計生産数が予定数通り 19時間で 生産完了 解を取得 Amplifyが 10秒で計 算 32 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com ロットまとめ問題 問題設定 定式化 実装 解を取得 Pythonによる実装イメージ #目的関数 for m in range(num_mac): for l in range(lmax): cost += coef * (lmax-l) * (t_proc*mac[m][l]).sum() # 処理時間 if (l>0): for fr in range(num_type): for to in range(num_type): cost += coef * (lmax-l) * ( t_switch[fr][to] * mac[m][l-1][fr] * mac[m][l][to] # 段取り時間 ) # 品種の1hot制約 for m in range(num_mac): for l in range(lmax): model += one_hot(mac[m][l]) # 品種の合計数制約 for t in range(num_type-1): # dummy品種は除く model += equal_to(sum_poly([mac[m][l][t] for m in range(num_mac) for l in range(lmax)]), num_lots[t]) 33 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 具体的な活用シーン 活用シーン1 活用シーン2 使う予定だったマシンが突然1台故障! ロットAの追加発注!今日中に納期回答を マシン数を減らして再計算 ロット数を増やして再計算 21時間で 生産完了 マシン9台、ロット100個 22時間で 生産完了 マシン10台、ロット120個 34 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 具体的な活用シーン 活用シーン3 活用シーン4 生産量増に伴いマシン増設検討 今月は注文が落ち着いているので稼働台数を減 らして省エネ マシンやロット数を増やして再計算 納期を守れる最小マシン数を計算 21時間で 生産完了 25時間で 生産完了 マシン12台、ロット150個 マシン5台、ロット55個 35 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com シフト割付 【問題】業務で求められる役割・役職・スキルと個人の能力や要求を考慮した最適シフトとは 業務要求 ・・ ・ マッチング 各従業員情報 ・・ ・ ・・ ・ 36 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com シフト割付 問題設定 各ラインの要求を満たすシフトの作成 定式化 目的関数: 複数の要求のバランス(充足率の平均の最大化、 分散の最小化、配置要求とのマッチングの最大化) 実装 制約条件: ① 従業員は同時に1ラインのみに配置可 ② 各ラインの要求管理職を配置することなど 解を取得 37 Copyright © Fixstars Group
Fixstars Corporation シフト割付の類似の実アプリの紹介 www.fixstars.com https://d1kg3huvzzdvtj.cloudfront.net/ 38 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Fixstars Amplify: オンラインデモ & チュートリアルページ https://amplify.fixstars.com/ja/demo 39 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com Q&A Copyright © Fixstars Group Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com フィックスターズでは仲間を募集しています! さまざまな専門性を持つエンジニアを募集しています。 詳細は https://www.fixstars.com/ja/recruit/ まで 41 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com AGVの渋滞回避の実装イメージ 目的関数→ 制約条件 累積待ち時間 [秒] 完了タスク数 [個] 累積待ち時間 経過時間 [秒] 経過時間 [秒] Amplify最適化 78s 場当たり的 86s 42 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 43 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 44 Copyright © Fixstars Group
Fixstars Corporation www.fixstars.com 45 Copyright © Fixstars Group