簡単な遺伝的アルゴリズム - Step 1

GA クラスライブラリ

このステップでは、遺伝的アルゴリズム(GA)を Java によって実現するための、基本的なクラス群を説明します。実際の問題に応用する場合は、これらのクラスを利用したり、拡張したりして使います。

ここで説明する GA クラスライブラリは、以下のクラスから構成されています。

これらのクラスのうち、実際に GA を使う上で理解する必要があるのは Gene と GA です。ソートに関するクラスは GA とは直接関係ありませんが、余裕があれば理解した方がいいでしょう。

戻る


Sortable インターフェイス

ソースコード

このインターフェイスは、QSort によって並べ替えることができるクラスが実装するべきインターフェイスです。このインターフェイスには次の2つのメソッドがあります。

メソッド 説明
boolean isBefore(Sortable s) 与えられた Sortable よりも前にあるべきかどうか。例えば、数値を小さい順位並べたいときは、< がそれにあたります。
boolean isAfter(Sortable s) 与えられた Sortable よりも後にあるべきかどうか。例えば、数値を小さい順に並べたいときは、> がそれにあたります。

クラス QSort では、これらのメソッドが返す値を手がかりにして、Sortable の配列を並べ替えます。

ページの先頭


QSort クラス

ソースコード

クイックソートアルゴリズムを使用して、Sortable の配列を並べ替えるクラスです。このクラスのメソッドはすべてクラスメソッドであり、静的にアクセスできます。

このクラスには、以下の3つのメソッドがあります。

メソッド 説明
static int partition(Sortable[] a,int i,int j) Sortable の配列 a の i 番目から j 番目までの要素をクイックソートで並べ替えるときの、分割軸を探します。
static void quickSort(Sortable[] a,int l,int r) Sortable の配列 a の l から r までの範囲をクイックソートにより並べ替えます。このメソッドは再帰的に呼び出され、その範囲内のすべての要素を並べ替えます。
static void sort(Sortable a) Sortable の配列 a 全体をクイックソートにより並べ替えます。

ページの先頭


Gene クラス

ソースコード

遺伝子を表すクラスです。この遺伝子は byte の配列として表現されています。

遺伝子の長さはこのクラスのインスタンスの生成時に指定して、固定です。遺伝子中の各染色体がどのような意味を持つかは応用する問題に応じて変化しますのでこのクラスでは定義されません。また、256種類以上の染色体を必要とするような問題へは、このクラスは対応できません。その場合は、int の配列にでも変えるとよいでしょう。

このクラスは以下のメンバを持ちます。

メンバ 説明
byte[] chromosome 遺伝子の染色体配列です。与えられた長さの byte の配列として表現されます。
double fitness この遺伝子の適応度です。この値が大きいほどよい遺伝子です。

また以下のメソッドを持ちます。

メソッド 説明
Gene(int n) 長さ n の遺伝子を生成します。遺伝子中の染色体はすべて0に初期化されています。
Gene(Gene g) 与えられた遺伝子 g と全く同じ遺伝子を生成します。このメソッドは遺伝子の複製を作る場合に使用されます。
Object clone() この遺伝子の複製を生成して返します。このクラス自体は抽象クラスであるためインスタンスを生成できません。よって、このメソッドも抽象メソッドです。
void calcFitness() この遺伝子の適応度を計算します。適応度は、応用する問題によって計算方法が異なるので、このメソッドは派生クラスでオーバーライドする必要があります。抽象メソッドです。
double getFitness() この遺伝子の適応度を得ます。
boolean isBefore(Sortable s) 遺伝子を並べ替えるときの比較を行います。
boolean isAfter(Sortable s) 遺伝子を並べ替えるときの比較を行います。
byte getRandomChromosome() ランダムな染色体を得ます。デフォルトでは byte 型の取りうる範囲でランダムに生成します。このメソッドをオーバーライドすることにより、必要な範囲に限定することができます。
void initRandom() この遺伝子をランダムに初期化します。
static void onePointCrossover(Gene g1,Gene g2) g1 と g2 とを1点交叉します。
static void flatCrossover(Gene g1,Gene g2,double p) g1 と g2 とを一様交叉します。p は入れ替える確率です。
void mutate(int n) 突然変異を起こします。与えられた数値 n 個の染色体をランダムに変化させます。
String toString() 遺伝子を文字列として表現します。2桁の16進数で表現されます。

