Function/service/ga - Nimbus Wiki - Nimbus

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

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

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

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

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

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

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

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

• jp.ossc.nimbus.service.ga

アプリケーション向けインタフェース GeneticAlgorithm

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

 import java.util.Random;
 
 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(10000);
 gene1.setMinValue(10);
 genom.addGene(gene1);
 
 // 遺伝子２を生成する
 IntegerGene gene2 = new IntegerGene();
 gene2.setName("2");
 gene2.setMutateRate(0.01f);
 gene2.setRandomRangeMargin(0.3f);
 gene2.setMaxValue(100);
 gene2.setMinValue(1);
 genom.addGene(gene2);
 
 // 種を生成する
 Seed mySeed = new MySeed(genom);
 
 // GeneticAlgorithmを取得
 GeneticAlgorithm ga  = (GeneticAlgorithm)ServiceManagerFactory.getServiceObject("GeneticAlgorithm");
 
 // 世代を跨いだ生存競争を行う
 Seed survivor = ga.compete(new Random(), mySeed, 10, true);
 
 // 生存者の適応値を取得する
 System.out.println(survivor.getFitness());

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

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

GeneticAlgorithm向けインタフェース SeedMatchMaker

インタフェースSeedMatchMakerは、GeneticAlgorithmが、世代内競争の結果から交配によって次世代の種を作るために、交配処理を委譲します。

このインタフェースの実装サービスは、下位サービスで、以下の上位サービスから使用します。

上位サービス	用途
jp.ossc.nimbus.service.ga.GeneticAlgorithm	種を交配させるために使用する

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

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

GeneticAlgorithm向けインタフェース ConvergenceCondition

インタフェースConvergenceConditionは、GeneticAlgorithmが、最終世代を決めるために、適応値の収束の判断を委譲します。

このインタフェースの実装サービスは、下位サービスで、以下の上位サービスから使用します。

上位サービス	用途
jp.ossc.nimbus.service.ga.GeneticAlgorithm	適応値の収束を判断させて、最終世代を決定するために使用する

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

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

サンプルは、以下。

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