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

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

確かに。ありがたい。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以下には４回の例を挙げましたが、１番最初の例は３番目と４番目の物を袋に入れるので３＋４＝７という感じです。

[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などローカル探索を入れたり、スケーリングも入れた方が探索効率があがると思います。

とりあえず。

さて本題やらなきゃ。

memorandums