締め切り

第一回レポート（第1問～第6問）：12月23日の２３：５９まで。

第二回レポート（第7問～第12問）：2月4日の２３：５９まで。

注意事項

• 講義の内容により変更の可能性がある。最終的な内容は必ず講義の際に確認すること。
• 各回で提出する課題数は任意であるが、最低数は1問である。 問題の難易度を印で示しているので、提出の際の参考にすること。 簡単な問題であれば2問以上を提出することがのぞましい。
• 原則として、締切日より遅れて提出された場合は 採点の対象としない。 ただし、何らかの理由があれば、 締め切りまでに提出したレポートについて更新・修正版をのちに 提出することは認めることがある。
• また、特段の理由があれば提出期限を延長する。
• 東大サーバーの不調などにより、提出用サイトにアクセスできないことがあるようです。そのため余裕をもって提出してください。締め切り直前にその事象が発生した場合にはITC-LMSに提出してください。

レポート採点方針

• 当然ながら提出したからといって満点とは限らない。
• とりあえず適当に書いて提出するというのは印象が悪いので注意せよ。
• 最終評価は合計点をもとにした相対評価となる。
• 難しい問題に挑戦したり、多くの人が解かないような問題を解答すると ポイントが高い。
• ＡＩらしいユニークな解答も評価する。
• 参考までに★で難易度を示しておく。

課題内容

1. （第1問：課題番号01★） 講義で説明したようにノーベル化学賞はゲームAIに関連している。
   その詳細はこのHPなどに詳しい。
   
   では、Folditを遊んでみてその実体験を報告せよ。 ただし 個人の責任でゲームに参加すること。
   
   とくに、
   
   • ゲームに直観が有効だったか
   • 本格的な科学に貢献できる意識があったか
   • 共同作業・闘争意識の効果はあるか
   • 将来のAIの応用に貢献するか
   について具体的な例（画面のスナップショットやデータ・記録）を示して、 詳しく考察することが必要である。
   
   Hint1: Foldit!の解説は 教科書 の6.1節にある。
   Hint2: 説明のスライドはここにある。また、Foldit!をもとにしてNatureに掲載された論文はここにある。
   
   
2. （第2問：課題番号02★★）
ヒトは類推推論が得意である。 教科書の2.2節にあるように、講義では以下のような例を説明した。
• IQテストにおける幾何学的類推問題
• 大火事の消火とガンの放射線治療法
• カードの裏表問題
• 法的推論とAI
• 教育における類推の効果
• ブーバ・キキ効果

（１）LLM(大規模言語モデル)でも類推推論が解けるらしい。自分で工夫して考えた問題で実際に実験してみよう。
ただし著名な問題はLLMに学習されているので注意すること。さまざまなChain of Thoughtや呪文を工夫してみよ。

（２）これらをふまえて、ヒトの知能とLLMとの類似性・違いを考察せよ。 また今後「強いAI」を実現するために、どのようなデータを集めて研究すべきか、類推推論の必要性などについて論述せよ。参照した文献、引用文献、出典は必ず文献リストに挙げること。

Hint: 以下の論文などが参考になる。
• 類推推論のためのpromptについてはこの論文のFig.1を参照せよ
• ConceptARC Benchmark



