基于遗传算法的多目标优化进行0-1规划

基于遗传算法的多目标优化进行0-1规划

• 基于遗传算法的多目标优化进行0-1规划
• • 1、题目背景
  • 2、算法框架
  • • 2.1目标函数的定义
    • 2.2约束函数的定义
    • 2.3个体生成函数的定义
    • 2.4交叉函数的定义
    • 2.5评估函数的定义
    • 2.6注册遗传算法
    • 2.7遗传迭代求最优解
  • 3、具体实例
  • • 3.1 2021年数学建模国赛C题第二问
    • 3.2 数据格式
    • 3.3 实例代码

基于遗传算法的多目标优化进行0-1规划

第一次写博客不知道从哪里下手， 之所以想开始博客写作一方面是想记录自己写过的代码，另一方面也分享一下自己在编程的时候遇到的问题，也希望可以帮助到各位。

1、题目背景

之所以做基于遗传算法的多目标优化进行0-1规划，是因为在做数学建模2021年C题的时候遇到了一个规划题，题目详情可以在数学建模官方网站下载参考。本篇博客主要还是讲解下算法的主要框架，在进行多目标优化求解的时候可以使用多种算法，如遗传算法（Genetic Algorithms）、粒子群算法（Particle Swarm Optimization）、差分进化算法（Differential Evolution）、NSGA-II（Non-Dominated Sorting Genetic Algorithm II）、SPEA2（Strength Pareto Evolutionary Algorithm 2），在这里我使用的是遗传算法，在使用python进行优化求解的时候也可以使用不同的库，如DEAP、PyGMO、GAFT，但更推荐使用DEAP，相对来说使用DEAP库来构建遗传算法结果更为清晰，支持遗传算法、进化策略和遗传规划等算法，提供了许多功能，例如多种选择和交叉算子、多种进化算法的实现、可视化工具等。

2、算法框架

总的来说，使用DEAP进行遗传算法的搭建主要包括一下几个部分：目标函数、约束函数、个体生成函数、交叉函数、评估函数、注册遗传算法和进行遗传迭代求最优解。使用DEAP进行遗传算法的搭建，需要首先定义目标函数和约束函数，这些函数形成了遗传算法的基础。然后需要定义个体生成函数和交叉函数，用于生成新的个体和产生下一代个体。还需要定义评估函数，以计算个体的适应度，并将这些函数注册到遗传算法框架中。在注册完函数之后，可以开始进行遗传算法迭代，通过选择、交叉和变异操作来生成新的个体，并使用评估函数计算其适应度。迭代过程将持续，直到达到预定的停止条件或者最大迭代次数为止。

除了上述基本步骤外，使用DEAP进行遗传算法的搭建还需要注意一些问题，例如选择合适的选择算子、交叉算子和变异算子，确定种群大小和迭代次数，以及如何处理复杂的多目标问题等等。此外，还可以使用DEAP提供的统计工具和可视化工具来分析和优化遗传算法的性能。

2.1目标函数的定义

遗传算法的目标是优化某个目标函数，因此需要定义目标函数，这个目标函数需要与优化问题相匹配。例如，如果要优化一个数学公式，则目标函数应该是该公式的输出结果。具体的目标函数可以根据具体的问题去定义，目标函数可以定义一个或多个，通常情况下是双目标和三目标。目标函数需要一个individual的数组，也可以说individual数组就是我们进行优化的对象，以下是我在优化的时候定义的其中一个目标函数：

