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

僕と MySQL と時々 MariaDB

Oracle Code Japan Tour in Sapporoに行ってきた

Java 情報系イベント 情報系一般

f:id:RabbitFoot141:20170605193043p:plain

はじめに

Oracle Code Japan TourがSapporoにくるとのことで初めて情報系のイベントに参加してみた。
というわけで実際に得た情報をあれこれまとめてみた。

すごいメモのような感じになっているので間違ってたらコメントなどくれると嬉しい。

Feed Back from Java Day Tokyo 2017

Java + Dockerが現在利用できるようになっている。
javaだけでなくoracleの製品も利用できるようになった。

java ee8修正案としてhttp2の実装がありになったりリアクティブプログラミングができるようになったりしていくとのこと
非同期と同期を組み合わせて高速化を図る。

javaの最新情報は以下にある
builder.japan.zdnet.com


Raspberry Pi with Java 9

jlinkというコマンドの話
必要なモジュールなどのみでjreを作成できるコマンド
ラズパイみたいにリソースが限られている時に有効

java se9ではhttp2のあれこれが乗っかる。

se9ではarm v5とarm v6(raspberry pi a,b,b+,zero)には未対応
そこでjavaを使いたいなら8以下のものを使うひつようが出てくる。

javafxをiphone,androidで使いたくなったらgluonが開発してるヤツを使える。
gluonhq.com


javaでラズパイのあれこれを動かすためのプロジェクトがあるためハードウェア制御などをjavaでも行うことができる。

ここではそのデモをみて大半が終わってしまった。
ただラズパイ上でjavaを動かすのも楽しそうだと思った。

Cloud Native Java EE

ここはjava ee使わんしネットワークとかあれこれやってないから普通に話聞いて面白いなぐらいしか感想がない。
ただdockerと組み合わせるのが面白かった。

あと
JOnsen – Java Unconference at a Japanese Onsen
っていうアンカンファレンスの話聞けてよかった。


Java SE 9のススメ

ここではjava9での互換性、新機能、改善点などについての話だった

互換性

java9で互換性がなくなったものがいくつかある

言語仕様とライブラリ

java se8ではアンダースコアを１文字変数名として使用できたが警告がでる状況だったが、se9からはアンダースコア１文字だけではコンパイルエラーとなる。

@deprecatedの付いているメソッドについて、今まではずっと残ってきたものでも本当になくなる可能性があるとのこと。
特にGUI関連のものや、OSに比較的依存したものがJigsawプロジェクトによりブラックオックス化される可能性が高いそう。

保守、運用

virtual VM,hprof,jhatなどなどのツールがno moreとなってしまう。

デフォルトのGCが現行のものだとParallel GCなところがG1GCに変更になる。
またそれ以前のCMSはdeprecatedになり今後のアップデートで消える可能性がある。

CMSとG1GCでは使えないのでゴリゴリチューニングしている人は注意が必要。

ただしメモリサイズが小さいマシンなどではparallel GCを使うのがよい。

新機能

今回は大きく分けて3つ

  • Project Jigsaw
  • JShell
  • Reactive Streams

が紹介された。

Project Jigsaw

背景:大規模システムになるとクラスパスが300個近くになることがあるが、実際バージョン違いだけだったりするのにこれはどうなのという問題
俗に言うjar hellに陥る問題。
ライブラリ更新で動作不良を起こしたり、publicがpublicすぎる問題などなど。

これらを辿って行くと依存性の欠如であったり、公開範囲を適切に設定できないなどなど。

これをモジュールにして解決しようというのがProject Jigsaw


モジュールに関して
現行のjarはほぼそのまま使える。
jarファイル中にメタ情報を付加する。
それらを管理するmodule-info.javaの有無が現行とse9のおおきな違い。

クラスパスが消えてモジュールパスに統一される可能性がある。


その他としてjava.baseにjava.langやjava.utilなどが統一されScalaっぽくimportしなくても使えるみたい

依存性の調査は

jdeps -s ファイル名.jar

でそのファイルが使ってるモジュールを表示してくれる。
それをもとにモジュールのあれこれを作成できるようになる。

JShell

javaのreplツール
jshellコマンドを打つと使用できるようになる。
ちなみに行末の;を省略してもいい
同じ変数名で別のデータ型の変数を宣言すると一番最後に変更したものに置換される。

Reactive Streams

非同期処理のためのインターフェース
http://www.reactice-streams.org
back pressureがあるタイプのPublish-Subscribeモデル。
subscriberがpublisherに要求するとsubscriptionが独自に生成されデータがどれだけ通過するか制限できるだか把握できるだか
ココらへんはあまり実感がわかなかった

改善

project coin
stream,collection

project coin