3. （第3問：課題番号03★）次の2問にすべて答えること。
1. 進化計算の原理を身近な例を用いて分かりやすく説明せよ。少なくとも以 下の項目についてアナロジーで解説すること。
• 交叉
• 突然変異
• 世代交代
• 集団初期化
• 選択・淘汰
• 適合度計算
• 探索が上手くいくようす
図と例証を用いて示すと良い。 講義では、飛行機、鉄道、動物などの例を用いた。 オリジナルでないものは採点しない。
2. 進化計算の面白い応用例・実用例について調べて考察せよ。
講義などで説明した例や以下のような著名な例は除く。
• 遺伝的アルゴリズムでブランコの漕ぎ方を学習させた動画
• 進化するマリオのお話
• 対話型似顔絵作成システムNIGAO
• グラディウスを学習させてみた
• 機械学習する物理エンジンの豚
• 自転車の形状と車輪の進化的設計
• GAでモナリザを描く
• Mondriaan Art by Evolution on the Web
• オノマトペ自動生成システム
• 遺伝的アルゴリズムを用いてハイハイを学習させる
• 顔モルフ
• 畝見先生のSBART(抽象画生成)
• Synplant「遺伝を利用したソフトウェアシンセサイザ」
• 『グリムノーツRepage』から見る遺伝的アルゴリズムのゲームバランス調整における事例とその可視化
• 進化計算をオープンハウスの宅地自動区割りに活用
• 物流センター在庫配置最適化
• 三菱電機のZEB（net Zero Energy Building）における設備運用最適化およびアスクルの在庫配置最適化の事例
• 放送局CM順位づけ業務に「進化計算ダーウィン」を導入
• 対話型進化計算を利用したネックレスデザインシステム
• sakanaAIの進化的アルゴリズムによる基盤モデルの構築

なおこの課題で求めているのはわかりやすいデモや応用であり、 学術論文や技術的詳細ではない。
実応用例については、 特許・新聞記事・論文などの出典とともに、どのように応用されているかをわかりやすく平易な言葉で説明すること。


4. （第4問：課題番号04★★）
ナイト・ツアー（教科書の例題3.2 ）というパズルを考えよう。教科書ではチェス盤の上に置かれたナイトをあるマスから他のマスに移動させる解法について説明した。なおナイトは下図のように最大８箇所の●の部分に移動できる．



ここではチェスのナイトの動きによって２個の数を互いに入れ替える操作を繰り返して、初期の配置から目的の配置に移行させるパズルを扱う。たとえば以下のようにナイトは動いて数を交換する。

最初のナイトの位置 1 2 3 4 5 6 7 8 9

Step1 6 2 3 4 5 1 7 8 9

Step2 6 2 3 4 5 7 1 8 9




（１）次の配置換えについての解を探索せよ。ただし最初のナイトの位置は右下（１の位置）とする。 A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率（解に到達するまでのノー ドの展開数）を比較すること。

初期状態 8 2 4 9 5 6 7 3 1

目標状態 1 2 3 4 5 6 7 8 9


（２）次の4x4の初期状態から始めて目的状態を探索するプログラムを作成せよ。ただし最初のナイトの位置は１のコマとする。 A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率（解に到達するまでのノー ドの展開数）を比較すること。

初期状態 10 1 12 4 5 13 7 9 15 3 2 6 11 14 8 16

目標状態 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16




（３）任意の4x4の初期状態から始めて目的状態を探索するプログラムを作成せよ。ただし最初のナイトの位置は１のコマとする。この問題では複数のナイト を順に動かしても良い。例えば、最初は１のナイトをいくつか動かし、次に３のナイトを動かすのも可能である。
A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率（解に到達するまでのノー ドの展開数）を比較するとよい。

初期状態 16 12 8 4 15 11 7 3 14 10 6 2 13 9 5 1

目標状態 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16




講義で説明した以下のプログラムを拡張するとよい。
• 8パズル（深さ優先探索）
• 8パズル（広さ優先探索）
• 8パズル（Ａ＊探索）

自分でA*用の（効果的な）ヒューリスティックスを考えて実験してみよう。



5. （第5問：課題番号05★★★）
ノーベル化学賞はタンパク質のフォールディング問題の解法によるものであった。これに関連してHPモデル格子型構造予測問題を自分で考案したアルゴリズムで解いてみよう。
2次元でのHP配列の最適な構造の探索に関してはさまざまに研究されていて、公開されているプログラムも多い。

ではこの配列を3次元で最適化してみよ。実験結果については、実行時間と成績（見つけたHH結合数）を報告すること。
GA,GP,NN,ACO,ABCなどどのようなものでもよいが、 オリジナルなアイディアが含まれているとなおよい。
まずは同じ問題を2次元で解き、それを拡張して3次元で解くのがよい。当然ながら、3次元での最適化の方が2次元よりもHH結合数は多くなるはずである。

