History: Function/service/ga - Nimbus - Nimbus

[フレームワーク]遺伝的アルゴリズム

アプリケーション開発において、計算式に複数の変数が含まれ、変数の取り得る値の組み合わせが膨大で、総当たりによる最適解を導くのが困難な問題を解く必要がある場合があります。
そのような膨大な計算量が必要な問題を、限られたリソース（計算能力や時間）で解く方法の一つに遺伝的アルゴリズムがあります。

遺伝的アルゴリズムでは、計算式内の変数を遺伝子（Gene）と呼び、その遺伝子を纏めたものを遺伝情報（Genom）と呼びます。
その遺伝情報を使って、ある遺伝情報における解を求める式を種（Seed）と呼びます。

まず、乱数を使って、様々な異なる遺伝情報を持った複数の種を生成します。この複数の種の集合を世代（Generation）と呼びます。
次に、世代内でそれぞれの種の解を求め、優秀な解を出す種を生き残らせます。
生き残った優秀な解を持つ種同士を交配させて、新たな種を作り出します。但し、生き残りの遺伝情報を交配させ続けると、解が偏ってしまい局所解に収束して、最適解に近づかなくなる可能性があります。そのため、交配の際に、一定の確率で突然変異を発生させる事で、局所解に陥る可能性を低減させます。
交配によって生まれた種の集合で、新たな世代を作り、また生存競争を行う。
この繰り返しによって、最適解に近い解を導き出す方法を、遺伝的アルゴリズムと呼びます。

この方法では、必ずしも最適解が導ける訳ではありませんが、最適解に近い解を、比較的短時間で、少ない計算量で導き出す事が可能になります。

遺伝子を表すインタフェースが、Gene。
遺伝情報を表すインタフェースが、Genom。
種を表すインタフェースが、Seed。
世代を表すインタフェースが、Generation。
種同士の交配のを行うインタフェースが、SeedMatchMaker。
世代競争のアルゴリズムを表すインタフェースが、GeneticAlgorithm。
世代競争の収束を決める条件を表すインタフェースが、ConvergenceCondition。

アプリケーション開発者は、Seedの実装を開発して、このフレームワークに投入する事で、最適解に近いSeedを獲得する事ができます。

関連するパッケージは、以下です。

• jp.ossc.nimbus.service.ga

インタフェース GeneticAlgorithm

インタフェースGeneticAlgorithmを使った簡単なアプリケーションのサンプルを示します。

 import jp.ossc.nimbus.core.ServiceManagerFactory;
 import jp.ossc.nimbus.service.ga.DefaultGenom;
 import jp.ossc.nimbus.service.ga.IntegerGene;
 import jp.ossc.nimbus.service.ga.Seed;
 import jp.ossc.nimbus.service.ga.GeneticAlgorithm;
 
 // 遺伝情報を生成する
 DefaultGenom genom = new DefaultGenom();
 
 // 遺伝子1を生成する
 IntegerGene gene1 = new IntegerGene();
 gene1.setName("1");
 gene1.setMutateRate(0.01f);
 gene1.setRandomRangeMargin(0.3f);
 gene1.setMaxValue(100);
 gene1.setMinValue(10);
 genom.addGene(gene1);
 
 // 遺伝子２を生成する
 IntegerGene gene2 = new IntegerGene();
 gene2.setName("2");
 gene2.setMutateRate(0.01f);
 gene2.setRandomRangeMargin(0.3f);
 gene2.setMaxValue(10);
 gene2.setMinValue(1);
 genom.addGene(gene2);
 
 // 種を生成する
 Seed mySeed = new MySeed(genom);
 
 // GeneticAlgorithmを取得
 GeneticAlgorithm ga  = (GeneticAlgorithm)ServiceManagerFactory.getServiceObject("GeneticAlgorithm");
 
 // 世代を跨いだ生存競争を行う
 Seed survivor = ga.compete(random, mySeed, 10, true);
 
 // 生存者の適応値を取得する
 System.out.println(survivor.getFitness());

実装サービスの一覧は以下のとおりです。

実装サービス	実装概要
jp.ossc.nimbus.service.ga.SimpleGeneticAlgorithmService	デフォルト実装

サンプルは、以下。

• サンプル１：遺伝的アルゴリズムを使ってみよう。