• 締切済み

Javaでの遺伝的アルゴリズムの実装について

別のWebサイトでも質問させていただいているのですが、 double[][] a={ {1,1,1,1,1,1,1,1,1,1}, {1,2,1,4,1,1,1,8,1,1}, {2,2,2,2,2,2,2,2,2,2}, {2,2,2,3,2,2,2,3,2,2}, {2,2,2,2,2,4,2,2,3,2}, }; のように予め決められている2次元配列(a[0],a[1],a[2],a[3],a[4]それぞれが遺伝子)と、 double[] fitness={50,100,60,90,120}; のように遺伝子それぞれに対応している適応度があるとして、(適応度は別プログラムで計算済み) 遺伝的アルゴリズムで予め設定された遺伝子と適応度をエリート及びルーレット選択、交叉、突然変異を行う(一世代のみ)プログラムをJavaを用いて作りたいのですが、 Web上にある例となるClassは初期集団をランダムで生成した上で、ランダムに生成された遺伝子に対し適応度計算を行い、それを選択、交叉、突然変異を行うClassに投げるものがほとんんどです。 なので、適応度計算を行わずに既にある遺伝子と適応度をどのようにして結びつけるのか、もともとランダムに生成された遺伝子に適応度計算を行うこと、複数世代行うことを前提に設計されている選択・交叉・突然変異等のClassをどう変更すればよいのかわからず、手詰まりになってしまいました。 周りの知り合いに聞いても、Javaは少しならわかるが専門外、遺伝的アルゴリズムは勉強したことがない人ばかりなので、聞きたくても聞けない状況となっております・・・。 遺伝的アルゴリズム及びJavaに詳しい方、どなたか実装例を教えていただけないでしょうか? 参考にさせていただいたURL:http://www.ics.kagoshima-u.ac.jp/edu/ProgramingJava/samples/SimpleGA/step1/index.html#GA%20%E3%82%AF%E3%83%A9%E3%82%B9

  • BRNA
  • お礼率100% (1/1)
  • Java
  • 回答数1
  • ありがとう数1

みんなの回答

  • mpro-gram
  • ベストアンサー率74% (170/228)
回答No.1

> 適応度計算を行わずに既にある遺伝子と適応度をどのようにして結びつけるのか wikiの説明では 「必要とされる条件は評価関数の全順序性と、探索空間が位相(トポロジー)を持っていることである。」 http://ja.wikipedia.org/wiki/遺伝的アルゴリズム よって、適応度算出方法の詳細は不明でも、与えられた遺伝子について、適応度順に並べる事が出来れば、その上位から選択が可能となるので、適応度計算部分(評価関数のこと)は「単に順列値を与えるだけのもの」でも十分ということである。 つまり、変化後の遺伝子が元の遺伝子群のどれに近いかで、適合度をその似ている遺伝子と同じにするか、または違いの程度で、何らかの比率を掛けるような適合度算出方法でも、それなりの結果をだせるのが遺伝的アルゴリズムということである。 Class の変更とは、つまり、適合度算出メソッドをそのように上書きするということだとおもう。

BRNA
質問者

お礼

mpro-gramさん回答ありがとうございます。 >>適応度計算部分(評価関数のこと)は「単に順列値を与えるだけのもの」でも十分ということである。 やはりできるんですよね! 遺伝子、適応度を事前に渡せるように、適応度算出部分、そして遺伝子生成部分のメソッドの書き換えを頑張ってみます。