配列の例としては以下の問題に挑戦するか、任意の配列を入力としてもよい。
• 配列20 (HP)2PH2PHP2HPH2P2HPH
• 配列48 P2HP2H2P2H2P5H10P6H2P2H2P2HP2H5
• 配列48 HPH2P2H4PH3P2H2P2HPH2PHPH2P2H2P3HP8H2
• 配列48 PHPH2P2HPH3P2H2PH2P3H5P2HPH2(PH)2P4HP2(HP)2
• 配列48 PH2P6H2P3H3PHP2HPH2(P2H)2P2H2P2H7P2H2
ただし、配列nは長さnの配列を示し、 数字は前の文字か文字列（括弧のとき）の繰り返しを示す。 例えば、(HP)2 -> HPHPなどとなる。

Hint: この論文にACOを用いた例と問題の詳細がある。


6. （第6問：課題番号06★★★）
平面上に23個の点をできるだけ「美しく」配置せよ。
23という数の個性をどのように生かして探索したのかについて説明すること。
見やすくなるために必要なら補助線（曲線）を書き加えよ。

• 例えば、10個の点であれば以下のようなものが考えられる。

  

• 進化計算を推奨するが、ニューラルネット、強化学習、その他のAI手法で探索してもよい。
• 評価関数（「美しさ」の基準、適合度）を工夫すること。例えば、対称性の個数、直線状に並んだ数、思いつきにくさ、希少性、力学的エネルギ―最小化などが考えられる。
• 個性を生かすことが重要なので、他の点数でも配置可能なもの（円周上、直線上など）はポイントが低い。
• 他の個数の点でも同様に面白くなってはいけない。 得られた結果がどのように面白いかを考察したかも重視する。
• 必ずしも最適解(?)が得られなくても成績評価には関係しない。 どれだけ工夫したか、考察したかで評価する。
• AI探索が目的なので、LLMに聞いたというような解答は原則的に認められない。

Hint: たとえば対話側進化計算（IEC）で配置を進化させる試みがある。これを拡張しても良い。 IECによる23点配置の進化のunityでのデモプログラムはここにある。

---

7. （第7問：課題番号07★） ヒトは確率推論が必ずしも得意ではない。またランダム性の認識に関しても間違えやすい。これらのことから、 スティーブン・ピンカー は「人間は合理性に反して、ある事象に明確な原因があると断定することがある」と述べている。では、LLM(や生成AI)とヒトはどのように違うのだろうか。これについて、自分の経験や検証実験などを通して考察せよ。
   少なすぎるもの・内容がないものは採点しない。
   以下のような手順をとること。
   
   （１）LLM(や生成AI)でいくつかの確率的推論を試す。promptや呪文、CoTなどさまざまに試して、答え方の違いや錯覚（hallucination）に注目すること。有名な問題例を直接使うとLLMは訓練例からそのまま回答する可能性があり、有用なデータが得られない。そのため 自分で工夫して実験を行うこと。
   （２）ヒトについての生データが以下にある。これらのいくつかを集計・整理する。すべてのデータを利用することはない。各自で取捨選択して回答すること。ヒトのコメントの錯覚部分が重要かもしれない。
   • 山田さん夫妻のこども
   • ヒカリムシとランダム点列
   • 落雷確率
   • 株価
   （３）以上をもとにして、LLM(や生成AI)とヒトにおける確率推論の類似性・相違点について考察せよ。 とくに、 スティーブン・ピンカー や ダニエル・デネット らの批判（「ベイズ推定や確率モデルをもとにした機械学習や深層学習では強いAIは造れない」）について思うところ（反論もしくは賛同など）を述べよ。
   （４）このような実験に関して今後工夫すべき点について考察せよ。例えば、LLMにどのような質問をすればよいか、ヒトに対してどのようなアンケートを集めるべきか、など。
   
   Hint1: ランダム性の錯誤（星座・ヒカリムシとランダムドット）、ギャンブラーの誤謬、ロンドンの爆撃については 参考書 の3.2節に説明されている。
   
   Hint2: 参考書 の2章、3章にある以下のような問題を利用すると良い。このうちの一部についてはアンケートや講義で説明している。当然ながら有名な問題をそのまま利用すると、解答例がLLMにあるので注意すること。
   
   • 乳がんの危険性
   • 山田さん夫妻のこども
   • 落雷の確率
   • ３囚人の問題
   • モンティホール問題
   • Truel

