GA により 2 変数関数の最小値を求める

データ例，プログラム

　　以下，複数のファイル構成になっています．ファイル間の区切りを「---･･･」で示します．

-------------------------i_data-------------------------
世代交代数 3000 乱数の初期値 123 関数 1 出力 300
個体数 20 子供の数 20 遺伝子長 20
エリート 2 突然変異率 0.03

-------------------------program-------------------------
/****************************/
/* ２変数関数の最小値       */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.StringTokenizer;
import java.util.Random;


public class Test {
	public static void main(String args[]) throws IOException
	{
		double mute;
		int fun, gen, max_gen, o_lvl, seed, size, child, len, elite;
		String str;
		StringTokenizer dt;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
					// データの入力
		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		max_gen = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		seed = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		fun = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		o_lvl = Integer.parseInt(dt.nextToken());

		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		size = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		child = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		len = Integer.parseInt(dt.nextToken());

		str = in.readLine();
		dt  = new StringTokenizer(str, " ");
		dt.nextToken();
		elite = Integer.parseInt(dt.nextToken());
		dt.nextToken();
		mute = Double.parseDouble(dt.nextToken());
					// 種の定義
		Species a = new Species(size, child, len, seed);
					// 初期設定
		gen = 0;
		a.I_std();
                    // 個体の評価
		a.Adap(fun);
					// 初期世代の出力
		if (o_lvl > 0)
			a.O_std(gen, 20);
					// 実行
		for (gen = 1; gen <= max_gen; gen++) {
						// 交叉
			a.C_unifm(0, 1.0);
						// 突然変異
			a.M_alle(mute);
						// 適応度の計算
			a.Adap(fun);
						// 淘汰
			a.S_roul(elite);
						// 出力
			if (o_lvl > 0 && gen%o_lvl == 0)
				a.O_std(gen, 20);
		}
					// 最終出力
		if (o_lvl == 0)
			a.O_std(gen-1, size+1);
	}
}

/*************************/
/* クラス Species の定義 */
/*************************/
class Species {
	private double pi[];   // 適応度
	private double ro[];   // ルーレット板
	private int size;   // 個体総数
	private int max_ch;   // 子供の数の最大値
	private int len;   // 遺伝子長
	private byte ind[][];   // 集団（個体の集まり）
	private byte pi_w[];   // 適応度計算指標
                           //   =0 : 未使用
                           //   =1 : 適応度計算前（突然変異はこの個体だけに適用）
                           //   =2 : 適応度計算済み（交叉時に親とみなす）
	private byte s_w[];   // 淘汰用指標（選択された回数）
	private Random rn;   // 乱数

	/****************************/
	/* コンストラクタ           */
	/*      s : 個体総数        */
	/*      mc : 子供の数       */
	/*      mx : 遺伝子長       */
	/*      seed : 乱数の初期値 */
	/****************************/
	Species(int s, int mc, int mx, int seed)
	{
		int i1, num;
	/*
	     乱数の初期設定
	*/
		rn = new Random(seed);
	/*
	     値の設定
	*/
		size   = s;
		max_ch = mc;
		len    = mx;
	/*
	     領域の確保
	*/
		num  = size + max_ch;
		ind  = new byte [num][2*len];
		pi   = new double [num];
		pi_w = new byte [num];
		s_w  = new byte [num];
		ro   = new double [num];
	}

