学生実験2 : 探索アルゴリズムその2・遺伝的アルゴリズム





更新情報
  • [2005-11-29] 作成中・・・．
  • [2005-12-07] ver 1.0.0 公開．
  • [2005-12-09] ver 1.0.1: オプション課題（実験実施方法に関するアンケート）を追加．LaTeX に gnuplot の図を取り込む手順を追加．
  • [2005-12-12] ver 1.0.2: レポートに関する注記を追加．
  • [2005-12-12] ver 1.0.3: ga-tsp.tar.gz を修正．



進め方

内容と目標
  • 計算機実験を通して探索や最適化のイメージを掴むとともに，計算機実験を効率良く実施するために何を考慮すべきかを理解する．
課題と提出方法
  • オプション課題を除いた全ての Level にトライし，レポートとしてまとめよ．
  • 1グループ1レポート提出．
  • メンバ（氏名・学籍番号）と担当内容を記載すること．
  • レポートは LaTeX で作成し，印刷物を提出すると共に PDF ファイルをメールで提出すること．ただし，プログラムのソースファイル一式は圧縮してメール添付で提出する事．メールのサブジェクトは下記参照．

    「Subject: [2005_slab2 search3] (曜日-グループ名) j040xx,j040xx,j040xx,j040xx」

    例：[2005_slab2 search3] (Mon-A) j040xx,j040xx,j04xx,j04xx

  • 表紙に上記サブジェクトと同じ情報を記入する事．
  • スクリーンキャプチャした図を掲載しない事．
  • 提出期限：実験日の10日後までに 705 室へ（12/12のクラスの期限は12/22，12/16のクラスは12/26）．
コンテンツ
  1. 遺伝的アルゴリズムとは？: Level 1 〜 Level 3
  2. アンケート: Level 4（オプション）
  3. Tips（図の取り込み方等）

1. 遺伝的アルゴリズムとは？

ダーウィン進化論をモデル化した最適化手法．

  • [自然淘汰] 環境に応じて優秀な個体が多くの子孫を残す事ができ，劣等な個体は淘汰される．
  • [形質遺伝] 子は親の形質を受け継ぐ．
  • （子は突然変異する事がある）

探索のイメージ

遺伝的アルゴリズムによる探索（進化）のイメージとフローチャート．

  1. 各個体はその環境内における適応度が評価される．
  2. 適応度に比例した確率で次世代に生き残る（淘汰・増殖）．
  3. 生き残った個体は交叉・突然変異により子孫を作る．


図2：探索のイメージ


図3：フローチャートとTSPでの進化イメージ

Level 1: ナップサック問題．

実験内容

  1. サンプルソース（ga-knapsack.tar.gz）はGAを「ナップサック問題」に適用した例である．この問題においてシード値を変更して適当回数実行し，評価値がどのぐらいの値で収束するかを確認せよ．使い方は 0README_ja.txt を参照．

    コメント：教師信号付きNNにおける学習と異なり，今回は「だいたいこの位になる」という目安自体が無い．この場合には，終了世代数を増やして実行する等，実験を繰り返して目星をつけるしか無い．ただし，それだけだと最終的に得られた解が本当に良い解なのかが判断出来ないため，一般的にはベンチマーク問題等，多数の研究者が適用している問題に適用し，比較により判断する事になる． 

    簡単な使い方：
  prompt> make
  prompt> ./run_ga.sh $seed_pop $seed_ga $ItemList $terminal_generation
　　$seed_pop：初期集団生成用シード値（整数）
　　$seed_ga：GAオペレータ用シード値（整数）
　　$ItemList：ナップサック問題ファイル名（KP_List.data）
　　$terminal_generation：終了世代数（整数）

  2. ナップサック問題「KP_List.data100」に変更し，適応度推移グラフを作成せよ．ただし，横軸は世代数，縦軸は適応度（評価値）とする．また，終了世代数は1000とし，シード値以外のパラメータは変更せずに行う事．

    コメント：5回分の実験結果を求め，平均化した平均化したグラフを作成する事．shell/perl等のスクリプト言語/表計算ソフト/gnuplot等を利用すると楽になるでしょう．ソースファイルそのものを改変するのもOK．

Level 2: 巡回セールスマン問題

実験内容

  1. サンプルソース（ga-tsp.tar.gz）はGAを「巡回セールスマン問題（Travelling Salesman Problem; TSP）に適用した例である．この問題において　Level 1.1 と同様に実行し，収束する評価値を確認せよ．終了世代数は 1000 世代とする．

    コメント：使用方法は 0README_ja.txt を参照．

  2. 問題「town24co」に適用するにあたり，以下に示す各パラメータを変更して実験せよ．優良解を発見しやすい組み合わせを検討せよ．ただし，終了世代数は 1000 世代とする．

    パラメータ変更目安
    集団数 POP_SIZE10以上〜1000以下
    エリート保存率 ELITE_COPY0.0〜1.0
    交叉確率 CROSS_RATE0.0〜1.0
    突然変異確率 MUTE_RATE0.0〜1.0

    注記：1つの組み合わせで収束するかどうかを確認する為に，1組み合わせにつきシード値を変更した実験を5回以上行い，最終世代において発見出来た最良解の評価値に関して最大・最小・平均値を求める事．これは，たまたま初期重みが適切な値に設定されたことにより学習が収束したのでは無い事を確認する為である．

  3. Level 2.2 において発見した最良個体（ベストな解）の評価値と巡回経路図を示せ．（その際のパラメータも記載する事）
  4. Level 2.2 で変更したパラメータ毎の結果から，適応度推移に見られる傾向・最良個体の評価値・収束能力等の点において，パラメータと探索挙動に関して考察せよ．
