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

このQ&Aに関連する最新のQ&A

A 回答 (3件)

質問が2/10の書き込みなので、もう遅いかもしれませ


んが、回答受付中だったのでとりあえず書いておきま
す。シンプルなGAのプログラムを組む程度であれば、
MATLABでもCでも、手間はほとんど変わらないと思い
ます。少々長いですがご容赦ください。

簡単な問題で考えましょう。解が整数のみとして、
0<=x<256の範囲において、関数(x-10)*(x-10)が最小値
となるような整数xをGAで求めてみましょう。

当然、答えはx=10となりますが、これがどのように
して求められるのか説明していきます。

まず、解の候補をいくつか(たとえば5個)ランダムに
作成します。0<=x<256の範囲内にある任意の整数が適
当に5個選ばれます。それを x_i(i=1,2,3,4,5)として
おきましょう。


-----------------------

(ステップ1)
目的は、関数f(x)=(x-10)*(x-10)の値が最も小さく
なるようなxを求めるので、(x_i-10)*(x_i-10)の値
が大きいものは、求めたい解とは違うので削除しま
す。

たとえば、解の候補が以下のように5つあったとき、

x_1 = 3
x_2 = 134
x_3 = 203  -> 削除
x_4 = 45
x_5 = 98

x_3はf(x_i)の値が最も大きいので、削除します。

一方で、x_1はf(x_i)の値が最も小さいので増殖
させます。つまり、

x_1 = 3
x_2 = 134
x_3 = 3 <- x_1と同じ値のものが増える
x_4 = 45
x_5 = 98

プログラムでは、x_3 = x_1と書くだけで済む話です。
これが、GAでいう「選択」とか「淘汰」と呼ばれる
ものです。

-----------------------

(ステップ2)
次は、x_iを「交叉」させます。つまり、親2人から
子供2人を生み出すことです。これは確率的に行う
ので、すべてのx_iが交叉するわけではありません。

たとえば、x_2とx_3が両親となって、子供が2人生ま
れるとしましょう。x_2とx_3を二進数で表現して、

x_2 = (10000110), x_3 = (00000011)

とし、適当な場所で値を入れ替えます。例えば、下位
3ビットのみ入れ替えるのであれば、

x_2 = (10000011), x_3 = (00000110)

となります。このようなビット列の入れ替えを確率
0.25くらいで行います。

-----------------------

(ステップ3)
最後に突然変異させますが、これはx_iのビット列
のうち、あるビットの値が0から1、もしくは1から0
に変化させるもので、確率0.01くらいの稀なケース
として行わせます。

-----------------------

ステップ1~3までの1回の操作を「1世代」と呼び
ます。これを何10世代、何100世代と繰り返していく
と、「f(x)の値を最小にする」という目的にあった
x_iのみが何世代にも渡って生き残って増殖していき
逆にf(x)の値が大きいx_iは数世代で死滅していきま
す。

大雑把ですが、これがGAの流れです。もちろん、ここ
で述べたことはあくまでイメージとして捉えるための
ものなので、詳細は専門書を読まれることをお勧め
します。私が講義で使ってるのは、萩原将文著「遺伝的アルゴリズム(朝倉書店)」です。最初の1,2章
を理解しておけば、概要を掴むには十分かと思います。
    • good
    • 1

GAを初めて学んだころは、下の書籍を参考にしました。


というか、もろにプログラムが載ってます。

安居院猛,長尾智晴,
「ジェネティックアルゴリズム」
昭晃堂,1993

さて、GAを実際に使うためには、
あらかじめ考えなくてはならないことがあります。
一つは解(ご質問の例では「○」)をどう染色体にコーディングするか、
もう一つは、適応度関数をどのように設定するか、です。

まずコーディングですが、一般的に数値を解として求めたい場合は、
2進数や、グレイコード(興味があったら調べて下さい)を染色体で表現します。
染色体での表現は、染色体長の二進ビット列ですが、
何も考えず整数を表現するのではなく、
たとえば染色体で表現された整数を100で割ったりすれば、
100分の1の精度で小数を表現することができます。
精度と定義域から染色体長とコーディング方法を決めるとよいですね。