# Objective functions
def objective1(individual):
    individual = np.array(individual)
    x_a = individual[:128].reshape(16, 8, order='C')
    x_b = individual[128:240].reshape(14, 8, order='C')
    x_c = individual[240:].reshape(20, 8, order='C')
    # 计算这三个矩阵中1的数目
    count_a = np.sum(x_a)
    count_b = np.sum(x_b)
    count_c = np.sum(x_c)
    return count_a + count_b + count_c`

其中individual是大小为400的一维个体数组，其中是进行0-1规划的数据，在这里对一维数组拆分成了三个二维矩阵（也可以不拆分），并计算三个矩阵中1的个数，个体矩阵中1的个数和作为优化的其中一个目标。在我的代码中一共定义了三个目标函数，这里仅给出一个作为示例。

2.2约束函数的定义

如果问题有约束条件，需要定义约束函数，以确保生成的个体满足这些约束条件。例如，如果问题要求所有个体的某些变量之和等于一个特定值或者在某个区间，则需要定义一个约束函数来确保每个个体满足这个条件。与目标函数的定义类似，约束函数的定义也需要一个individual数组，在进行同一次遗传迭代的时候，多个目标函数和约束函数所传入的individual数组数据都是一致的，这样才可以达到既满足约束不断趋近目标函数的目标值。在我的代码中一共定义了三个约束条件，以下是我在优化的时候定义的其中一个约束函数：

def constraint1(individual):
    individual = np.array(individual)
    x_a = individual[:128].reshape(16, 8, order='C')
    x_b = individual[128:240].reshape(14, 8, order='C')
    x_c = individual[240:].reshape(20, 8, order='C')
    row_a_sums = x_a.sum(axis=1)
    row_b_sums = x_b.sum(axis=1)
    row_c_sums = x_c.sum(axis=1)
    # 约束条件3 每个供应商只用一个转运商
    constraint3 = 0
    for i in range(len(row_a_sums)):
        if row_a_sums[i] < 0 or row_a_sums[i] > 1:
            constraint3 += 1
    for i in range(len(row_b_sums)):
        if row_b_sums[i] < 0 or row_b_sums[i] > 1:
            constraint3 += 1
    for i in range(len(row_c_sums)):
        if row_c_sums[i] < 0 or row_c_sums[i] > 1:
            constraint3 += 1
    return constraint3 <=0

在这个约束函数中，对一维数组individual拆分成了三个二维矩阵，并计算三个矩阵中每行元素的和，确保每个二维数组每行的和是0或1（即确保每个二维数组每行最多只有一个1），如果满足条件返回一个TRUE，不满足返回FALSE，返回的值不一定是Boolean值，可以是其他类型，只要在后续判断的时候符合逻辑即可。

2.3个体生成函数的定义

前面讲到individual个体数组就是我们进行优化的对象，那么对于individual数组的生成也有多种方法。定义一个函数来生成初始种群中的个体，这个函数应该生成符合问题要求的随机个体。例如，如果要优化一个数学公式，则可以随机生成符合预定范围的变量，并将这些变量组合成一个个体。定义个体生成函数通常有两种方式，一种是直接使用DEAP 库中的 initRepeat 方法生成一个个体，另外一种是自定义一个个体生成函数，确保生成的个体达到想要的结果。以下是两种方法的示例：

（1）使用DEAP 库中的 initRepeat 方法

toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=2) 

这行代码使用 DEAP 库中的 initRepeat 方法生成一个个体，其中 creator.Individual 指定了个体的类别， toolbox.attr_float 指定了个体的属性生成函数， n=2 指定了个体的属性数量。creator.Individual 是一个由 list 类型派生出来的类，它的实例是一个由属性组成的列表。toolbox.attr_float 指定了一个属性生成函数，用于生成一个随机的实数，其范围为 [-1, 1]。n=2 指定了个体的属性数量为 2，因此每个个体由两个随机实数构成。

使用 initRepeat 方法可以方便地生成一定数量的相同类型的个体，而不需要手动编写循环来生成每个个体。在遗传算法中，通常会使用 initRepeat 方法生成一个初始种群，然后使用选择、交叉和变异算子生成新的后代个体，并将其合并到当前种群中进行下一轮迭代。最终，遗传算法会返回一个最优个体，其属性值代表了问题的最优解。
（2）使用自定义个体生成函数：

def initIndividual():
    individual = np.zeros(400, dtype=int)
    for i in range(50):
        row_start = i * 8
        if np.random.uniform() < 0.7:
            j = np.random.choice(8)
            row_start += j
            individual[row_start] = int(1)
    # 创建个体对象
    ind = creator.Individual(individual)
    return ind

在自定义的个体生成函数中，使用 NumPy 库中的 zeros 方法创建一个大小为 400 的整型数组，然后使用循环随机地将其中的一些元素设置为 1。

循环中的 i 变量用于迭代所有的行，其中每行包含 8 个元素。row_start 变量用于计算当前行的起始下标，即 i*8。随后，使用 np.random.uniform() 方法生成一个随机实数，如果小于 0.7，则在当前行内随机选择一个元素，将其设置为 1。这里使用 np.random.choice(8) 方法从 0 到 7 中随机选择一个整数，表示当前行内的某个位置。也就是每行最多只有一个1，虽然我在约束中限制了每行只有一个1，但为了加快优化算法的收敛速度，在生成个体的时候对个体数组也进行了构造和设计。

最后，将生成的二进制串个体转换为 DEAP 库中的 creator.Individual 类型，并返回该个体对象。在 DEAP 的遗传算法中，可以使用该函数作为个体生成函数，生成一个由二进制串个体组成的初始种群。一定主要自定义的个体生成函数的返回值要是creator中的Individual类型。

此外，还需要将自定义个体生成函数注册到遗传算法中去，使用以下代码进行注册。

# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, initIndividual)
toolbox.register("population", tools.initRepeat, list,  initIndividual)

使用了 DEAP 库中的 initIterate 和 initRepeat 方法来注册个体生成函数和种群生成函数。

2.4交叉函数的定义

定义一个函数来实现个体之间的交叉操作，以产生新的个体。例如，可以随机选择两个个体，然后从它们的基因中随机选择一些片段进行交换，以产生新的个体。交叉函数的定义方式与个体生成函数的定义方式相似，可以使用DEAP 库中提供的交叉方法，也可以使用自定义的交叉方法然后注册到遗传算法中。以下是两种方法的示例：
（1）使用DEAP 库中提供的交叉方法

toolbox.register("mate", tools.cxTwoPoint)

这行代码使用 DEAP 库中的 cxTwoPoint 方法注册了一个两点交叉算子，该算子用于对两个个体进行交叉操作。

在遗传算法中，交叉是将两个个体的某些部分进行组合，生成新的个体的过程。两点交叉算子是其中一种常用的交叉算子，它首先随机选择两个交叉点，然后将这两个交叉点之间的部分进行交换。除了两点交叉，DEAP 库中还提供了其他的交叉方法，可以自行查阅。
（2）使用自定义的交叉方法

def swap_crossover(child1, child2):
    # 对 child1 和 child2 进行基因对换
    child1[:], child2[:] = child2[:], child1[:]

由于我在代码中做的是0-1规划，如果使用DEAP 库中的 cxTwoPoint 方法或者其他交叉方法，在后续遗传迭代生成的个体中不能保证个体元素是0或1（即可能产生0-1的浮点数或者其他非范围的数），不符合0-1规划的条件，所以在这里我自定义的交叉函数是只对子个体进行对换操作，而不改变个体的元素。

# 注册基因对换交叉方法
toolbox.register("mate", swap_crossover)

在自定义的交叉函数定义完成之后，还必须将其注册到遗传算法中。

2.5评估函数的定义

既然对于一个优化算法来说，有了优化目标，就需要对优化的目标进行评定，所以需要定义一个函数来评估每个个体的适应度，以确定它们在下一代中的选择概率。例如，可以将每个个体的目标函数值作为适应度，以便更好地选择适合的个体。

def evaluate(individual):
    if not constraint1(individual) or not constraint2(individual) or not constraint3(individual):
        return float('inf'), float('inf'), float('inf')  # Return infinite values for violated constraints
    objective1_val = objective1(individual)
    objective2_val = objective2(individual)
    objective3_val = objective3(individual)
    # Return the objectives as a tuple
    return objective1_val, objective2_val, objective3_val

这段代码实现了一个个体评价函数 evaluate，用于计算个体在多目标优化问题中的适应度值。具体来说，该函数接受一个个体作为输入，然后计算该个体在问题的三个目标函数上的取值，并将三个目标函数的值作为一个元组返回。

在计算目标函数值之前，该函数首先对个体进行约束检查。具体来说，该函数使用了三个约束函数 constraint1、constraint2 和 constraint3，对个体是否符合问题的约束进行检查。如果个体不符合约束条件，则将三个目标函数的值全部设为无穷大，表示该个体不可行。

如果个体符合约束条件，则计算其在三个目标函数上的取值，并将三个目标函数的值作为一个元组返回。具体来说，该函数使用了三个目标函数 objective1、objective2 和 objective3，分别计算个体在问题的三个目标函数上的取值。最终，该函数将三个目标函数的值作为一个元组返回，表示该个体在多目标优化问题中的适应度值。

2.6注册遗传算法

在目标函数、约束函数、个体生成函数、交叉函数、评估函数等各个子模块都定义完毕之后就可以构建遗传算法了，通常来说遗传算法的注册需要包括以下内容。

# Create FitnessMulti object as fitness object and define weights
creator.create("FitnessMulti", base.Fitness, weights=(-1, -0.1, -0.5))

# Create Individual object as an individual in the population and specify fitness
creator.create("Individual", list, fitness=creator.FitnessMulti)

toolbox = base.Toolbox()

# Attribute generator
toolbox.register("attribute", random.uniform, 0, 1)  # Assuming continuous variables between 0 and 1

# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, initIndividual)
toolbox.register("population", tools.initRepeat, list,  initIndividual)

toolbox.register("evaluate", evaluate)
# Constraints
penalty_value = 10  # Adjust penalty value based on the problem
toolbox.decorate("evaluate", tools.DeltaPenalty(constraint1, penalty_value))
toolbox.decorate("evaluate", tools.DeltaPenalty(constraint2, penalty_value))
toolbox.decorate("evaluate", tools.DeltaPenalty(constraint3, penalty_value))
# Genetic operators

# 注册基因对换交叉方法
toolbox.register("mate", swap_crossover)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.1)  # Adjust parameters if needed
toolbox.register("select", tools.selNSGA2)

creator.create(“FitnessMulti”, base.Fitness, weights=(-1, -0.1, -0.5)) 权重的负号表示该目标函数是一个最小化目标函数。在多目标优化问题中，通常会定义多个目标函数，每个目标函数都有一个权重系数，用于平衡不同目标之间的重要性。权重系数的正负号决定了该目标函数是最小化目标函数还是最大化目标函数。在这里，creator.create(“FitnessMulti”, base.Fitness, weights=(-1, -0.1, -0.5)) 定义了三个目标函数的权重，分别为 -1、-0.1 和 -0.5。这里的负号表示这三个目标函数都是最小化目标函数，即目标函数值越小，个体的适应度越高。
creator.create(“Individual”, list, fitness=creator.FitnessMulti) 使用 creator.create 方法定义了一个名为 Individual 的新类别，该类别继承自 Python 中的 list 类，并将 FitnessMulti 类别作为其适应度值。
toolbox = base.Toolbox() 代码使用 base.Toolbox() 方法创建了一个工具箱对象 toolbox，用于注册个体的属性生成、初始化方法、评价函数、约束条件、遗传算子等操作。具体来说，该段代码使用 toolbox.register 方法注册了属性生成器、个体初始化器、种群初始化器、评价函数、约束条件、基因对换交叉方法、高斯变异方法和选择方法等操作。
toolbox.register(“attribute”, random.uniform, 0, 1) 注册了一个属性生成器，用于生成个体的属性值。该生成器使用 random.uniform 方法，以均匀分布随机生成一个在 [0, 10] 区间内的实数作为个体属性值。
toolbox.register(“individual”, tools.initIterate, creator.Individual, initIndividual) 注册了一个个体初始化器，该初始化器使用 tools.initIterate 方法，以 initIndividual 函数作为迭代器，逐个生成个体的属性值，并将 creator.Individual 类别作为个体类型。
**toolbox.register(“population”, tools.initRepeat, list, initIndividual) ** 注册了一个种群初始化器，该初始化器使用 tools.initRepeat 方法，以 initIndividual 函数作为个体初始化器，逐个生成种群中的个体，并将 list 类作为种群类型。
toolbox.register(“evaluate”, evaluate) 注册了一个评价函数，用于计算个体在多目标优化问题中的适应度值。
toolbox.decorate(“evaluate”, tools.DeltaPenalty(constraint1, penalty_value)) 注册了三个约束条件，用于限制可行解的解空间。penalty_value 表示约束条件不满足时所施加的惩罚值，在使用 tools.DeltaPenalty 这种约束处理器时，当个体不满足约束条件时，会将其适应度值惩罚为原来的值加上惩罚值。penalty_value 的设置可以影响到优化算法的收敛性和结果，通常需要根据具体问题的特点进行调整。
toolbox.register(“mate”, swap_crossover) 定义了一个交叉算子，用于将两个个体进行基因对换操作。
toolbox.register(“mutate”, tools.mutGaussian, mu=0, sigma=1, indpb=0.1) 定义了一个变异算子，用于对个体的某些决策变量进行高斯变异操作。
toolbox.register(“select”, tools.selNSGA2) 定义了一个选择算子，用于根据多目标优化问题的特点，选择多个非支配解作为下一代种群的父代。

经过以上的各个部分的定义和遗传算法的注册之后，使用遗传算法的多目标优化进行0-1规划的优化算法就搭建完成，接下来就可以使用遗传迭代进行最优解的求解。

2.7遗传迭代求最优解

使用注册的遗传算法函数，开始进行迭代，直到找到满足停止条件的最优解或者达到要求的最大迭代次数为止。

population_size = 200
num_generations = 100
crossover_probability = 0.5  # Adjust probability if needed
mutation_probability = 0.2  # Adjust probability if needed

# Generate initial population
initial_population = toolbox.population(n=population_size)

# Copy the initial population to the main population
population = initial_population[:]
for individual in population:
    fitness_values = evaluate(individual)
    individual.fitness.values = fitness_values
# Evolution loop
for generation in range(num_generations):
    # Evaluate population fitness values
    fitnesses = toolbox.map(evaluate, population)
    for individual, fitness in zip(population, fitnesses):
        individual.fitness.values = fitness

    # Select next generation individuals
    offspring = toolbox.select(population, len(population))

    # Clone selected individuals
    offspring = list(map(toolbox.clone, offspring))

    # Apply crossover and mutation
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < crossover_probability:
            toolbox.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values

    for i in range(len(offspring)):
        if random.random() < mutation_probability:
            offspring[i] = initIndividual()
            del offspring[i].fitness.values
    # Replace worst individuals with the elite individuals from the previous generation
    elite_size = 10  # Number of elite individuals to preserve
    # 根据适应度值对当前种群进行排序
    population.sort(key=lambda x: x.fitness.values)
    # 将精英个体替换掉最差的个体
    offspring[-elite_size:] = population[:elite_size]
    # 使用后代更新当前种群
    population[:] = offspring
    # Output the best individual and its fitness in each generation
    best_individual = tools.selBest(population, k=1)[0]
    best_fitness = best_individual.fitness.values
    print(f"Generation {generation + 1} - Best Fitness: {best_fitness}")

# Output the final optimization result
best_individual = tools.selBest(population, k=1)[0]
best_fitness = best_individual.fitness.values
print(f"Best Fitness: {best_fitness}")
best_individual = np.array(best_individual)
print(f"Best Individual: {best_individual}")

这段代码实现了一个基本的遗传算法，用于求解多目标优化问题。主要步骤包括种群初始化、评价、选择、交叉、变异、精英策略等。主要代码可以分为以下几个流程：

（1）定义种群大小、迭代次数、交叉概率和变异概率等参数

population_size = 200
num_generations = 100
crossover_probability = 0.5  # Adjust probability if needed
mutation_probability = 0.2  # Adjust probability if needed

（2）生成初始种群，并计算每个个体的适应度值

initial_population = toolbox.population(n=population_size)

population = initial_population[:]
for individual in population:
    fitness_values = evaluate(individual)
    individual.fitness.values = fitness_values

（3）进入迭代循环
每次循环对当前种群进行选择、交叉和变异操作，生成下一代种群。

for generation in range(num_generations):
    # Evaluate population fitness values
    fitnesses = toolbox.map(evaluate, population)
    for individual, fitness in zip(population, fitnesses):
        individual.fitness.values = fitness

    # Select next generation individuals
    offspring = toolbox.select(population, len(population))

    # Clone selected individuals
    offspring = list(map(toolbox.clone, offspring))

    # Apply crossover and mutation
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < crossover_probability:
            toolbox.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values

    for i in range(len(offspring)):
        if random.random() < mutation_probability:
            offspring[i] = initIndividual()
            del offspring[i].fitness.values

    # Replace worst individuals with the elite individuals from the previous generation
    elite_size = 10  # Number of elite individuals to preserve
    population.sort(key=lambda x: x.fitness.values)
    offspring[-elite_size:] = population[:elite_size]
    population[:] = offspring

    # Output the best individual and its fitness in each generation
    best_individual = tools.selBest(population, k=1)[0]
    best_fitness = best_individual.fitness.values
    print(f"Generation {generation + 1} - Best Fitness: {best_fitness}")

在每一代迭代中，首先使用 toolbox.map 方法对当前种群进行评价，计算每个个体的适应度值。然后，使用 toolbox.select 方法选择下一代个体。接下来，使用 toolbox.clone 方法对选择的个体进行克隆，以便进行后续的交叉和变异操作。接着，对每对相邻的个体（称为父代）进行交叉操作，如果随机数小于交叉概率，则进行交叉操作，并删除子代的适应度值。然后，对每个个体进行变异操作，如果随机数小于变异概率，则将其替换为一个新的随机个体，并删除其适应度值。接着，使用精英策略，将上一代的精英个体替换掉下一代中适应度最差的个体，以保留优秀的个体。最后，使用选择方法选出当前种群中的最优个体，并输出其适应度值。
（4）输出最终的最优个体和适应度值
输出每一代中最优个体的适应度值，并在迭代结束后输出最终的最优个体和适应度值。

best_individual = tools.selBest(population, k=1)[0]
best_fitness = best_individual.fitness.values
print(f"Best Fitness: {best_fitness}")
best_individual = np.array(best_individual)
print(f"Best Individual: {best_individual}")

在迭代过程中，每一代的最优个体的适应度值都被输出。在迭代结束后，使用 tools.selBest 方法选出当前种群中的最优个体，并输出其适应度值和基因序列（这里使用 numpy 库将个体对象转换为数组）。

3、具体实例

3.1 2021年数学建模国赛C题第二问

参考问题 1，该企业应至少选择多少家供应商供应原材料才可能满足生产的需求？
针对这些供应商，为该企业制定未来 24 周每周最经济的原材料订购方案，并据此制定
损耗最少的转运方案。试对订购方案和转运方案的实施效果进行分析。

3.2 数据格式

max_A_values.xlsx、max_B_values.xlsx、max_C_values.xlsx中数据为排名前50的供应商中在未来24周可以分别提供A、B、C材料的供应量，max_data.xlsx中是排名前50的供应商中在未来24周可以分别提供材料的供应量，即没有区分材料种类，是max_A_values.xlsx、max_B_values.xlsx、max_C_values.xlsx的拼接，max_A_values.xlsx、max_B_values.xlsx、max_C_values.xlsx和max_data.xlsx数据格式均一致，如下表所示。

3.3 实例代码

限于比赛还没结束，就先暂时不给了，有需要的可以评论区留言或者+q联系。