最適化工学に芽吹く 進化計算 （メタヒューリスティック） 最適化工学技塾 塾長 豊橋技術科学大学 名誉教授 清水　良明 　　　　　　　２０１7.9.2７.

Presentation on theme: "最適化工学に芽吹く 進化計算 （メタヒューリスティック） 最適化工学技塾 塾長 豊橋技術科学大学 名誉教授 清水　良明 　　　　　　　２０１7.9.2７."— Presentation transcript:

1 最適化工学に芽吹く 進化計算 （メタヒューリスティック） 最適化工学技塾 塾長 豊橋技術科学大学 名誉教授 清水　良明 　　　　　　　２０１7.9.2７

2 最適化(Optimization)とは 大辞林 第三版 日本大百科全書(ニッポニカ)
　システム工学などで、ある目的に対し最も適切な計画を立て設計すること。また、そのような選択を行うこと 日本大百科全書(ニッポニカ) 目的に対してもっとも適切な方針・計画をたて、設計を行い、あるいはそうした選択を行うこと 工学一般において基本的課題となるもので、「システム工学」の3本の柱の一つの数学的体系（他の二つはシミュレーションとエバリュエーション）。 自然科学のみならず経済学など社会科学分野でも有用 合理的な最適決定・選択にはしかるべき「情報」を必要とすることから、情報科学的問題でもある。

3 （数理的）最適化(Optimization)とは
広範な問題解決のための 「魔法の学問」（成蹊大, 新村） 最適化問題 (x, f, X) で構成 ”Max f(x) subject to x∈X” ① x： 決定変数 （n次元） ② X： 制約条件（集合） ③ f： 評価（目的）関数 　 Players Theater 決めるものは どのような条件で Scenario 何を目指して

4 最適化問題の分類 1．制約式 の有る、無し、から (1) 制約条件なし問題 (2)制約条件付き問題
① 決定変数 ② 制約条件 ③ 評価関数 最適化問題の分類 1．制約式　　　の有る、無し、から (1) 制約条件なし問題 (Non-constrained optimization problem, NCP) (2)制約条件付き問題 (Constrained optimization problem, CP) 求解労力： NCP <<< CP

5 最適化問題の分類 ２．制約式 ，目的関数 の関数形から (1) 線形計画問題 ： 線形 (2) 二次計画問題 ： ２次形， 線形
① 決定変数 ② 制約条件 ③ 評価関数 最適化問題の分類 ２．制約式　　　，目的関数　　の関数形から (1) 線形計画問題 ： 線形 (Linear Programming problem,Linear Programs;LP) (2) 二次計画問題 ：　　　２次形，　　線形 (Quadratic Programming problem,QP) (3)非線形計画問題 ：　　　　　いずれか非線形 (Nonlinear Programming problem,NLP) 求解労力： LP << QP <<<< NLP

6 最適化問題の分類(Cont’d) ３. 決定変数 の性質から (1) 数理計画問題 ： 実数; x∈Rn
３. 決定変数　　の性質から (1) 数理計画問題 ： 実数; x∈Rn (Mathematical Programming problem, MP) (2) (全)整数計画問題 ： 整数; x∈In ((All) Integer Programming problem, IP) (3) 混合整数計画問題 ： 整数と実数 (Mixed-Integer Programming problem, MIP) (4) (全)0-1計画問題 ： Binary; x∈{0,1}n ((All) Zero-One Programming problem) (5) 0-1混合計画問題 ： Binaryと実数 (Mixed-Zero-One Programming problem) 組合せ的性質⇒求解労力ー飛躍的に増大

7 最適化問題の分類(Cont’d) ４. 目的関数 の質(A)や数(B)からの分類 (A-1) 単峰性目的最適化
(Single-peak problem) (A-2) 多峰性目的最適化 (Multi-peak problem) (B-1)単一目的最適化 ：　f(x) ; スカラー (Single-objective problem) (B-2) 多目的最適化 ：　 f(x) ;ベクトル (Multi-objective problem) 数学的評価で完結 主観的評価が必要 現実的意思決定手法

8 最適化問題の分類(Cont’d) ５. 不確定量に対する認識からの分類 (1) 考慮しない (2) 考慮する (a) 確定的変動問題
(Deterministic programming problem) (b) 統計的最適化問題 (Stochastic programming problem) (a)不確定パラメータに対する評価関数 　　　　の期待値を最適化 　 (b)制約条件が与えられた生起確率で 　　　　成立するという条件下での最適化 (c) ファジィ最適化問題 (Fuzzy programming problem) 不確定範囲が確定 分布が既知 範囲が不明瞭

