『実践 遺伝的アルゴリズム』の紹介

当社の藤原博文が、人工知能の基本技術の一つである遺伝的アルゴリズムについて、理論は最小限に抑え、実装を中心に詳しく説明した電子ブック (EPUB) を出版しました。実装は Java で行っていますが、実装の基本を中心に説明しているので、他言語での実装にもそのまま利用できます。

導入部では、巡回セールスマン問題を例に、実装を説明しています。遺伝的アルゴリズムでは、染色体の交叉と突然変異で最適化を進めていきますが、このとき対象の課題をいかにモデル化することが重要かを、複数のモデルにより比較説明しています。遺伝的アルゴリズムは、モデリングにより性能が大きく左右されます。

本体では、ナンバーエリアという図形的な要素も入り、かつサイズが可変なパズルの問題の自動生成を遺伝的アルゴリズムで実装、改善していく方法を示しています。

第 1 部は準備編です。問題を自動生成しようとしていますが、事前準備として問題を解くこと、問題の難易度を判定することなどが必要になります。そのためにソルバーを作ります。

第 2 部は実装編です。第 1 部で準備したソルバーを利用して、遺伝的アルゴリズムを実装していきます。染色体とは何か、交叉や突然変異をどう処理するかのモデリングを行います。さらに、実際に動かすと、色々なトラブルが発生するので、回避手段を説明しています。遺伝的アルゴリズムは計算量が多く、処理に時間がかかります。そのため、進化状況をモニタリングする方法や、その表示結果も示しています。

第 3 部は応用編です。第 2 部までで一応問題を作れますが、プレイヤーが楽しみ、さらに驚く問題にはなりません。また、難易度を自由に調整できなければいけません。パズルの問題は、パズル作家が作問する場合、さまざまなことを考慮して作られますが、それらの工夫、さらには人間ではとても不可能な面倒な工夫も遺伝的アルゴリズムを応用することで実装しています。

スケジュール問題など、さまざまなことに遺伝的アルゴリズムは使われていますが、多くの実際的な問題では、入力データや制約条件が複雑で、実用レベルのプログラムにするには準備や結果の評価の部分が大半となり、遺伝的アルゴリズム自体の習得を達成しづらくなるので、数理パズルを例に説明しました。

表紙の動物は、国の特別天然記念物、アマミノクロウサギです。