関連するQ&A

  • 遺伝的アルゴリズムについて

    GAについて、かなり初歩的な質問です。 交叉に用いた親は次世代に残すものなのでしょうか? 初期集団で適応度の高い親が出来て、世代を重ねてもその親が生き残っているというのは、なんか遺伝というイメージから少しずれた気がしたので。 よろしくお願いします。

  • 遺伝的アルゴリズムによる繰り返し囚人のジレンマ

    初めて質問をさせていただきます。ヨロシクお願いします。 遺伝的アルゴリズムによる繰り返し囚人のジレンマゲームに関するプログラミングについて分からないことがあります。 当方はC++初心者のためクラスの使い方がイマイチ分かりません。 クラスの概念は文献により理解できるのですが便利さが実感できません。 具体的にいうと、遺伝的アルゴリズムのどの部分にクラスが適用できるのでしょうか?クラスを用いないで強引にプログラムすることは出来そうなのですが…。 囚人のジレンマゲームに関わらず、遺伝的操作(選択、交叉、突然変異)をクラスの概念を用いてプログラムする際のヒントとコツなどを教えて下さい!また遺伝子情報は配列を用いて表現するのでしょうか?なにぶん遺伝的アルゴリズムは初めてなので分からないことだらけです。ヨロシクお願いいたしますm(__)m

  • 遺伝的アルゴリズム

    遺伝的アルゴリズムをCで組み、Cygwinのgccコマンドでコンパイルしたのですが、実行するとエラーが出てしまいます。 gsb内で実行しwhereコマンドで異常箇所を探した場合のメッセージは以下の通りです。 #0 0x61016525 in stack_info::walk () from /usr/bin/cygwin1.dll #1 0x7c859dcc in OutputDebugStringsA () from /cygdrive/c/WINDOWS/system32/kernel32.dll #2 0x40010006 in ?? () #3 0x00000000 in ?? () プログラムは長いので載せられませんが、アルゴリズム中の染色体は二次元配列の遺伝子を含む構造体です。 遺伝子の配列に関わるノード数(chromo[timeslot][NODE]←このNODEです。プログラム冒頭で値をdefineで宣言しています)が30位なら世代数が比較的多くても動くのですが、これが50あたりになると世代数が低くてもエラーが出てしまいます。 printf関数で交叉や突然変異の結果を表示しているのですがちゃんと動作しているようです。 二台のパソコンどちらでやってもこのようなメッセージが出るので困っています。何が起こっているか見当がつく方、いらっしゃいましたら助言願います。 よろしくお願いいたします。

  • GA(遺伝的アルゴリズム)を教えてください!

    はじめまして。 先日、大学でGA(遺伝的アルゴリズム)を使って 簡単な掛け算の(例えば、3×○=12で○の中に当てはまる 数字を導き出す)問題を解いてくるようにと課題がありました。 しかし、GAに関しては基本的な用語(交叉や突然変異など)を 教わったのみでプログラムが全然分かりません。 自分でも色々調べてみたのですが、全く参考になりそうなものが 見つかりませんでした。 そこで、もしご存知の方がいらっしゃるなら教えていただけないでしょうか? プログラムを組む場合にはC言語(C自体も使ったことがありません・・・。) を使うことになるのですが、できればMATLABを使いたいと思っています。 もちろんC言語でも構いませんので、よろしくお願いします!

  • 遺伝的アルゴリズムの評価式に関する質問です。

    膨大な数の組み合わせから正解の組み合わせを求めるという大規模組み合わせ問題があったとします。 このような問題を遺伝的アルゴリズムを用いて解こうとしているのですが、今用いている評価式より良いアイデアが自分では考えつかなかったため質問します。 以下、問題や用いている遺伝的アルゴリズムに関する詳しい説明です。 例えば、仮に、23, 21, 65, 78, 43, 78, 83, 56, 78 ,89 の10個の数の組み合わせがあるとき、 合計して109になる組み合わせ(23,21,65)を見つけたいという問題です。(正解の組み合わせは複数個あっても、一個見つかれば良い。また正解の組み合わせは必ずあるものとする。) この問題を遺伝的アルゴリズム(GA)を使って解くとします。 以下、簡単なGAの説明です。 表現型に2進数ビット列を用いる。 個体数は200とし、初期個体はランダムで生成する。 評価式はf(x) = b/(b+|b-t|)(bは正解の組み合わせの合計値で、tは2進数ビット列で1を立てた場所の数の合計値である。)。終了条件はこの評価値がf(x)=1になることである。 交叉は一様交叉で突然変異も行う。 表現型について詳しく説明すると、 コード化に 0と 1の並びである2進数ビット列を用いて、 その場所に対応する数を加算する場合は1を, 逆に加算しない場合は0を遺伝子の表現型に立てビット列を生成しました。 例えば今回の正解の組み合わせ(109)を2進数ビットで表すと下のようになる。 23, 21, 65, 78, 43, 78, 83, 56, 78 ,89 1 1 1 0 0 0 0 0 0 0 ←2進数ビットを用いた表現型。 (1が立っている場所の数が加算されて合計で109となり、これが正解の組み合わせであることがわかる。) そして、この遺伝的アルゴリズムの評価式を f(x) = b/(b+|b-t|) とします。(bは正解の組み合わせの合計値で、tはビット列で1を立てた場所に対応する数の合計値である。) 評価式f(x)=1になる、つまり正解の組み合わせが見つかれば、遺伝的アルゴリズムは終了する。 この評価式で遺伝的アルゴリズムを回しているのですが、この簡単な評価式では近似解に陥ったとき、解を求めるのがどうしても遅くなってしまいます。 全体的に長く、わかりにくい説明で申し訳ないのですが、この評価式の改善案、またはこの遺伝的アルゴリズムの改善案などがあれば教えていただきたいです。 以上、よろしくお願いします。

  • 遺伝的アルゴリズムのプログラミングについてですが・・・

    遺伝的アルゴリズムのプログラムの基本的な流れが↓のページ http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm に 【1.初期化 2.生物集団の評価 3.交叉 4.突然変異 5.各個体の評価 6.淘汰】と書かれてあるのですが、 f(x) = sin(3x) + 0.5sin(9x) + sin(15x + 50) [0.1]区間の最大値を求める↓のプログラム http://www.sist.ac.jp/~suganuma/cpp/3-bu/18-sho/genetic/C++/gene_f.txt  に当てはめるとどの部分がどこに当たるのでしょうか…(また、このプログラムはどこからどのように読んでいけばいいのでしょうか…)。一応コメントが書かれていますがよく分かりません><; わかる方がいらっしゃいましたらよろしくお願いしますm( _ _ )m また、遺伝的アルゴリズムのプログラミングをする際の注意点があれば教えてください。

  • 遺伝的アルゴリズム

    遺伝的アルゴリズムのプログラムを作っているのですがサンプルソースの下の関数のやってこるこがよく意味がわかりません。よかったら解説 お願いします。 // 一点交叉 void one_point_crossover(struct genotype *ind) { int i, ia, ib; // 個体インデックス int j; // 遺伝子座インデックス int c; // 交叉点 int test[M]; // 個体の利用フラグ int temp[N]; // 遺伝子を入れ替えるための仮変数 // 4/24修正 int r; // 乱数値 for(i=0; i<M; i++) test[i] = 0; ia = ib = 0; for(i=0; i<M/2; i++) { // 個体をランダムにペアリング for(; test[ia]==1; ia=(ia+1)%M); test[ia] = 1; r = random() % (M-2*i) + 1; while(r>0) { ib=(ib+1)%M; for(; test[ib]==1; ib=(ib+1)%M); r--; } test[ib] = 1; // 個体iaとibを交叉 if(flip(Pc)) { c = random() % N; for(j=0; j<c; j++) { temp[j] = ind[ia].gene[j]; ind[ia].gene[j] = ind[ib].gene[j]; ind[ib].gene[j] = temp[j]; } } } } // End of one_point_crossover()

  • 対話型遺伝的アルゴリズムについて。

    対話型遺伝的アルゴリズムについて。 現在,IGAを用いたアプリケーションを構築するための勉強をしている者です。 進化計算処理の一つ,「交叉」について2つ疑問があります。 <質問1>=============================== 例えば, 「ユーザに好きな色を評価してもらいながら最適な色(好みの色)を作り出してもらう」 「パラメータはRGB3原色の3つ」 とするとき,評価及び進化計算の過程でRGBの値が 親1 R=63 G=127 B=255 親2 R=50 G=240 B=0 の親があったとします. これを以下のように,10進数のまま交叉するというのではだめなのでしょうか。 親1 R=63 G=127 <交叉位置> B=255 親2 R=50 G=240 <交叉位置> B=0          ↓ 子1 R=63 G=127 B=0 子2 R=50 G=240 B=255 もちろんこれだと2進数化(コード化)した時とは違い,各原色はそっくりそのまま入れ換えることになります。 ただ,それでも最適解へ収束するということには変わらないと思います。 従来の2進数にコード化して行う明確な理由を教えて頂けないでしょうか。 <質問2>=============================== 上記のアルゴリズムであれば, 整数である「表現型」のままの交叉ということになるのでしょうか。 もしそうであれば,ここは従来の交叉は使えず「実数値GA」なるものを使わなければいけないのでしょうか。 ==================================== 以上2点です。 どちらか1つの回答でも結構です。 どうぞ,よろしくお願いします。

  • Javaアルゴリズムで分からないことがあるので質問します。

    Javaアルゴリズムで分からないことがあるので質問します。 a,b,c,d,e,f,g これらの文字を各一回使ってできる文字列の、全てのパターンを一覧で表示したいのですが、なかなかうまくいきません。 出力結果は、下記のように全パターン出力するようなJavaプログラムなんですが。 ↓出力結果↓ abcdefgh abcdefhg abcdehfg ・・・・・・・・ hgfedacb hgfedcab hgfedcba ※自分ではとりあえずここまでできています。 public class Test {  public static void main(String[] args) {  String[] pattern = {"a","b","c","d","e","f","g","h"};   for(int i = 0; i <= pattern.length; i++){    System.out.print(pattern[i]);    if(i == pattern.length){   System.out.println("");    }   }  } } 宜しくお願いします。

  • singletonによるインターフェイスの実装

    Java勉強中の初心者です。 標題の件についてお願いします。 以下、簡単に条件を説明させていただきます。 Aクラス = メインクラス Bクラス = インターフェイスクラス Cクラス = DとEを動的に生成するクラス Dクラス = インターフェイスを実装するクラス Eクラス = インターフェイスを実装するクラス AクラスにB.getInstance(name)があります。 for文の無限ループがあります。 Cクラス class C { public static B getInstance(String name) { // Aクラスのaと変数nameが比較して一致したら // Dクラスのインスタンス生成 // 一致しなかったらEクラスのインスタンス生成 if(A.a.equals(name)){ return D.getInstance(); }else{ return E.getInstance(); } } } Dクラス class D implements B{ private D() { } public static D getInstance() { D d = new D(); return d; } // インターフェイスでのメソッド省略します。 } Eクラス class E implements B{ private E() { } public static E getInstance() { E e = new E(); return e; } // インターフェイスでのメソッド省略します。 } この条件の時にnewするたびにインスタンスが 生成されてしまいます。 インスタンスの生成が一度だけしか 生成されないようにするには、C,D,Eクラスで どのように記述すればいいか悩んでいます。 (骨組みは書けましたが) クラスを簡単に省略してわかりづらいと 思いますがよろしくお願いします。

    • ベストアンサー
    • Java

専門家に質問してみよう