それが僕には楽しかったんです。

僕と MySQL と時々 MariaDB

遺伝的アルゴリズムとその応用

アルゴリズム Java

遺伝的アルゴリズム ~Genetic Algorithm~

遺伝的アルゴリズム(Genetic Algorithm)とは、近似解を探索するアルゴリズム。
主にランダム性を持って要素を変化させる。進化的アルゴリズムの一つでもある。

このアルゴリズムはデータを遺伝子として表現し、一つ一つを個体とする。
その個体を複数用意して、適応度計算をし低いものを交叉や組み換え、突然変異させ解を探っていく。
個体を何世代も変化させていくので、組み合わせ最適化問題(後述)などで効果を発揮する。

遺伝的アルゴリズムの基本原理

遺伝的アルゴリズムの基本原理を説明する。

ここでは n \in \mathbb{N} 個の個体と g \in \mathbb{N}世代で行うと仮定する。

  • 初めに現世代と次世代の個体が入る集合をそれぞれ一つずつ用意しておく。
  • 現世代にn個の個体をランダムに生成する。
  • 評価関数を使用し、現世代の個体が持つ適応度を計算する
  • ある確率において、次の３つのどれかを行い結果を次世代に保存する。これを次世代個体がn個になるまで行う。
    • 個体を２つ選択し交叉させる
    • 個体を一つ選択し、突然変異させる
    • 個体を一つ選択し、そのままコピーする
  • 次世代個体を現世代にコピーし評価し直す
  • これまでの手順をg回繰り返した後、最も適応度の高い個体が解になる確率が高い。

遺伝的アルゴリズムにおける個体操作

これまで出てきたのは次の３つ

  • 選択
  • 交叉
  • 突然変異

選択

選択は自然淘汰をモデル化していて、適応度に基づいて個体を削除したり作成する操作のこと。
この選択の手法として次の３つが挙げられる

  • ルーレット選択
  • ランキング選択
  • トーナメント選択

これらが代表的な選択だが、ここに出てきた選択を使用せず
高い適応度の個体を一定数そのまま残すという手法を取ることでも似た結果が得られる。
ただし、選択アルゴリズムを使うと初期収束の原因になったり
高い適応度の個体を残し過ぎると解の多様性が失われるなどの問題がある。

交叉

交叉、つまり組み換えは個体のもつ情報を組み替え適応度に変化をもたせるもの。
選択では適応度自体が変化する訳ではないので
遺伝的アルゴリズムにおいて交叉は最適解に近づけるための重要な遺伝操作といえる。
この交叉というのにも以下のような種類がある。

  • 一点交叉
  • 二点交叉
  • 多点交叉
  • 一様交叉

交叉は重要な操作であるから、この中から最適なものを選ぶ必要がある。
一番実装しやすいのは1/2の確率で要素を入れ替える一様交叉だと思う。

突然変異

突然変異は選択と同様に、生物に見られる遺伝的な特徴をモデルにしたもの。
選択は生物の自然淘汰がモデルだったのに比べ、突然変異はその名の通り突然変異をモデルにしたものである。

突然変異は交叉や選択に関わらず一定の確率で行う必要があるがその確率は0.1%~1%台が望ましく
高くても数%以内にするべきと言われている。
この確率が高すぎると、遺伝的アルゴリズムではなくちょっと面倒な乱択アルゴリズムになってしまい、最適解に収束しにくくなる。

遺伝的アルゴリズムの問題点

遺伝的アルゴリズムには代表的な問題点が存在する。

  • 初期収束
  • ヒッチハイキング

である。

初期収束

これは最初の方の世代で偶然適応度がものすごく高い個体が生成され。
世代が進むにつれて、その個体が現世代次世代を通して爆発的に増加してしまうこと。
中途半端な段階で収束してしまうと、最適解を得ることが難しくなる。
この時は突然変異の確率や、選択の確率を見直す必要がある。

ヒッチハイキング