特徴
（通常の）コンピュータの持つ特徴と異なり，曖昧な処理が得意である一方，厳密な処理は苦手である．
  • 得意：コーディング＋評価＋遺伝子操作（交叉・突然変異）が実装出来れば，どのような問題にでも適用可能．
  • 苦手：上記項目の何れか/複数が実装出来ない問題（インタラクティブGA等，評価を人間に一任する事で解決する手法もある）．
Level 3: 検討

検討内容

  1. Level 2 の問題は，都市配置が特徴的であるためそれを利用して探索効率を改善する事が可能である．どのような方法でも構わないので，改善案について検討せよ．
  2. NNと同様に，チューニングする必要のあるパラメータが複数ある時には適切なパラメータを求める事そのものが困難となっている事が少なくない．このパラメータ・チューニング問題を解決するにはどのような方法が考えられるか，検討せよ．（Level 2 について，実際にその方法で実施すると加点）
  3. （オプション）問題「town48R0.5r0.386.O」へ変更し，優良解を発見しやすいパラメータの組み合わせを検討せよ．集団数・終了世代数については上限を設けない．また，発見した最良個体の評価値と巡回経路図を示せ．（その際のパラメータも示す事）



2. アンケート（オプション）

Level 4: オプション

実験の内容・進め方に関するコメント等

  1. 今後の為に参考にしたいので，情報工学実験2・探索アルゴリズム1〜3で扱った内容，実験の進め方等について意見があれば書いてください（当然，どのような意見であってもレポートの評価を下げる事はしません．）．「授業評価アンケート」の際に書いてもらっても構いません．参考までに，今回の実験では以下の点を考慮した内容のつもりで実施しました．
    • 扱った内容：探索アルゴリズムの考え方，NN，GA
    • 中心課題：

      （1）計算機実験を実施するにあたっての考え方，特に，実験計画・実験・結果収集・結果解析・レポート作成までの一連の作業をするにあたって考慮すべき点の発見と，対処方法の検討．

      （2）(1)の実験を効率良く実施する為に検討すべき項目の調査と，それを解決する手段に関する検討．

      （3）パラメータ・チューニングの必要性やそれらを効率的に実現する為の前処理・後処理のためのテキスト処理や自動化に関する考え方，

      （4）（主題ではないですが）サンプル・ソフトウェアの利用を通した，システム設計面における外部設計指針，マニュアル整備等の必要性確認．

    • 進め方

      （1）「解説→グループ討論/実施→全体討論」という形式を取り，他の人/グループが同じテーマを与えられた時にどのような事を考え，アイデアを整理し，どのように発表するのかについて，学生全員が実験時間中に把握出来るように心がけた．

      （2）「共同作業（グループ制）」とする事で，個人レベルでの理解度の底上げに努めた．これは，解説の段階で理解度の早い学生は他の人へ教示する事でそのスキルとより理解度が深まる上に，理解度が不十分であった学生は同環境にいる学生の視点からの教示により理解しやすくなる事を期待して実施した．

      （3）(2)の間接的な効果として，自分の意見を第三者へ伝えるコミュニケーション能力・レポート作成技術の向上が挙げられます．これはどのような職に就こうとも求められるスキルです！

  2. 今後，実施を検討している以下の項目に関する，賛成/反対等の意見．

    （1）レポートの開示．取りあえず，今回の分については採点後，評価の高いレポートについて了承を得てから開示の有無を決定するつもりです．

    （2）最急降下法，NN，GA以外のアルゴリズムを用いた実験（「アルゴリズムとデータ構造」等，他の講義で出てくるアルゴリズムを利用した実験等）．

  3. やって欲しかった内容，その他に関する意見．



3. Tips

  1. Excel等の表計算ソフトでデータを収集・解析した結果をグラフ化する．

    gnuplot 等 EPS 形式で出力出来る図作成ソフトを利用する． gnuplot の場合なら，それが読み込める形式（text）に保存し，「2. LaTex に gnuplot の図を取り込む．」の手順にて図を作成し，LaTeX に取り込む．

  2. LaTex に gnuplot の図を取り込む．
    1. グラフ化するデータを準備する．
    2. gnuplot でグラフ化する．以下は result.dat 内のデータを線グラフ化する例．ここでは LaTeX 用に eps 形式で作成しています． 
      gnuplot> set terminal postscript eps
gnuplot> set output "result.eps"
gnuplot> set title "figure title..."
gnuplot> set xlabel "x title..."
gnuplot> set ylabel "y title..."
gnuplot> plot "result.dat" with line
    3. LaTeX に取り込む． 
      \documentclass[a4paper,10pt]{jarticle}
\usepackage{graphicx}

\begin{document}
\begin{figure}
 \begin{center}
  \includegraphics[scale=0.5]{result.eps}
  \caption{図のテスト}
 \end{center}
\end{figure}

\end{document}
    4. 参考：講義関連資料/info1-latex（白土先生）



参考文献・サイト