最適化特論2

更新日:2017-05-22

時間割コード

2501412

ナンバリングコード

GSI-11-6028-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

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

春2期

講義室


開講専攻

数理情報学専攻

担当教員 所属

柳浦睦憲,小野廣隆

所属

数理情報学専攻

メールアドレス

yagiura@is.nagoya-u.ac.jp


授業概要


◆講義目的

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

◆授業内容

最適化特論2では,最適化特論1に続く科目として,計算困難な離散最適化問題(主にNP困難であるもの)に
現実的に対処するために用いられる代表的なアルゴリズムの設計手法を取り上げる。
巡回セールスマン問題や充足可能性問題などの代表的な離散最適化問題を例に,基本戦略である局所探索法をはじめ,
アニーリング法,遺伝アルゴリズム,タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みに従って
具体的なアルゴリズムを設計し構成する方法を修得する。

〔計画〕
1. イントロダクション
2. 代表的な離散最適化問題
3. 欲張り法と局所探索法の設計法
4. 反復型解法の探索空間と移動戦略
5. メタヒューリスティクスの枠組み
6. メタヒューリスティクスの実現法
7. 総合討論

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

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

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

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

成績評価方法・基準

講義中に与える課題の評価50%,期末のレポート50%で評価し,合計100点満点で60点以上を合格とする。

Course Title

Optimization 2(Advanced Lecture)

Class Timetable Code

2501412

Numbering Code

GSI-11-6028-J

Course Category

Main majors

Credits

Elective1

Class Format


Grade

Master1-2

Semester, Day and Period

Spring 2 semester

Instructor(s)

YAGIURA Mutsunori,ONO Hirotaka

Affiliation

Department of Mathematical Informatics

Mailaddress

yagiura@is.nagoya-u.ac.jp


Course Topics

In this course, we study the ways of designing and implementing 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