最適化特論1, 2 (柳浦)
2024年度春1, 2期 木曜日3時限 13:00-14:30 (原則オンラインを予定しています. 講義室(情報学研究科棟第4講義室)での対面講義を行う場合は事前に通知します)
- 問合せ先: yagiura "at" i.nagoya-u.ac.jp ("at"を@に置き換えてください)
- 初回: 4月11日 (予定)
- 最適化特論1と2は連続する講義です．必ず両方受講してください．
- 講義内容: 計算困難な離散最適化問題(主にNP困難であるもの)を対象として，
それらに現実的に対処するために用いられる代表的なアルゴリズムの設計手法を講述する．
基本戦略として局所探索法を解説したのち，アニーリング法，遺伝アルゴリズム，
タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みについて，
局所探索の一般化に基づく統一的な視点から詳しく述べる．
巡回セールスマン問題や充足可能性問題などの代表的な離散最適化問題を例に，
具体的なアルゴリズムの構成方法についても紹介する．
- 単位取得基準:
- 最適化特論1: レポートの得点が60点以上であること.
- 最適化特論2: コンペティション・レポート・プレゼンの得点合計が60点以上であること.
- 参考書: 柳浦, 茨木, 組合せ最適化: メタ戦略を中心として
（経営科学のニューフロンティア2），朝倉書店, 2001.
- 参考資料
注．解説論文のPDFファイルにはアクセス制限あり．
これらのPDFファイルを不特定多数がダウンロード出来る場所には置かないでください．
- 柳浦,
組合せ最適化: 実践的解法を中心として，
マルチメディアライブラリー第13編，
システム制御情報学会，2010年1月.
- 柳浦睦憲, 野々部宏司,
分枝限定法 ─ さらなる計算効率の希求,
システム/制御/情報, Vol. 50, No. 9, pp. 350-356, 2006年9月.
- オペレーションズ・リサーチ, Vol. 58, No. 12の特集
「はじめようメタヒューリスティクス」に掲載された記事．
- 柳浦，組合せ最適化問題に対する実践的解法の開発を目指して,
第30回RAMPシンポジウム講演論文集, pp. 213-230, 2018.
- D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon,
Optimization by Simulated Annealing: An Experimental Evaluation;
Part II, Graph Coloring and Number Partitioning,
Operations Research 39 (1991) 378-406.
- 講義の補足資料
- 連絡事項（休講，講義室変更など）
- レポート課題（暫定版）
柳浦のホームページ