ホームページ目次2013-06-11(前)2014-09-02(次の話)

遺伝的アルゴリズムでパズル問題の自動生成三昧

2013年9月20日

今年になってから、人工知能の基本技術の1つである「遺伝的アルゴリズム」をいじっている。 このアルゴリズムは、その名の通り、まるで遺伝子、染色体の働きを真似て、色々な面倒な問題を解こうというものだ。

そもそも生命は、なぜこのように進化したのか、偶然が重なったにしては、あまりにも上手く進化している。 これを、コンピュータ上で高速にシミュレーションできれば、さまざまな問題が解けるのではないかという魂胆、下心が、 本アルゴリズムの肝心なところである。

まあ、ようするに、何でも染色体で表現して、2本の染色体を適当に絡み合わせて子供染色体を作ったり、 ときには染色体を適当にぶち壊して、つまり突然変異させたりする。 そんな操作をコンピュータ上で延々と繰り返すと、意味不明の染色体が、いつの間にか意味ある、有意義なものに化けるのだ。

ということで、ちょこっとだけネットで勉強して、プログラムを組み始めた。 適当にやってみたら、不思議な異に、結構上手く行くのだ。

やっていることは、パズルの問題を自動生成である。 ネットの多くの情報は、遺伝的アルゴリズムを使って、パズルを解くというものが多いのであるが、 それにどれだけの意味があるのか分からない。 せっかくの遺伝的アルゴリズムなのだから、問題を作るのに使わなくてどうする、という考えしかこちらはないのだ。

ということで、成果をあちこちでプレゼンしてきたり、飲み屋で説明してきたり、遺伝的アルゴリズムの専門家に会って、 著者の本を持参してサインをもらって来たりした。

プレゼン資料(PDF)もUPした。 4MBくらいあるけれど、今の時代、どうってことないだろう。 内容は、「四角に切れ」と「橋をかけろ」である。

本質的なところは書かれているので、これだけを見て、プログラムを作るのは十分できるのではないかと思う。 ぜひ挑戦してみよう。 できれば、他のパズルの自動生成にチャレンジしてみよう。 ちょっと性能をよくすれば、パズル作家以上の問題を作るのもそんなに難しくは無い。 ただし、調整には、パズル、プログラム、人工知能(遺伝的アルゴリズム)について知る必要があるが。


ホームページ目次2013-06-11(前)2014-09-02(次の話)