ダイヤモンド演算子などのあれこれに対するものだが
se8ではそれまでの問題がほとんど解決されたが匿名クラスでは使用できなかった。
それをse9では改善し、ほぼすべての場所でダイヤモンド演算子を使えるようになる。

Stream

ファクトリメソッドとして

  • ofNullable
  • iterate

が追加される。

そのほかのメソッドでは

  • take/dropWhile

^ Collectors.flatMapping

  • Collectors.filtering

が追加され関数型のあれこれが割と使えるようになる。

Optionalはstream,flatMapと併用を前提にした設計になる。
ifPresentOrElseが追加され、値がなかった時(Else)にどうするか記述できるようになる。
orの中にoptionalを書けるようになる。

ofメソッドも追加され

List<Integer> list = List.of(1,2,3)

と実装できる。
これはイミュータブルとして生成される。

その他

javadocがhtml5に対応。
検索窓が追加されるがデフォルトで検索窓にフォーカスがあてられるためスペースでしたにいけなくなった。

リリースは2017/09/21に変更になった。
JDK 9 Early-Access Builds
ここで最新情報をあされる。

追記(2017/06/04)

このセッションを担当してくださった桜庭さんの方から資料がアップされたのでここにも掲示。

www.slideshare.net


まとめ

初めての情報系勉強会参加だったけどかなり面白かった。
普段Scalaしか書かないけどJavaのあれこれも面白そうだと感じた

日本語版NetBeans8.2をUbuntuにいれてみた

Java 情報系一般

なぜかNetBeansをいれることになった

友達曰く、「NetBeansが英語なのとプロジェクトを開けない」とのことで実際に検証してみた。
普段はVSCodeかVimとsbtでScala,Javaしか書かない人間のUbuntuにはそんな便利なもの入ってるわけもなく
実際に導入しながらそれらを試してみた。

NetBeans日本語化できないのか？

最初から日本語化されてるのあったっぽい

ja.netbeans.org

ダウンロードした

ダウンロードして、homeディレクトリにnetbeans-8.2-javase-linux.shみたいなファイルを持ってくる。

インストールした

次のコマンド打ったらこんな出力でた

$ sh netbeans-8.2-javase-linux.sh 
インストーラを構成しています...
システムでJVMを検索しています...
インストール・データを抽出しています...
インストーラ・ウィザードを実行中...

これでインストーラが起動したので

f:id:RabbitFoot141:20170516231435j:plain

どんどん次へなり、進むなりを押していく

すると最高に嫌な予感がする。
こんなのが出てきた。

f:id:RabbitFoot141:20170516232508j:plain

これ無視し続けて、なんとかインストールすると

起動はするが、プロジェクト開くときにこんなのがでた

f:id:RabbitFoot141:20170516233126j:plain

まぁ開けないわな。

開き方を変えた

netbeansをいれたディレクトリに移動する

$ cd netbeans-8.2

そこでさらにbinディレクトリに移動する。

~/netbeans-8.2$ cd bin
~/netbeans-8.2/bin$

ここまできたら、次のコマンドを実行してjdkとやらの場所を確認する

~/netbeans-8.2/bin$/usr/sbin/update-java-alternatives -l
java-1.8.0-openjdk-amd64       1081       /usr/lib/jvm/java-1.8.0-openjdk-amd64
java-8-oracle                  1077       /usr/lib/jvm/java-8-oracle

みたいなことになるから、jdkのほうをコピペして次のコマンドで実行する

~/netbeans-8.2/bin$./netbeans --jdkhome /usr/lib/jvm/java-1.8.0-openjdk-amd64

これで使えるようになった(はず)。

それ以外で

UbuntuならUbuntu Softwareからインストールすると楽。
英語だけど。

最後に

一回使ってみたけど、やっぱりNetBeans使いにくい。

【メモ】sbtで自作ライブラリを使えるようにした話

Scala

とりあえず公開したかった。

なんか公開したかった。
sbtで使えるようにしたかった。

何をやったか

とりあえず次のサイトを参考にしてあれこれした

qiita.com
qiita.com
d.hatena.ne.jp


具体的には

  • ライブラリをビルドする
  • github pagesを作成しそこにビルドしたやつをぶん投げる
  • wgetでテストする
  • sbtで使えるかテストする

ライブラリをビルドする。

とりあえず、sbtプロジェクトに作成してるであろうBuild.scala,build.sbt的なあれこれに次を追加する。

Build.scalaならsettingsの中に突っ込んでください。
それ以外のname,version,scalaVersionはもうすでに設定したものとする。

publishTo := Some(Resolver.file("名前",file("jar,pomなどを作成するディレクトリを指定"))(Patterns(true, Resolver.mavenStyleBasePattern)))

ここで一度プロジェクトをコンパイルする。

$ sbt compile


これでokなら次を実行する

$ sbt publish