8. （第8回問：課題番号08★★） 講義で説明したRBN（ランダム・ブーリアン・ネットワーク）に関する実験をしてみよう。 以下のようなパラメータをさまざまに設定してみること。
   • ノード数（４～７程度）
   • ノードの次数（２、３、４）
   • コンスタント関数の有無
   • ネットワークのトポロジー（つながりかた）
   これにより、アトラクタ（周期的振る舞い）がどのように生成するかを観察せよ。 次の図のような推移図を表示・構成すると分かりやすい。

   

   

   
   さらに、次のような点について実験結果から考察すること。
   • どのようなリミットサイクルの長さが観測されるか？
   • 点アトラクタ（１つだけの吸収状態）の観測可能性
   • ランダム関数を（一定の条件で）確率的に変動させるとどうなるか？
   • 点アトラクタ数の平均値が1になることの検証
   • 生命や脳のモデルとしての可能性、とくに「カオスの縁の生命」という考え方の是非について

   Hint1: 講義で説明した実験プログラム(RBN,確率RBN)は ここにある。

   Hint2: RBNの解説は 教科書の3.1節にある。

9. （第9回問：課題番号09★） 講義では人間のリスク認知の偏りやヒューリスティックスとしてのプロスペクト理論について説明した。 では、LLM(や生成AI)も同じような認知や知覚の偏りを示すのであろうか？ 実験的に検証してみよう。
   少なすぎるもの・内容がないものは採点しない。
   以下のような手順をとること。
   
   （１）質問をLLM(や生成AI)に対して行い、promptや呪文・CoTなどさまざまに工夫して答え方の違いを観察する。
   とくに 無関係な選択肢からの独立性や一億円のチャンスおよび 最後通牒ゲーム について面白そうな題材を試すとポイントが高い。
   また、講義で説明したフレーミング効果、授かり効果、損失回避、Rabinの定理、アレのパラドクスなどに関する検証をするとよい。
   なお、有名な問題例を直接使うとLLMは訓練例からそのまま回答する可能性があり、有用なデータが得られない。そのため 自分で工夫 した例で検証すること。
   （２）ヒトのデータと比較して、ヒトとLLM(や生成AI)との認知の相違点・類似性について考察せよ。 これらをふまえて、LLMを実世界（金融やマーケットなど）に応用するときの課題・問題点を考慮すると良い。
   （３）このような実験に関して今後工夫すべき点について考察せよ。例えば、LLMにどのような質問をすればよいか、ヒトに対してどのようなアンケートを集めるべきか、など。
   
   Hint1: 講義資料は ここ にある。プロスペクト理論については 参考書 の６章に、最後通牒ゲームについては同じ本の4.5節において説明されている。
   Hint2: ヒトに対するデータは、上の講義資料に書かれている。また関連するアンケートデータは以下にある。適宜集計や編集して使用してほしい。
   • 新聞購読のおとり広告
   • ラビンの定理
   • 一億円のチャンス
   • 最後通牒ゲーム
   Hint3: GPTにプロスペクト理論が適応するかについて調べた研究論文が ここにある。また、プロスペクト理論を想定した金融やマーケットにLLMを利用する研究は ここにある。

