マッチ箱で作るAI（遺伝的アルゴリズム）

AI（人工知能）は人間の知能をコンピュータ上で再現する技術で、遺伝的アルゴリズムを含む様々なアルゴリズムが提案されている。

遺伝的アルゴリズムは生物の進化を模したアルゴリズムで、問題の解を遺伝子で表現して最適解を導き出す。この記事では、マッチ箱を用いて遺伝的アルゴリズムの基本的な仕組みを解説する。

以下の図に示すような簡単な巡回セールスマン問題を解くこと考える。

会社から出発して4件の家を訪問し、最短時間で会社に帰ってくるための最適ルートを求めたい。例えば、ルート「始点→A→B→C→D→終点」は計30分かかるのに対し、ルート「始点→A→C→B→D→終点」は計24分で後者の方が望ましいルートである。

マッチ箱で遺伝的アルゴリズムを表現するため、ルートの各ステップで通過する点の数だけマッチ箱を用意して、以下のように配置する。また、その際に通過する点に対応した本数のマッチ棒をマッチ箱の中に入れておく（下図ではわかりやすいようにマッチ箱の下に表示する）。今回の問題では、マッチ箱の数は４つで、この４つのマッチ箱が遺伝子に対応する。

まずは適当に、マッチ箱遺伝子の集団を用意する。

この集団の中から成績上位の親を２つ選び、これらを交叉して子を作成する。なお、今回の問題では同じ場所を２回以上通ることはできないという制約がある。そこで、交叉は、ランダムに２箇所選んでその部分には一方の親から遺伝子をそのまま書き写し、残り部分は重複のないように他方の親から同じ順番で遺伝子を書き写すことにする。

まず、成績上位の親を２つを選び出す。

次に、ランダムに２箇所選び（下図の赤枠部分）その部分には一方の親から遺伝子をそのまま書き写し、残り部分は他方の親から重複のないように同じ順序で遺伝子を書き写す。

具体的には、子１の赤枠の部分は親１の遺伝子をそのまま書き写し、その他の部分は親２の遺伝子から書き写す。親２の遺伝子は3→4→2→1だったので重複しないように1と4を取り除くと3→2の順になる。したがって、その他の部分にはこの順で遺伝子を書き写す。子２についても同様。

さらに、突然変異として片方の子のみランダムに２つのマッチ箱を入れ替える。

マッチ箱遺伝子の集団から成績下位の２つを排除し、作成した子２つを追加する。

遺伝的アルゴリズムでは上記のような操作（親の選択、交叉、突然変異、世代交代）を何度も繰り返し、より優秀な遺伝子を生成していく。

試しにもう一度、上記の操作を繰り返す。まず、成績上位の親を２つを選び出す。

次に、ランダムに２箇所選び（下図の赤枠部分）その部分には一方の親から遺伝子をそのまま書き写し、残り部分は他方の親から重複のないように同じ順序で遺伝子を書き写す。

さらに、突然変異として片方の子のみランダムに２つのマッチ箱を入れ替える。

マッチ箱遺伝子の集団から成績下位の２つを排除し、作成した子２つを追加する。

以下、同様の世代交代を何ステップか繰り返し、A→C→D→Bが最適解であることを確認する。

現在利用されている遺伝的アルゴリズムでは、効率よく最適解に到達できるように、親の選択、交叉、突然変異などに対して様々な方法が提案されているが、原理的にはマッチ箱遺伝的アルゴリズムとほぼ同じである。