するとさっき指定したディレクトリに「名前」のディレクトリとその直下に「名前_ScalaVersion」のディレクトリが生成されている

github pagesを作成しそこにビルドしたやつをぶん投げる

公開したいライブラリがgithubのレポジトリにあるとして、そのレポジトリにgh-pagesというブランチを作る。
とりあえずそこにindex.htmlを投げる。

そしていつもどおりgh-pagesにpushする。

その勢いでさっきビルドしたあれこれをぶん投げる。
手順はこれで終わり。

wgetでテストする

次のコマンドを走らせてdlできればok

 wget https://[username].github.io/reponame/projectname/projectname_scalaVersion/version/projectname_scalaVersion-version.jar

これでダウンロードできないなら何かしら失敗しているか、gh-pagesの反映に時間がかかることがあるので最初にリンクを張ったサイトをみてどうにかしてみる。

sbtで使えるかテストする

適当にプロジェクト作るかどうにかして別のBuild.scalaで使うには次のようにする

//ライブラリを追加するところに
"projectName" % "projectName_scalaVersion" % "Version"

//resolverを作って次を記述
resolvers += "Maven Repo on github" at "https://[username].github.io/projectName/"


これでダウンロードできる(はず)

Newton-Raphson法と単位円内接正多角形を使った円周率近似をScalaでやってみた

Scala アルゴリズム 数学

やってみた

C言語縛りは面白くないので例によってScalaでやってみた

こんなやつをコードにした

まずNewton-Raphson法は次の式におけるxの値を求める

\displaystyle f(x) = g(x) - C = 0

このあと登場するけど、単位円内接正多角形を使う近似では漸化式をつかっていくわけだけども
その中で平方根を計算しないといけないのでCを任意実数定数として関数g(x)を次のようにする

\displaystyle g(x) = x^2

すると次の式におけるxを近似的に求めることになる

\displaystyle f(x) = x^2 - C = 0 \\ x^2 - C = 0 \\ x^2 = C

Newton-Raphson法ではこれを次の式を満たす様に微分を使いながら近似していく

{ \displaystyle x_{n+1} = x_n - \frac{f(x_n)}{\frac{df}{dx}(x_n)} }

ここまでNewton-Raphson法

次に単位円を用いて円周率を求める。
しかし、円周がわからない。
これは円周率が不明であるためである。

そこで単位円内に内接正多角形を作って円周とみなす。
これは漸化式で表現でき正n角形のnが大きくなればなるほどその周の長さが円周の長さに近づく。

その内接正多角形の一辺の長さが次の式となる
{ \displaystyle L_{n+1} = \sqrt{ 2-2\sqrt{1-(\frac{L_n}{2})^2} } \: or \: L_{n+1} = \sqrt{2-\sqrt{4-(L_n)^2}} }

というわけでコードにしてみた

実際に書いたコード

object calcPI{

    val max = 20

    def main(args:Array[String]):Unit = {
        var Ln = newtonRaphson(2)//L_1

        var n = 0
        var pow = 2
        while( n < max ){
            println( pow * Ln )
            Ln = newtonRaphson(2 - newtonRaphson(4-Ln*Ln))
            n += 1
            pow *= 2
        }
    }

    def newtonRaphson(c:BigDecimal):BigDecimal = {
        var x:BigDecimal = c
        var dx:BigDecimal = -func(x,c) / dfunc(x)

        while( 1.0e-16 < dx.abs  ){
            x += dx
            dx = -func(x,c) / dfunc(x)
        }

        return x
    }

    def func(x:BigDecimal, c:BigDecimal):BigDecimal = x*x - c
    def dfunc(x:BigDecimal):BigDecimal = 2.0*x
}

これを実行して、出力結果をdatファイルにおとしてgnuplotでグラフにするとこんな感じになる

f:id:RabbitFoot141:20170504120319p:plain

BigDecimal使ってはいるけど精度的にはまだまだかなと思うけどある程度できた。

Newton-Raphson法を用いた円周率近似

C言語 アルゴリズム 数学

Newton-Paphson法の基礎原理

Newton-Raphson法とは次の式を満たすxの値を見つけるアルゴリズム
{ \displaystyle f(x) = g(x) - C = 0 }
ここではg(x)を任意の微分可能な関数としてCを実数定数とする。
つまりNewton-Rapshon法は次の式を満たすxの値を見つけるアルゴリズムとなる。

{ \displaystyle g(x) = C }

つまり以下の様にg,Cが与えられた時は2の平方根を求めることになる。

{ \displaystyle g(x) = x^2, C = 2 }

実際の計算

基礎原理はうえで紹介したので実際に解を近似して求める。というのも上記の式を満たすxがすぐに正確に見つかるわけではないことによる。
そこで与えられたf(x)を一回微分して接線の方程式を求め、その接線とx-軸の接点におけるx座標で再びf(x)に戻り微分し接点のx座標を求める…。
これを再帰的に繰り返すことで求めたいxに近似していくこととなる。
その漸化式は次のようになる。

