| 授業の目的 【日本語】 | | 多くの離散最適化問題がNP困難であることが知られており，それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の実践的手法を学び，それらを用いた問題解決の力を養う。
具体的には，基本戦略として構築型の解法である欲張り法と反復改善型の解法である局所探索法を学んだのち，
アニーリング法，遺伝アルゴリズム，タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みに基づくアルゴリズム設計について学ぶ。
|
|
|
| 授業の目的 【英語】 | | |
|
| 到達目標 【日本語】 | | 多くの離散最適化問題がNP困難であることが知られており，それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の手法について理解するとともに，それらを用いた問題解決の力を養う。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | 最適化特論２では，最適化特論１に続く科目として，計算困難な離散最適化問題（主にNP困難であるもの）に
現実的に対処するために用いられる代表的なアルゴリズムの設計手法を取り上げる。
巡回セールスマン問題や充足可能性問題などの代表的な離散最適化問題を例に，基本戦略である局所探索法をはじめ，
アニーリング法，遺伝アルゴリズム，タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みに従って
具体的なアルゴリズムを設計し構成する方法を修得する。
〔計画〕
1. イントロダクション
2. 代表的な離散最適化問題
3. 欲張り法と局所探索法の設計法
4. 反復型解法の探索空間と移動戦略
5. メタヒューリスティクスの枠組み
6. メタヒューリスティクスの実現法
7. 総合討論 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に課題を与えた場合はその評価と期末レポートおよびコンペティション結果を総合的に評価し，合計１００点満点で６０点以上を合格とする。 | |
|
|
| 教科書・参考書 | | | 必要に応じて参考資料を配布し，講義のウェブサイトからダウンロードできるようにする。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した内容を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|