 |
本書の最後は、「何でもシミュレーションしてみよう」と題し、ギャンブルから、最近注目されている、ジェネティックアルゴリズムまで、乱数を用いた、さまざまな、確率実験を、試みます。
クラップスという名のゲーム文献（８）（１３）
カジノで行われているダイス（サイコロ）を使った、クラップスというゲームをとりあげます。このクラップスに限らず、カジノで行われるゲームは、すべて
胴元が有利となるようなルールが定められています。したがって長時間平均すれば、必ず胴元が勝つ仕組みとなっているわけですが、必勝法はないものでしょう
か。
まず、クラップスのルールを説明します。クラップスは２個のサイコロを用いておこないます。２個のサイコロの目の合計は２から１２までの値をとりま
す。（３．５節で示したとおり、７の出る確率が最も大きい。）プレーヤは２個のサイコロを振って、その和が７または、１１の時（これをナチュラルといいま
す）は勝ちで,２、３あるいは１２の時（これをクラップスといいます）は負けです。もしそれ以外のとき、すなわち、４、５、６、８、９または、１０がでた
ときは、その値をポイントといい、ひきつづき同じポイントまたは７が出るまで、サイコロを振ります。そして同じポイントがでれば、プレーヤの勝ち、それ以
前に７が出れば、負けとなります。もしプレーヤが勝てば、自分の賭け金の２倍の払い戻しを受けます。
このゲームは、たいへんよくできて、ごく僅かな確率の差で、胴元が勝つようにできています。
必勝法
このゲームで必ずプレーヤが勝つ方法はあるでしょうか。もしそれがあれば、ぜひカジノに行って見たいものです。倍増法という必勝法が知られています。倍
増法というのは、まず１ドルの賭け金からスタートし、もし勝てば、次も１ドルを賭けますが、負けた場合は２ドルを、さらに負ければ前回の賭け金の２倍の額
を次々に賭けていく方法です。この方法では、負けた金額をとりもどせるので、必勝法となりそうです。はたして、これがほんとうに必勝法となるのでしょう
か。クラップスにおいて、倍増法をシミュレーションしてみましょう。
シミュレーション・プログラム
ではクラップスのシミュレーションプログラムS1010.javaの説明を行ないます。まず、(1)サイコロの関数を作ります。
int dice();
により、整数１～６の一様分布の乱数を発生させます。次に、(2)のとおりクラップスのルールどおりに記述して、関数
int craps(void);
を作ります。１回目のサイコロの目の和を sum1 , ２回目以後のサイコロの目の和を sum2 としています。この関数は、勝ちの場合１、負けの場合０の値を返します。
次にメインプログラムですが、１回の賭け金を k ドル、現在の持ち金を q ドルとします。(3)が倍増法による賭けで、もし勝った場合、次の賭け金を１とし、負けた場合前回の２倍を賭けることとします。プログラムでは、賭けを何回も繰り返し、横軸賭けの回数 t 、縦軸持ち金 q をグラフに表示するようにしています。
シミュレーションの結果
プログラムを実行すると、図１０．１．１のように時間とともに、着実に持ち金は増加していきますが、時々負けが続くと賭け金が急増し、赤字に転落すると
きがあります。もしその時、もち金がなくなれば破産ですが、なお余裕があって倍々と賭けることができれば、必ずプラスになります。しかしながら、通常は胴
元のほうが資金は豊富で、負けが続いても持ちこたえられるのに対し、客のほうが先に底をついてしまいます。もし十分な資金を用意することができれば、ぜひ
カジノへ行って、ひと儲けして下さい。
| 図１０．１．１ 倍増法による必勝法 |
 |