次に適応度関数ですが、これは求めたい解が最大適応度になるような関数にします。
例の問題であれば、たとえば
f = 1 ÷ ( | 12 - 3x○ | + α )
とかなんとかすると、○が4のときにfが最大になりますね。

このような決め事を経て、いよいよプログラミングをするわけですが、
これは#1の方のご回答が適当と思われますので、割愛します。
上で書いた適応度は最適解のとき最大になりますので、
ルーレット選択の方法が#1の方の説明と異なりますから、
一応アルゴリズムを簡単に説明しておくと、
全個体の適応度の総和Sを求め、0~Sの乱数Rを発生させ、
個体番号(たとえば配列の要素番号)順の累積和と比較し、
Rが初めて累積和を下回ったときの番号の個体を選択します。
この方法で2つの個体を選択すれば交叉や突然変異によって新しい個体を生成することができます。
そして、個体数だけの個体を生成したところで世代交代になります。
    • good
    • 0

はじめまして。


私は以前に遺伝的アルゴリズムを
若干やっていたものです。
私も似たような課題プログラムをC言語で作成しました。
そのときはX^2の(0<x<10)での最大値を求める課題でした。
基本的には、アルゴリズムは変わらないはずです。

#define G_SIZE 8 //遺伝子配列のサイズ

struct Gene { //遺伝子の構造体
int binary[G_SIZE]; //遺伝子(0、1の値)
int x; //遺伝子から生成される変数x
int result; //実際の計算結果(3×X)
int value; //評価値
}

と以上の様に宣言してみます。
ここでは、遺伝子=3×○の○の値としています。
binaryは遺伝子を2進数の配列と仮定しています。
これを十進数に直したのがメンバ変数のXです。
resultは実際に3×Xの計算結果です。
上での構造体(遺伝子)を乱数など用いて幾つも生成していき
そこから遺伝的アルゴリズムの流れを適用します。
必要とされる関数としては、
実際に掛け算をする関数(1)、
掛け算の結果からその遺伝子が解に近いかを評価する関数(2)、
遺伝子を淘汰させる関数(3)、
遺伝子を交叉さえる関数(4)、
突然変異をさせる関数(5)、
以上が必要です。(主な流れはmain()内で作成)
(1)は簡単です。(関数化する必要も無い様に思われますが流れを見易くするため)
(2)は、理想とする解を
#define ID_VALUE 12 //Ideal Value(理想的な値)
として、12にどれだけ近いかを評価値とすれば良いと思います。
例えば
int value_as( int a ) { //評価関数
int res; //返り値

res = ID_VALUE - a; //理想的な値との差を取る
if ( res < 0 ) res = (-1)*res; //値を正の値にする
return res;
}
以上の様なのはどうでしょうか?
GAが最適解を取りえるかを左右する部分でもありますが、
簡単な問題なのでこの程度がちょうど良いかと思います。
(3)はルーレット法を用いてはどうでしょうか。
(私はそれしか知らないんです。すいません)
ルーレット法はご存知かと思いますが、
この方法は全体の評価値の中で、その遺伝子がどれだけの割合を占めているかで
次の世代への生存確率を決定するものです。
大学の課題ということなので、ここはヒントを書き加えるのみにさせて頂きます。
そのほうが質問者のこらからのプログラミング技術向上のためかと思います。
○流れ
 (1)全体の評価値の総和をとる(ルーレットの作成)
 (2)遺伝子毎の範囲を記録(ルーレット盤上で占める範囲)
 (3)乱数をとる(ルーレットに当てる矢)(ダーツをイメージして下さい)
 (4)何回か(1)~(3)を繰り返す。(繰り返しの回数は定数か乱数で決定)
 (5)矢の当たった遺伝子を削除(淘汰)
