背包问题：继承自集合

再次以这个例子为例，我们将使用一个非常简单的问题，即0-1背包问题。这个例子的目的是展示DEAP的简单性以及从简单列表或数组以外的任何东西继承的便利性。

许多进化算法教科书提到，拥有一个高效的算法最好的方式是拥有一个接近问题的表示。在这里，有什么比集合更接近一个袋子呢？让我们让我们的个体继承自 set 类。

creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
creator.create("Individual", set, fitness=creator.Fitness)

就是这样。你现在有了实际上是集合的个体，它们具有通常的属性 适应度 。适应度是第一个目标（背包的重量）的最小化和第二个目标（背包的价值）的最大化。我们现在将创建一个包含100个随机物品的字典，以映射其价值和重量。

# Create the item dictionary: item name is an integer, and value is 
# a (weight, value) 2-tuple.
items = {}
# Create random items and store them in the items' dictionary.
for i in range(NBR_ITEMS):
    items[i] = (random.randint(1, 10), random.uniform(0, 100))

现在我们需要初始化一个种群及其中的个体。为此，我们需要一个 Toolbox 来注册我们的生成器，因为集合也可以通过输入的可迭代对象来创建。

toolbox = base.Toolbox()
toolbox.register("attr_item", random.randrange, NBR_ITEMS)
toolbox.register("individual", tools.initRepeat, creator.Individual, 
    toolbox.attr_item, IND_INIT_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

瞧！最后要做的是定义我们的评估函数。

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

一切准备就绪，可以进行进化了。哦，等等，由于DEAP的开发者很懒，没有可以直接应用于集合的交叉和变异操作符。我们来定义一些。例如，一个交叉操作，从两个父代生成两个子代，可以是第一个子代是两个集合的交集，第二个子代是它们的绝对差。

def cxSet(ind1, ind2):
    """Apply a crossover operation on input sets. The first child is the
    intersection of the two sets, the second child is the difference of the
    two sets.
    """
    temp = set(ind1)                # Used in order to keep type
    ind1 &= ind2                    # Intersection (inplace)
    ind2 ^= temp                    # Symmetric Difference (inplace)
    return ind1, ind2

变异操作符可以随机地从集合输入个体中添加或移除一个元素。

def mutSet(individual):
    """Mutation that pops or add an element."""
    if random.random() < 0.5:
        if len(individual) > 0:     # We cannot pop from an empty set
            individual.remove(random.choice(sorted(tuple(individual))))
    else:
        individual.add(random.randrange(NBR_ITEMS))
    return individual,

然后我们在工具箱中注册这些操作符。由于这是一个多目标问题，我们选择了NSGA-II选择方案 : selNSGA2()

toolbox.register("evaluate", evalKnapsack)
toolbox.register("mate", cxSet)
toolbox.register("mutate", mutSet)
toolbox.register("select", tools.selNSGA2)

从这里开始，剩下的工作就是编写算法或使用 algorithms 中提供的算法。这里我们将使用 eaMuPlusLambda() 算法。

def main():
    NGEN = 50
    MU = 50
    LAMBDA = 100
    CXPB = 0.7
    MUTPB = 0.2

    pop = toolbox.population(n=MU)
    hof = tools.ParetoFront()
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean, axis=0)
    stats.register("std", numpy.std, axis=0)
    stats.register("min", numpy.min, axis=0)
    stats.register("max", numpy.max, axis=0)

    algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
                              halloffame=hof)

    return pop, stats, hof

最后，可以使用 ParetoFront 来检索进化过程中最佳的非支配个体，并创建一个 Statistics 对象来编译四代不同的统计数据。Numpy 函数在统计对象中注册时使用了 axis=0 参数，以便独立计算每个目标的统计数据。否则，Numpy 会为两个目标计算一个单一的平均值。

完整的 examples/ga/knapsack。