19914


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

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

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

[code]

    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
    
[/code]

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

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

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

[code]

    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
    
[/code]

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


CC BY-SA 3.0
2015-12-12T09:51:04.420
19912
2015-12-17T21:21:18.653
2015-12-17T21:21:18.653
7837
13593
question
python
DEAPにおける出力結果の詳細について


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

[Computing Statistics — DEAP 1.1.0
documentation](http://deap.readthedocs.org/en/master/tutorials/basic/part3.html)

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

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

[code]

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


CC BY-SA 3.0
2015-12-12T10:37:00.977
19913
2015-12-12T10:37:00.977
3589
19912
answer


# 問題

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

**品物**

  * 品物は(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については[こちら](http://deap.readthedocs.org/en/master/api/tools.html?highlight=selnsga2#deap.tools.selNSGA2)

# 結果の見方

  * 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します。どうしたら殿堂入りになるのかいまいちはっきりしませんでしたが、最高の評価の個体はこれで見られます。

[code]

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

**結果**

[code]

    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)
    
[/code]

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


CC BY-SA 3.0
2015-12-12T10:44:50.617
19914
2015-12-17T21:20:16.530
2015-12-17T21:20:16.530
7837
7837
19912
answer