2012年1月3日火曜日

[python] 遺伝的アルゴリズムって結構難しいのね

pythonの数値計算ライブラリについて調べてみた。
ぱっと見つかったのは、numpy, scipy, pyevolve。

scipy


この辺を参考にした。
Pythonによる数値計算
Python Scientific Lecture Notes

① インストール
バージョン古いけどめんどくさいからyumでいいや。
# yum install scipy
numpyも一緒に入る。

② 使い方
ぱっとみ、簡単そうに見える。
eigen3とかと変わらなそう。
使うときがきたら調べよう。
これインストールしとけば、潜在意味解析とかもいけそう。
SciPyを用いて潜在的意味解析(LSA)

PHPで潜在意味解析したときは、
わざわざeigen3のphp extensionとか作ってたのに。

PHPで潜在意味解析
kokukuma / php-lsa



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

また、pythonで遺伝アルゴリズムを扱うライブラリ、
pyevolveが面白そうだったから入れておいた。

ここに書いてある事をまるっとぱくってやってみた。
pyevolveによる遺伝的アルゴリズム

[karino@localhost numerical_calculation]$ ./pyevolve_test.py 
Gen. 1 (0.20%): Max/Min/Avg Fitness(Raw) [4101.01(4101.00)/0.00(0.29)/3994.99(3994.99)]
Gen. 50 (10.00%): Max/Min/Avg Fitness(Raw) [4892.40(4101.00)/0.00(2901.00)/4794.55(4077.00)]
Gen. 100 (20.00%): Max/Min/Avg Fitness(Raw) [4101.02(4101.00)/0.00(0.29)/3890.97(3890.97)]
Gen. 150 (30.00%): Max/Min/Avg Fitness(Raw) [4101.02(4101.00)/0.00(0.29)/3878.97(3878.97)]
Gen. 200 (40.00%): Max/Min/Avg Fitness(Raw) [4101.03(4101.00)/0.00(0.29)/3724.94(3724.94)]
Gen. 250 (50.00%): Max/Min/Avg Fitness(Raw) [4101.03(4101.00)/0.00(0.29)/3770.96(3770.96)]
Gen. 300 (60.00%): Max/Min/Avg Fitness(Raw) [4101.03(4101.00)/0.00(0.29)/3688.96(3688.96)]
Gen. 350 (70.00%): Max/Min/Avg Fitness(Raw) [4101.02(4101.00)/0.00(0.29)/3806.96(3806.96)]
Gen. 400 (80.00%): Max/Min/Avg Fitness(Raw) [4101.02(4101.00)/0.00(0.29)/3864.97(3864.97)]
Gen. 450 (90.00%): Max/Min/Avg Fitness(Raw) [4101.01(4101.00)/0.00(0.29)/3994.99(3994.99)]
Gen. 500 (100.00%): Max/Min/Avg Fitness(Raw) [4834.80(4101.00)/0.00(3001.00)/4477.56(4029.00)]
Total time elapsed: 5.989 seconds.
[0, 0, 1, 1, 1]
商品C price: 1100 size: 5
商品D price: 1200 size: 7
商品E price: 1800 size: 8
total price: 4100 total size: 20

おぉ、ちゃんと結果出た。


遺伝的アルゴリズムを使って、条件を満たす数列を作成する。

おまけにもう一問やってみる。

以下の条件を満たす数列Aを計算する。
① Aのある位置から順に数字を取り出すと、最短X回ですべての種類の要素を取得できる。
② Aのどの位置から取り出しても、最大Y回ですべての要素を取得できる
③ 数字を取り出す際、末尾まできたら、先頭に戻る。

こんな数列を遺伝アルゴリズムを使って作成する。

#!/usr/bin/python
# coding=utf-8

from pyevolve import G1DBinaryString
from pyevolve import G1DList
from pyevolve import GSimpleGA
from pyevolve import Mutators

#GA setting
GENERATION = 500
POPULATION_SIZE = 50

# data
#BASE_ARRAY = [1,2,3,4,5,6,7]
BASE_ARRAY = [1,2,3,4,5,6]
SEQUENCE_LENGTH = 12
MAX_NUMBER = 11
MIN_NUMBER = 7