9 最適化問題の分類(Cont’d) ６. 問題 の規模からの分類 使う計算機環境により相対的！ (1)大規模問題： n×m 大
６. 問題　　　　の規模からの分類 (1)大規模問題：　n×m 大 (Large-scale problem) (2)中規模問題：　n×m 中 (Medium-scale problem) (3)小規模問題：　n×m 小 (Small-scale problem) 分類1. から 6. の組合せ ⇒多数の種類の問題 全能者は いないよ！ ⇒対戦者ごとに工夫 最適化工学の出番 n：変数の数 m：制約式の数 使う計算機環境により相対的！　

10 産官学の ワークショップで議論 ２００4.6－２００6.3 こういう最適化があれば (^V^)
意思決定者の思考パターン・決定プロセスに即している 粒度の異なる問題（世界経済、DNA）を一元的に扱える あいまいな情報にも対応してロバストな解を導ける 最適化結果の提示方法に工夫がある 専門家でなくても利用できる 汎用解析ソフトとの連携が容易である 　・・・・・ 日本学術振興会第143委員会 　WS26最終報告書 (2008)

11 最適化工学とは (Optimization Engineering) 最適化を主たる要素技術として 技術・工学の現実的な問題解決を目指す
演者の造語！ 最適化工学とは (Optimization Engineering) 最適化を主たる要素技術として 技術・工学の現実的な問題解決を目指す マネジメント体系 まだ生まれたばかりです 2010年

12 最適化工学のスタンス 知のサイクル 現実 仮想 “共有”して認識 最適化 “みえる化”して共有 モデル データ シナリオ 意思決定支援 抽出
還元 12 “みえる化”して共有 最適化理念 最適化理論 最適化手法 最適化ソフト

13 最適化工学実践の６ステップ 問題定義 価値システム設計 問題定式化 システム分析 最適化 意思決定（事後解析） ～する Why What
How、Who

14 最適化工学の実行支援（IDEF0モデル）

15 多目的最適化(Multi-objective Optimization；
　　　　MOP)＝実用的／最適化工学の柱 ベクトル 多目的最適化問題 MOP： (x, f, X)で構成 ”Max {f1(x), f2(x), ‥, fN(x)} subject to x∈X” f ：複数の評価基準 価値観の多様化 多目的最適化問題の特徴 競合する - 義理と人情 競争する – ライバルの存在 共通の評価尺度なし 　　　　　- 美味い(主観的)-早い(時間)-安い(円) Sense of proportion あれもこれも よくしたい。 でも・・・・ 利益　　　　環境

16 多目的最適化の規範 ＝パレート最適性 ⇒ 合理的規範 代替案 A,B,Cの選好において 順序付け可能 (2) 順序付け不可能
　　＝パレート最適性 代替案　A,B,Cの選好において 順序付け可能 　　f1(A)＞f1 (C) f1(B)=f1(C) f2 (A) =f2 (C) f2(B) ＞f2 (C) Ａの方が美味くて 味は同程度だが、 値段は同じ Ｂの方が安い 第一目的の選好等高線 第二目的 (2) 順序付け不可能 f1(A) ＞f1(B) ： Ａは美味いが、Ｂより高い f2 (A)＜f2 (B) ： Ｂは安いが、Ａよりまずい 譲れない条件、あとは好み次第 ⇒ 合理的規範 　　パレート最適解集合 (稜線：p～q）

17 多目的最適化手法の分類 Increasing preference ● 選好最適解 パレート最適解集合 少なくとも一つは負けない！

18 「メタヒューリスティック」 メタとは多面的とか多義的といった接頭語
ヒューリスティックとは、発見的とか試行錯誤とか訳されている。もともとは、ギリシャ語のheuriskein(見つける)を語源としている。アルキメデスが入浴中に浮力の原理を発見したとき、裸で家に飛んで帰ったといわれる俗説中の叫び声、ユーレカ！(Eureka; I have found.)にも通じる。

19 メタヒューリスティック手法（単一目的） Particle Swarm Optimization (PSO) ‐群れの知
自然界の物理現象や生物の行動にヒント 多峰下で大域的で実用的な求解 近似最適化手法 遺伝アルゴリズム（GA）‐生物の進化 Differential Evolution (DE)‐実数版ＧＡ 焼なまし法（SA） ‐金属性能の改善 タブー探索法（TS) ‐チェックリストの活用 Particle Swarm Optimization (PSO) ‐群れの知 Ant Colony Optimization (ACO) ‐蟻のトレイル etc.