以上のでプログラムが書けるのではないでしょうか?
(4)の交叉の関数も然程難しくはありません。
乱数を用いて交叉する遺伝子の組を決定し、
配列binaryのどの部分を入れ替えるかを乱数で決定します。
(一点交叉の場合。多点交叉の場合は乱数で範囲を決定すれば出来ます。)
(5)でも同様に、
乱数を用いて突然変異をするかを決定し、
配列binaryのどの部分の値を変えるかを乱数で決めます。
そして、(1)から(5)までの行程を複数回行い終了決定条件に至ったら
終了させます。
終了決定条件は自分で考えてみてください。
例えば、
 遺伝子全部が同じ値になったらそれを解みなして終了、とか
この終了決定条件も遺伝子数などに左右され、最適解を出すかという部分にも
色々と影響してきます。
ここを変えることで解への収束速度が変わる訳です。
(実際には突然変異、交叉をさせる確立と評価関数の方が影響は大きい)

以上で参考になれば幸いです。
課題頑張ってください。
    • good
    • 1

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qエクセルで種類を数える関数が無いのは何故?

エクセルで種類を数える関数が無いのは何故なんでしょうか?

エクセルで種類を数えるには、いくつかの関数を組み合わせるのが一般的ですよね?
直接数える関数が無いのは、訳があるんでしょうか?

Aベストアンサー

>>エクセルで種類を数える関数が無いのは何故なんでしょうか?

やっぱり、そういう関数が必要な方が全体からみたら少数派だと、エクセルの開発者たちが考えているからではないかと思います。
また、既存の関数を組み合わせたら、対処可能だから、無理して新しい関数を作る必要性もない、開発の優先順位が低いって判断もあるでしょうね。

私は、エクセルの表を作ったり、エクセルVBAでプログラムを作ったりしますけど、そういう関数が必要になったことが全くありませんし。

QMQL4というプログラム言語について。 どうにかこのプログラム言語が学びたいのですが、何からしたら

MQL4というプログラム言語について。

どうにかこのプログラム言語が学びたいのですが、何からしたら良いのか、わかりません。自分でMT4用のインジケーターを作りたいという思いがあります。

Aベストアンサー

プログラムの基礎からでしたらここがおすすめかと思います。
http://jidoubaibai.com/burogu7.html

実際にどういう関数があるかはこちら
http://mt4-traders.com/reference/
http://www.metasys-seeker.net/MQL4_Reference_ver1/MQL4_Reference_Contents.html

あとはどのプログラム言語を学ぶ上でも同じですが
ひたすらにグーグル検索力を磨くということです。

Qエクセルの関数で

エクセルの関数辞典を見ていたら、CUMPRINC関数というのがありました。
しかし、エクセルの「挿入」→「関数」→関数の分類で「財務」というのを選択したのですが、一覧表に載っていません。
どこに載っているのでしょうか?
どうすればこの関数を使えますか?
ちなみにシートの上でやっても関数の反応をしませんでした。

Aベストアンサー

Yahooで検索してみると、参考URLが引っかかりました。

参考になりませんか?

参考URL:http://money-sense.net/doc/20041215_224257.php

Q秒数を入力すると○時間○分○秒と計算するプログラム

はじめまして、Javaのプログラムの問題で
プログラム実行後に秒数を入力すると○時間○分○秒と計算するプログラムを作成しろとでました。
例 何秒を変換しますか?
  3856(キーボードから入力)
  3856秒は1時間4分16秒です。

for文を使うらしいのですが調べても全く分からない状態です。
学校でJavaを習ってまだ半年です。教科書はやさしいJava第3版です。
回答のほうお願いいたします。

Aベストアンサー

Javaだと課題の丸投げになっちゃいますから、C言語で回答してみる。

#include "stdio.h"

int main(void)
{
int s,s2,m,h;

printf("何秒を変換しますか?:");
scanf("%d", &s);

m = s / 60;
s2 = s % 60;

h = m / 60;
m = m % 60;

printf("%dは%d時間%d分%d秒です。\n",s,h,m,s2);
}

