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