memorandums

日々のメモです。

Apache Commons MathのGAでナップザック問題を

昨日、子供がインフルにかかり、家族で唯一かかっていなかったので嫁さんが家にいない方がいいよと。

確かに。ありがたい。

そこでやりかけた仕事があったので研究室へきました。

とある調査をしていて、なかなか動かせずにいるのですが、そのときにたまたま目にしたのがタイトルです。

有名なApache Commons Mathクラスライブラリに遺伝的アルゴリズムが実装されています。

せっかくなのでいざというときに使えるようにしておきたいな。。。と思いまして。少しごにょごにょしました。

その結果をアウトプットしておこうというのがこのエントリーの趣旨です。

既にはるか昔に関連した以下のエントリーを書いてくださった方がいて、そのエントリーを参考にさせていただきました。

d.hatena.ne.jp

ちなみにこのライブラリは以前使った記憶があるのですが。。。どこにも記録が残されていない。残念です。勘違いかもしれません。こういうところに記録しておくのは自分自身のためになります。

今回やったのはタイトルの通りで袋詰め問題です。

ナップサック問題 - Wikipedia

ソルバーを使えばいいのですが、大昔に大学院生のときにGAを使った最適化をテーマにしていたので(当時は全部Cで自作)。。。懐かしくもありです。

実装は簡単です(GAのことを少し知っていないとキーワードを見ただけではイメージがしにくいとは思いますが)。

ソースはGithubにおきました。

github.com

言わずもがなですが、使用するときにはApache Commons Mathライブラリを以下からダウンロードしてきて(この例では3.6を使用しています)、jarをクラスパスに追加してくださいね。

Math – Commons Math: The Apache Commons Mathematics Library

アイテムが10個なので全探索しても2^10=1024なので一瞬で解けてしまう問題ですが。。。

mainメソッドは以下のような感じにしました。袋に入れる10個の重さを1〜10と設定、目標の総重量を7にしてみました。

public static void main(String [] args) {
	new GATest()
	.setWeights(new Integer[] {1,2,3,4,5,6,7,8,9,10})
	.setTargetWeight(7)
	.execute();
}

実行結果は以下のような感じです。最良値を1つだけ表示するので、何度か手動で実行した結果を挙げます。

1になっている番目の物を袋に入れる、という感じで読みます。

以下には4回の例を挙げましたが、1番最初の例は3番目と4番目の物を袋に入れるので3+4=7という感じです。

[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0]

fitnessメソッドを書き換えれば他の問題にも使えます。

実際に使うにはHillCrimbなどローカル探索を入れたり、スケーリングも入れた方が探索効率があがると思います。

とりあえず。

さて本題やらなきゃ。