| S1010.java ギャンブル必勝法 | Download | 実行 | |
/* S1010.java
* ギャンブル必勝法
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import window.Window;
public class S1010 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 = 30;
int HIGHT = 400;
int WIDTH = 640;
long t; /* 賭の回数 */
long q = 100; /* 持ち金 はじめは１００ドル */
long k = 1; /* １回の賭金１ドル */
long T_END = 500; /* 終りの回数 */
/*グラフィックの準備*/
w.setWindow(0, 0.0,0.0,(double)T_END,500.0,
SPACE,HIGHT-SPACE,WIDTH-SPACE,SPACE);
w.axis(0, "t", T_END/10, "q", 100, g);
w.moveTo(0, 0.0, q, g);
g.setColor(Color.blue);
/*メイン*/
for (t = 1; t <= T_END; t ++) {
q = q - k;
if (craps() == 1) { /* (3)勝った場合 */
q = q + 2 * k;
k = 1; /* １ドル賭ける */
} else { /* 負けた場合 */
k = k * 2; /* ２倍賭ける */
}
w.lineTo(0, (double)(t), (double)(q), g);
}
}
public static int dice(){ /* (1)サイコロ */
return((int)(Math.random() * 6.0 + 1));
}
public static int craps(){ /* (2)クラプスのルール */
int r; /* 1:勝ち 0:負け */
int sum1; /* 和１ */
int sum2; /* 和２ */
sum1 = dice() + dice();
if (sum1 == 7 || sum1 == 11) { /* ナチュラル */
r = 1;
} else if(sum1 == 2 || sum1 == 3 || sum1 == 12) { /* クラップス */
r = 0;
} else {
sum2 = 0;
r = 0;
while (sum2 != 7) { /* ７が出るまで */
sum2 = dice() + dice();
if (sum2 == sum1) { /* ポイント */
r = 1;
break;
}
}
}
return(r);
}
}
|
在庫管理問題とは
企業や産業システムでは、原料や製品が供給から需要ひ向かって流れていく過程において、それらを貯蔵する機能が必要です。この貯蔵容量と、それを運用管理する最適の方法を決定するのが、在庫管理問題です。
例えば、ある商店が商品を問屋から仕入れて、客に販売する場合を考えてみましょう。商品を一度に多量仕入れると、在庫をたくさんかかえ、そのための費用
がかさみます。逆に少量の在庫では、大きな需要があった場合に品切れの危険が生じ、得べかりし利益をそこない、ひいてはその店の信用を失います。しから
ば、① 在庫に要する費用、② 問屋への発注のための費用、③ 品切れが発生した場合にこうむる損失の合計を最小にして、利益を最大にするには、いつどれ
だけ問屋に発注すべきでしょうか。
販売店の在庫 q は、図１０．２．１のように毎日の売上げ k 個ずつ減少していきます。基準発注点 q1 をわったら、 a 個の発注をしますが、すぐには入荷せず、 lt 日の遅れがあります。図１０．２．２のように、在庫量は変化するでしょう。売上げ個数と入荷おくれが確率的である場合を考え、
q1 の最適値を求めるためのシミュレーション・プログラムを作ってみましょう。
| 図１０．２．１ 在庫モデル |
 |
| 図１０．２．２ 在庫 q の変化と lt |
 |
プログラムのポイント
売上げ個数は、毎日平均 AL のポアソン分布に従うとします。また入荷遅れ日数 lt は平均 ET 、標準偏差 ST の正規分布にしたがうものとします。これらの乱数の発生には４章で作った関数を用います。シミュレーション・プログラムの方式は１日をクロックとして進める固定時間方式を用います。ここで重要な変数は、(1)入荷遅れ日数
lt で次の意味を持ちます。
lt > 0 ：すでに発注ずみであり、あと lt 日で納品される。
lt = 0 ：本日納品される。
lt < 0 ：発注していない。
(2)で１日平均 k 個ポアソン分布の売上げがあったとします。(3)で発注点 q1 を割り、まだ発注していなければ発注します。(4)で q が負になれば、在庫なしで販売しそこなった数 ls を数えます。(5)では、本日納品されたので、在庫に A を加えます。(6)で在庫費用の累計を計算します。 T_END 日分のシミュレーションを終わったあと、発注費用の累計 sc2 、品切れ損失の累計 sc3 、売上個数の累計 yk を計算し、総売上げ rr を求めます。そしてグラフをプロットし、発注点 q1 をかえ、シミュレーションを続けます。
アウトプット
１００００日分のシミュレーションを q1 を０から１００まで変化させ、繰り返し行います。 出力されたグラフ図１０．２．３を見ると、q1=45 の時に、利益が最大となることがわかります。
| 図１０．２．３ 在庫管理の問題 シミュレーション結果 |
 |