	/*********************************/
	/* 標準出力                      */
	/*      gen : 現在の世代         */
	/*      out : n>0 : ｎ個ずつ出力 */
	/*********************************/
	void O_std(int gen, int out)
	{
		double cv = 5.0 / (Math.pow(2.0, (double)len) - 1.0), x, y, w;
		int count = 0, i1, i2, num = 0;

		System.out.println("第 " + gen + " 世代");

		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 0) {

				num++;
				System.out.print(num + " ");

				x = 0.0;
				w = 0.0;
				for (i2 = len-1; i2 >= 0; i2--) {
					if (ind[i1][i2] > 0)
						x += Math.pow(2.0, w);
					w += 1.0;
				}
				x *= cv;

				y = 0.0;
				w = 0.0;
				for (i2 = 2*len-1; i2 >= len; i2--) {
					if (ind[i1][i2] > 0)
						y += Math.pow(2.0, w);
					w += 1.0;
				}
				y *= cv;

				System.out.print(x + " " + y);

				if (pi_w[i1] > 1)
					System.out.println(" 適応度 " + pi[i1]);
				else
					System.out.println();

				count++;
				if (count == out)
					count = 0;
			}
		}
	}

	/************/
	/* 初期設定 */
	/************/
	void I_std()
	{
		int i1, i2, i3, sw1, sw2;
	/*
	     適応度
	*/
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (i1 < size)
				pi_w[i1] = 1;   // 適応度の計算前
			else
				pi_w[i1] = 0;   // 未使用
		}
	/*
	     染色体
	*/
		for (i1 = 0; i1 < size; i1++) {
			sw1 = 0;
			while (sw1 == 0) {
	                              // 遺伝子の決定
				for (i2 = 0; i2 < 2*len; i2++)
					ind[i1][i2] = (rn.nextDouble() > 0.5) ? (byte)1 : (byte)0;
	                              // 重複個体のチェック
				sw1 = 1;
				for (i2 = 0; i2 < i1 && sw1 > 0; i2++) {
					sw2 = 0;
					for (i3 = 0; i3 < 2*len && sw2 == 0; i3++) {
						if (ind[i1][i3] != ind[i2][i3])
							sw2 = 1;
					}
					if (sw2 == 0)
						sw1 = 0;
				}
			}
		}
	}

	/**************/
	/* 親のコピー */
	/**************/
	void C_copy()
	{
		int i1, i2, k, p, p1, p2 = 0, sw;
                         // 親の選択
		p1 = select();
		sw = 0;
		while (sw == 0) {
			p2 = select();
			if (p1 != p2)
				sw = 1;
		}
                         // コピー
		for (i1 = 0; i1 < 2; i1++) {
			p       = (i1 == 0) ? p1 : p2;
			k       = position();
			pi_w[k] = 1;
			for (i2 = 0; i2 < 2*len; i2++)
				ind[k][i2] = ind[p][i2];
		}
	}

	/*******************************************************/
	/* 交叉（一様交叉．[0,1]を等確率で発生させ，1であれば，*/
	/*       親１，0であれば親２の遺伝子を子１が受け継ぐ） */
	/*      pair : 親のペア数                              */
	/*      pr : 交叉確率                                  */
	/*******************************************************/
	void C_unifm(int pair, double pr)
	{
		int i1, i2, k1, k2, p1, p2 = 0, sw;
	/*
	     初期設定
	*/
		if (pair == 0)
			pair = max_ch / 2;
	/*
	     交叉
	*/
		for (i1 = 0; i1 < pair; i1++) {
                         // 交叉しない場合
			if (rn.nextDouble() > pr)
				C_copy();
                         // 交叉する場合
			else {
                              // 親の選択と子供を入れる場所
				p1 = select();
				sw = 0;
				while (sw == 0) {
					p2 = select();
					if (p1 != p2)
						sw = 1;
				}
				k1       = position();
				pi_w[k1] = 1;
				k2       = position();
				pi_w[k2] = 1;
                              // 交叉
				for (i2 = 0; i2 < 2*len; i2++) {
					if (rn.nextDouble() > 0.5) {
						ind[k1][i2] = ind[p1][i2];
						ind[k2][i2] = ind[p2][i2];
					}
					else {
						ind[k1][i2] = ind[p2][i2];
						ind[k2][i2] = ind[p1][i2];
					}
				}
			}
		}
	}

	/**************************************/
	/* 突然変異（対立遺伝子との置き換え） */
	/*      pr : 突然変異率               */
	/**************************************/
	void M_alle(double pr)
	{
		int i1, i2;

		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] == 1) {
				for (i2 = 0; i2 < 2*len; i2++) {
					if (rn.nextDouble() <= pr)
						ind[i1][i2] = (rn.nextDouble() > 0.5) ? (byte)1 : (byte)0;
				}
			}
		}
	}

	/*************************************/
	/* 淘汰（エリート・ルーレット選択）  */
	/*      elite : エリートで残す個体数 */
	/*************************************/
	void S_roul(int elite)
	{
		int i1, i2, i3, k = 0, max, n = 0, p, sw;
	/*
	     初期設定
	*/
		for (i1 = 0; i1 < size+max_ch; i1++)
			s_w[i1] = 0;
	/*
	     重複個体を削除
	*/
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 0) {
				for (i2 = i1+1; i2 < size+max_ch; i2++) {
					if (pi_w[i2] > 0) {
						sw = 0;
						for (i3 = 0; i3 < 2*len && sw == 0; i3++) {
							if (ind[i1][i3] != ind[i2][i3])
								sw = 1;
						}
						if (sw == 0)
							pi_w[i2] = 0;
					}
				}
			}
		}

		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 1)
				n++;
		}

		if (n == 0) {
			System.out.println("***error  残す個体がない (S_roul)");
			System.exit(1);
		}
	/*
	     淘汰して残す個体を選ぶ
	*/
                         // エリートの選択
		sw = 0;

		while (k < elite && k < n && sw == 0) {
			max = -1;
			for (i1 = 0; i1 < size+max_ch; i1++) {
				if (pi_w[i1] > 1 && s_w[i1] == 0) {
					if (max < 0 || pi[i1] > pi[max])
						max = i1;
				}
			}
			if (max < 0)
				sw = 1;
			else {
				s_w[max] = 1;
				k++;
			}
		}
                         // ルーレット選択
		int count = 0;

		while (count < size+max_ch && k < size && k < n) {
			p = select();
			if (s_w[p] > 0) {
				sw = 1;
				count++;
			}
			else {
				count = 0;
				s_w[p]++;
				k++;
			}
		}
                                   // 選択に失敗した場合の処理
		if (k < size && k < n) {
			for (i1 = 0; i1 < size+max_ch && k < size && k < n; i1++) {
				if (pi_w[i1] > 1 && s_w[i1] == 0) {
					s_w[i1] = 1;
					k++;
				}
			}
		}
                              // 複数回選択されたものの処理
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (s_w[i1] == 0)
				pi_w[i1] = 0;
		}

		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (s_w[i1] > 0) {
				if (s_w[i1] > 1) {
					for (i2 = 2; i2 <= s_w[i1]; i2++) {
						k       = position();
						pi_w[k] = 2;
						pi[k]   = pi[i1];
						for (i3 = 0; i3 < 2*len; i3++)
							ind[k][i3] = ind[i1][i3];
					}
				}
			}
		}
	}

	/************************/
	/* 適応度の計算         */
	/*      sw : 関数の種類 */
	/************************/
	double Adap(int sw)
	{
		double cv = 5.0 / (Math.pow(2.0, (double)len) - 1.0), max = 0.0, x, x1, x2, x3, y, w;
		int i1, i2, k = -1;

		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] == 1) {

				x = 0.0;
				w = 0.0;
				for (i2 = len-1; i2 >= 0; i2--) {
					if (ind[i1][i2] > 0)
						x += Math.pow(2.0, w);
					w += 1.0;
				}
				x *= cv;

				y = 0.0;
				w = 0.0;
				for (i2 = 2*len-1; i2 >= len; i2--) {
					if (ind[i1][i2] > 0)
						y += Math.pow(2.0, w);
					w += 1.0;
				}
				y *= cv;

				pi_w[i1] = 2;
				switch (sw) {
					case 1:
						x1     = x - 1.0;
						x2     = y - 2.0;
						pi[i1] = -x1 * x1 - x2 * x2;
						break;
					case 2:
						x1     = y - x * x;
						x2     = 1.0 - x;
						pi[i1] = -100.0 * x1 * x1 - x2 * x2;
						break;
					case 3:
						x1     = 1.5 - x * (1.0 - y);
						x2     = 2.25 - x * (1.0 - y * y);
						x3     = 2.625 - x * (1.0 - y * y * y);
						pi[i1] = -x1 * x1 - x2 * x2 - x3 * x3;
						break;
				}
			}

			if (pi_w[i1] > 0 && (k < 0 || pi[i1] > max)) {
				max = pi[i1];
				k   = 1;
			}
		}

		return max;
	}

	/************************/
	/* 空いている場所を探す */
	/************************/
	int position()
	{
		int i1, k = -1;

		for (i1 = 0; i1 < size+max_ch && k < 0; i1++) {
			if (pi_w[i1] == 0)
				k = i1;
		}

		if (k < 0) {
			System.out.println("***error  空いている場所がない --position--");
			System.exit(1);
		}

		return k;
	}

	/**************/
	/* 個体の選択 */
	/**************/
	int select()
	{
		double sum, x;
		int i1, k, n = 0, sw;
	/*
	     ルーレット版の用意
	*/
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 1)
				n++;
		}
		sum = 1.0 / n;
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 1)
				ro[i1] = sum;
		}

		sum = 0.0;
		for (i1 = 0; i1 < size+max_ch; i1++) {
			if (pi_w[i1] > 1) {
				sum    += ro[i1];
				ro[i1]  = sum;
			}
		}
	/*
	     選択
	*/
		x  = rn.nextDouble();
		sw = 0;
		k  = 0;
		for (i1 = 0; i1 < size+max_ch && sw == 0; i1++) {
			if (pi_w[i1] > 1) {
				if (x <= ro[i1]) {
					sw = 1;
					k  = i1;
				}
			}
		}

		return k;
	}
}
		