#
def calc_comp(start, chromosome):
    """要素コンプリートまでの抽出回数を計測"""
    """function documentation"""
    tmp = []
    for x in xrange(len(chromosome)):

        idx = start + x
        if idx >= len(chromosome): idx -= len(chromosome)

        if chromosome[idx] in BASE_ARRAY and chromosome[idx] not in tmp:
            tmp.append(chromosome[idx])
            if len(list(set(tmp))) == len(BASE_ARRAY):
                return x+1

def calc_max_min(chromosome):
    """要素コンプリートまでの最大・最小抽出回数を計測"""
    max = 0
    min = int(SEQUENCE_LENGTH)
    for x in xrange(len(chromosome)):
        num = calc_comp(x, chromosome)
        if num > max: max = num
        if num < min: min = num
    return (max, min)


# 評価関数
def eval_func(chromosome):
    """要素コンプリートまでの最大・最小抽出回数を計測"""

    #score = 30 
    score = 0

    # 異なる値が多いほうが評価
    tmp = []
    for value in list(set(chromosome)):
        if value in BASE_ARRAY and value not in tmp:
            tmp.append(value)
            score += len(tmp)
        else:
            score += 0

    # 要素コンプリートまでの最大・最小抽出回数を計測
    maxn, minn = calc_max_min(chromosome)

    # 要素コンプリートまでの最大・最小抽出回数を計測
    if maxn == 0:
        score = score
    elif maxn == MAX_NUMBER and minn == MIN_NUMBER:
        score = score * 2 + 30
    else:
        score = score * 2 - abs(maxn - MAX_NUMBER) - abs(MIN_NUMBER - minn)


    # 最低でも0を返す
    if score < 0: score = 0
    return score

# main
def main():
    """遺伝アルゴリズムの計算"""
    genome = G1DList.G1DList(SEQUENCE_LENGTH)
    genome.evaluator.set(eval_func)
    genome.setParams(rangemin=1,rangemax=max(BASE_ARRAY))

    # シンプル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())
    print best
    maxn, minn = calc_max_min(best)
    print "max : ",
    print maxn
    print "min : ",
    print minn


if __name__ == '__main__':
    main()
    #print calc_comp(0, [3,1,2,4,5,6,1,2,3])
出力結果
[karino@localhost numerical_calculation]$ ./pyevolve_sequence.py 
Gen. 1 (0.20%): Max/Min/Avg Fitness(Raw) [40.34(72.00)/30.36(15.00)/33.62(33.62)]
Gen. 50 (10.00%): Max/Min/Avg Fitness(Raw) [71.35(72.00)/40.06(39.00)/59.46(59.46)]
Gen. 100 (20.00%): Max/Min/Avg Fitness(Raw) [72.17(72.00)/38.70(39.00)/60.14(60.14)]
Gen. 150 (30.00%): Max/Min/Avg Fitness(Raw) [69.34(72.00)/23.01(15.00)/57.78(57.78)]
Gen. 200 (40.00%): Max/Min/Avg Fitness(Raw) [76.68(72.00)/26.19(40.00)/63.90(63.90)]
Gen. 250 (50.00%): Max/Min/Avg Fitness(Raw) [74.30(72.00)/34.99(40.00)/61.92(61.92)]
Gen. 300 (60.00%): Max/Min/Avg Fitness(Raw) [80.33(72.00)/0.00(39.00)/67.48(66.94)]
Gen. 350 (70.00%): Max/Min/Avg Fitness(Raw) [77.47(72.00)/23.67(41.00)/64.56(64.56)]
Gen. 400 (80.00%): Max/Min/Avg Fitness(Raw) [77.42(72.00)/22.22(40.00)/64.52(64.52)]
Gen. 450 (90.00%): Max/Min/Avg Fitness(Raw) [75.17(72.00)/32.34(40.00)/62.64(62.64)]
Gen. 500 (100.00%): Max/Min/Avg Fitness(Raw) [73.73(72.00)/7.40(15.00)/61.44(61.44)]
Total time elapsed: 52.364 seconds.
[3, 3, 6, 5, 2, 5, 4, 1, 4, 2, 6, 1]
max :  11
min :  7

一応それっぽくなった。
でも、元の要素増やすとすぐできなくなる。

問題はまぁ、評価関数の作り方でしょうな。
ほしい結果に適した評価関数を作る基本的な考え方ってあるのかな。

0 件のコメント:

コメントを投稿