20 メタヒューリスティック手法の光と影 背景知識が不要(微分可能条件など） タフ（多峰性、大域性、組合せ問題など） 周辺ソフトとの併用が容易
理論的説明が困難 最適性の保証がない 入念なチューニングが必要 Schekel Schewelfel ベンチマーク問題例 Griewangk Goldstein & Price Branin Rosenbrock

21 メタヒューリスティック手法（多目的） Pareto Simulated Annealing (PSA)
2019/1/16 メタヒューリスティック手法（多目的） Pareto Simulated Annealing (PSA) Multi-Objective Particle Swarm Optimization (MOPSO) Multi-Objective Deferential Evolution (MODE) Non-dominated Sorting Genetic Algorithm II (NSGA II) Strength Pareto Evolutionary Algorithm II (SPEA II) etc. ○ Distance Distribution Number パレート解集合を求める 評価項目 数 距離 分布 最適化？ 解析では

22 生産システムの（組合せ）最適化問題 ロジステックス ロジステックス スケジューリング(作業の段取り） レイアウト(装置・施設の間取り）
ネスティング(部品の割り付け） 製品投入順序 発注方策 人員配置 etc. ロジステックス 次元の呪い（タフな計算）からは逃れられない。 ⇒工夫のしどころ

23 SFA: 1/17 ’14 （Yoshiaki Shimizu)
ロジスティクスとは 軍隊における物資調達・輸送活動またはその手段 ↓ 素材や製品などの物の流通を 経済的に合理化するための組織的なマネジメント ロジスティクスの対象範囲：グローバル化＋総合化 （グリーン／リ―バスロジステックス） 単に物の流れだけでは不充分 情報システムと密接に連動した 効率的な物流 協働的な物流 Co-opetition (Co-operation + Competition) SFA:　1/17 ’14　（Yoshiaki Shimizu) A mule column of the 2nd Punjabi Regiment carries supplies to the front line, Burma, 1944.

24 ロジスティックス最適化体系 社会のダイナミズムに連携する要請 階層をまたぐ課題 Strategic 基本手法 （戦略） 概念設計
（多くの研究例） 具体化問題 （少ない研究例） 詳細化問題 （かなりの研究例） 在庫（多期間、多品種） 求解能力（並列化） 種類・規模 多目的 マルチモーダル （ネットワーク設計） （配送・運用計画） 基本設計 （運用計画、 　　スケジュール） グリーンロジスティックス Strategic （戦略） Tactic （戦術） Operational （運用） 概念設計 不確定性 詳細設計 社会のダイナミズムに連携する要請 階層をまたぐ課題 時間窓 引取・積合わせ ロット分割 共同搬送 リスク 低炭素 生産計画連携 ﾘｱﾙﾀｲﾑ性 巡回配送 需給全体

25 [1] 戦略的問題 戦略問題 立地-配分 戦術問題 運用問題 古くから 多数の研究 計画期間 大規模問題の求解 組合せ数：２デポ数 長期計画
工場 　立地-配分 デポ 中期計画 戦術問題 立地ー配分 -VRP 立地 配分 運用問題 短期計画 Vehicle Routing Problem (VRP ) 顧客 ：工場， ：デポ， ：顧客， ：運搬車両

26 [2] 運用問題 運用問題 戦略問題 戦術問題 計画期間 多数の研究 巡回配送 長期計画 組合せ数：(顧客数 !)ルート数 中期計画
立地ー配分 -VRP 短期計画 運用問題 Vehicle Routing Problem (VRP ) 巡回配送 ：デポ， ：顧客， ：車両

27 コスト（燃費）やCO2排出量は距離と搭載重量に依存
VRPにおける輸送コストの勘定法 満杯運搬 空運搬 キロ基準 トンキロ (Weber) 基準 積載重量 [t] ×輸送距離 [km] 輸送距離 [km] × コスト係数　[1/(t・km)] × コスト係数　[1/km] IIE 2013, Istanbul, Turkey コスト（燃費）やCO2排出量は距離と搭載重量に依存 トンキロ (Weber) ベースの方が現実的 車両の自重も影響、運用固定費も必要 ⇒　Weber基準（修正）セービング法の開発

28 VRPのハイブリッド解法 キロベース（対称⇒同じ） トンキロベース（非対称⇒別々） 配達 直接引取 立寄り引取 配送・引取同時
種々の問題を同じ枠組みで トンキロベース（非対称⇒別々） キロベース（対称⇒同じ） 配達 直接引取 　　e.g., ゴミ収集 立寄り引取 　　e.g.,リユース 配送・引取同時 　　e.g., LPGボンベ 終 始 初期解 (修正セービング法) 収束? No Yes 更新 (修正タブーサーチ) 高い輸送効率 ⇒省エネルギ 大規模問題にも

29 [3] 戦術問題 戦術問題 限られた研究 計画期間 戦略問題 輸送費＝トンキロベース 不整合性の存在 立地ー配分 -VRP 運用問題
組合せ数：2デポ数 (顧客数 !)ルート数 長期計画 　立地-配分 　輸送費＝トンキロベース 統一した 輸送コスト評価 配分 中期計画 戦術問題 不整合性の存在 立地ー配分 -VRP 立地 短期計画 運用問題 VRP 　輸送費＝キロベース 巡回配送 ：工場， ：デポ， ：顧客， ：運搬車両

30 自然で整合的な統合が可能 ハイブリッドメタ解法の手順 Start End 総費用 戦略問題 の評価 運用問題 立地／配分 収束?
Plant Depot Customer End Yes 立地の更新(Modified tabu search) デポの初期立地 収束? No デポへの顧客の割り当て (Graph algorithm) 総費用 の評価 初期巡回路 (Modified saving method) 戦略問題 マルチデポ VRP 運用問題 Yes 巡回路の更新 (Modified tabu search) No 収束? ハイブリッドメタ解法の手順

31 現実的観点・社会的要請からの展開 リスク、不確定性 自然環境との共生 ３D地図データ A D C G B F E H I J K

32 事業継続計画 (BCP：Business Continuity Plan)
戦略的：施設倒壊リスク下でのアプローチ 事業継続計画 (BCP：Business Continuity Plan) 倒壊発生 March 2011, Japan July 2011,Thailand Before After 回復状態 100% 事業レベル Required Time Objectiveを短く 目標 目標 Time 継続的に維持 BCPでの回復曲線 BCPなしでの回復曲線 ネットワークの適切なバックアップを確保

33 レジリエント(頑強＋柔軟)な解の探求 倒壊確率下での 期待コストの最小化 デポ 顧客 RE1 RE RRS1 配送センタ RRS2 DC
平時・異常時の配送 顧客 DC1 DC2 URS RRS1 RRS2 RE1 RE2 RRS : 堅牢なデポ　（高価） URS : 脆弱なデポ　（安価） 異常時の配送 倒壊確率下での 期待コストの最小化 RE 配送センタ DC RS 平時の配送 デポ RE1: 常に堅牢なRRS1から供給 RE2: 平時は脆弱なURS, 異常時には堅牢なRRS2から供給

34 低炭素社会実現への 生産・消費者の共生ロジスッテクス エコ消費者が エコ生産者を育て エコ物流を作る どちらを選びますか CO2
　 生産・消費者の共生ロジスッテクス グリーン生産者 & 消費者 どちらを選びますか CO2 収集拠点 産地 (candidate) 小売店 エコ消費者が エコ生産者を育て エコ物流を作る \2/kg-CO2 \509 CO2: 2 kg Price: \505 サプライチェーン でのCO2 排出量 A県産（不揃）　　　　　　　　　　　　　　　　　B県産（定形）　 \510 CO2: 5 kg Price: \500 生産方法、輸送手段、輸送距離 生産方法

35 ３D巡回配送問題 ドローン配達 自動運転⇒ 上り、下り、平地で 3D地図データ 燃費は異なる Upper band ）θ -θ（
Lower band Upper band

36 知の創成に向けて 時代背景・現実を感じながら Remember 最適化工学のスタンス 知のサイクル 現実 仮想 “共有”して認識 最適化
モデル データ シナリオ 意思決定支援 現実 仮想 還元 抽出 最適化 “共有”して認識 “みえる化”して共有 知のサイクル 時代背景・現実を感じながら Remember 最適化工学のスタンス 36

37 経済・経営専攻でも 「最適化工学のすすめ」”おわりに”より抜粋
最適化が現実の意思決定支援技術としての地位を確立し，最適化工学として発展していくためには広いスコープが必要となると認識しているからである。 経済・経営専攻でも 化学，機械，電気，環境，建築など工学の各分野を専門としながら，最適化とその周辺技術を意思決定の道具として自在に操れる人材が育つことが最適化工学の目指すところである。欲をいえば社会科学や経済に関わる視点もそこでは求めたい。 若年層へのこうした学際的興味の広がりと彼らの資質の涵養がこれからのものづくり，ひいては工学に必要になると考えている。 本書がこうした試みの一つのたたき台になり，最適化工学の今後の発展につながることを願っている。

38 ハードOK! CPLEX（ソフト）の1988－2004間の効率化は、3300倍, 計算機の性能は1600倍 ⇒ 併せると530,0000倍
コストパーフォーマンス比率> 106 小型化比率> 106 ⇒単位費用、単位容積あたりの処理性能（Megaflops）> 1012 10,000,000,000 1,000,000,000 Itanium 2 (9 MB cache) タフな計算も恐れる必要はない ムアーの法則 18－24 ヶ月で倍の能力 100,000,000 ハードOK! Itanium 2 Pentium 4 Itanium 集積回路上のトランジスタ数 10,000,000 Pentium Ⅲ Pentium Ⅱ Pentium 1,000,000 486 386 100, 000 286 8086 10,000 8080 2,300 8008 4004 1971 1980 1990 2000 2004 年月 Bixby, R.E., “Beyond the Moore’s law”，from lecture note (2003)

39 手法・アルゴリズムの所在 身近で使える ものを一つ習得！ Webベース
NEOSサーバ ( HP of Univ. 市販の最適化ソフトウェア(PC, WSベース) LINDO社（LINDO､LINGO) ILOG 社（CPLEX) Dash Associates社（ XPRESS) Mathematical Systems社（ NUOPT) Gurobi Optimization社 (Gurobi) メインフレーム MPS/X (IBM) AMPS (FACOM) 　Even on R, Microsoft Excel, Matlab, CAD soft, … 身近で使える ものを一つ習得！