| S1020.java 在庫管理の問題 | Download | 実行 | |
/* S1020.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 S1020 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 = 30;
int HIGHT = 400;
int WIDTH = 640;
long A = 100; /* １回の入荷量 */
long AL = 5; /* １日の平均売上個数 */
long ET = 6; /* 納品するまでの平均日数 */
long ST = 2; /* 納品するまでの日数の標準偏差 */
double SP = 7000.0; /* 売値 */
double PC = 5000.0; /* 仕入れ単価 */
double C1 = 20.0; /* １日１個当たりの在庫費用 */
double C2 = 10000.0; /* １回の発注にともなう費用 */
double C3 = 500.0; /* 品切れ１個あたりの損失 */
long T_END = 10000; /* 終りの時刻 */
long Q1_MAX = 100; /* q1の最大値 */
long tt; /* シミュレーション日数 */
long q; /* 現在在庫量 */
long q1; /* 発注点 */
long k; /* １日の売上個数 */
long zk; /* kの累計 */
long yk; /* 売上個数の累計 */
long ls; /* 在庫割れのため売り損なった個数 */
long nn; /* 発注回数 */
long lt; /* (1)入荷遅れ日数 */
double sc1; /* 在庫費用の累計 */
double sc2; /* 発注費用の累計 */
double sc3; /* 品切れ損失の累計 */
double rr; /* 総売上 */
int l = SPACE; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat("0");
/*グラフィックの準備*/
w.setWindow(0, 0.0,0.0,Q1_MAX,1.0e08,
5*SPACE,HIGHT-SPACE,WIDTH-SPACE,SPACE);
w.axis(0, "q1", 10, "rr", 1e07, g);
w.moveTo(0, 0.0, 0.0, g);
g.drawString(" q1 rr" ,10 ,l);l = l + 12;
/*メイン*/
for (q1 = 0; q1 <= Q1_MAX; q1 = q1 + 5) { /* q1を0からQ1_MAXまで変化させ
シミュレーションを行う */
/* 初期設定 */
tt = 0; q = A; zk = 0; ls = 0; nn = 0; lt = -1;
sc1 = 0.0; sc2 = 0.0; sc3 = 0.0;
/* １日分のシミュレーション */
while (tt <= T_END) {
k = poisson(AL); /* (2)k個売れた */
q = q - k;
zk = zk + k;
if (q < q1 && lt < 0) { /* (3)発注点を割ったので発注する */
lt = (long)normal(ET, ST);
nn = nn + 1;
}
if (q < 0) { /* (4)在庫割れのため売り損ない */
ls = ls - q;
q = 0;
}
if (lt == 0) { /* (5)入荷 */
q = q + A;
}
sc1 = q * C1 + sc1; /* (6)在庫費用の累計を計算 */
lt = lt - 1;
tt = tt + 1;
}
sc2 = nn * C2;
sc3 = ls * C3;
yk = zk - ls;
rr = (SP - PC) * yk - sc1 - sc2 - sc3; /* 総売上の計算 */
/* 出力 */
g.drawString(" " + q1 + " " + exFormat1.format(rr) , 10, l);
l = l + 12;
if (q1 == 0) {
w.moveTo(0, q1, rr, g);
} else {
w.lineTo(0, q1, rr, g);
}
}
}
long poisson(double lambda) { /* ポアソン乱数発生 */
double xp = Math.random();
long k = 0;
while (xp >= Math.exp(-lambda)) {
xp = xp * Math.random();
k = k + 1;
}
return (k);
}
double normal(double ex, double sd) { /* 正規乱数発生 */
double xw = 0.0;
double x;
long n;
for (n = 1;n <= 12; n ++) {
xw = xw + Math.random();
}
x = sd * (xw - 6.0) + ex;
return (x);
}
}
|
鉄は強磁性体
本節では、シミュレーション技術を用いて、１つ１つの原子の動きを計算し、物質全体としてどういう性質をもっているかを、鉄のような強磁性体を例に解析してみましょう。
原子の模型は、図１０．４．１のように、原子核のまわりを電子がまわっているように書けます。電子はマイナスの電気をもっており、電子が回転運動すると
磁場ができます。その軸は原子の中心を通り、電子の軌道面に対して垂直です。この磁場のことを電子の軌道磁気モーメントと言います。また電子は自転しなが
ら軸のまわりを回っており、これによっても、磁場が生じています。これをスピン磁気モーメントと言います。これら二種類の磁気モーメントが加え合わされ、
原子１つの磁気モーメントとなります。
| 図１０．４．１ 原子の模型 |
 |
