学生実験2 : 探索アルゴリズムその1





更新情報
  • [2005-11-05] 作成中・・・．
  • [2005-11-10] ver. 0.9.0 公開．
  • [2005-11-16] ver. 0.9.1. Level 2 を微分ベースで検討させるように修正し，サンプルソースを追加．
  • [2005-11-17] ver. 0.9.2. Level 3 を組み合わせ最適化問題ベースで検討させるように修正．
  • [2005-11-21] ver. 0.9.3. Level 2, 3 の課題を一部修正．また，サンプルソースに Makefile, 0README_ja.txt を追加しました．



進め方

内容と目標
  • 復習を兼ねて，実験1で学んだ技術の応用．
  • 人工知能関連科目（人工知能，ニューラルネット，知能ロボット，実験3/4（進化計算，知能ロボット））へのイントロダクション．
  • グループ討論，計算機実験を通して探索や最適化のイメージを掴むとともに，計算機実験を効率良く実施するために何を考慮すべきかを理解する．
実験の進め方
  • グループ作業．

    各課題についてグループ間で議論し，プログラミング，考察，文書作成等を共同作業で行う事．作業分担についてはこちらからは指定しないが，各自担当した箇所が分かるように明示する事．

  • 各レベル毎に，「解説＞グループ討論（実装，計算機実験，考察）＞全体討論（報告会）」を行う．
評価基準

報告会では主にプレゼンや質疑応答により「コミュニケーション能力と国際性，論理性」を中心に評価する．

レポートでは指定した課題をこなしている（提出している）事を前提に基準点を設け，以下の項目に沿って加点・減点を行う．

加点
  • 実験中に示した手法ではなく，自力で探し出した異なる手法で問題を解決した場合（積極性・実践性・創造性）．
  • 手法の利点・欠点や限界等に関して自主的にトライした結果・考察が示されている場合（積極性・専門性）．
減点
  • 論理的矛盾が見られる場合（論理性）．
  • 結果を示さずに考察のみを記載してたり，結果に対する考察に整合性が見られない場合（コミュニケーション能力）．
  • タイプミスや可読性の欠如，数式等記号の印字ミス，提出期限の遅れ等，多方面に関して大きな誤りではない場合．

課題と提出方法
  • 全ての Level にトライし，レポートとしてまとめよ．
  • 1グループ1レポート提出．
  • メンバ（氏名・学籍番号）と担当内容を記載すること．
  • レポートは LaTeX で作成し，印刷物を提出すると共に PDF ファイルをメールで提出すること．ただし，プログラムのソースファイル一式は圧縮してメール添付で提出する事．メールのサブジェクトは下記参照．

    「Subject: [2005_slab2 search1] j030xx,j030xx,j030xx,j030xx」

  • 表紙に曜日を含める事．
  • 提出期限：実験日の10日後までに 705 室へ（11/21のクラスの期限は12/1，11/25のクラスは12/5）．
コンテンツ
  1. 1. 探索とは？: Level 1
  2. 2. 連続関数の最適化: Level 2.x
  3. 3. 不連続関数の最適化: Level 3.x

1. 探索とは？

前提

（探索が何なのかを考える前に・・・） コンピュータを利用して効率良く問題解決したい． 特に，ここでは AI で対象とする問題を解決するための一般的枠組みを学ぶ．

  • AI で対象とする問題：ゲーム理論，音声/画像認識，ロボティクス，マイニング，予測，同定，，，
  • 参考：人工知能研究（What's AI @ 人工知能学会）

Level 1 : コンピュータと人間の違いを述べよ
コンピュータが人間より得意とするモノは何か？逆に，人間より不得手のモノは？
注記：レポートでは，各々2つ以上を列挙して説明する事．

問題解決

人間と全く同じことができるのであればただのマンパワーとして考えれば良いが，コンピュータはそうではない． では，コンピュータに取って都合の良い解決方法があるのだろうか？

そもそも人間の行っている問題解決とは？

どうすれば解決できる？

1. 問題の定式化

実世界の問題→形式的記述．
言い換えると，計算機で扱える（＝プログラミング・実装できる）ように置き換える．

  • 手法：問題表現の抽象化・再構成

    e.g.) 状態空間法：<Q,O,φ,Q_i,Q_f> （参考：講義「人工知能」，第2回目：問題解決）

  • ポイント：記述方法によって解き方の効率が大きく異なる（事がある）．
  • コメント：一つの側面に過ぎないですが，「問題空間を必要十分に定義する」事と考えると理解しやすいかも．
2. 形式的処理

形式的記述をその世界のルールに従った方法で処理（＝プログラミムを実行）して解を求める．

Q: 効率良く計算機実験を行うためにはどうすれば良いのか？ （ハードウェア/ソフトウェア）
3. 形式的な解の解釈
解の意味を実世界で表す．



2. 連続関数の最適化

コンピュータで解決するには？

探索：人間のように知的に処理 <-> 全ての解を調べ尽くす

どれだけ計算資源を割り当てることができるのか，どれだけ時間資源を割くことができるのかといったコストの観点を捨て去ることはできないが，理想的には，無駄無く適切な解を求めたい．
→では，どうやって求めるのがベストな方法なのか？

Level 2 : 連続関数における探索手法を検討し，その効率を示せ．

Level 2.1 〜 2.3 に示した関数について，最急降下法により最小値を求めるプログラムを作成し，計算機実験により評価し，結果を示した上で考察せよ．

なお，最適解を求める（発見する）にあたり，出発点となる解はランダムに選ばれるものとする．

