2

GAを用いて最適化する必要がありその為にpythonのモジュールの1つであるDEAPを使っています。
試しとしてExampleのナップサック問題を実装しました。
https://github.com/DEAP/deap/blob/a2765c3344cb834f47eaab22efbb961e18f4aed7/examples/ga/knapsack.py

そこで質問なのですが、このコードを実装した時に出力されるstdやmin、maxの中身はどのように見ればよろしいのでしょうか。

自分の理解としては、maxはあるリストを与えた時にそのリスト内の最大値を返すものだと思っており、そのためにDEAPモジュール内にあるalgorithmsに

def eaMuPlusLambda(population, toolbox, mu, lambda_, cxpb, mutpb, ngen,
                   stats=None, halloffame=None, verbose=__debug__):
    """This is the :math:`(\mu + \lambda)` evolutionary algorithm.

    :param population: A list of individuals.
    :param toolbox: A :class:`~deap.base.Toolbox` that contains the evolution
                    operators.
    :param mu: The number of individuals to select for the next generation.
    :param lambda\_: The number of children to produce at each generation.
    :param cxpb: The probability that an offspring is produced by crossover.
    :param mutpb: The probability that an offspring is produced by mutation.
    :param ngen: The number of generation.
    :param stats: A :class:`~deap.tools.Statistics` object that is updated
                  inplace, optional.
    :param halloffame: A :class:`~deap.tools.HallOfFame` object that will
                       contain the best individuals, optional.
    :param verbose: Whether or not to log the statistics.
    :returns: The final population
    :returns: A class:`~deap.tools.Logbook` with the statistics of the
              evolution.

    The algorithm takes in a population and evolves it in place using the
    :func:`varOr` function. It returns the optimized population and a
    :class:`~deap.tools.Logbook` with the statistics of the evolution. The
    logbook will contain the generation number, the number of evalutions for
    each generation and the statistics if a :class:`~deap.tools.Statistics` is
    given as argument. The *cxpb* and *mutpb* arguments are passed to the
    :func:`varOr` function. The pseudocode goes as follow ::

        evaluate(population)
        for g in range(ngen):
            offspring = varOr(population, toolbox, lambda_, cxpb, mutpb)
            evaluate(offspring)
            population = select(population + offspring, mu)

    First, the individuals having an invalid fitness are evaluated. Second,
    the evolutionary loop begins by producing *lambda_* offspring from the
    population, the offspring are generated by the :func:`varOr` function. The
    offspring are then evaluated and the next generation population is
    selected from both the offspring **and** the population. Finally, when
    *ngen* generations are done, the algorithm returns a tuple with the final
    population and a :class:`~deap.tools.Logbook` of the evolution.

    This function expects :meth:`toolbox.mate`, :meth:`toolbox.mutate`,
    :meth:`toolbox.select` and :meth:`toolbox.evaluate` aliases to be
    registered in the toolbox. This algorithm uses the :func:`varOr`
    variation.
    """
    logbook = tools.Logbook()
    logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])

    # Evaluate the individuals with an invalid fitness
    invalid_ind = [ind for ind in population if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
    for ind, fit in zip(invalid_ind, fitnesses):
        ind.fitness.values = fit

    if halloffame is not None:
        halloffame.update(population)

    record = stats.compile(population) if stats is not None else {}
    logbook.record(gen=0, nevals=len(invalid_ind), **record)
    if verbose:
        print logbook.stream

    # Begin the generational process
    for gen in range(1, ngen + 1):
        # Vary the population
        offspring = varOr(population, toolbox, lambda_, cxpb, mutpb)

        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit

        # Update the hall of fame with the generated individuals
        if halloffame is not None:
            halloffame.update(offspring)

        # Select the next generation population
        population[:] = toolbox.select(population + offspring, mu)

        # Update the statistics with the new population
        record = stats.compile(population) if stats is not None else {}
        logbook.record(gen=gen, nevals=len(invalid_ind), **record)
        if verbose:
            print logbook.stream
        import pdb
        pdb.set_trace()

    return population, logbook

とpdbをいれて実行し、p populationと実行しましたがよくわからないリストが出されるのみで上手くいきませんでした。

追記
populationがどのような個体から計算されているか見ることは出来ませんか?
例えばMAXでは[ 49.  865.83549407] と算出されてきますが、それがどのような個体の組合せで算出されているのでしょうか。

現在、私は[1 40][3 60]・・・・・のような個体の組合せで算出されると認識しております。
そのためにitemsの中身をみればよいと考え以下の様にコードを変えてみましたがpopulationで算出された1個目ととこれで計算した中身の1個目との計算が合わず上手く行きませんでした。

def evalKnapsack(individual):
    weight = 0.0
    value = 0.0
    for item in individual:
        weight += items[item][0]
        value += items[item][1]
        print items[item][0]
        print items[item][1]
    if len(individual) > MAX_ITEM or weight > MAX_WEIGHT:
        return 10000, 0   

    return weight, value

何卒、よろしくお願いします。

2 件の回答 2

0

問題

重さと価値の異なる品物を、ナップサックにできるだけ詰め込み、価値が最大になるような組み合わせを求める問題です。

品物

  • 品物は(ID, 重さ、価値)で定義されています。
  • 品物は全部でNBR_ITEMS個あります。
  • 品物のIDは0から始まる連番で0..NBR_ITEMS-1です。
  • 重さは1..10の値
  • 価値は一様分布の0..100の値です。

ナップサック

ナップサックに入る品物はMAX_ITEM個、重量の合計はMAX_WEIGHTを超えないものとします。
一般的なナップサック問題では容積も制約に入っていますが、この実装では重さと価値だけです。

設計

EAで解くためには、一般に個体 Individual、人口 Population、適応度評価 evaluate、交叉 mate、突然変異 mutate、選択 selectが必要です。

  • 個体 Individual: ある品物の組み合わせが入ったナップサック。例Individual([1,2,3])は品物ID1, 品物ID2, 品物ID3が入ったナップサック。初期状態ではIND_INIT_SIZE個だけランダムに選択した品物が入っています。
  • 人口 Population: ナップサックMU個で人口を形成します。
  • 適応度評価 evaluate: evalKnapsack(individual)でナップサック個体の評価をします。合計の重さと合計の価値をそのまま評価値とします。この関数は個体を入力とし、出力は(合計の重さ, 合計の価値)のタプルです。品物の数がMAX_ITEMを超えるか、合計重量がMAX_WEIGHTを超えた場合は合計重量を10000, 価値を0として適応度が最悪の評価になるようになっています。さらに、出力のタプルに、重さには-1を掛け、価値には+1を掛けています。つまり重さは軽いほうが評価が高くなり、価値は高いほうが評価が高くなります。creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))にあるweightsは品物の重量ではなく評価値のタプルの要素それぞれに対する重み付けになります。
  • 交叉 mate: cxSet(individual1, individual2)により、両ナップサックに入っている品物のAND, 同様にXORをとったものを子孫として出力します。AND, XORがどういう意味を持つのかはGAの教科書を参照してください。
  • 突然変異 mutate: 50%の確率で品物がナップサックの中から一つなくなったり、商品全体からランダムに選ばれた商品がナップサックに一つ追加されたりします。局所解に陥らないための工夫。
  • 選択 select: ここではDEAPが提供しているselNSGA2という選択関数を使います。NSGA-IIについてはこちら