10. （第10問：課題番号10★★） メタヒューリスティクスには、数多くの手法が 提案されている。たとえば以下のようなものがある。これらのいくつかは講義で説明した。
    • Artifical Bee Colny (ABC)
    • Ant colony optimization (ACO)
    • Particle Swarm Optimization (PSO)
    • カッコウ探索：Cuckoo search　
    • Harmony Search (HS)
    • カエル探索：Shuffled Frog-Leaping Algorithm (SFLA)
    • Honey-Bee Mating Optimization (HBMO)
    • Invasive Weed Optimization (IWO)
    • Teaching-Learning-Based Optimization (TLBO)
    • ホタル探索：Firefly Algorithm (FA)
    • コウモリ探索：Bat Algorithm (BA)
    • Plant Propagation Algorithm (PPA)
    • Water Cycle Algorithm (WCA)
    • Symbiotic Organisms Search (SOS) algorithm
    • Harris hawks optimization (HHO)
    • Black Hole Algorithm (BHA)
    • Fruit fly optimization algorithm (FOA)
    • Ant lion optimizer (ALO)
    • Moth-flame optimization algorithm (MFO)
    • Elephant herding optimization (EHO)
    • Coral reef optimization
    • Monarch butterfly optimization
    • Egyptian Vulture Optimization
    • Lion swarm optimization
    • ネコ探索：Cat swarm optimization
    • ゴキブリ探索：Cockroach Swarm Optimization
    • バクテリア探索：Bacterial Foraging Optimization
    • 灰色オオカミ探索：Grey Wolf Optimiation (GWO)
    • 花火アルゴリズム：fireworks algorithm
    • クジラ探索：Whale optimization algorithm
    • リス探索：Squirrel search algorithm
    • 重力探索：Gravitational search algorithm (GSA)
    • ひらめき探索：Brain Storm Optimization (BSO)
    • 集団心理療法探索：Group Counseling Optimization (GCO)

    

    
    なお、メタヒューリスティックス研究に関しては、玉石混交であったり、同じような手法の重複提案であるような批判もなされている。その詳細は 『深層学習とメタヒューリスティクス ディープ・ニューラルエボリューション（6.8節）』 にある。
    ここでは、LLM(や生成AI)に基づいて新しいメタヒューリスティックを提案し、実際にコード化をして動作確認をしてみよう。 以下の手順にしたがうこと。
    

    （１）LLMにメタヒューリスティックスの例を３～６個程度あげさせて、その詳細について説明してもらう。特定のキーワードをpromptに入れた方がよい。例：大域的探索のため、群知能、組み合わせ探索、など。

    （２）（１）であげられたそれぞれのアルゴリズムに関して、重要な特徴や探索性能に影響を与える要素に関して説明させる。それの妥当性について考察せよ。幻覚症状（hallucination）に注意すること。

    （３）特定のタスクに対して、（１）であげられたメタヒューリスティックスのハイブリッド版やそれらの改良版を提案させる。それについて説明させ、pseudo-codeやpython codeを出力させる。特定タスクとしては、TSPやNクィーンのような具体的な問題などでよいが、有名な問題には解答例がLLMにあるので面白くない。より一般的な探索問題として指定することを奨励する。
    Hint: promptとしては、「多様性を維持せよ」、「exploration(探査)とexploitation(利用)の効果的なバランスをとれ」、「局所解に陥らない」、「目的関数の評価回数をできるだけ少なくする」など講義で説明した探索に重要な要素を入れるのが好ましい。

    （４）実際にpseudo-codeを実行させてLLMの提案を検証する。（３）で想定したタスクを実際に解かせてみる。その上で、fatal　error（明確なバグ）があるか・修正可能か、実行レベルでの性能、計算効率、すでにあるメタヒューリスティックスとの比較、などについて考察せよ。

    なお、ここではLLMを利用してメタヒューリスティックスのハイブリッド法や新手法を提案することを目指しているので、得られたメタヒューリスティックスが不十分であっても問題ない。むしろ、LLMを利用する場合の有用性や欠点、拡張点を考察してほしい。

    
    Hint1: メタヒューリスティックスについて、最近の解説には以下のような論文がある。
    1. Crow Search Algorithm: Theory, Recent Advances, and Applications
    2. Sea Lion Optimization Algorithm for Solving the Maximum Flow Problem
    
    Hint2: LLMでメタヒューリスティックスのアルゴリズムを創る論文は ここ にある。

