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