到達目標
1. 自然界の遺伝のしくみ、遺伝的アルゴリズムの概要を説明できる。
2. 巡回セールスマン問題などに適した遺伝子コーディングを説明できる。
3. 遺伝的アルゴリズムをプログラミング言語で記述できる。また、様々な最適化問題に適用することができる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 自然界の遺伝の仕組みを応用した遺伝的アルゴリズムの流れを、フローチャートで説明できる。また、期限内に所定のレポートを高い完成度で提出できる。 | 自然界の遺伝の仕組みを応用した遺伝的アルゴリズムの流れを、フローチャートで説明できる。また、期限内に所定のレポートを概ね提出できる。 | 自然界の遺伝の仕組みを応用した遺伝的アルゴリズムの流れを、フローチャートで説明できない。また、期限内に所定のレポートを提出できない。 |
| 評価項目2 | 巡回セールスマン問題などの具体例にGAを適用する際の順序表現を説明できる。また、遺伝的アルゴリズムのパラメータが最適解探索に及ぼす影響を考察し、説明できる。また、期限内に所定のレポートを高い完成度で提出できる。 | 巡回セールスマン問題などの具体例にGAを適用する際の順序表現を説明できる。また、遺伝的アルゴリズムのパラメータが最適解探索に及ぼす影響を概ね説明できる。また、期限内に所定のレポートを概ね提出できる。 | 巡回セールスマン問題などの具体例に適用する際の順序表現を説明できない。また、期限内に所定のレポートを提出できない。 |
| 評価項目3 | プログラム言語を用いて、遺伝的アルゴリズム、各種スケーリング技法を実装できる。具体例に対して、パラメータが最適値探索に及ぼす影響を考察し、説明できる。様々な問題にGAを適用することができる。また、期限内に所定のレポートを高い完成度で提出できる。 | プログラム言語を用いて、基本的な遺伝的アルゴリズムやスケーリング技法を実装できる。様々な問題にGAを適用することが概ねできる。また、期限内に所定のレポートを概ね提出できる。 | プログラム言語を用いて、基本的な遺伝的アルゴリズムやスケーリング技法を実装できない。様々な問題にGAを適用することができない。また、期限内に所定のレポートを提出できない。 |
学科の到達目標項目との関係
教育方法等
概要:
自然界の遺伝のしくみ、遺伝的アルゴリズムの概要を理解し、巡回セールスマン問題、Nクイーン問題、囚人のジレンマ問題などに適した遺伝子コーディングや最適値探索手法を学ぶ。また、様々な最適解探索問題に対し遺伝的アルゴリズムを適用し、プログラミング言語で記述する。
授業の進め方・方法:
プリントをベースに輪講形式で授業を進める。遺伝的アルゴリズムの基本を学習した後、プログラミング言語で実装し巡回セールスマン問題やNクイーン問題などに適用する。次に、様々な最適化問題に遺伝的アルゴリズムを適用し、Gtype、Ptype、適合度、選択、突然変異などの遺伝的アルゴリズムパラメータが最適解探索にどのような影響を及ぼすかを考察する。
注意点:
この科目では、調査活動やレポート課題などで60時間の自学自習を課す。なお、年間総合評価が60点に満たない場合は、再提出したレポートや再評価試験にて評価する。再評価でも60点に満たない場合は単位を認定しない。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
ガイダンス・遺伝的アルゴリズムとは |
本講義の学習内容や目標、評価方法について理解し、説明できる。遺伝的アルゴリズムの概念を理解し、説明できる。
|
| 2週 |
GAの扱う世界 |
GAの基礎的な知識を理解し、説明できる。
|
| 3週 |
巡回セールスマン問題 |
遺伝的アルゴリズムを巡回セールスマン問題に適用する手法や問題点について理解し、説明できる。
|
| 4週 |
Nクイーン問題 |
遺伝的アルゴリズムをNクイーン問題に適用する手法や問題点について理解し、説明できる。
|
| 5週 |
囚人のジレンマ |
遺伝的アルゴリズムを囚人のジレンマに適用する手法や問題点について理解し、説明できる。
|
| 6週 |
ブール関数の充足問題 |
遺伝的アルゴリズムをブール代数の充足問題に適用する手法や問題点について理解し、説明できる。
|
| 7週 |
スケーリング技法 |
線形スケーリング、シグマスケーリングなどの適合度のスケーリング技法を理解し、説明できる。
|
| 8週 |
選択のメカニズム |
ルーレット方式、ランク方式、トーナメント方式などの選択方式を理解し、説明できる。
|
| 4thQ |
| 9週 |
遺伝的アルゴリズムのコーディング（１） |
各種プログラミング言語を用い、遺伝的アルゴリズムを実装できる。
|
| 10週 |
遺伝的アルゴリズムのコーディング（２） |
各種プログラミング言語を用い、遺伝的アルゴリズムを実装できる。
|
| 11週 |
遺伝的アルゴリズムのコーディング（３） |
各種プログラミング言語を用い、遺伝的アルゴリズムを実装できる。
|
| 12週 |
様々な問題への応用（１） |
様々な最適化問題に遺伝的アルゴリズムを適用する手法を理解し、説明できる。
|
| 13週 |
様々な問題への応用（２） |
様々な最適化問題に遺伝的アルゴリズムを適用する手法を理解し、説明できる。
|
| 14週 |
様々な問題への応用（３） |
様々な最適化問題に遺伝的アルゴリズムを適用する手法を理解し、説明できる。
|
| 15週 |
定期試験 |
期末までの学習範囲について到達度を確認し、改善することができる。
|
| 16週 |
定期試験答案返却 |
期末までの学習範囲について到達度を確認し、改善することができる。
|
評価割合
| 試験 | レポート | プレゼンテーション | 合計 |
| 総合評価割合 | 30 | 40 | 30 | 100 |
| 基礎的能力 | 10 | 10 | 10 | 30 |
| 専門的能力 | 10 | 20 | 10 | 40 |
| 分野横断的能力 | 10 | 10 | 10 | 30 |