コメント

  • 最急降下法以外の手法を実装する場合には，何らかの点で効率が良い事を理論的に説明した上で結果・考察を示す事．
  • 効率の指標には計算量，メモリ使用量，実行時間等様々な物差しがあるが，どの指標を用いても良い．例えば，探索点（解）の数が1万個あるとし，その内何割程度の解空間を調べる事で最適解を発見できる，というような考察でもOK．
  • ランダムな解からスタートするため，Level 2.3 のような多峰の関数においては必ずしも最適解を発見できるとは限らない．この場合には「試行 10 回中 5回は最適解を発見できる」等として，どのぐらいの確率で成功するのかを示した上で，これを改善する策について言及すること．
  • Level 2.3 では同じ最適値の解が2つあるが，このような場合どのようにすれば複数最適解を獲得出来るか，検討せよ．（オプション：実装し，結果も示すと加点）

実装時のヒント

  • 微分値を利用する際，目的関数 f(x) を微分した関数 f'(x) はプログラマが設定して良い．（任意の関数 f(x) を微分出来るように実装する必要は無い）
  • 微分値が正の値の場合，最適解（最小値）は相対的にどの位置にあるか？同様に，負の値を取る場合にはどの位置にあるかを考えて実装せよ．言い換えると，「現在地 xi の微分値を求め，その値に応じて x 軸のどの方向へ探索するかを決定する必要がある．
  • 微分値を基に x を移動させる幅を決定する際，「xnext = x -α*f'(x)」とせよ．学習係数αは 0 より大きい整数とし，この値を変更する事でどのように探索が行われるかを観察せよ．
  • x は「-10 <= x <= 10」とする．
  • サンプルソース：search1-sample.tar.gz

    ランダムな初期位置の決定，指定した回数分探索を行う，定義域内を外れたら終了，の3点は実装済．詳細はソース内の 0README_ja.txt や，上記の「実装時のヒント」を参照．

    f(x), f'(x) 及び x の移動方法を実装し，実験せよ．

注記：レポートには以下の点を含めて考察する事．

  • 探索の手続き，フローチャート．
  • プログラムソース（スクリプトを含む）．

    ただし，紙に印刷する必要は無く，レポート内には最小限のみを記載した上で，ソース全体はメールに添付の上提出する事．

  • 実行結果．

    無駄に全てを示す必要はなく，第三者が読んでも理解できる程度に，必要十分に示す事．

  • 考察．

    特に学習係数αと微分値が探索に及ぼす影響について考える事． 必要に応じて適切な図表を作成し，理解しやすい考察となるようにする事．

Level 2.1 : y = x
Level 2.2 : y = x2
Level 2.3 : y = -x*sin(x)



3. 不連蔵関数の最適化

Level 3 : 不連続関数における探索手法を検討し，その効率を示せ．

Level 3.1 〜 3.3 に示した関数はステップ関数（不連続関数）であり，微分を活用した解法は適用できない． 解空間（x軸）全てを調べる事なく，一部を調べる事で最適解を求めるにはどうすれば良いか，検討せよ．

コメント
  • 実装は必須ではないが，加点対象とする．
  • 一般的に，組み合わせ最適化問題は問題空間が広すぎるため，「必ず最適解を発見する」という保証は出来ない．今回は，何らかの点で全探索よりも性能が良い事を示せる手法であればOKとする．
  • Level 3.x 毎に特化した手法を検討する必要は無い．一般的に微分が利用出来ない問題（組み合わせ最適化問題）を解く為のアプローチを検討せよ．もしくは，どれか一つに絞ったアプローチについて検討しても良いが，その際には Level 3.2 か 3.3 のどちらかにする事．
  • Level 3.2, 3.3 は要素数の増加に伴い問題空間が指数関数的に増加する．このような問題を組み合わせ最適化問題と呼ぶ．組み合わせ最適化問題の場合には，問題空間があまりにも広大すぎるために「可能な限り無駄な探索を省く事で探索領域を狭め，効率良く良質な解を探し出す」事を目指す必要がある．
注記：レポートには以下の点を含めて考察する事．
  • 問題空間の特徴について
    • 解を構成する要素の増加に伴う問題空間サイズの増加具合を計算量及び図として示す事．
    • 要素数/問題空間サイズと全探索時の実行時間や使用メモリサイズ等の関係．

      適当な性能を持った計算機を明記し，それを利用した場合の時間として構わない．ただし，あまりにも性能が低すぎる計算機ではダメ．実際に計算させようとした時の目安が分かる指標を最低でも1つは示す事．

  • 探索の手続き，フローチャート．
  • 提案手法の利点・欠点．
Level 3.1 : y = x*sin(x) with steps
  • 解 x は整数とする．
  • x が 0...10 の時は問題空間サイズは10である．0...100の時は？
Level 3.2 : ナップサック問題
複数の品物(それぞれの品物は,重さと値段が事なる)が与えられた時,重さがナップサックに入る最大重量以内でなるべく合計の値段が最大になるような品物の組み合わせを求めよ.

  • 品物の数が3個の時，解 x は 001(1つ目をナップサックに入れる），011(1つ目と2つ目をナップサックに入れる）という表現で表すことができる．
  • 品物の数が3個の時の問題空間サイズは？4個の時は？N個の時は？
Level 3.3 : 巡回セールスマン問題
ある2次元空間上のマップにおいて複数の都市が与えられた時，全ての都市を巡回するのに要するコスト（巡回経路長）を最小化せよ．

  • 都市数が3の時，解 x は123（都市1→都市2→都市3），213（都市2→都市1→都市3）という表現で表す事ができる．
  • 都市数が3の時の問題空間サイズは？4都市の時は？N都市の時は？
Level X: どのような組み合わせ最適化問題，または最適化手法があるか？
オプション課題なので，自由に考えてもらって構いません． 先行研究を調べた場合には参考文献（Webの場合はURL）を挙げる事．



参考文献・サイト