結果の見方

  • genは世代です。nevalsはこの世代で新たに適応度評価が行われた個体の数です。(同じ品物の組み合わせのナップサックの評価は一度しかしない)
  • avgは人口に含まれるすべてのナップサックの[重量の平均、価値の平均]
  • stdは同様に[重量の標準偏差、価値の標準偏差]。つまりどれだけバラついているか。
  • minは最低の価値のナップサックの[重量, 価値]。からっぽのナップサックで価値は0という結果
  • maxは最高の価値のナップサックの[重量, 価値]。重量48, 価値823が最高のようです。

    $ python knapsack.py
    gen nevals avg std min max
    0 50 [ 19.52 231.98214002] [ 6.58252231 69.12192829] [ 6. 100.29201362] [ 36. 408.42409383]
    1 93 [ 5.94 130.56782075] [ 7.16215052 131.43022643] [ 0. 0.] [ 22. 408.42409383]
    2 85 [ 2.42 70.83298161] [ 5.37806657 122.97049141] [ 0. 0.] [ 22. 417.53104832]
    3 90 [ 1.96 83.73195692] [ 3.42321486 110.37429143] [ 0. 0.] [ 15. 430.52070247]
    :
    :
    :
    47 97 [ 14.78 446.17273931] [ 12.07524741 210.74568506] [ 0. 0.] [ 43. 805.93842781]
    48 92 [ 16.44 475.61670512] [ 12.23954248 214.80580845] [ 0. 0.] [ 43. 805.93842781]
    49 83 [ 18.38 510.53414622] [ 12.65684005 208.27056741] [ 0. 0.] [ 43. 805.93842781]
    50 91 [ 18.5 504.01464329] [ 13.5782915 227.94333029] [ 0. 0.] [ 48. 823.83477683]

殿堂入り

hof (hall of fame, 殿堂入り)を表示するには次のようにprintします。どうしたら殿堂入りになるのかいまいちはっきりしませんでしたが、最高の評価の個体はこれで見られます。

if __name__ == "__main__":
    pop, stats, hof= main()
    for ind in hof:
        print ind, ind.fitness

結果

