• 締切済み

遺伝アルゴリズム　遺伝的オペレータの選択処理における「ルーレット選択」を実行するサブルーチンをプログラミング

学校の課題でプログラミングの課題がでたのですが、その授業ではプログラミングは一切指導されないので、作成できなくて困っています。 どなたかアドバイスをお願いします。。。 よろしくお願いします。 課題は以下の通りです。 遺伝アルゴリズム　遺伝的オペレータの選択処理における「ルーレット選択」を実行するサブルーチンをプログラミングせよ ルーレット選択のアルゴリズム 手順１：世代tの個体群X（ｔ）の中のN個の個体の適合度fi,i=1,....,N,と、その総計fsum=Σfi（i=1～N）を求める 手順２：〔0,1〕の乱数rand()を発生させ、s=rand()*fsumとする 手順３：Σfi（i=1～k）、fi≧sとなるような最小のkを求めて、k番目の個体を世代k+1に生き残る個体の候補とする 手順４：候補となる個体数がNになるまで、手順２，３を繰り返す。 お手数ですがよろしくお願いします。

みんなの回答

回答No.2

学生係ではなく教務係でしょう。 手順１～４で充分アルゴリズムが示されています。 基本的なプログラミングができなければ、 この講義について行くのは無理でしょう。 担当教員も教務係もそういうのではないでしょうか？ まず、基本的なプログラミングを 他人に頼らず、自分で勉強してから 受講してみてください。

  • neKo_deux
  • ベストアンサー率44% (5541/12319)
回答No.1

> その授業ではプログラミングは一切指導されないので、作成できなくて困っています。 担当教官にその旨伝え、課題が出来ないのでどうすれば良いのか、指示を仰いでください。 改善しない場合は学生係へ相談を。

  1. カテゴリ
  2. 学問・教育
  3. その他（学問・教育）