交叉において、最適解の生成を妨げる遺伝をしてしまう現象。
これは等確率な交叉を行う一様交叉を使用することで防ぐことができる。

応用例

遺伝的アルゴリズムを使用して、「ナップサック問題」を解いてみる。
これは組み合わせ最適化問題の一つである。

問題

上限が6kgのナップサックに対して値段と重量が以下の品物を入れる。
そのとき、上限重量以下で値段が最高になる組み合わせを求める。

A:1kg 100-yen
B:2kg 300-yen
C:3kg 350-yen
D:4kg 500-yen
E:5kg 650-yen

余談だが、この問題は全探索か貪欲法、動的計画法でも解くことができる。

どの様に遺伝的アルゴリズムを決めるか

個体を10体とする。
適応度計算後、ソートする。
上位50%を下位50%にコピーし、コピーされた個体に交叉と突然変異を行う。
指定された世代まで行う。

今回はこれでいく。

ソースコード

精度があまり高くなく、まだ最適解以外の解も出てしまうがこれが一応遺伝的アルゴリズムを使用したコードになる

import java.util.*;

public class GA implements Algorithm{
	
	final int[] PRICE = {100,300,350,500,650};//yen
	final int[] WEIGHT = {1,2,3,4,5};//kg
	final int MAX_WEIGHT = 6;
	final int NUMBER_GENE = 8;
	final int NUMBER_ITEM = 5;
	final int MUTATE_RATE = 1;
	final char[] NAME = {'A','B','C','D','E'};
	int[][] gene;//individual
	int[][] value;//fitness and price
	
	Random rnd;
	
	static final int GENERATION = 100;
	
	public GA(){
		rnd = new Random();//init instance
	}

	@Override
	public void createIndividual() {
		gene = new int[NUMBER_GENE][NUMBER_ITEM];
		Random rnd = new Random();
		//create first generation
		for(int i = 0; i < NUMBER_GENE; i++){
			for(int j = 0; j < NUMBER_ITEM; j++){
				int init = rnd.nextInt(2);//range 0 to 1
				gene[i][j] = init;
			}
		}
	}

	@Override
	public void calcIndividual() {
		value = initValue();//initialization of this array
		int count_gene = 0,count_item = 0;
		
		for(int i = 0; i < NUMBER_GENE; i++){
			for(int j = 0; j < NUMBER_ITEM; j++){
				if(gene[i][j] == 1){
					value[count_gene][count_item] += PRICE[j];
					value[count_gene][count_item+1] += WEIGHT[j];
					
					if(value[count_gene][count_item+1] > 6){
						//if gene's weight over 6kg,this value become 0
						//and exit this loop
						value[count_gene][count_item] = 0;
						break;
					}
				}
			}
			count_gene++;
		}
	}

	@Override
	public void showIndividual() {
		for(int i = 0; i < NUMBER_GENE; i++){
			System.out.print("GENE."+(i+1));
			for(int j = 0; j < NUMBER_ITEM; j++){
				System.out.print("["+gene[i][j]+"]");
			}
			System.out.print("価値:"+value[i][0]);
			System.out.print("重量:"+value[i][1]);
			System.out.println("適応度:"+value[i][0]);// price = fitness
		}
	}

	@Override
	public void sortIndividual() {
		//value's price = fitness
		int[] sort = new int[NUMBER_GENE];
		for(int i = 0; i < NUMBER_GENE; i++){
			sort[i] = value[i][0];
		}
		
		Arrays.sort(sort);//sorted
		
		int count = 0;
		int[] array2 = new int[NUMBER_GENE];
		
		for(int i = 0; i < NUMBER_GENE; i++){
			for(int j = 0; j < sort.length; j++){
				if(sort[j] == -1)continue;
				if(value[i][0] == sort[j]){
					array2[count] = j;
					count++;
					sort[j] = -1;
					break;
				}
			}
		}
		
		int[][] result = new int[NUMBER_GENE][NUMBER_ITEM];
		int[][] result_of_value = new int[NUMBER_GENE][NUMBER_ITEM];
		
		for(int i = 0; i < NUMBER_GENE; i++){
			result_of_value[array2[i]][0] = value[i][0];
			result_of_value[array2[i]][1] = value[i][1];
			for(int j = 0; j < NUMBER_ITEM; j++){
				result[array2[i]][j] = gene[i][j];
			}
		}
		
		gene = result;
		value = result_of_value;
		
	}

