情報工学実験 3 : 進化計算

目的
  • 最適化の分野で well-known な手法である遺伝的アルゴリズム（Genetic Algorithm）を用いたシミュレータ作成を通し，プログラミング技術・問題設計・評価・考察といった一連の計算機実験のために必要なプロセスを体験して貰うことを目的としています．
  • なお，共同（チーム）開発を通した実験になります．チーム内での情報共有だけでなく，必要に応じて他チームとの連携も取れるように「報告・連絡・相談」を確実にするように心がける事．
進め方
  • 最初の1〜2週間はガイダンスがメインですが，その後の週は逐次進捗状況を報告してもらい，それに対して指導するという形式になるかと思います．
  • 2名1チームで取り組み，最終アウトプットとしては*ドキュメント付き*のオープンソースとして公開することを目指します．
  • ドキュメントを含め，開発には CVS を利用すること．
  • 開発の一部または全てを他チームに依頼し，他チームを含めた共同開発を検討しています．言い換えると，各チームは「自チームの欲しいシステムを他チームに開発依頼しつつ，他チームから依頼されたシステムを開発する」ことになります．進展具合を見つつ，期間内に終了出来そうにない場合はチーム内完結の開発に変更するかもしれません．
  • 課題は，基本的に全ての Level をやるものとする．ただし，「オプション」と記載されている箇所に付いては各自/チームの判断に委ねる．
  • 先行研究の参照:

    GA は古くから広範囲にわたり利用されているため，論文・書籍・解説・webページ等が英語/日本語を問わず豊富にあります．これらの先行研究を参照することはカンニングではありません．むしろ推奨されます．追実験（先行研究通りに実装し，結果の妥当性を検証する等）をするというスタンスも良いでしょう．．ただし，参考する際には敬意を払って文献情情報を示すことを忘れないように．

  • 既存プログラムの利用:

    開発する事そのものを含めて実験であるため，基本的にはダメです．が，他チームと比較して，同程度以上の機能追加（インタフェース改善など）をやれるのであれば，利用してもらって構いません．ただし，最終的にオープンソースとして公開するものですので，ライセンスに十分気をつけて事前に確認してください．

スケジュール

1週目：背景・基礎知識, Level 1

資料: PDF

実際にGAが何かを述べる前に，目的を明確にするため，背景知識・目的・目標を学びましょう．
  • 探索（最適化）とは
  • 組み合わせ最適化問題と探索アルゴリズム
  • 完全解放と近似解法
Level 1: コンピュータを使って計算（シミュレーション）をするとはどういうことか．何のためにコンピュータを使用するのかを考え，それを実現する方法について検討せよ．また，それらの目的達成のために便利なツールがあればそれを示せ．
2週目：GA基礎, Level 2

資料: PDF

目的を達成する方法はGAだけに限りません．他と比べてどのような特徴があるのだろうか？
  • 近似解法例とその特徴
  • GA（概要）
Level 2: GAの特徴を3つ以上挙げ，その利点・欠点について考察せよ．他の探索アルゴリズムと比較するとなお良い．
オプション：時間があれば，さらに他の最適化手法（全探索・山登り法・ニューラルネット・タブー探索等何でも可）についても同様に検討し，手法としての違いについて指摘せよ（加点対象）．（例えば，具体的な対象問題について適用しやすさ・手法選択の妥当性等の観点から指摘する等）
3週目：拡張GA紹介，コードから読むGA, Level 3

資料: PDF

実際に適用されている研究例を見て，どのように応用出来るか考えてみましょう．
  • 遺伝的プログラミング（GP）：人工蟻による餌探索問題
  • インタラクティブGA：紅型（配色・デフォルメ）
Level 3: GAで解く問題を探し出し，定式化せよ．なお，翌週以降ではこれをもとに要求仕様・要件定義・外部設計・内部設計・テスト計画を立案していく事になる．それを踏まえた上で，見つけて来た問題に付いては十二分にサーベイをすること．（要求仕様まで考えておくと，今後のスケジュールがスムーズになります！）
オプション：その際，その問題ならではの特性をまとめ，それをうまくGAで処理するための方法論について考察せよ（加点対象）．
4-6週目：企画, Level 4-7
  • 問題定義（要求仕様，要件定義）
  • 外部設計
  • 内部設計
  • テスト計画