鉄の原子の場合は、スピン磁気モーメントの釣合がひどくずれており、原子１つ１つが小さな磁石となっており、その強さはすべての元素の原子なかで一番強
いのです。鉄の原子は、結晶の格子点に固定されて動くことができませんが、その向きは自由に変り、いろいろの方向を向きます。鉄の棒を磁化して磁石にする
というのは、できるだけたくさんの原子の磁場の方向を並行にそろえることにほかなりません。
これはごく大ざっぱにいうと、鉄原子の電子スピンによる磁気モーメントは、近接する原子間では、互いに逆向きよりも平行の方がエネルギーが低くなるような相互作用が動いているためです。（図１０．４．２ａ）
磁石が磁石でなくなる
ところが温度を高くすると、原子はしだいに無秩序になり、上向き下向きのスピンの原子があらわれます。そしてある温度（ピエル・キュリーが発見した。
キュリー温度という）を越すと、向きがばらばらになり、鉄全体の磁気モーメントはほぼ零になり、鉄は磁石でなくなってしまうのです（図１０．４．２ｂ）。
このことを、強磁性体からの相転移といいます。シミュレーションにより、この相転移の実験をしてみましょう。
| 図１０．４．２ 絶対零度の場合とある温度の場合のスピン磁気モーメント |
 |
イジング・モデル
今原子が図１０．４．３のように２次元格子状に並んでいるとします。原子
(i,j) の状態は、スピンが上向きか、下向きかという２つの状態だけをとるものとし、それを
s(i, j)=1 , s(i, j)= -1 とします。この値をスピン変数といいます。
ある原子 (i0, j0) が、まわりの原子から受けるエネルギーは、まわりの原子のスピンの方向と、自分のスピンの方向によって決まり、その値は、
 |
・・・・・ |
式１０．４．１ |
となります。 J は物質によって異なり、 (i0, j0) から離れるにしたがって小さな値となります。特に原子 (i0, j0) から見てすぐ隣りの原子からのみ相互作用を受けるとすれば、式は、
 |
|
|
| ・・・式１０．４．２ |
|
|
となります。 e の値は、原子 (i0, j0) から見て、まわりの原子のスピンの方向が全部逆であれば、一番大きく、また原子
(i0, j0) とまわりの原子のスピンが全部同じであれば、一番小さくなります。
ある温度で、原子 (i0, j0) が向きを反転する確率は、統計力学の教えるところにより、単位時間あたり、
 |
・・・・・ |
式１０．４．３ |
となります。ここで、 k はボルツマン定数、 T は絶対温度、 e は式の値、 A は定数です。
式１０．４．２と、式１０．４．３から、原子 (i0, j0) が反転する確率は、 T が高くなると高くなり、逆向きの原子にとりかこまれているとき最も高く、まわりの原子と同じ向きのとき最も低くなります。
このようなモデルを提案者の名前をとって、イジング・モデルといいます。
| 図１０．４．３ |
 |