	@Override
	public void selectIndividual() {
		
		int count = NUMBER_GENE/2;
		
		for(int i = 0; i < NUMBER_GENE/2; i++){
			for(int j = 0; j < NUMBER_ITEM; j++){
				gene[i][j] = gene[count][j];
			}
			count++;
		}
		
	}

	@Override
	public void crosserIndividual() {
		
		//first point and second point
		int f = 0;
		int s = NUMBER_ITEM-1;
		
		boolean flag = false;
		
		for(int i = 0; i < gene.length/2; i++){
			flag = (gene[i][NUMBER_ITEM/2] == 1)?true:false;
			if(flag){
				gene[i][NUMBER_ITEM/2] = 0;
				gene[i+gene.length/2][NUMBER_ITEM/2] = 1;
			}else{
				gene[i][NUMBER_ITEM/2] = 1;
				gene[i+gene.length/2][NUMBER_ITEM/2] = 0;
			}
		}
		
	}

	@Override
	public void mutateIndividual() {
		int random = (int)(Math.random()*10);
		for(int i = 0; i < NUMBER_GENE/2; i++){
			if(random <= MUTATE_RATE){
				if(gene[i][NUMBER_ITEM-1] == 0){
					gene[i][NUMBER_ITEM-1] = 1;
				}else{
					gene[i][NUMBER_ITEM-1] = 1;
				}
			}
		}
	}
	
	/**
	 * initialization of value -> array
	 * @return initValue<br>
	 * initialized array
	 * */
	public int[][] initValue(){
		int[][] initValue = new int[NUMBER_GENE][2];
		for(int i = 0; i < NUMBER_GENE; i++){
			for(int j = 0; j < 2; j++){
				initValue[i][j] = 0;
			}
		}
		return initValue;
	}
	
	public static void main(String... args){
		
		//make instance
		GA m = new GA();
		m.createIndividual();//create first generation
		System.out.println("第1世代");
		int count = 0;
		while(count < GENERATION){
			if(count > 0)System.out.println("第"+(count+1)+"世代");
			m.calcIndividual();
			m.sortIndividual();
			m.showIndividual();
			m.selectIndividual();
			m.crosserIndividual();
			m.mutateIndividual();
			count++;
		}
		
		System.out.println("選択したものは");
		
		for(int i = 0; i < m.NUMBER_ITEM; i++){
			if(m.gene[m.NUMBER_GENE-1][i] == 1){
				System.out.print(m.NAME[i]);
			}
		}
        System.out.println();
		
	}
}

/**
 * interface required to implements a genetic algorithm for this problem
 * */
interface Algorithm {
	
	/**
	 * method to generate the initial individual
	 * */
	public void createIndividual();
	
	
	/**
	 * method to calculate the fitness of the individual
	 * */
	public void calcIndividual();
	
	
	/**
	 * method to display the information of the generated individuals
	 * */
	public void showIndividual();
	
	
	/**
	 * method that are sorted in descending order the individual in fitness
	 * */
	public void sortIndividual();
	
	
	/**
	 * method to the selected cull the lower half of the individuals
	 * and want to copy the upper half to the lower half
	 * */
	public void selectIndividual();
	
	
	/**
	 * method to replace the random value is copied to the half in the individual
	 * */
	public void crosserIndividual();
	
	
	/**
	 * method to mutate the value ramdomly
	 * */
	public void mutateIndividual();
}