Qエクセルの関数 ネスト

エクセルの関数 ネスト

エクセルの関数で、ネストさせるときがあるとおもうのですが、

関数を内側に書いたらよいのか外側に書いたらよいのか分からなくなる時があります。

エクセルの関数に関してわかりやすく書いてあるページなどありますか。

Aベストアンサー

こんばんは

Excel2003までは、ネストが7まで、2007では64までが可能です。
http://www.google.co.jp/search?hl=ja&source=hp&q=excel+%E3%83%8D%E3%82%B9%E3%83%88%E3%80%802003%E3%80%802007&aq=f&aqi=&aql=&oq=&gs_rfai=

「仕様上は可能」でも、複雑なネストは間違いが生じやすいですし、変更もしにくくなります。「出来るだけネストはしない」「適宜、中間結果をセルに出力する」という方法を採った方が、間違いが少なく、柔軟性のあるシステムになると思います。

>エクセルの関数に関してわかりやすく書いてあるページなどありますか。
関数の個別の機能ならば、Webサイトも書籍も多数あるのですが、「組み合わせて使う」というのはその場その場での発想になってしまうと思います。

QC言語のプログラム問題

【質問】
次の処理を行うプログラムを作成する。
(1)10個の要素を持つ一次配列dat[10]を宣言する
(2)dat[0]に0、dat[1]に1をセットする
(3)dat[2]以降の要素には、前の2つの要素の和を計算し入力する。
(4)配列の各要素の値を表示する

【プログラム作成例】
dat[ 0] = 0
dat[ 1] = 1
dat[ 2] = 1
dat[ 3] = 2
dat[ 4] = 3
dat[ 5] = 5
dat[ 6] = 8
dat[ 7] = 13
dat[ 8] = 21
dat[ 9] = 34

上記の解答は下記の通りなのですが、下記以外の解答方法を教えてはいただけないでしょうか?
C言語に詳しい方よろしくお願いいたします。


#include <stdio.h>
main()
{
int i, dat[10];
dat[0] = 0;
dat[1] = 1;

for (i=2; i<10; i++) {
dat[i] = dat[i-2] + dat[i-1];
}
for (i=0; i<10; i++) {
printf ("dat[%2d] = %2d\n", i, dat[i]);
}
return (0);
}

【質問】
次の処理を行うプログラムを作成する。
(1)10個の要素を持つ一次配列dat[10]を宣言する
(2)dat[0]に0、dat[1]に1をセットする
(3)dat[2]以降の要素には、前の2つの要素の和を計算し入力する。
(4)配列の各要素の値を表示する

【プログラム作成例】
dat[ 0] = 0
dat[ 1] = 1
dat[ 2] = 1
dat[ 3] = 2
dat[ 4] = 3
dat[ 5] = 5
dat[ 6] = 8
dat[ 7] = 13
dat[ 8] = 21
dat[ 9] = 34

上記の解答は下記の通りなのですが、下記以外の解答方法を教えてはいただけないでしょうか?
C...続きを読む

Aベストアンサー

Cはもはや覚えていませんが・・・。

#include <stdio.h>
main()
{
int i, dat[10];
dat[0] = 0;
dat[1] = 1;

for (i=0; i<2; i++) {
printf ("dat[%2d] = %2d\n", i, dat[i]);
}
for (i=2; i<10; i++) {
dat[i] = dat[i-2] + dat[i-1];
printf ("dat[%2d] = %2d\n", i, dat[i]);
}
return (0);
}

上記のような方法でも可能だし、0~9まで一度のfor()でif()使っても出来ますね。
後は回したり比較したりの回数が多ければ速度が落ちる、くらいでしょうか。
(1)~(4)の手順を完全に守れ、というならば、質問にある方法
程度しかないでしょう。

自信はありませんのであしからず・・・。

Qエクセル関数の解読サイトなんてありますか?

エクセル関数の解読サイトなんてありますか?

いつもお世話になっております<(_ _)>

