/* S1050.java
 *        ナップザック問題 
 *         (C) H.Ishikawa 2008 
 */

package simulation;

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.text.DecimalFormat;

import window.Window;

public class S1050 extends Applet implements ActionListener {
	Button button0;
	public void init() {
		button0 = new Button(" 再実行 ");
		add(button0);
		button0.addActionListener(this);
	}
	
	public void actionPerformed(ActionEvent e) {
		String label = e.getActionCommand();
		repaint();
	}

	public void paint(Graphics g){
		Window w ;
		w = new Window();
		
		int SPACE = 40;
		int HIGHT = 400;
		int WIDTH = 640;
		
		int			LENGTH	=	40;				/* 染色体の長さ */
		int			SIZE	=	10;				/* 集団の大きさ */
		double		MAX_WEIGHT	=	10.0;		/* 品物の重量の最大値 */
		double		MAX_VALUE	=	10.0;		/* 品物の価値の最大値 */
		double		LIMIT	=	100.0;			/* ナップザックに入る重量の限界値 */
		int			G_END	=	2000;			/* 繰り返し数 */
		double		PROB	=	0.01;			/* 突然変異の確率 */
		double		PROB2	=	0.5;			/* 初期化の確率 */
		int			gene[][]	=	new int[2*SIZE][LENGTH];		/* (1)染色体 */
		int			next_gene[][]	=	new int[2*SIZE][LENGTH];	/* (2)新世代の染色体 */
		double		weight[]	=	new double[LENGTH];			/* 品物の重量 */
		double		value[]	=	new double[LENGTH];				/* 品物の価値 */
		double		total_weight[]	=	new double[2*SIZE];		/* 重量の合計 */
		double		total_value[]	=	new double[2*SIZE];		/* 価値の合計 */
		int			v_sort[]	=	new int[2*SIZE];				/* 順番 */

		long		generation;					/* 世代を表すforのカウンタ */
		int			k,l;						/* gene[k][l]のためのforのカウンタ */
		int			l_rand;						/* 交叉位置 */
		int			k_sort;						/* ソート用のforのカウンタ */
		int			i_swap;						/* スワップ用変数 */
		double		swap;						/* スワップ用変数 */	
        int			line = HIGHT;				/* 表示行 */
        DecimalFormat exFormat1 = new DecimalFormat("0");
        
		/* グラフィックの準備 */
		w.setWindow(0,  0.0,0.0,G_END,120,
	            SPACE,HIGHT/2-SPACE/2,WIDTH-SPACE,SPACE);
		w.axis(0, "generation", G_END / 10, "weight", 20, g);
		w.moveTo(0, 0.0, 0.0, g);
		w.setWindow(1,  0.0,0.0,G_END,250,
	            SPACE,HIGHT-SPACE,WIDTH-SPACE,HIGHT/2+SPACE/2);
		w.axis(1, "generation", G_END / 10, "value", 50, g);
		w.moveTo(1, 0.0, 0.0, g);

		/* (3)染色体のイニシャライズ */
		for (k = 0 ; k < SIZE; k ++) {
			for (l = 0; l < LENGTH; l ++) {
				if (Math.random() < PROB2){
					gene[k][l] = 1;
				}
			}
		}
		
		/* (4)品物の重さと価値の設定 */
		for (l = 0; l < LENGTH; l ++) {
			weight[l] = MAX_WEIGHT * Math.random();
			value[l]  = MAX_VALUE * Math.random();
		}
		  
		  
		  
		/* (5)メイン始まり */
		for (generation = 1; generation <= G_END; generation ++) {

			/* 交叉 */
			for (k = 0; k < SIZE; k = k + 2) {
				l_rand=(int)(Math.random() * LENGTH);  /* (6)交叉位置 */
				for (l = 0; l < l_rand; l ++) {
					gene[k+SIZE][l] = gene[k][l];
				}
				for (l = l_rand; l < LENGTH; l ++) {
					gene[k+SIZE][l] = gene[k+1][l];
				}
				for (l = 0; l < l_rand; l ++) {
					gene[k+1+SIZE][l] = gene[k+1][l];
				}
				for (l = l_rand; l < LENGTH; l ++) {
					gene[k+1+SIZE][l] = gene[k][l];
				}
			}

			/* (7)突然変異 */
			for (k = SIZE ; k < 2 * SIZE; k ++) {
				for (l = 0; l < LENGTH; l ++) {
					if (Math.random() < PROB) {
						gene[k][l] = 1 - gene[k][l];
					} 
				}
			}

			/* (8)目的関数の計算 */
			for (k = 0; k < 2 * SIZE; k ++) {
				total_weight[k] = 0.0;
				total_value[k] = 0.0;
				for (l = 0; l < LENGTH; l ++) {
					total_weight[k] = total_weight[k] + gene[k][l] * weight[l]; /* (9) */
					total_value[k] = total_value[k] + gene[k][l] * value[l];    /* (10) */
				}
				if (total_weight[k] > LIMIT) {
					total_value[k] = 0.0;         /* (11) */
				}
			}

			/* (12)ソート */
			for (k = 0; k < 2 * SIZE; k ++) {
				v_sort[k] = k;
			}
			for (k = 0; k < 2 * SIZE; k ++) {
				for (k_sort = k + 1; k_sort < 2 * SIZE; k_sort ++) {
					if (total_value[k] < total_value[k_sort]) {
						swap =          total_value[k_sort];
						total_value[k_sort] = total_value[k];
						total_value[k] =      swap;
						i_swap =              v_sort[k_sort];
						v_sort[k_sort] =      v_sort[k];
						v_sort[k] =           i_swap;
					}
				}
			}

			/* 新世代におきかえ */
		    for (k = 0; k < 2 * SIZE; k ++) {
		    	for (l = 0 ;l < LENGTH; l ++) {
		    		next_gene[k][l] = gene[v_sort[k]][l];  /* (13) */
		    	}
		    }
		    for (k = 0; k < 2 * SIZE; k ++) {
		    	for (l = 0; l < LENGTH; l ++) {            
		    		gene[k][l] = next_gene[k][l];          /* (14) */
		    	}
		    }

		
		    /* 表示 */

		    w.lineTo(0, generation, total_weight[v_sort[0]], g);
		    w.lineTo(1, generation, total_value[0], g);
		}
		g.drawString("gene =  " , 10, line); 
		for (l = 0; l < LENGTH; l ++) {
			g.drawString("" + gene[0][l], 80 + l* 10, line);
	    }
	    line = line + 12;
	    g.drawString("total_weight =" + exFormat1.format(total_weight[v_sort[0]]) +
	    		"  total_value =" +  exFormat1.format(total_value[0]), 10, line);
	}
}