この遺伝子クラス Gene は実際は抽象クラスであり、そのままではインスタンスを作ることはできません。応用する場合はこのクラスを継承して具体的な遺伝子クラスを作成して使います。応用例は Step2 以降を見てください。

このクラスで重要なメソッドは交叉と突然変異に関するもの、および適応度に関するものです。つまり、calcFitness(),getFitness(),onePointCrossover(),flatCrossover(),mutate() は重要です。

calcFitness() メソッドは抽象メソッドです。つまり、このメソッドはこのクラスでは定義されず、派生クラスによって定義されることが要求されています。このメソッドは、遺伝子の適応度を計算します。遺伝子は自分自身の適応度を保持する fitness というメンバ変数を持ちますから、このメソッドでは、必要な適応度を計算して fitness に格納します。適応度の計算は、応用する問題によって異なります。どういう遺伝子が「よい」遺伝子なのかを、何らかの方法で数値化できる必要があります。

getFitness() は、その遺伝子が現在持っている適応度を返します。実際は fitness の値を返すだけです。

onePointCrossover() は1点交叉を行います。このメソッドはクラスメソッドであり、静的にアクセスできます。与えられた2つの遺伝子を、ランダムに選ばれた点を境にして、それより後を入れ替えます。g1 と g2 の2つの遺伝子を与えた場合、

新しい g1 = (古い g1 の前) + (古い g2 の後)

新しい g2 = (古い g2 の前) + (古い g1 の後)

となります。どこで切られるかは、その都度、ランダムに決められます。

flatCrossover() は一様交叉を行います。このメソッドも静的にアクセスできます。一様交叉では、与えられた2つの遺伝子の染色体1つ1つについて、入れ替えるかどうかを確率 p に基づいて決めます。例えば p=0.5 ならば、2つの遺伝子はほぼ半分ずつ混ざります。

mutate() は突然変異を起こします。このメソッドは整数値 n を取り、染色体のうち n 個をランダムに変えます。このときの変化には getRandomChromosome() メソッドが使われます。ただし、重複して同じ染色体が2回変わったりすることもあります。

ページの先頭


GA クラス

ソースコード

このクラスは、与えられた遺伝子集団に対して、遺伝アルゴリズムを実行します。

このクラスは以下のメンバを持ちます。

メンバ 説明
Gene[] gene 遺伝的アルゴリズムを適用する遺伝子集団です。
Gene[] gene_tmp 選択処理の際に、一時的に選択した遺伝子を格納するための配列です。本クラスでは、選択処理後、この配列と gene とを入れ替えることで、コピーする時間を節約します。

また、以下のメソッドを持ちます。

メソッド 説明
GA(Gene[] gene) 遺伝子集団を与えて生成するためのコンストラクタです。
Gene getElite() 最も適応度の大きい遺伝子(エリート)を探して返します。線形探索を行います。
Gene doTournamentSelect(int n) トーナメント方式の選択処理を行います。トーナメント候補として、ランダムに n 個の遺伝子を選びます。
Gene[] select(int n) エリート保存、n-トーナメント方式の選択処理を行います。選択処理の結果、gene と gene_tmp が入れ替わりますので、新しい gene を返します。このメソッドを呼び出した側では、遺伝子集団を個のメソッドが返す値に変更します。
void crossover(int ty) 指定した方式で交叉します。ty=0 ならば1点交叉、ty=1 ならば一様交叉です。
void mutate(int n,int m) 指定した個数だけ突然変異します。全遺伝子集団の中から n 個の遺伝子を選び、それぞれの遺伝子の m 個の染色体をランダムに変更します。
void print(PrintStream ps) 遺伝子集団を表示します。

通常、遺伝的アルゴリズムを応用する場合、必要な個数の遺伝子集団を作り、それを与えて本クラスを作ります。そして、本クラスの select(),crossover(),mutate() を繰り返して実行します。応用プログラムの大まかな流れは以下のようになります。

Gene[] g=new Gene[N];		// 遺伝子集団を生成
for(int i=0;i<N;i++)
  g[i]=new MyGene();		// 各遺伝子を生成
GA ga=new GA(g);			// 遺伝アルゴリズムを生成

for(int c=0;c<MAX;c++){

  // 何らかの方法で各遺伝子を評価

  ga.select(3);			// 選択
  ga.crossover(0);		// 交叉
  ga.mutate(1,1)			// 突然変異
}

具体的な応用例は、Step2 以降を見てください。

ページの先頭