　　提示したプログラムは，以下に示す 3 つの 2 変数関数の最小値を求めるためのものです．一様交叉，一般的な突然変異，及び，エリート＋ルーレット選択を使用しています．

1. f = (x - 1)² + (y - 2)²　　最小値：(1,2) で 0.0
2. f = 100(y - x²)² + (1 - x)²　　最小値：(1,1) で 0.0
3. f = (1.5 - x(1 - y))² + (2.25 - x(1 - y²))² + (2.625 - x(1 - y³))²　　最小値：(3,0.5) で 0.0

コンパイルした後，入力データ記述ファイル「i_data」を適当に修正し，コマンドラインから，

java Test < i_data

と入力してやることによって実行できます．

　　入力データ記述ファイル「i_data」は，例えば，以下のように記述します．

世代交代数 1000 乱数の初期値 12345 関数 1 出力 100
個体数 20 子供の数 20 遺伝子長 20
エリート 2 突然変異率 0.03		

　　上に示した各データにおいて，日本語の部分は次に続くデータの説明になっていますので，数字の部分だけを修正してください．日本語の部分を変更しても構いませんが，削除したり，間に半角のスペースを入れるようなことはしないでください．各データの意味は以下に示す通りです．

• 世代交代数 1000　　最大世代交代数を入力します．

• 乱数の初期値 12345　　乱数の初期値を入力します．

• 関数 1　　対象とする関数を指定します．上述の a，b，及び，c の各関数に対応し，1，2，または，3 を入力します．

• 出力 100　　何世代毎に各個体の状態を出力するかを入力します．この例の場合，100世代毎に出力されます．

• 個体数 20　　集団サイズを入力します．

• 子供の数 20　　交叉で生成される子供の数を入力します．

• 遺伝子長 20　　各変数毎の遺伝子長です．

• エリート 2　　エリートとして残す個体数です．残りは，ルーレット選択で選択されます．

• 突然変異率 0.03　　突然変異率です．