- HOME
- 研究
- サイエンス&テクノロジー
- 進化するプログラム —遺伝的アルゴリズムは人間を超えるか—
進化するプログラム —遺伝的アルゴリズムは人間を超えるか—
コンピュータ理工学部 インテリジェントシステム学科 岡田 英彦准教授
遺伝的アルゴリズムは人間を超えるか
コンピュータプログラムは仕事の手順書のようなものです。プログラムによってコンピュータはさまざまなデータを処理することが可能になっていますが、一般的には人間の手でよりよい手順書が与えられます。もし人間のように自ら学び、自ら問題を解決するようなプログラムが作られたとしたら私たちの世界はどのように変わるのでしょうか。岡田先生が研究しているのは、生物の進化を工学的に真似た遺伝的アルゴリズム(GA−Genetic Algorithm)。このアルゴリズムのしくみと応用について、ロボカップサッカーを例にお話いただきました。
ロボカップサッカー —シミュレーションリーグ
「2050年にサッカーの世界チャンピオンに勝てる、自律型ロボットのチームを作る」ことを目標に、人工知能やロボット工学などの研究を推進しているロボカップサッカー※1。研究の実験・発表の場として競技会形式の国内大会、世界大会が毎年行われています。
切符の券売機を例にとってみると、ユーザインタフェースはどうすれば切符が買いやすくなるか、使い勝手のよい券売機を研究すること。一方、そもそも切符を買わずに電車に乗れたらもっとよいだろうと、プリペイドカードやICOCAなどのICカードを考え出すのがHCIの分野だといえるでしょう。発想を転換することで新しい乗車システムを考えるのです。
このうち研究の題材にしているのは、コンピュータ内の仮想フィールドで人工知能プログラミングされた選手同士が対戦するシミュレーションリーグ。ボールがどの位置にあれば取りに行く、相手選手がどのくらいの位置に来たらパスを出すなど選手ごとにパラメータ※2を自由に設定することができ、強くて賢いチームを作るべくさまざまな研究がなされています。
※1 「2050年にサッカーの世界チャンピオンに勝てる、自律型ロボットのチームを作る」ことを目標に人工知能やロボット工学などの研究を推進し、さまざまな分野に応用させることを目的としたランドマーク・プロジェクト。国内大会は現在、シミュレーションリーグ、マイクロロボットサブリーグ、小型ロボットリーグ、中型ロボットリーグ、スタンダードプラットフォームリーグ、ヒューマノイドリーグにわかれている。
※2 選手の動作を制御するために設定する値。
遺伝的アルゴリズム(GA)を使った自ら強くなるチーム
シミュレーションリーグでの主な研究は、「強い」チームになるように、選手の個人技や選手間の連携などの工夫を考えて、その工夫をプログラム化する方法です。けれどもそれでは人間の発想内にとどまりますし、サッカーのプロではない我々がチャンピオンに勝つのは難しいでしょう。人は練習や学習を重ねて成長します。プログラムも同じように自ら“強く”なれないものでしょうか。
そこで考えたのが、生物の進化の過程をもとに考え出された遺伝的アルゴリズムを使う方法です。生物は親から遺伝子を受け継ぎ、自然淘汰を繰り返すことで環境に適した遺伝子を残します。この進化の過程をヒントにして考えられたGAを使い、チーム1つを生物1匹に見立てて自然淘汰のシミュレーションを行うことで、チームが進化していく(強いチームだけが生き残り、より強いチームを生み出していく)ことができるのではないかと考えたのです。チームのなかには11人の選手がいますので、それらの選手がもっているパラメータをひとまとめにしたものが、そのチームの染色体です。パラメータの値が変われば選手の動作の仕方が変わりますので、パラメータの値の決め方次第で、強いチームにも弱いチームにもなります。
GAの主な流れは図1の通りです。初めに、パラメータの値をランダムに決めたチームを数多く作ります。ランダムに決めるだけですので、この時点では、「どういう値にすれば強くなるか」ということを知っている必要はありません。続いて、淘汰を行うためには、各チームの強さを調べなければなりません。強いチームだけを生き残らせるためです。そこで、人間が考えて作ったサンプルのプログラムをいくつか用意しておき、そのチームと試合をさせます。試合結果の得点と失点を見て、互いのチームの強さを判断します。子を残すことができるのは強いチームだけです。親となるチームを選抜し、親同士を交こう叉さ させることで新しい世代(子)を作り出します。最後に、一定の確率でパラメータをランダムな値に置き換える突然変異を加えます。
突然変異を加えるのは、強い親チーム同士から生まれる子チームが、互いに似たようなチームばかりに偏ってしまうことを避けるためです。別の値が混じることによって、もっとよいチームが生まれる可能性が出てくるのです。この①初期世代作成→②強さの評価→③選択→④新世代作成→⑤突然変異→②〜⑤→…を何世代も繰り返してチームを進化させていきます。
単目的GA
簡単な実験も行っています。初期世代を30チーム作り、強さの評価のために、3つのサンプルチームと対戦させました。得点は多く失点は少ないチームほど「強い」と評価します。一方だけがよくてもあまり高くは評価されません。親チームから子チームを作る交叉の方法としては、図2のような「一点交叉」という方法を使いました。親チームは、30チームのなかで上位にいるチームほどより高い確率で選ばれる「ルーレット選択法※3 」で選びます。これを30世代繰り返しました。
チーム数も世代数も少ない実験でしたが、チームの進化をある程度示す結果が出ました。また、対戦相手であるサンプルチームが攻撃重視型の場合は失点を抑えるような進化が、守備重視型の場合は得点を増やすような進化がそれぞれ見られました。実世界での生物の進化は環境の変化に合わせて進みますが、同じことが、ロボカップサッカーのチームにGAを適用した場合にも起こったということです。
このシミュレーションでは、30チームの強さの順位づけを、サンプルチームと対戦したときの得点・失点で決まる1つの数値(得失点差のようなもの)に基づいて行っていました。このように、1つの評価基準で個体の順位を決め、その評価基準の値がよりよくなるよう進化させるGAは「単目的GA」と呼ばれています。
※3 左のようなルーレットを作成し、ランダムに次世代に残す個体を決める選択方法。強いチームほど幅が広く選ばれる確率が高くなるが、弱いチームであっても選択される可能性がある。
多目的GA
サッカーチームが進化する過程のなかで、「10対11で負けたチームA」と、「2対1で勝ったチームB」の2チームがあったとします。勝敗だけを見ればチームBのほうが「強いチーム」であり、試合に負けたチームAは、生き残れない(次の世代に子を残せない)かもしれません。しかし、チームAは試合には負けましたが10点もの大量点数をとることができています。したがって、チームAの遺伝子には「得点を多くとる」のに有効な特徴が含まれている可能性が大きいと考えられます。このチームAの遺伝子は、次の世代に「もっと得点をとれるチーム」を作ることに役立つかもしれません。
「単目的GA」のときには、得点と失点の両面を平均的に見て強さの順位を決めていたので、Aのようなチームをあまり高く評価できませんでした。そこで、Aのようなチームは「得点能力の高いチーム」として、Bのようなチームは「失点防止能力の高いチーム」 として、どちらも順位を高く評価する方法を考えました。このように、評価の観点を1つに絞らず複数の観点で評価するようなGAは「多目的GA」と呼ばれます。
今度は、この「多目的GA」を用いてシミュレーションを行いました。対戦相手には強いチームも弱いチームも含めて使いました。チーム数は60に、世代数は100世代以上に増やしました。また、交叉の方法は「一様交叉」(図2)に変更しました。60チームは世代が進むにつれて、得点主義のチーム、失点防止主義のチーム、得点・失点バランス主義のチームに分化しながら進化していきました(図3)。つまり、多目的GAを用いることで、いろんな特徴をもったチームへと進化させられることがわかったのです。
チーム単位から選手単位へより複雑なGAへ
ひと昔前に人工知能(AI − Artificial Intelligence)がさかんに研究された時の方法は、人間のプロから思考や行動のルールを聞き出してそれをプログラムするものでした。このAIは一見プロと同じような優秀な働きをしますが、ルールのなかで想定されていない状況になると応用が利きません。最近のAI研究ではコンピュータが数ある情報から役立つ知識を見つける(=学習する)ことや知識をもとに新しい結論を得る(=推論する)ことに重きが置かれています。
GAも学習アルゴリズムの一種と考えることができます。生物であれば何万年とかかる進化の過程をコンピュータは得意な計算パワーを使って瞬時に繰り返し、最適な結果を導こうとします。ロボカップサッカーでは初期世代を強いチームから始めることもできます。しかし、サッカーのことを何も知らないまま勝手に強くなるチームを作ることができたら他にも応用が利きそうですから、ランダムな値から始めて結果を出したいと思っています。
これまでに行ってきた研究では、まだ、評価尺度は試合結果のみ、対象もチーム単位です。しかし、実際の評価尺度はこれだけではありません。シュート回数、パス成功回数、アシスト回数、パスのインターセプト回数、ボールの保持時間など、多岐に渡ります。これらの観点からも評価を行うためには、対象を選手単位にする必要があるでしょう。評価方法はかなり複雑になりますが、今後進めていければと考えています。
GAを使った他の研究
稼げるロボット――株ロボ
ロボカップサッカーと同じ方法で研究しているのが、株の売買をするプログラム。「株ロボ」と呼ばれています。GAを用いてシミュレーションを繰り返すことで人間が思いつかないような新しい株売買ルールをもったプログラムができるかもしれません。人間を超える稼げるロボットが育つかどうか、目下研究中です。
誰でも作曲家に――自動作曲
音楽は音符の並びで表されます。その音符の並びを遺伝子に見立ててGAを適用することで、人の好みにあうように音楽を進化させることが可能になってくるでしょう。コンピュータがランダムに作った曲を人間が聴いてそのなかからよいと思う曲を選び、「よい曲」を親としてコンピュータが次の曲を生成します。このようなサイクルを繰り返せば、次第に、その人の好みにあった曲へと進化していくことが期待されます。音符、楽譜、楽器などの知識がまったくない人でも着メロやBGMなどを作れるようになれば面白いと考えています。
アドバイス
学生のひらめきから新しい研究も
高校生のみなさんには、大学に入ったら「こんなことを学びたい」「この先生の所でこんな研究をしてみたい」といった将来のビジョンをもって進学してほしいと期待しています。何かを「研究」してみることに興味があってチャレンジ精神豊かな人は大歓迎です。私も学生諸君と一緒に進めることでいろいろな研究ができますし、新しい研究が生まれることもあります。
これまでにも例えば、メガネのように装着してコンピュータの画面を表示する「ヘッドマウントディスプレイ(HMD)」を使った研究にチャレンジしたいとの学生のアイデアが、人が見ている視界にコンピュータが情報を重ね合わせ表示する「拡張現実感ユーザインタフェース」を応用したシステムの研究につながりました。トランプゲームへの応用例では、人が自分の手札や卓上のカードを見ているとき、その見ているカードについての情報(カードの強さなど)や、いまとるべき手の情報(どのカードを手札から捨てるべきかなど)を、視界に重ね合わせて表示します。このシステムを使えば、トランプゲームのルールをよく知らなくてもそのゲームを行うことができ、ゲームをしながらルールを自然に覚えられるようになりました。これと同じ技術を使って、英語の文書を読むとき、人が紙面上で見ている英単語の日本語訳をその英単語の近くに重ね合わせ表示するシステムも開発しました。
コンピュータ理工学部 インテリジェントシステム学科 岡田 英彦准教授
- プロフィール
-
博士(工学)。マンマシンインタフェースの研究や、GAのような知的計算アルゴリズムの応用の研究などに取り組んでいる。