エクセルファイルに関数の入った数式が入力されています。
セルごとに複数の関数が入っていますが、私にはちっともわかりません。

そこで質問です。
こんなとき「エクセル関数を解読」してくれるようなサイトってありませんか?

たとえば検索窓があってそこに「=SUM(S1:S13)」わからなくて困っている関数式を入力。
すると答えの別ボックスに「S1~S13までの数値の合計」と出てくるようなサイト。

それに近いサイトでも良いので知っている方がいらっしゃればぜひ、教えてください<(_ _)>

Aベストアンサー

もし、

=IF(E14="","",IF(O14="",(IF(E14>"18:00"*1,"18:00",E14)-IF(C14<="8:00"*1,"8:00",C14))*24*1300,(IF(E14>"18:00"*1,"18:00",E14)-IF(C14<="8:00"*1,"8:00",C14))*24*1625))

だったら、どういう文章が出て欲しいのでしょうか?

もしE14が空白だったら、
 空白、
そうじゃなかったから、
 もしO14が空白だったら、
  (もしE14が18:00より大きかったら18:00、そうじゃなかったらE14)-(もしC14が8:00以下だったら8:00、そうじゃなかったらC14)×24×1300
 そうじゃなかったら、
  (もしE14が18:00より大きかったら18:00、そうじゃなかったらE14)-(もしC14が8:00以下だったら8:00、そうじゃなかったらC14)×24×1625

って感じですか?
数式をそのまま読解したほうが解りやすくないですか?

QC言語 プログラムの質問

下記の問題はすでに他で回答されていますが、私のプログラムのどこがいけないかチェックしていただけませんか?

1)101人以下のクラスがあり、学生には1から通し番号が付いているものとする。 このクラスのある科目の得点を通し番号順にキーボードから受けとり、負の得点が入力されたら全員の入力が終わったものとする。 その後、キーボードから入力された番号の人の得点をxx点と漢字で表示し、存在しない番号が入力されたらプログラムを終了する。

2)第 1 種の定形外通常郵便物の料金は、次の表のように定められている。 郵便物の重さを g 単位で入力すると、料金が出力されるプログラムを作成しなさい。 ただし、以下の点を考慮すること。
*重さと料金の表は、2 次元配列として取り扱うこと

*指定された範囲外の値(負の値,0,4001以上)が入力された場合は、正しい値が入力されるまで入力処理を繰り返すこと

  重さ  料金
  50gまで  120円
  100gまで  140円
  150gまで  200円
  250gまで  240円
  500gまで  390円
 1000gまで  580円
 2000gまで  850円
 4000gまで  1150円
-----------------------------------------
自分のプログラム
1)
#include <stdio.h>

int main(void) {
int Snumber[101],score[101],i,n;

for(i=0;i<101;i++){
scanf("%d",&score[i]);
if(score[i]<0){
break;
}
}

for(n=0;n<i;n++){
if(score[i-1]==''){
break;
}
printf("学生番号:%d\n %d\n",Snumber[i],score[i-1]);

}

}
-----------------------------------------------

2)
#include <stdio.h>

int main(void) {
int weight,i;
int array[8][2] = { {50,120},
{100,140},
{150,200},
{250,240},
{500,390},
{1000,580},
{2000,850},
{4000,1150},
};

scanf("%d",&weight);
for(i=0;i<8;i++){
if(weight<=0){
break;
}else if(weight>= 4001){
break;
}else if(weight <= array[i][0]){
printf( "料金 : %d円\n", array[ i ][ 1 ] );
}
}


}

下記の問題はすでに他で回答されていますが、私のプログラムのどこがいけないかチェックしていただけませんか?

1)101人以下のクラスがあり、学生には1から通し番号が付いているものとする。 このクラスのある科目の得点を通し番号順にキーボードから受けとり、負の得点が入力されたら全員の入力が終わったものとする。 その後、キーボードから入力された番号の人の得点をxx点と漢字で表示し、存在しない番号が入力されたらプログラムを終了する。

2)第 1 種の定形外通常郵便物の料金は、次の表のように定...続きを読む