プログラムのポイント
以上のモデルを、シミュレーションにより実現します（プログラムS1040.java）。温度を高温にすると、あちらこちらで、同時に反転が起こりますが、シミュレーションでは、時計を停止させ、ランダムに原子を選び出し、処理します。
それにはまず、モデルの磁石の原子に相当する配列を用意します。(1)で１辺の大きさが、
MAX+2 （値は 0 から MAX+1 ）の配列を作り、その中の 1 から MAX までを使います。 0 と MAX+1 は式１０．４．２の計算をするとき i 、 j が 1 や MAX の値をとったとき、その隣りの値が配列をはみださないようにするためです。(2)そして初期状態は、絶対零度としすべて磁気モーメントは同方向、すなわち
s(i,j)=1 とします。
次に(3)、(4)で２つ１組の １ から ＭＡＸ までの整数値をとる一様分布の乱数を発生させます。この１組の乱数により、原子を１つ選び、式１０．４．２の相互作用のエネルギーを計算し（5）、式１０．４．３の反転の確率を計算します（6）。ここで
w0 = kT/J とおいて正規化温度としています。また A = exp(-4/w0) とします。別に発生した乱数とこの確率を比べ（7）、乱数の方が小さければ、原子を反転させます（8）。この処理を ＭＡＸ×ＭＡＸ 回繰り返すと、各原子について、平均１回処理を行ったことになるので、クロックを１進めます。
アウトプット
s(i, j)=1 である原子の数を数えて、磁化率を計算します（9）。磁化率は全部の原子が
s(i, j)=1 であれば１, １と－１が半々であれば０の値を取ります。また、ディスプレイに、刻々と原子の反転の様子をプロットさせます。それには反転のたびに
s(i, j) が１の時は青、－１の時は赤で表示します。これによりミクロな原子の動きをパターンとして視覚に訴えることができます。
プログラムを実行してみましょう。図１０．４．４のように絶対零度では、一面に正のモーメント（図では青）であったものが、しだいに負のモーメントの部分（図では赤）ができ、時間の経過とともにそれが合体し（これを磁気ドメインといいます）、形も刻々変化していきます。
ウィンドウ１のグラフは、磁化率をあらわします。
ある温度（キュリー点）以下では、磁化率は０にならず磁石のままで、ある温度
Tc をこえると、相転移が起こり磁化率が０となり、磁石が磁石でなくなっていきます。この時の正規化温度の、理論値は、
 |
・・・・・ |
式１０．４．４ |
で与えられます。 プログラムでは正規化温度w0 を変えることができるようになっていますから、 wc を中心に色々変えて相転移が起こる様子を実験してみて下さい。
| 図１０．４．４ イジングモデル シミュレーション結果 |
 |
