ホームページ著作&協力戻る

実践 遺伝的アルゴリズム

書 名実践 遺伝的アルゴリズム
著 者藤原博文
発売日2014年12月5日
発行元オライリー・ジャパン 本書紹介ページ
定 価1800円(税別)
サイズPub mobi (電子出版)
ISBN978-4-87311-707-2

久々に書いたプログラミング関係の本である。 といっても、プログラミング言語の本ではなくて、アルゴリズムのかなり詳細な、かつ実用レベルの実践的な方法を示した本である。

人工知能分野で、最適化問題というのが非常に重要な分野である。 世の中の様々な課題を、ある条件が最適になるように調整するという要求がある。 多数のパラメータを調整し、もっとも良い状態にしなさいとか、条件を満たすようにとにかくパラメータを調整しなさいなどだ。

可変なパラメータ数が少ないうちは、人間が調整してもなんとかなる。 しかし、数が増えてくると、人間ではとても手に負えなくなる。 コンピュータで行うとき、パラメータ数が少なければ手当たりしだい、あるいは総当りで試せばよいのだが、直ぐに限界に達する。 どんなスパコンをもってこようとも、宇宙の歴史より長い時間がかかるようになってしまう。

そういうときでも、なんとか最適のパラメータ、あるいは条件を満たすパラメータを求めてしまおうというのが最適化問題だ。

有名な問題で「巡回セールスマン問題」というのがある。N個の町を順番に回って元に戻ってくるのだが、最短経路で回れというのだ。 なお、簡単のため、任意の2つの町の距離は直線距離で計算してよいものとする。
町の数(点数)が数個なら人手で調べてもなんとかなる。 点数が20以下なら、コンピュータで虱潰しでなんとかなるかも知れない。 でも、50、100、あるいはもっと多数の町になってくるとどうにもならなくなる。

こういうときに、遺伝的アルゴリズムが役に立つ。 ということで、最初に、遺伝的アルゴリズム自体の簡単な解説があるのだが、巡回セールスマン問題を例にして説明してる。

しかし、ここで終わったら、ただの学部生向けの教科書の解説になってしまう。 ということで、実際に遺伝的アルゴリズムを実用的に使っているところを、その後延々と説明している。

このところ、仕事として、パズルの問題を自動生成して、出版社とか、スマホの会社とかに、問題を提供している。 つまり、大量に、要望に沿った問題を安価に、短時間に作って提供しなくてはならない。 しかし、人間が作っていたのでは、手間が大変だし、パズルの問題をどんどん作れるような人は存在しない。 それに、人間が作ったら、問題の作成コストが掛かり過ぎる。

ということで、せっかくコンピュータを使い込んでいるし、最近はコンピュータの性能も向上してきたので、 普通のパソコンで人工知能プログラムを動かしても十分早くなってきたので、自動生成して問題を作っては納品している。 そのパズルの自動生成で非常によく使われるのが、遺伝的アルゴリズムである。

かなり多くのパズルで遺伝的アルゴリズムが有効であることがわかっている。 一番遊ばれているナンプレでもそうである。 ナンプレは簡単なので、通常レベルの問題ならば、遺伝的アルゴリズムを使わなくても大丈夫だが、 極めて実現困難な条件をつけると、遺伝的アルゴリズムが威力を発揮する。 つまり、ナンプレの問題作りでも、いろいろな世界記録に挑戦するようになると、遺伝的アルゴリズムは必須になってくる。

しかし、今回は、ナンプレを取り上げなかった。 ひとつは、既にナンプレの問題の自動生成はあちこちにソースも公開されていて、今更基本的なところから延々と書く気が起きなかったのだ。 それ以前に、ナンプレに飽きている。 パズル問題作成依頼のほとんどがナンプレで、もう作り飽きているのだ。 だから、さらにナンプレの自動生成について書くなど、とうてい考えられないのだ。それは拷問なのだ。

ということで、ナンプレとは傾向の違う問題として、ナンバーエリアという、タイル上の盤面を四角形に分割するパズルにした。 数字だけのパズルよりも、図形的な要素が入るほうが楽しいではないか。

ナンプレを避けた大きな理由は、サイズが9x9の固定であることだ。 多くのパズルが、盤面のサイズが可変なので、ぜひここは盤面が可変で、小さいスマホの画面向けから、 新聞見開き大の問題まで、まったく同じプログラムで対応できるようなものにしたかったのだ。

ナンバーエリアになるには、他にも色々な理由が重なったのだ。 ナンバーエリアに関するプログラミングコンテストがあったのも影響している。 一番影響しているのは、もちろん、ナンプレよりもナンバーエリアの方が気に入っているからだが、 残念なことに、ナンバーエリアはナンプレほど普及していない。

ナンバーエリアは、ニコリは「四角に切れ」の名前で出しているが、比較的やさしい問題ばかりだ。 もう少し上級の手筋も使わないと面白い問題にならないのだが、あえて避けているようだ。 本書では、少ない個数の手筋しか説明していないけれど、ニコリの問題よりも遥かに難しい問題も 短時間で作れてしまうプログラムの作り方を説明している。

なお、プログラムを用いて自動的に問題を作るので、難しい手筋を使っても良いという指定をして自動生成すると、 とても人間には手に負えないような問題も簡単に作れる。つまり超絶難問ナンバーエリアができてしまうのだ。 そういう超絶難問は、いまのところナンプレに関してしか問題を提供していない。

パズルの問題を単に自動生成するだけなら、遺伝的アルゴリズムを使えばたいていのパズルで簡単にできる。 しかし、それでは商用レベルの問題にはならない。 面白さ、美しさ、奇想天外さなど、色々な工夫、仕掛けなどを盛り込まないと商品レベルの問題にはならない。 そのため、本書では、問題が作れるようになった後で、さまざまな特徴有る問題を、遺伝的アルゴリズムを利用して 作る方法を説明している。特徴を、様々な制約条件で指定すると、それらの制約条件を全て満たすような問題を ちゃんと探してくれるようにする方法を、いくつものタイプの違う制約条件で説明している。

遺伝的アルゴリズムによる問題の自動生成の良い所は、やたらに面倒な条件を指定しても、何の文句も言わず延々調べ続けて 条件に合う問題を見つけようとしてくれることだ。 同様のことをプロのパズル作家に依頼しても、とうてい作ってもらえない。 また、一度作成できても、さらに良いものが欲しくなったら、自動生成ならまた走らせれば済むから、 気に入らない問題を気軽に捨てることができる。 これが、パズル作家が手作業で長時間かけて作った場合、そう簡単に捨てられないし、もうちょっと改良して欲しいといっても、 改善するのは甚だ困難である。

あ、こんなに書いてしまったら、誰でも勝手に問題を作れるようになって、注文が来なくなりそうだが、 そうなると暇になって、また好きなことができるようになるかも知れない。

さて、実際はどうなるだろうか?

2014年12月6日


ホームページ著作&協力戻る