{ \displaystyle x_{n+1} = x_n - \frac{f(x_n)}{\frac{df}{dx}(x_n)} }

この漸化式をC言語を用いたコードとして表現していく。
ここでは平方根を求めることにする。

コード化する

ひとまず次のプログラムをベースにする。

#include<stdio.h>

int main(){
    return 0;
}

ここで関数fとそれを一回微分したdfを関数として作る。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

//プロトタイプ宣言
double Func(double x,double C);//変数xとCが必要となる
double dFunc(double x);//fを微分しているのでxのみ必要

int main(){
    return 0;
}

double Func(double x, double C){
    return x*x - C; //x^2-Cを計算して返す
}

double dFunc(double x){
    return 2.0*x; //2xを返す
}

これで準備は出来た。

次に微分して…。となるがCで微分を扱うのは難しいので数学的に考えてfとxのみの式に直す。
それは以下になる。

{ \displaystyle \frac{df}{dx}(x_n) = \frac{f(x_n)}{x_n-x_{n+1}} }

というわけでNewton-Raphson法を用いて平方根を求める。ここでは誤差が{10e-6}になるまで続けることにする。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

//追加した
#define EPS 10e-6

//プロトタイプ宣言
double Func(double x,double C);//変数xとCが必要となる
double dFunc(double x);//fを微分しているのでxのみ必要

double Newton(double C);//平方根を求めたい値を実数で受け取る

int main(){

    printf("%12.10f\n",Newton(2) );

    return 0;
}

//Newton-Rapshon法を用いてcの平方根を求める。
double Newton(double C){
    
    double x = C;
    double dx = -Func(x,C)/dFunc(x);
    
    while( fabs(dx) > EPS){
        x += dx;
        printf("%12.10f\n",x);
        dx = -Func(x,C)/dFunc(x);
    }
    return x;
}

double Func(double x, double C){
    return x*x - C; //x^2-Cを計算して返す
}

double dFunc(double x){
    return 2.0*x; //2xを返す
}


これで平方根をNewton-Raphson法を使って求めることができる。
ただし、誤差があることに注意。

円周率近似

円周率近似も漸化式を用いて行う。
http://oto-suu.seesaa.net/article/291513400.html
上記のサイトがそれを紹介しているが半径が{\frac{1}{2}}なので、半径を単位円において考えることにする。
基本的には正n角形の周を求め円周に近似していくことになる。

その場合、漸化式は次のようになる。
{ \displaystyle L_{n+1} = \sqrt{ 2-2\sqrt{1-(\frac{L_n}{2})^2} } or L_{n+1} = \sqrt{2-\sqrt{4-(L_n)^2}} }

ソースコードにする

これをソースコードにするとこうなる

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define EPS 1.0e-8
#define POW 2

double Newton(double);
double Func(double, double);
double dFunc(double);

int main(){

    double Ln = Newton(2.0);//L_1 = sqrt(2)
    printf("%12.10f\n",Ln);
    int n = 1;
    int pow_base = 2;
    int n_max = 20;

    while( n < n_max ){ 
        
        printf( "%12.10f\n", pow_base * Ln );
        Ln = Newton( 2-Newton(4 - pow(Ln, 2)) );
        n += 1;
        pow_base *= POW;

    }

    return 0;
}


//平方根を求める
double Newton(double C){
    
    double x = C;
    double dx = -Func(x, C) / dFunc(x);
    
    while( fabs(dx) > EPS ){
        x += dx;
        dx = -Func(x, C) / dFunc(x);
    }

    return x;
}


double Func(double x, double C){
    return x*x-C;
}

double dFunc(double x){
    return 2.0 * x;
}

これで円周率の近似値が求められた。

githubでコミットしても芝生が生えなかったわけ

情報系一般

昨日、githubの自分のレポジトリにコミットしてたら唐突に芝生が生えなくなった。

それで色々ググった結果

  • masterブランチじゃないとだめ
  • ローカルレポジトリの登録アドレスがgithubアカウントのメールアドレスになっていないとだめ
  • forkしたやつもだめ

みたいなあれこれが書いてあって、それ以外の原因は見つからなかった。

がしかし、自分の環境ではmasterブランチにコミットしていたし、メアドも合ってるし、自分で作成したレポジトリだしってことで
沼に陥ったので、github supportにこれらの問題をぶん投げた。

すると返信があって

「ラグってるだけだと思うから、24時間以上して芝生生えなかったらまたメールしてね」

と来たので今朝見たら、本当にラグってただけだった。

なんか芝生もすぐに反映されなくて、数時間ラグることもあるらしい。

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

アルゴリズム 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();
}