| S1040.java イジングモデル | Download | 実行(長時間ＣＰＵ占有) | |
/* S1040.java
* イジングモデル
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import window.Window;
public class S1040 extends Applet implements ActionListener {
Button button0;
Button button1;
boolean sw =false;
TextField text;
double w0; /* 正規化温度 */
public void init() {
add(new Label("正規化温度(2.27を中心に試す)="));
text = new TextField("2.27");
add(text);
button0 = new Button(" 実行 ");
button1 = new Button("クリア");
add(button0);
add(button1);
button0.addActionListener(this);
button1.addActionListener(this);
}
public void actionPerformed(ActionEvent evt) {
String label = evt.getActionCommand();
if (label.equals(" 実行 ")) {
sw = true;
w0 = Double.parseDouble(text.getText());
} else {
sw = false;
}
repaint();
}
public void paint(Graphics g) {
Window w ;
w = new Window();
int SPACE = 30;
int HIGHT = 480;
int WIDTH = 640;
int MAX = 250; /* 配列の大きさ */
long T_END = 1000; /* シミュレーションを終わる時刻 */
int s[][] = new int[MAX+2][MAX+2]; /* (1)磁気モーメントの値
s[i][j]=1あるいはs[i][j]=-1 */
int i,j; /* 着目している原子の番号 */
int e0; /* 相互作用の値 */
int m; /* s[i][j]=1である原子の数 */
int n; /* forのカウンタ */
int tt = 0; /* シミュレーションの時刻 */
double p; /* 反転の確率 */
double gika; /* 磁化率 */
/* 準備 */
w.setWindow(0, 0,0,MAX, MAX, SPACE,MAX+SPACE,MAX+SPACE,SPACE);
w.axis(0, "", MAX, "", MAX, g);
w.setWindow(1, 0,0.0,T_END,1.0, SPACE,HIGHT-SPACE,WIDTH-SPACE,MAX+2*SPACE);
w.axis(1, "時間", T_END / 10.0, "磁化率", 0.1, g);
w.moveTo(1, 0, 1.0, g);
m = MAX * MAX;
/* (2)初期状態 */
for (j = 0; j <= MAX + 1; j ++) {
for (i = 0; i <= MAX + 1; i ++) {
s[i][j] = 1;
}
}
/* メイン */
if (sw) { /*"実行"が押されたとき*/
while (tt < T_END) {
for (n = 1; n <= MAX * MAX; n ++) {
/* (3)1からMAXまでの乱数 */
i = (int)(MAX * Math.random()) + 1;
/* (4)1からMAXまでの乱数 */
j = (int)(MAX * Math.random()) + 1;
/* (5)相互作用エネルギーの計算 */
e0 = -s[i][j] * (s[i][j - 1] + s[i][j + 1] ]
+ s[i - 1][j] + s[i + 1][j]);
/* (6)反転確率 */
p = Math.exp(((double)(e0) - 4.0) / w0);
if ( p > Math.random()) { /* (7) */
s[i][j] = -s[i][j]; /* (8)反転 */
m = m + s[i][j];
}
if (s[i][j] == 1) {
g.setColor(Color.blue);
w.putPixel(0, (double)(i), (double)(j), g);
} else {
g.setColor(Color.red);
w.putPixel(0, (double)(i), (double)(j), g);
}
}
tt = tt + 1;
gika = (double)(2 * m) / (double)(MAX * MAX) - 1.0; /* (9)磁化率 */
g.setColor(Color.green);
w.lineTo(1, tt, gika, g);
}
stop();
}
}
}
|
ジェネティック・アルゴリズムとは
ジェネティック・アルゴリズム（ＧＡ）は遺伝的アルゴリズムともよばれ、生物の進化過程をシミュレーションすることによって、たくさんの組み合せのなか
から最適な解を見つけ出す手法のことをいいます。ダーウィンの自然淘汰理論というのがありますが、これを基礎に、生物の進化過程を工学的モデルにおきかえ
たものです。
進化過程の概要は、おおよそ次のようにあらわされるでしょう。まず、０と１の値をもつ遺伝子(Gene)からなる染色体（Chromosome)を考え
ます。この染色体のあつまりを集団(Population)といいます。それに対し図１０．５．１ように（１）、（２）、（３）の操作をほどこします。
（１） 交叉
集団内の２つの染色体の組（ペア）において、交叉(crossover)という遺伝子の一部の入れ替えがおこなわれること。
（２） 突然変異
各染色体において、ある確率で、遺伝子の一部が０から１あるいは、１から０に返転すること。
（３） 選択
（１）、（２）をへた遺伝子をもった染色体のうち環境へのより高い適応性をもつものが、選択されること。
（１）、（２）、（３）の遺伝子的操作を１世代とよび、この操作をくりかえしていくと、その集団はより環境に順応する方向に進化します。
ジェネティック・アルゴリズムでは、さまざまな組み合わせを遺伝子からなる染色体で表現し、その組み合わせごとの目的関数を計算します。そして、その値
の高いものを選択し、それを残すよう生存競争を何世代にもわたり行わせれば、最終的には、目的関数の値が最大となるようにすることができます。
ジェネティック・アルゴリズムの原理は、驚くほど単純ですが、その探索能力は非常に高く、通常の方法では解を見つけにくい場合でも、比較的容易に正確に近づくことができるといわれています。
| 図１０．５．１ 組み替え（交叉と突然変異） |
 |
ナップザック問題
ジェネティック・アルゴリズムのメカニズムを「ナップザック問題」という典型的な組み合せ問題を例に、プログラムを作ってみましょう。
図１０．５．２のように、ナップザックがあります。ナップザックにはこべる重さには限界があります。たくさんの異なる重さの、異なる価値をもつ品物が与
えられたとき、重さがナップザックの限界値内で品物を幾つか選択し、その時の価値の合計が最大となるような組み合せを見つけるという問題です。すなわち、
この場合の目的関数は価値の合計で、ナップザックがこわれない範囲で、価値が最も高くなるよう、品物を選んで運ぼうとするものです。
| 図１０．５．２ ナップザックの問題 |
 |
