ナップサック問題の解探索

図6.2 n= 18の問題生成における評価値の推移

た．一方で，遺伝的アルゴリズムによる問題生成プログラムではヒント数 n= 19,20の問 題生成に成功した．また，評価値の推移を見ると，n = 17のときモンテカルロ木探索の評

価値は35678ミリ秒時点で554となり，それ以降上昇していない．n= 18の場合において

も，33411ミリ秒の時点で550となりそれ以降上昇していない．一方，遺伝的アルゴリズム

はヒント数17または18のどちらの場合においても断続的に評価値が上昇した．

6.2 ナップサック問題の解探索

ナップサック問題について，モンテカルロ木探索と遺伝的アルゴリズムを適用し解探索を 行った．品物数をnとしたときのナップサック問題形式は次の通りである．

ナップサック数m ： 3

ナップサック容量C： C₀ = 4n, C₁ = 5n, C₂ = 6n 品物j の重量 ： ₁₀ⁿ〜n

品物j の価値 ： ⁿ₅〜2n

6.2 ナップサック問題の解探索

表6.2 得られた近似解

品物数n MCT GA 最適解

50 2635(-14) 2649(0) 2649

100 6316(-17) 6323(-10) 6333 150 12972(-131) 13029(-74) 13103 200 16748(-749) 17328(-169) 17497 250 22853(-905) 23511(-247) 23758 300 28149(-1585) 28575(-1159) 29734

C 値 ： 1.0 展開閾値： 100

また遺伝的アルゴリズムのパラメータは，次のように設定した．

世代サイズ： 30 交叉率： 50%

突然変異率： 30%

エリート数： 1

選択方法： ルーレット選択

以上の条件で，品物数nが50, 100, 150, 200, 250, 300の場合について，それぞれ解探索 を行った．終了条件は探索開始から600秒(=10分)経過とした．モンテカルロ木探索によ る近似解は，終了までに行われたプレイアウト結果のうち，評価値が最も高かったものとし た．遺伝的アルゴリズムによる近似解は，終了時の個体集団のなかで最も適応度が高かった ものとした．

各nに対する実験結果を表6.2に示す．括弧内の数字は，得られた近似解と最適解の差 である．また，nが200, 250, 300の時の評価値の推移について，図6.3，図6.4，図6.5に 示す．

6.2 ナップサック問題の解探索

図6.3 n= 200の問題に対する評価値の推移

表6.2から解るとおり，モンテカルロ木探索によって得られた近似解は，遺伝的アルゴリ ズムによって得られたものよりも低かった．

評価値の推移をみると，モンテカルロ木探索のプレイアウトによる探索では早い段階で近 似解を発見していることがわかる．モンテカルロ木探索が表6.2に示した近似解を得た時間

6.2 ナップサック問題の解探索

図6.5 n= 300の問題に対する評価値の推移

表6.3 MCTで得られた近似解と同時点でのGAの近似解

品物数n 実行時間(ミリ秒) MCTによる近似解 GAによる近似解(MCTとの差)

50 729 2635 2608(-27)

100 2406 6316 6065(-251)

150 11419 12972 12471(-501)

200 17059 16748 16576(-172)

250 30359 22853 21353(-1500)

300 55757 28149 26325(-1824)

と，その時点での遺伝的アルゴリズムによる近似解について表6.2に示す．すべてのnにお いて，モンテカルロ木探索が近似解を得た段階では遺伝的アルゴリズムによる近似解よりも 高い評価値を得た．しかし，それ以降実験終了までプレイアウトによる近似解の更新が無い ため，最終的に遺伝的アルゴリズムが高い評価値を得た．