最適化特論２

更新日：2020-04-09

ナンバリングコード

GSI-11-6028-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

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

春2期木曜3限目

講義室

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

開講専攻

数理情報学専攻

担当教員 所属

柳浦睦憲，小野廣隆

所属

数理情報学専攻

メールアドレス

yagiura@i.nagoya-u.ac.jp


授業概要

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

◆講義目的

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

◆授業内容

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

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

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

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

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

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

成績評価方法・基準

講義中に課題を与えた場合はその評価と期末レポートおよびコンペティション結果を総合的に評価し，合計１００点満点で６０点以上を合格とする。

Course Title

Optimization 2（Advanced Lecture）

Numbering Code

GSI-11-6028-J

Course Category

Main majors

Credits

Elective1

Class Format


Grade

Master1-2

Semester, Day and Period

Spring 2 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 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