ナップザック問題のプログラム
ナップザック問題を、ジェネティック・アルゴリズムの手法で解く場合、まず、ナップザックに品物が入っている状態を染色体に対応させて、表現する必要があります。図１０．２．５の例では、品物１、３、４をナップザックに入れている状態ですから、これを染色体で
０１０１１
と表現します。
プログラムS1050.javaについて説明していきます。 LENGTH という長さをもつ染色体 を SIZE 個用意します。実際には組み替え操作のため、この２倍の配列gene[][]を(1)により用意します。また、(2)により新世代の染色体を表わす配列 next_gene[][] も準備します。このほか１つ１つの品物の重量、価値をあらわす配列 weight[] 、value[] 、染色体に対応した重量の合計、価値の合計をあらわす配列 total_weight[]、total_weight[] を用います。
(3)で染色体をPROB2 の確率で１にセットしする初期状態にします。 また(4)において、各品物ごとの重量と価値も乱数でセットしておきます。
(5)からがメインの始まりで、遺伝子の組み替え（交叉と突然変異）、目的関数の計算、ソート、新世代へのおきかえ、表示という手続きを、
G_END で示される世代にわたって繰り返し計算します。
遺伝子の組み替えは、図１０．５．３のように行います。 k 番目の染色体と、 k+SIZE 番目の染色体がペアであるとして、交叉の操作を行います。(6)のように交叉位置を乱数で発生させ、
k 番目の後半と k+SIZE 番目の後半を入れ換えます。次に(7)以下のように k の値が SIZE 以上の染色体について PROB という確率で、１と０を反転させ、突然変異を起こさせます。
次に、(8)目的関数を計算します。目的関数は、染色体ごとの、合計の重量と合計の価値です。
gene[k][l] に選ばれた品物の組み合せが示されていますから、(9)あるいは(10)のように、その配列に重量、あるいは価値の配列をかけ、合計の重量、価値を計算します。その場合、重量の合計が、ナップザックの重量の上限
LIMIT をこえた場合、(11)により価値をゼロとし、その染色体が選択されないようにします。
次に、(12)以下のように、価値の合計を大きい順にソートします。ソートのアルゴリズムはさまざまなものがありますが、ここでは、簡単な選択法というアルゴリズムを用います。
total_value[k] について、まず、 k を固定し、 k+1 以下のものと比較し、より大きいものがあれば、それと置き換えます。そして、
k を次々増やして行くと、 total_value[k] が大きい順に並びます。また、 v_sort｢k] に、0,1,2,3,･･･の値を入れておくと、このソートが終わった状態で v_sort[k] に, total_value[k] の大きい方から順番の値が入ります。
ソートの結果を示す v_sort[k] により、(13)のように、大きい順に、 gene[k][l] を取り出し、それを新世代の next_gene[k][l] の染色体を作り、(14)によりgene[k][e]を入れ換えます。
| 図１０．５．３ 遺伝子の組み換え |
 |
結果の出力
２つのウインドウに横軸世代、縦軸それぞれ重量の合計、価値の合計をグラフ表示します。また、もっとも目的関数の大きい k = 0 の染色体の構造、またそのときの重量の合計、価値の合計を表示します。
このプログラムを走らせると、図１０．５．４のように、１００世代ほどで、最適に近い値が得られていますが、１０００世代くりかえし実行する必要があります。
| 図１０．５．４ ナップザック問題 シミュレーション結果 |
 |
| S01050.java ナップザック問題 | Download | 実行 | |
/* 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 ++) {
/* (9) */
total_weight[k] = total_weight[k] + gene[k][l] * weight[l];
/* (10) */
total_value[k] = total_value[k] + gene[k][l] * value[l];
}
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);
}
}
|
１．１０．１節のクラップスは胴元が有利なゲームです。勝っても負けても、毎回１ドルずつ賭け続けた場合、どのくらいの回数でプレーヤが破産するか確かめなさい。
（解答） A1010.java | 実行 |
２． １０．２節の在庫管理問題では、発注点をわった時に発注していたが、毎週１回定時に入荷があるとして、その入荷量を前々日の在庫量により決定し、それにより発注する方法について、シミュレーションし、最適入荷量 を求めなさい。
（解答） A1020.java | 実行 |
３．プログラムs1040.cで w を wc を中心に変えて実行してみなさい。 w が wc より小さい場合、磁化率が０とならず磁石のままであることをたしかめなさい。また
w が wc より大きい場合、磁化率が０となる速度が早いことをたしかめなさい。
（解答省略）
|
 |