11. （第11問：課題番号11★★★） 講義ではアリのフェロモンによる効率的な探索について説明した。 しかしながらこれは一面であり、それほど簡単ではないことが知られている。 例えば、アリはそれほど勤勉ではなくサボるのがいるとされている。それぞれのアリの働き始める閾値が違う。 その研究については以下に詳しい。
    1. 働かないアリに意義がある
    2. 社会性昆虫のコロニーの中に遺伝的基盤を持つ非協力系統が存在（総合文化研究科土畑研・虫ラボ）
    
    では、これに関してシミュレーションで検証してみよう。
    以下のようにするとよい。
    1. アリの数を限定する。各アリの働き始める閾値をランダムに決める。
    2. 閾値の低いアリから餌集めに従事する。
    3. 餌集めの効率が下がると閾値の高いアリが餌集めをし始める。
    
    頑強性(餌の数や位置への変化、障害物の出現、部分的なアリの消滅などへの頑強性)を比較すると良い。
    
    なお、「怠ける 」の定義に注意すること。巣にとどまるアリと定義すると、単にアリ数を変えることになってあまり面白くない。よって、疲労・休息を考えて、閾値の低い勤勉なアリに疲労がとどまり休息するなどと現実的な仮定になるだろう。
    
    ただし、必ずしも的確に比較できなくても成績評価には関係しない。 どれだけ工夫したか、考察したかで評価する。
    
    Hint: アリのフェロモン・トレイルのシミュレーションプログラムは以下で提供している。 その他にもいろいろとあるので、各自の得意な環境を探すとよい。
    1. アリの知恵（6.1節）
    2. Ant Simulation by Python
    3. Swarmの教科書の9.7節。上のシミュレーションのJava版コード。Swarmのインストールが必要なので、アルゴリズムを参考にする程度が望ましい。

12. （第12問：課題番号12★★★） メタヒューリスティックスを用いた多目的最適化のシミュレータを作成せよ。 2次元のパレートフロントをうまくとらえられるかを実験してみよう。

    以下のいずれかの手法を１つ以上(できれば２つ)用いること。

    • ANN (Artificial neural networks)
    • ACO (Ant colony optimization)
    • Gravitational search
    • ABC (Artificial bee colony)
    • GWO (Grey wolf optimizer)

    講義で説明した多目的最適化のVEGAシミュレータは ここにある（java executable file）。 またシミュレータの使用方法はここにある。 javaソースファイルははここにある。

    以下に述べられている例題か自分で考えた面白い例題を試すこと。 パレートフロントが異なる問題（凸型フロント、凹型フロントなど）の実験を行って 結果を観察するとよい。

    • 多目的最適化例題集
    • 多目的最適化の分かりやすい説明と例題のある論文

    探索で得られたパレート解の 精度に対する評価指標としては以下の2つを用いるとよい。

    • 優越個体割合（Ratio of Non-dominated Individuals: RNI）
    • 解の多様性の評価指標として被覆率（Cover Rate: CR）詳しくはこの資料を参照。
    
    Hint1: VEGAのアルゴリズムとシミュレータの解説は この本の5.6節にある。
    Hint2: 以下の論文などが参考になる。
    • 多目的ANN(1)
    • 多目的ANN(2)
    • 多目的ACO
    • 多目的Gravitational search
    • 多目的ABC
    • 多目的GWO

提出方法

以下のものを提出すること。提出方法はここに示す通りである。

• プログラムを作成した場合、 実現したシステムに関する説明（どの部分をどう創意工夫したかなど）。さら にアルゴリズム、ソースリストの説明。
• 結果の表示（グラフなどを用いると分かりやすい）。
• 結果に関する考察と評価。
• 授業に関するコメント、要望など（次回の参考にするので是非書いて下さい）。