Aベストアンサー

> if(score[i-1]==''){

この意図は?

> printf("学生番号:%d\n %d\n",Snumber[i],score[i-1]);

Snumber[i]は宣言したままで、何も代入されていません。

このループ中、iに変化はありません。つまり、Snumber[i]もscore[i-1]も常に同じものを表します。
何が変化するかをよく考えてください。


> *指定された範囲外の値(負の値,0,4001以上)が入力された場合は、正しい値が入力されるまで入力処理を繰り返すこと

というプログラムになっていません。
範囲外は即終了になっています。

また、このプログラムでは、関係無い料金まで表示されます。
条件をよく考えてください。

Qエクセル関数を、書き写して分析できるツールはある?

タイトルの件、質問します。

エクセルの関数を分析する際に、エクセルの数式バーや、セルに入っている関数を
F2を教えて見るのでは、見にくい場合があります。

現在は、私は、メモ帳に関数をコピーして、分析したり、修正したりしています。
エクセルの機能or他ソフトで、関数を分析できるツールはあるのでしょうか??

【エクセルバージョン】
2003、2007

Aベストアンサー

難解な数式を理解したいとき,最も便利に利用できるのは,2003ではツールメニューのワークシート分析にある「数式の検証」です。
2007では数式タブにあります。

メンドクサイ数式のセルで数式の検証を使い,どの関数やどのカッコから計算が進んでいくのかを1ステップずつトレースして理解します。また意図しない結果がどの段階で発生しているのか追跡します。

このやり方は勿論間違った数式(意図しない結果が出てきた場合)を追跡するのにも使いますが,むしろ誰かに教わった「正しい数式」を理解する時に便利な方法です。
そもそも計算が通っていない(たとえばカッコの対応が間違えていて,Enterしても受け付けてくれないようなミスをしている場合)には使えません。



また,数式バーの中で数式の「中」にカーソルを入れて左右の矢印キーでカーソルを動かしていったときに,「(」や「)」をまたいだ瞬間に,対応する「閉じカッコ」「始まりのカッコ」が色つきで強調表示されるのを確認しながら,カッコの対応がまちがえてないかなどを調べるのも簡易な良い方法です。


あまり使わない方法ですが,数式の中で適宜ALT+Enterを打って「セル内改行」してしまい,数式を縦に分解して書いてみるのも整理しやすい方法のひとつです。

難解な数式を理解したいとき,最も便利に利用できるのは,2003ではツールメニューのワークシート分析にある「数式の検証」です。
2007では数式タブにあります。

メンドクサイ数式のセルで数式の検証を使い,どの関数やどのカッコから計算が進んでいくのかを1ステップずつトレースして理解します。また意図しない結果がどの段階で発生しているのか追跡します。

このやり方は勿論間違った数式(意図しない結果が出てきた場合)を追跡するのにも使いますが,むしろ誰かに教わった「正しい数式」を理解する時に便利...続きを読む

Q突然変異について 突然変異によって遺伝子の多様性は、、 高くなる、低くなる、変化がない のどれ

突然変異について

突然変異によって遺伝子の多様性は、、

高くなる、低くなる、変化がない

のどれでしょうか。。

そして突然変異の発生頻度には特に何と何が強く影響を与える。

【放射線、酸素、窒素、二酸化炭素、紫外線】
の中から2つ選ぶ問題で
参考書色々調べたのですが載ってなかったので教えてもらえたらお願いします!

Aベストアンサー

突然変異によって遺伝子の多様性は→「高くなる」
集団内、または種内で遺伝的変異の量が多ければそれだけ遺伝的多様性がある証拠であり、突然変異はその究極のソースですから。

発生頻度に影響をあたえるのは→放射線 紫外線
生物は自然の状態でも一定の低い頻度で突然変異をおこしていますが、この頻度を増大させる作用をもつ要因を突然変異原といいます。放射線、紫外線はこの突然変異原にあたります。


人気Q&Aランキング

おすすめ情報