コラム / 遺伝的アルゴリズム / 第4章

HOME 研究室概要 コラム 周辺探索 メンバー 掲示板 リンク

第4章 ナップサック問題でのシミュレーション

 では、最後に今までの総まとめとして、実際に遺伝的アルゴリズムを用いてナップサック問題を解いてみます。そうすることで、みなさんにも遺伝的アルゴリズムの良さが具体的にわかってもらえるはずです。

 このページの目次

4.1節 ナップサック問題
4.2節 問題のマッピング
4.3節 シミュレーション結果

 4.1節 ナップサック問題

 まずは、ナップサック問題について説明します。ナップサック問題とは、複数の品物(それぞれの品物は、重さと値段が違う)が与えられたときに、重さがナップサックに入る最大重量以内で、なるべく合計の値段が最大になるような品物の組み合わせを探す問題です。

ナップサック問題

図.9: ナップサック問題

 今回の例題では、表.1のような50個の品物を用意してみました。またナップサックに入る最大重量は、40kgとします。

表.1: 今回の例題で用いる品物

重さ:値段重さ:値段重さ:値段重さ:値段重さ:値段
2
10
7
2
4
9
10
7
8
5










21
22
28
21
12
24
15
2
25
28
3
10
9
8
8
5
7
3
9
7










4
22
36
2
7
40
14
40
33
21
2
10
7
9
7
2
10
4
9
10










28
22
14
36
28
21
18
12
24
15
4
7
8
5
2
3
10
9
7
8










21
2
25
28
28
4
22
36
31
2
8
5
7
5
7
3
9
7
7
9










7
40
14
4
28
40
33
35
21
20

 さて、この問題をパッと見て、皆さんは、最適解がわかりましたか? この問題の組み合わせは全部で、 250 にもなります。一つ一つ調べていたのでは、キリがありませんよね?

 4.2節 問題のマッピング

 では、4.1節のナップサック問題に遺伝的アルゴリズムをどのように適用するのかを説明していきます。

『コーディング』

 まずは、この問題の解を遺伝的アルゴリズムの染色体で表現するためにをコーディングを行います。ここでは、染色体を図.10のように表すことにします。

染色体のコーディング

図.10: 染色体のコーディング

 50個の品物それぞれに遺伝子を与えます。遺伝子は、0 か 1 のどちらかの値をとることにします。ここでは、0 の場合はその品物を選ばない、 1 の場合はその品物を選ぶものとします。それを一列に並べたものを今回の染色体とします。

 そして、今回のシミュレーションでは、個体数を32として、32個の染色体を用意します。

『評価関数』

 適応度は、良い個体ほど高い値になる必要があります。そこで今回は、染色体が選択した品物の値段の合計をそのまま適応度とします。ただし、ナップサックに入れる品物の重さには上限があるので、上限を越すような選択に対しては、ペナルティーとして非常に悪い適応度を与えることにします。

 まず、品物の数を N 、ナップサックに入る最大重量を W MAX とします。そして、j 番目の品物の値段を P ( j ) 、重さを W ( j ) とします。さらに、32個の染色体の内 i 番目の染色体の中のj 番目の品物に対応する遺伝子の値を I i ( j ) とします。すると、32個の染色体の内 i 番目の染色体の適応度 f i は、次式のように計算することにします。

ナップサック問題の適応度関数

『選択』

 選択とは適応度に応じて環境に適した個体を確率的に選ぶ操作でした。ナップサック問題では、エリート保存戦略と適応度比例戦略を併用することにします。つまり、一番評価の高い染色体は、そのまま次世代に残し、それ以外の染色体は、適応度比例戦略で選びます。

『交叉』

 交叉とは二つの個体の間で文字列の部分的な交換を確率的に行う操作でした。ナップサック問題では、文字列をランダムに2ヶ所で切断し、中央部を入れ替える2点交叉を使用することにします。

2点交叉

図.11: 2点交叉

『突然変異』

 突然変異とは個体中の特定の遺伝子を別の値に確率的に変更する操作でした。ナップサック問題では、文字列の1ヶ所をランダムに反転させる一点突然変異を用います。また、その突然変異の起こる確率は、1%とします。

 最後に今まで説明したパラメータをまとめると次のようになります。

  個体数 : 32
  選択 : エリート保存戦略を併用した適応度比例戦略
  交叉 : 2点交叉
  突然変異率 : 1%

 よって、これらのパラメータをもとに、実際にシミュレーションを行ってみることにします。

 4.3節 シミュレーション結果

 (結果についての説明)

ページの上へ 前の章へ 上のページへ 付録へ


企画・製作 村上・泉田研究室 HP製作委員会(2001)
ご意見・お問い合わせは、こちら までどうぞ。