技術をかじる猫

適当に気になった技術や言語、思ったこと考えた事など。

遺伝的アルゴリズムでナップザック問題

実際には以下の書籍の写経だけど。

機械学習と深層学習 Pythonによるシミュレーション

機械学習と深層学習 Pythonによるシミュレーション

書いたソースはコレ

github.com

平均応答を見る限り、7-11回目位の成績が良くて、その後若干劣化した。
過学習状態なのだろうかとも思うが…

毎回この手のコード見ると思うのだけど、驚くほど抽象化してない。
要するに読みづらい。

何かの折に、リファクタしたいな…

遺伝的アルゴリズムは、最適解こそ出てくる保証がないが、8-9割くらい正解に近い解答なら短時間でたたき出すことができる…らしい。
そりゃ全幅探索なんてするよりかは早いんだろうけど…全幅探索も、メモ化できる範囲ならかなり高速に解けるので、そこまで利用できるかは良くわからない。