Individual([]) (0.0, 0.0)
Individual([2]) (1.0, 98.76105507362524)
Individual([8, 2]) (2.0, 166.70753298734314)
Individual([8, 2, 18]) (3.0, 213.25102920934796)
Individual([8, 2, 6]) (4.0, 252.84067436843833)
Individual([8, 2, 18, 6]) (5.0, 299.38417059044315)
Individual([8, 2, 12, 6]) (6.0, 334.3359191914945)
Individual([8, 2, 12, 18, 6]) (7.0, 380.8794154134993)
Individual([8, 2, 12, 6, 14]) (9.0, 408.57515242995765)
Individual([2, 6, 8, 12, 14, 18]) (10.0, 455.1186486519625)
Individual([1, 2, 6, 8, 12, 18]) (12.0, 472.881816681132)
Individual([1, 2, 6, 8, 12, 14]) (14.0, 500.57755369759036)
Individual([2, 6, 7, 8, 12, 14, 18]) (15.0, 527.2475085776873)
Individual([2, 6, 7, 8, 9, 12, 14, 18]) (16.0, 533.6303451092098)
Individual([2, 6, 7, 8, 9, 10, 12, 14, 18]) (18.0, 538.2023476616862)
Individual([1, 2, 6, 7, 8, 12, 14]) (19.0, 572.7064136233151)
Individual([1, 2, 6, 7, 8, 9, 12, 14]) (20.0, 579.0892501548377)
Individual([0, 2, 6, 7, 8, 9, 12, 14, 18]) (21.0, 596.6522505410983)
Individual([2, 3, 6, 7, 8, 12, 14, 18]) (23.0, 607.6470073924423)
Individual([1, 2, 3, 6, 7, 8, 12, 18]) (25.0, 625.4101754216118)
Individual([1, 2, 3, 6, 7, 8, 10, 12, 18]) (27.0, 629.9821779740884)
Individual([1, 2, 3, 6, 7, 8, 12, 14, 18]) (28.0, 699.649408660075)
Individual([1, 2, 3, 6, 7, 8, 10, 12, 14, 18]) (30.0, 704.2214112125515)
Individual([1, 2, 3, 6, 7, 8, 12, 14, 16, 18]) (32.0, 736.0695346872124)
Individual([1, 2, 3, 6, 7, 8, 9, 12, 14, 16, 18]) (33.0, 742.4523712187349)
Individual([1, 2, 3, 5, 6, 7, 8, 12, 14, 18]) (37.0, 764.9462992280614)
Individual([1, 2, 3, 5, 6, 7, 8, 12, 14, 16, 18]) (41.0, 801.3664252551988)
Individual([1, 2, 3, 5, 6, 7, 8, 10, 12, 14, 16, 18]) (43.0, 805.9384278076752)
Individual([1, 2, 3, 5, 6, 7, 8, 10, 12, 14, 16, 17, 18]) (48.0, 823.8347768280346)

※ Individualに表示されているのは、品物のIDです。元の重さと価値を知るにはprint items[品物のID]とします。

7
  • 標準偏差が世代が進むにつれて大きくなる理由:最初は乱数で初期化された遺伝子で皆一様だったのが、世代が進むにしたがって交叉と淘汰が繰り返され優秀な遺伝子と劣性遺伝子の差が大きくなったからでしょう。 Commented 2015年12月12日 11:14
  • ありがとうございます。おかげさまでmain関数の中に追記し、実行してみたところpopulationの中身を見ることが出来ました。 ここでpopulationがどのような個体から計算されているかみることは出来るでしょうか?
    – kishi-kun
    Commented 2015年12月14日 7:38
  • 質問中にあるコードのpopulation[:] = toolbox.select(population + offspring, mu)この部分で現在のpopulation+子孫の中からmu個の個体を選択していて、その直後にrecord = stats.compile(population)しています。ある世代のmaxはここで計算されているので、ここで` print population`すれば個体一覧が得られるはずです。 Commented 2015年12月14日 18:06
  • ありがとうございます。 実装してみましたが、MAXが[ 48. 823.83477683]に対し得られたものがMAX Individual([1, 2, 3, 5, 6, 7, 8, 10, 12, 14, 16, 17, 18])という結果でした。48でも823でもないのですが、これはなんの配列なんでしょうか
    – kishi-kun
    Commented 2015年12月16日 9:52
  • Individual([1,2,3,..])の中の数字はナップサックに入れる品物のIDです。品物のリストはknapsack.pyの39行目で作られています。items[i] = (random.randint(1, 10), random.uniform(0, 100))とあるのはタプルの最初の要素が品物の重さ、次の要素が品物の価値です。ID1,2,3..でitemsから重さと価値を読み出せば、その合計の重さが48, 合計の価値が823になります。この実装に合わせて回答を書き直します。DEAPはフレームワークで、個体のデータ構造、交叉、選択など各ステップは実装次第なので、一般論では分かりにくいと自分自身思いました。 Commented 2015年12月16日 17:59
0

こちらはご覧になりましたか?

Computing Statistics — DEAP 1.1.0 documentation

githubのexampleではmain関数がpop, stats, hofの三つの値を返しているので、これらを使って結果を見ることを意図しているのだと思います。

exampleの最後の部分を次のように変更してみて下さい。

if __name__ == "__main__":
    pop, stats, hof = main()
    record = stats.compile(pop)
    print(record)

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。