関連するQ&A

  • 遺伝的アルゴリズムの遺伝子の長さについて

    今、グラフ理論と遺伝的アルゴリズム（以下ＧＡ）の勉強をしています。 グラフ理論の最小全域木問題をＧＡを使って解こうと考えています。そこで、個体の遺伝子の長さをそのグラフの点の数Ｎにすればよいのではないかと考えました。 しかし、グラフが大きく、点の数Ｎが１００や１０００になった場合は、遺伝子の長さも非常に長くなってしまいます。これはＧＡとして問題があるかないかについて教えてください。 よろしくお願いします。

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

    遺伝的アルゴリズムのプログラムの基本的な流れが↓のページ 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 また、遺伝的アルゴリズムのプログラミングをする際の注意点があれば教えてください。

  • 遺伝的アルゴリズム

    10個の荷物（1.0キログラム、5.0、2.0、…etc）が一つずつあるとして、それらの荷物を一つずつリュックサックに入れるとき、総重量が30キロを越えないようにしたい、という問題を遺伝的アルゴリズムでプログラミングしたいのですが、その荷物を入れる場合は1、入れない場合は0というようにする場合、どうプログラミングすればよいのでしょうか。どうしても分からないので、プログラムをそのまま記述して頂けると非常にありがたいです。よろしくお願いします。

  • 遺伝的アルゴリズム

    遺伝的アルゴリズムのプログラムを作っているのですがサンプルソースの下の関数のやってこるこがよく意味がわかりません。よかったら解説 お願いします。 // 一点交叉 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()

  • 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}, }; のように予め決められている２次元配列（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

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

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

  • 遺伝子アルゴリズムの2点交叉について教えてください

    下記のプログラムを改良して2点交叉にしたいのですが、遺伝子アルゴリズムもC++も初心者なので、よくわかりません。どなたかお知恵を貸してください。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include "come.h" int kousa() { unsigned int max=100; unsigned int max2=17; int a,b,c,d; int i,v,w,y,n,o,k,p,f; char kari[1][17]; w=0;//カウンタ n=0; srand((unsigned)time(NULL)); for(v=0;v<100;v++) { for(i=0;i<17;i++) { get[v][i]=next[v][i]; //next[175][17]からget[100][17]へコピーする(親) } } for(o=0;o<100;o++) { for(k=0;k<17;k++) { take[o][k]=next[v][k]; //next[175][17]からtake[100][17]へコピーする(子) } } for(d=0;d<50;d++) { a=(rand()%max); //1つ目の交叉する列を見つける b=(rand()%max); //2つ目の交叉する列を見つける c=(rand()%max2); //交叉ポイント見つける for(;c<17;c++) //1点交叉 { kari[n][c]=get[a][c]; get[a][c]=get[b][c]; get[b][c]=get[n][c]; } for(y=0;y<17;y++) { take[w][y]=get[a][y]; //get[100][17]からtake[50][17]へコピー take[w+1][y]=get[b][y]; } w=w+2; } for(p=0;p<100;p++) { for(f=0;f<17;f++) { next[nextpop][f]=take[p][f]; } nextpop++; } return 0; }

  • C言語 遺伝的アルゴリズムでのエラーについて

    与えられた乱数を二つのグループにわけ、その差が小さくなるようなプログラムを書いているつもりです。 が、コンパイルし、実行したところsegmentation fault が表示されます。 segmentation fault が表示される理由はわかっていますが、どこでそういった現象がおこっているのか判断できない状況です。 どなたかよろしくお願いします。 #include<stdio.h> #include<stdlib.h> #include<time.h> //染色体の数 #define Number_of_ch 10 //エリート選抜の割合 #define Selection 0.3 //交叉率 #define Cross_ratio 0.7 //突然変異率 #define Mutation_ratio 0.1 //ループ回数 #define Number_of_loop 100 int main(int argc , char *argv[]) { int f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,x,y,z; int Number_of_gene = argc-1;//遺伝子の数 int chromosome[Number_of_ch][Number_of_gene],distmin[Number_of_gene];//染色体と遺伝子 int best_chromosome[Number_of_gene],Number_of_cross=0,ch_1=0,ch_2=0,point=0,temp=0,temp_1=0,temp_2=0,abc=0,loop=0; float real_Number[Number_of_gene] , dist[Number_of_ch] , best = 100.0; float sum0 = 0.0 , sum1 = 0.0 ; //入力値の記録 for(i=0 ; i<argc ; i++){ real_Number[i] = atof(argv[i+1]); } srand((unsigned)time(NULL)); //染色体の初期化 for(j=0 ; j<Number_of_ch ; j++){ for(k=0 ; k<Number_of_gene ; k++){ chromosome[j][k] = rand() % 2;//0 or 1のグループ分け } } //----------------------ループ開始------------------------ while(loop < Number_of_loop){ //差分 for(l=0 ; l<Number_of_ch ; l++){ for(m=0 ; m<Number_of_gene ; m++){ if(chromosome[l][m] == 0){ sum0 = sum0 + real_Number[k]; } else{ sum1 = sum1 + real_Number[k]; } } dist[l] = abs(sum1 - sum0); } //評価と記憶 for(n=0 ; n<Number_of_ch ; n++){ if(dist[n] < best){ best = dist[n]; for(o=0 ; o<Number_of_gene ; o++){ best_chromosome[o] = chromosome[n][o]; } } } //ソート for(p=0 ; p<Number_of_ch ; p++){ for(q=1 ; q<Number_of_ch-p+1 ; q++){ if(dist[q-1] > dist[q]){ for(r=0 ; r<Number_of_gene ; r++){ distmin[r] = chromosome[q][r]; chromosome[q][r] = chromosome[q-1][r]; chromosome[q-1][r] = distmin[r]; } } } } //エリートの選抜 for(s=Number_of_ch*Selection ; s<Number_of_ch ; s++){ for(t=0 ; t<Number_of_gene ; t++){ chromosome[s][t] = best_chromosome[t]; } } //交叉 Number_of_cross = Number_of_ch * Cross_ratio; for(u=0 ; u<Number_of_cross ; u++){ ch_1 = (Number_of_ch-1) * (rand()/32767); ch_2 = (Number_of_ch-1) * (rand()/32767); point = (Number_of_gene-1) * (rand()/32767); for(x=point ; x<Number_of_gene ; x++){ temp_1 = chromosome[ch_1][x]; for(y=0 ; y<Number_of_gene ; y++){ if(chromosome[ch_1][x] == chromosome[ch_2][y]){ temp_2 = chromosome[ch_2][x]; chromosome[ch_2][x] = chromosome[ch_2][y]; chromosome[ch_2][y] = temp_2; } for(z=0 ; z<Number_of_gene ; z++){ if(chromosome[ch_2][x] == chromosome[ch_1][z]){ chromosome[ch_1][x] = chromosome[ch_1][z]; chromosome[ch_1][z] = temp_1; } } } } } //突然変異 for(f=0 ; f<Number_of_cross ; f++){ for(g=0 ; g<Number_of_gene ; g++){ if(rand()/32767 < Mutation_ratio){ abc = (Number_of_gene-1) * (rand()/32767); temp = chromosome[f][g]; chromosome[f][g] = chromosome[f][abc]; chromosome[f][abc] = temp; } } } loop = loop + 1; } //結果の出力 printf("# best = %f \n",best); for(h=0 ; h<Number_of_gene ; h++){ printf("%d",best_chromosome[h]); } printf("\n"); }

  • C言語 遺伝的アルゴリズムでのエラーについて

    再度質問させていただきます。 以下のプログラムを実行するとsegmentation faultが出たり出なかったりします。 いまいち原因が分からないので回答お願いします。 ちなみに目的としては、 0~1の乱数が複数個与えられたときに、与えられた乱数を2つのグループに分け、その2グループの差ができるだけ小さくなるようにする。 といったものです。 よろしくお願いします。 #include<stdio.h> #include<stdlib.h> #include<time.h> //染色体の数 #define Number_of_ch 10 //エリート選抜の割合 #define Selection 0.3 //交叉率 #define Cross_ratio 0.7 //突然変異率 #define Mutation_ratio 0.2 //ループ回数 #define Number_of_loop 100 int main(int argc , char *argv[]) { int f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,x,y,z; long int Number_of_gene = argc-1;//遺伝子の数 int chromosome[Number_of_ch][Number_of_gene],distmin[Number_of_gene];//染色体と遺伝子 int best_chromosome[Number_of_gene],Number_of_cross=0,ch_1=0,ch_2=0,point=0,temp=0,temp_1=0,temp_2=0,abc=0,loop=0; double real_Number[Number_of_gene] , dist[Number_of_ch]; double best = 100.0; double sum0 = 0.0 , sum1 = 0.0 ; //入力値の記録 for(i=0 ; i<Number_of_gene ; i++){ real_Number[i] = atof(argv[i+1]); } srand((unsigned)time(NULL)); //染色体の初期化 for(j=0 ; j<Number_of_ch ; j++){ for(k=0 ; k<Number_of_gene ; k++){ chromosome[j][k] = rand() % 2;//0 or 1のグループ分け } } //----------------------ループ開始------------------------ while(loop < Number_of_loop){ //差分 for(l=0 ; l<Number_of_ch ; l++){ for(m=0 ; m<Number_of_gene ; m++){ if(chromosome[l][m] == 0){ sum0 = sum0 + real_Number[m]; } else{ sum1 = sum1 + real_Number[m]; } } if(sum0 > sum1){ dist[l] = sum0 - sum1; } else{ dist[l] = sum1 - sum0; } } //評価と記憶 for(n=0 ; n<Number_of_ch ; n++){ if(dist[n] < best){ best = dist[n]; for(o=0 ; o<Number_of_gene ; o++){ best_chromosome[o] = chromosome[n][o]; } } } //ソート for(p=0 ; p<Number_of_ch ; p++){ for(q=1 ; q<Number_of_ch-p+1 ; q++){ if(dist[q-1] > dist[q]){ for(r=0 ; r<Number_of_gene ; r++){ distmin[r] = chromosome[q][r]; chromosome[q][r] = chromosome[q-1][r]; chromosome[q-1][r] = distmin[r]; } } } } //エリートの選抜 for(s=Number_of_ch*Selection ; s<Number_of_ch ; s++){ for(t=0 ; t<Number_of_gene ; t++){ chromosome[s][t] = best_chromosome[t]; } } //交叉 Number_of_cross = Number_of_ch * Cross_ratio; for(u=0 ; u<Number_of_cross ; u++){ ch_1 = (Number_of_ch-1) * (rand()/32767); ch_2 = (Number_of_ch-1) * (rand()/32767); point = (Number_of_gene-1) * (rand()/32767); for(x=point ; x<Number_of_gene ; x++){ temp_1 = chromosome[ch_1][x]; for(y=0 ; y<Number_of_gene ; y++){ if(chromosome[ch_1][x] == chromosome[ch_2][y]){ temp_2 = chromosome[ch_2][x]; chromosome[ch_2][x] = chromosome[ch_2][y]; chromosome[ch_2][y] = temp_2; } for(z=0 ; z<Number_of_gene ; z++){ if(chromosome[ch_2][x] == chromosome[ch_1][z]){ chromosome[ch_1][x] = chromosome[ch_1][z]; chromosome[ch_1][z] = temp_1; } } } } } //突然変異 for(f=0 ; f<Number_of_cross ; f++){ for(g=0 ; g<Number_of_gene ; g++){ if(rand()/32767 < Mutation_ratio){ abc = (Number_of_gene-1) * (rand()/32767); temp = chromosome[f][g]; chromosome[f][g] = chromosome[f][abc]; chromosome[f][abc] = temp; } } } loop = loop + 1; } //結果の出力 printf("# best = %f \n",best); for(h=0 ; h<Number_of_gene ; h++){ printf("%d",best_chromosome[h]); } printf("\n"); }

  • 整数の選択

    アルゴリズムに関する質問です． n個の相異なる整数が配列 A[1..n] に格納されていて，その配列の中からk番目に小さい整数を選ぶ問題のアルゴリズムを考えています．kは 1<=k<=n を満たす自然数であり，この選択問題は O(n) で解けるものです． ヒープを使ったりして考えたのですがうまくいきません．どなたかこのアルゴリズムを教えてください．よろしくお願いします．

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する