40 R studio　コンソール画面 ソフト　OK! GA, DE, SA, TS, PSO

41 併せてOK! 最適化ロードマップ Let’s optimize freely! ゴール スタート QPを NLPで メタ解法で ② ① ③
問題は評価量を 最大化または最小化 することで実現 できますか 改善したい問題 がありますか 調査して下さい 問題解決のための 最適化モデルが 定式化できました Max/Min f(x) s.t. x∈X f(x)は⑤より，x∈X は ⑦の結果です 評価量が何に 影響を受けるか わかりますか 問題に 応じて 最適化 手法を 決定 します スタート x に関する 条件はありますか それを数式モデル f(x) のように 表わせますか ②を f、③を x と 表わすとき，f と x 間の相互関係が 相関を調べる 実験や シミュレーション ができますか f(x)は線形 Xも線形モデル ですか 条件をモデル化 メタモデル（応答曲面）を作成して下さい 検討結果を 持って識者 に相談して 下さい 吟味の上，意思決定 に役立てて下さい 結果が求まり ましたか 実現方法を検討 して下さい f(x)は二次形式 xに組合せ的要素がある時はMIPに、 f(x)が複数の時は多目的最適化問題となります QPを NLPで LPを使って下さい ゴール 最適化ロードマップ はい いいえ ① ② ③ ④ ⑤ ⑥ ⑧ ⑦ ⑨ ⑩ ⑪ メタ解法で ⑧でmeta-f(x) and/or meta-X と読み替えて下さい ⑫ Let’s optimize freely! 併せてOK!

42 「雑俳」（最適化工学のすすめ、2010.2) 「松島や ああ松島や 松島や」という俳句は，俳聖，松尾芭蕉が「奥の細道」紀行で松島を訪れた際に，あまりに絶景なので句が浮かばず詠んだという一説がある。 これに習って，「最適化 ああ最適化 最適化」と詠んでみた。最適化があまりに工学的問題解決に有用なので，思わず感嘆の思いがこみ上げ， この句に及んだという戯言が 流布することを夢見て筆をおく。

43 ご清聴お疲れ様