最適化特論１

更新日：2020-04-09

ナンバリングコード

GSI-11-6027-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

学期 曜日 時間 集中講義の有無

春1期木曜3限目

講義室

情報学研究科棟1階第3講義室

開講専攻

数理情報学専攻

担当教員 所属

柳浦睦憲，小野廣隆

所属

数理情報学専攻

メールアドレス

yagiura@i.nagoya-u.ac.jp


授業概要

多くの離散最適化問題がNP困難であることが知られており，それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の実践的手法を学び，それらを用いた問題解決の力を養う。
具体的には，基本戦略として構築型の解法である欲張り法と反復改善型の解法である局所探索法を学んだのち，
アニーリング法，遺伝アルゴリズム，タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みについて学ぶ。

◆講義目的

多くの離散最適化問題がNP困難であることが知られており，それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の手法について理解するとともに，それらを用いた問題解決の力を養う。

◆授業内容

最適化特論１では，計算困難な離散最適化問題の中から，主にNP困難であるものを対象として，
それらに現実的に対処するために用いられる代表的なアルゴリズムの基礎を取り上げる。
基本戦略として構築型の解法である欲張り法と反復改善型の解法である局所探索法を学んだのち，
アニーリング法，遺伝アルゴリズム，タブー探索法などに代表されるメタヒューリスティクスと
呼ばれる枠組みについて，局所探索の一般化に基づく統一的な視点から，それらの基本的な考え方を修得する。

〔計画〕
1. イントロダクション
2. 離散最適化問題
3. 欲張り法と局所探索法
4. アニーリング法
5. 遺伝アルゴリズム
6. タブー探索法
7. 総合討論

◆教科書・参考文献・履修条件等

必要に応じて参考資料を配布し，講義のウェブサイトからダウンロードできるようにする。

◆授業期間中の課題・宿題等

講義において説明した内容を理解するために課題を与える。

成績評価方法・基準

講義中に課題を与えた場合はその評価と期末レポートを総合的に評価し，合計１００点満点で６０点以上を合格とする。

Course Title

Optimization 1（Advanced Lecture）

Numbering Code

GSI-11-6027-J

Course Category

Main majors

Credits

Elective1

Class Format


Grade

Master1-2

Semester, Day and Period

Spring 1 semester Thursday 3

Instructor(s)

YAGIURA Mutsunori, ONO Hirotaka

Affiliation

Department of Mathematical Informatics

Mailaddress

yagiura@i.nagoya-u.ac.jp


Course Topics

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.

Course Purpose


Course Contents


Textbooks, Reference Materials and Requirements


Assignment


Grading Criteria