| 科目コード | 科 目 名 | |||||||||
| 8518 | プログラミング特論 : Heuristic Techniques | |||||||||
| 教 員 名 | 武藤義彦 : MUTO Yoshihiko | |||||||||
| 学年 | 単位・時間 | 科目区分 | 授業形態 | |||||||
| 1 | ２・100分 | 選択 | 講義・後期 | |||||||
| 授業概要 | スケジューリング問題や巡回セールスマン問題などの組み合わせ最適化問題を解く手法として，最初に分枝限定法などの列挙法を学び，その問題点を明らかにする．次に，最適化問題の解法としてアニーリング，ニューラルネットワークおよび遺伝的アルゴリズムを学び，これらのコーディングを分析・応用することで各手法の特徴を明らかにする． | |||||||||
| 到 達 目 標 | 評 価 方 法 | |||||||||
| (1)組合せ最適化問題の規模を把握できる． (2)各手法の理論を説明できる． (3)各手法をプログラムとして実装し，パラメータ設定等が与える影響を分析できる． |
評価方法は，(1)期末試験，（2）レポートを評価する．評価配分は，（１）70％，（2）30％とする． | |||||||||
| 学習・教育目標 | (D)① | JABEE基準１（１） | (d)-(3) | |||||||
| 授 業 計 画 | 回 | 項 目 | 内 容 | |||||||
| イントロダクション | 組合せ最適化問題の定式化，ナップサック問題や巡回セールスマン問題などの例の提示 | |||||||||
| 第１ | ||||||||||
| 列挙法 | 分枝限定法と動的計画法 | |||||||||
| 第２ | ||||||||||
| 局所探索法 | 実数最適化問題を例として局所探索の手法を学ぶ | |||||||||
| 第３ | ||||||||||
| アニーリング(1) | アニーリングの理論と実装の理解 | |||||||||
| 第４ | ||||||||||
| アニーリング(2) | SAを用いたナップサック問題の求解（問題の把握と実装） | |||||||||
| 第５ | ||||||||||
| アニーリング(3) | SAを用いたナップサック問題の求解（実装の続き） | |||||||||
| 第６ | ||||||||||
| ニューラルネットワーク(1) | ニューラルネットワークのアーキテクチャ：誤差関数と逆誤差伝播法 | |||||||||
| 第７ | ||||||||||
| ニューラルネットワーク(2) | 階層型ニューラルネットワークの実装の理解，および簡単な問題を用いたシミュレーション | |||||||||
| 第８ | ||||||||||
| ニューラルネットワーク(3) | NNを用いた株価予測モデルの構築（問題の把握と実装） | |||||||||
| 第９ | ||||||||||
| ニューラルネットワーク(4) | NNを用いた株価予測モデルの構築（実装の続き） | |||||||||
| 第１０ | ||||||||||
| 遺伝的アルゴリズム(1) | 遺伝的アルゴリズムの基本概念であるコード化，選択，交叉，突然変異オペレータ | |||||||||
| 第１１ | ||||||||||
| 遺伝的アルゴリズム(2) | 巡回セールスマン問題のためのコード化，交差，突然変異の検討 | |||||||||
| 第１２ | ||||||||||
| 遺伝的アルゴリズム(3) | GAを用いた巡回セールスマン問題の求解（問題の把握と実装） | |||||||||
| 第１３ | ||||||||||
| 遺伝的アルゴリズム(4) | GAを用いた巡回セールスマン問題の求解（実装の続きと解の検討） | |||||||||
| 第１４ | ||||||||||
| まとめ | 全体の学習事項のまとめを行う．また授業評価アンケートを行う． | |||||||||
| 第１５ | ||||||||||
| 関連科目 | ||||||||||
| 教 科 書 | ||||||||||
| 参 考 書 | 伊藤・草薙，コンピュータシミュレーション，オーム社 | |||||||||
| 授業評価・理解度 | 最終回に授業評価アンケートを行う。 | |||||||||
| 副担当教員 | ||||||||||
| 備 考 | 適宜プリントを配布する | |||||||||