以下のLevelに示している通り，期間内で要求仕様・要件定義・外部設計・内部設計・テスト計画の企画案を立案せよ．この際，下記の事に留意しつつ検討する事．
  • 互いの認識を明文化等により明確化することで「一方的な認識（暗黙部分）」にならないように気をつけること．
  • 開発期間・人的パワー等の制約を考慮した上で，双方に取っての適切な妥協案を見出すこと．
  • Level 4: Level 3 で選択した問題に対し，要求仕様書・要件定義書を作成せよ．必要に応じ，外部設計までを自チームでやることにしても良い．
    • Level 4-1（要求仕様）: チームで選択した問題に対し要求仕様をまとめ，他チームへ開発依頼せよ．
    • Level 4-2（要件定義）: 他チームから依頼された要求仕様をもとに話し合い，開発すべき要件を定義せよ．この時，曖昧な部分を明確にするだけでなく，ユーザ自身も気づいていない箇所を提案する等，理想的なシステムに近づける事を念頭に置く事．（ただし，制約条件により実際に開発するシステムは理想的な物になる必要は無く，妥協点を探す事になる）
  • Level 5（外部設計）: 要件定義書をもとに，外部設計書を作成せよ．
  • Level 6（内部設計）: 要件定義書・外部設計書をもとに，内部設計書を作成せよ．
  • Level 7（テスト計画）: 要件定義書・外部設計書・内部設計書をもとに，テスト計画書を作成せよ．
7-10週目：プログラミング, Level 8-12
  • 一部の機能を外注．
  • Level 8: コーディング及び適応度関数を実装し，幾つか特徴的な解の適応度を求め，それが適当な差異として出てくるか確認せよ．
  • Level 9: 1つ以上の選択オペレータを実装し，実装したオペレータがどのようなものか説明せよ．
  • Level 10: 1つ以上の交叉オペレータを実装し，実装したオペレータがどのようなものか説明せよ．
  • Level 11: 1つ以上の突然変異オペレータを実装し，実装したオペレータがどのようなものか説明せよ．
  • Level 12: 具体的な問題へGAを適用し，評価・考察せよ．その際，たまたまうまくいった結果のみを示すのではなく，シード値を何度か変更して実行した複数回の結果を平均するなどにより，「平均的にこのぐらい解ける」というデータで考察するように留意せよ．
    オプション：また，実験を効率よく行うため（レポート作成のためのグラフ自動生成等を含む）に作成したスクリプトがあればそれを示し，説明せよ（加点対象）．
11週目：テスト, Level 13
  • 結合テスト・システムテスト
Level 13: テスト計画で予定していたテストを実施し，動作を検証せよ．想定通りの動作である場合，公開するために必要な作業を洗い出し，公開せよ．動作が想定外である場合，おかしい箇所を発見し，修正せよ．
12-13週目：評価・修正, Level 14-15
開発予備日も含めて，この期間内に開発終了するようにスケジューリングしましょう．
  • Level 14: Level12 で得られた解は十分なものであったか？また問題空間と探索に要した時間的にはどうか？不十分であると考える場合にはその原因がどこにあるのかを考え，改善方法を示せ．
  • （オプション）Level 15: 基本的に遺伝的アルゴリズムは時間のかかる探索手法である．また，初期集団に良質の解が含まれていると局所解へと収束しがちであったり，適切なパラメータを設定するためには試行者がそのシミュレータ・問題に慣れてノウハウを獲得する必要があるなど，様々な問題点が指摘されている．これらを解決するために，メタGAや並列分散GA等が提案されているが，今回実装したGAをそのように実装する方法について検討せよ．途中まででも構わないので実装/検討していると加点対象とする．
14-15週目：公開・最終報告, Level 16-
  • Level 16: 開発したシステムのプレゼンテーション資料を作成せよ．
  • Level xxx: 自分で新しい Level を定義し，それを実装/検討せよ．
  • Level other: 本実験の内容や実施方法に関するコメント・リクエストがあれば報告お願いします（加点対象）．
参考文献・サイト