pyevolveによる遺伝的アルゴリズム(1)

時代はすでに遺伝的プログラミングに移行している感がありますが、遺伝的アルゴリズム(Genetic Algorithm)をやってみます。
pythonのライブラリである『pyevolve』を使うと、笑っちゃうほど簡単にGAができちゃいます!フヒヒwwwサーセンwww

■pyevolve
http://pyevolve.sourceforge.net/


それでは、早速pyevolveでナップサック問題を解いてみましょう。

ナップサック問題とは?

ここに重さ20kgまで入るナップサックがあります。
そして5種類の商品があります。

重さ 価格 1kgあたりの価値
商品A 3kg ¥800 ¥266.6
商品B 5kg ¥900 ¥180
商品C 5kg ¥1,100 ¥220
商品D 7kg ¥1,200 ¥171.4
商品E 8kg ¥1,800 ¥225

(各商品は1個づつしかないものとします)

ナップサックに、どの商品の組み合わせを詰め込めば最大の価値を得られるでしょうか?

pyevolveでナップサック問題を解く

標本数は50個で500世代まで試行しました。
ソースコードは、分かり易さ優先で冗長に書きましたが、70行程度で収まっています。

#!/usr/local/bin/python
# -*- coding: utf-8 -*-
from pyevolve import G1DBinaryString
from pyevolve import GSimpleGA
from pyevolve import Mutators

#GA設定
GENERATION      = 500   #試行世代数
POPULATION_SIZE = 50    #1世代につきての標本数

#ナップザック設定
KNAP_SIZE       = 20    #ナップザックのサイズ

#商品データ
items = []
items.append({'id':u'商品A','price': 800,'size':3})
items.append({'id':u'商品B','price': 900,'size':5})
items.append({'id':u'商品C','price':1100,'size':5})
items.append({'id':u'商品D','price':1200,'size':7})
items.append({'id':u'商品E','price':1800,'size':8})
max_size = sum([x['size'] for x in items])

def calc_func(chromosome):
    u"""遺伝子から価値とサイズの合計を求める"""
    price = 0
    size  = 0
    for x in xrange(len(chromosome)):
        if chromosome[x]:
            price += items[x]['price']
            size  += items[x]['size']
    return (price,size)

def eval_func(chromosome):
    u"""遺伝子の評価点数を返す"""
    #遺伝子から価値とサイズを求める
    price,size = calc_func(chromosome)
    
    #ナップザックサイズをチェック
    if KNAP_SIZE < size:
        #オーバーしているサイズに応じて0〜1点を与える
        over_score = 1.0-float(KNAP_SIZE-size)/float(max_size)
        return max(0.0,over_score)

    return 1.0 + float(price)
    
if __name__ == "__main__":
    #対立遺伝子は0と1のみなのでG1DBinaryStringを使用
    genome = G1DBinaryString.G1DBinaryString(len(items))
    genome.evaluator.set(eval_func)

    #シンプルGAの作成
    ga = GSimpleGA.GSimpleGA(genome)
    ga.setGenerations(GENERATION)
    ga.setPopulationSize(POPULATION_SIZE)
    
    #GAの開始(途中経過を非表示にしたい場合はfreq_stats=0にする)
    ga.evolve(freq_stats=50)
    best = list(ga.bestIndividual())

    #結果表示
    for x in xrange(len(best)):
        if best[x] != 0:
            print items[x]['id'],
            print "price:", items[x]['price'],
            print "size:",items[x]['size'] 
    price,size = calc_func(best)
    print "total price:",price,"total size:",size
実行結果
商品C price: 1100 size: 5
商品D price: 1200 size: 7
商品E price: 1800 size: 8
total price: 4100 total size: 20

一番価値が高い組み合わせは、商品C,D,Eとなりました。
1kgあたりの価値が一番高かった「商品A」を捨てる事が最適だったという結果が面白いですね。

自分で作るといろいろ面倒な遺伝的アルゴリズムが、たった70行たらずで出来るとは、pyevolveすげー!

pyevolveによる遺伝的アルゴリズム(2)へつづく・・・